yacc.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

		while(t == ';')
			t = gettok();
		*mem++ = -nprod;

		/* check that default action is reasonable */
		if(ntypes && !(levprd[nprod]&ACTFLAG) && nontrst[*prdptr[nprod]-NTBASE].value) {

			/* no explicit action, LHS has value */
			int tempty;

			tempty = prdptr[nprod][1];
			if(tempty < 0)
				error("must return a value, since LHS has a type");
			else
				if(tempty >= NTBASE)
					tempty = nontrst[tempty-NTBASE].value;
				else
					tempty = TYPE(toklev[tempty]);
			if(tempty != nontrst[*prdptr[nprod]-NTBASE].value)
				error("default action causes potential type clash");
		}
		nprod++;
		if(nprod >= NPROD)
			error("more than %d rules", NPROD);
		prdptr[nprod] = mem;
		levprd[nprod] = 0;
	}

	/* end of all rules */
	defout(1);

	finact();
	if(t == MARK) {
		Bprint(ftable, "\n#line\t%d\t\"%s\"\n", lineno, infile);
		while((c=Bgetrune(finput)) != Beof)
			Bputrune(ftable, c);
	}
	Bterm(finput);
}

/*
 * finish action routine
 */
void
finact(void)
{

	Bterm(faction);
	Bprint(ftable, "#define YYEOFCODE %d\n", 1);
	Bprint(ftable, "#define YYERRCODE %d\n", 2);
}

/*
 * define s to be a terminal if t=0
 * or a nonterminal if t=1
 */
int
defin(int nt, char *s)
{
	int val;
	Rune rune;

	val = 0;
	if(nt) {
		nnonter++;
		if(nnonter >= NNONTERM)
			error("too many nonterminals, limit %d",NNONTERM);
		nontrst[nnonter].name = cstash(s);
		return NTBASE + nnonter;
	}

	/* must be a token */
	ntokens++;
	if(ntokens >= NTERMS)
		error("too many terminals, limit %d", NTERMS);
	tokset[ntokens].name = cstash(s);

	/* establish value for token */
	/* single character literal */
	if(s[0] == ' ') {
		val = chartorune(&rune, &s[1]);
		if(s[val+1] == 0) {
			val = rune;
			goto out;
		}
	}

	/* escape sequence */
	if(s[0] == ' ' && s[1] == '\\') {
		if(s[3] == 0) {
			/* single character escape sequence */
			switch(s[2]) {
			case 'n':	val = '\n'; break;
			case 'r':	val = '\r'; break;
			case 'b':	val = '\b'; break;
			case 't':	val = '\t'; break;
			case 'f':	val = '\f'; break;
			case '\'':	val = '\''; break;
			case '"':	val = '"'; break;
			case '\\':	val = '\\'; break;
			default:	error("invalid escape");
			}
			goto out;
		}

		/* \nnn sequence */
		if(s[2] >= '0' && s[2] <= '7') {
			if(s[3] < '0' ||
			   s[3] > '7' ||
			   s[4] < '0' ||
			   s[4] > '7' ||
			   s[5] != 0)
				error("illegal \\nnn construction");
			val = 64*s[2] + 8*s[3] + s[4] - 73*'0';
			if(val == 0)
				error("'\\000' is illegal");
			goto out;
		}
		error("unknown escape");
	}
	val = extval++;

out:
	tokset[ntokens].value = val;
	toklev[ntokens] = 0;
	return ntokens;
}

/*
 * write out the defines (at the end of the declaration section)
 */
void
defout(int last)
{
	int i, c;
	char sar[NAMESIZE+10];

	for(i=ndefout; i<=ntokens; i++) {
		/* non-literals */
		c = tokset[i].name[0];
		if(c != ' ' && c != '$') {
			Bprint(ftable, "#define	%s	%d\n",
				tokset[i].name, tokset[i].value);
			if(fdefine)
				Bprint(fdefine, "#define\t%s\t%d\n",
					tokset[i].name, tokset[i].value);
		}
	}
	ndefout = ntokens+1;
	if(last && fdebug) {
		Bprint(fdebug, "char*	yytoknames[] =\n{\n");
		TLOOP(i) {
			if(tokset[i].name) {
				chcopy(sar, tokset[i].name);
				Bprint(fdebug, "\t\"%s\",\n", sar);
				continue;
			}
			Bprint(fdebug, "\t0,\n");
		}
		Bprint(fdebug, "};\n");
	}
}

char*
cstash(char *s)
{
	char *temp;

	temp = cnamp;
	do {
		if(cnamp >= &cnames[cnamsz])
			error("too many characters in id's and literals");
		else
			*cnamp++ = *s;
	} while(*s++);
	return temp;
}

long
gettok(void)
{
	long c;
	Rune rune;
	int i, base, match, reserve;
	static int peekline;

begin:
	reserve = 0;
	lineno += peekline;
	peekline = 0;
	c = Bgetrune(finput);
	while(c == ' ' || c == '\n' || c == '\t' || c == '\f') {
		if(c == '\n')
			lineno++;
		c = Bgetrune(finput);
	}

	/* skip comment */
	if(c == '/') {
		lineno += skipcom();
		goto begin;
	}
	switch(c) {
	case Beof:
		return ENDFILE;

	case '{':
		Bungetrune(finput);
		return '=';

	case '<':
		/* get, and look up, a type name (union member name) */
		i = 0;
		while((c=Bgetrune(finput)) != '>' && c >= 0 && c != '\n') {
			rune = c;
			c = runetochar(&tokname[i], &rune);
			if(i < NAMESIZE)
				i += c;
		}
		if(c != '>')
			error("unterminated < ... > clause");
		tokname[i] = 0;
		for(i=1; i<=ntypes; i++)
			if(!strcmp(typeset[i], tokname)) {
				numbval = i;
				return TYPENAME;
			}
		ntypes++;
		numbval = ntypes;
		typeset[numbval] = cstash(tokname);
		return TYPENAME;

	case '"':
	case '\'':
		match = c;
		tokname[0] = ' ';
		i = 1;
		for(;;) {
			c = Bgetrune(finput);
			if(c == '\n' || c <= 0)
				error("illegal or missing ' or \"" );
			if(c == '\\') {
				tokname[i] = '\\';
				if(i < NAMESIZE)
					i++;
				c = Bgetrune(finput);
			} else
				if(c == match)
					break;
			rune = c;
			c = runetochar(&tokname[i], &rune);
			if(i < NAMESIZE)
				i += c;
		}
		break;

	case '%':
	case '\\':
		switch(c = Bgetrune(finput)) {
		case '0':	return TERM;
		case '<':	return LEFT;
		case '2':	return BINARY;
		case '>':	return RIGHT;
		case '%':
		case '\\':	return MARK;
		case '=':	return PREC;
		case '{':	return LCURLY;
		default:	reserve = 1;
		}

	default:
		/* number */
		if(isdigit(c)) {
			numbval = c-'0';
			base = (c=='0')? 8: 10;
			for(c = Bgetrune(finput); isdigit(c); c = Bgetrune(finput))
				numbval = numbval*base + (c-'0');
			Bungetrune(finput);
			return NUMBER;
		}
		if(islower(c) || isupper(c) || c=='_' || c=='.' || c=='$')  {
			i = 0;
			while(islower(c) || isupper(c) || isdigit(c) ||
			    c == '-' || c=='_' || c=='.' || c=='$') {
				if(reserve && isupper(c))
					c += 'a'-'A';
				rune = c;
				c = runetochar(&tokname[i], &rune);
				if(i < NAMESIZE)
					i += c;
				c = Bgetrune(finput);
			}
		} else
			return c;
		Bungetrune(finput);
	}
	tokname[i] = 0;

	/* find a reserved word */
	if(reserve) {
		for(c=0; resrv[c].name; c++)
			if(strcmp(tokname, resrv[c].name) == 0)
				return resrv[c].value;
		error("invalid escape, or illegal reserved word: %s", tokname);
	}

	/* look ahead to distinguish IDENTIFIER from IDENTCOLON */
	c = Bgetrune(finput);
	while(c == ' ' || c == '\t'|| c == '\n' || c == '\f' || c == '/') {
		if(c == '\n')
			peekline++;
		/* look for comments */
		if(c == '/')
			peekline += skipcom();
		c = Bgetrune(finput);
	}
	if(c == ':')
		return IDENTCOLON;
	Bungetrune(finput);
	return IDENTIFIER;
}

/*
 * determine the type of a symbol
 */
int
fdtype(int t)
{
	int v;

	if(t >= NTBASE)
		v = nontrst[t-NTBASE].value;
	else
		v = TYPE(toklev[t]);
	if(v <= 0)
		error("must specify type for %s", (t>=NTBASE)?
			nontrst[t-NTBASE].name: tokset[t].name);
	return v;
}

int
chfind(int t, char *s)
{
	int i;

	if(s[0] == ' ')
		t = 0;
	TLOOP(i)
		if(!strcmp(s, tokset[i].name))
			return i;
	NTLOOP(i)
		if(!strcmp(s, nontrst[i].name))
			return NTBASE+i;

	/* cannot find name */
	if(t > 1)
		error("%s should have been defined earlier", s);
	return defin(t, s);
}

/*
 * copy the union declaration to the output, and the define file if present
 */
void
cpyunion(void)
{
	long c;
	int level;

	Bprint(ftable, "\n#line\t%d\t\"%s\"\n", lineno, infile);
	Bprint(ftable, "typedef union ");
	if(fdefine != 0)
		Bprint(fdefine, "\ntypedef union ");

	level = 0;
	for(;;) {
		if((c=Bgetrune(finput)) == Beof)
			error("EOF encountered while processing %%union");
		Bputrune(ftable, c);
		if(fdefine != 0)
			Bputrune(fdefine, c);
		switch(c) {
		case '\n':
			lineno++;
			break;
		case '{':
			level++;
			break;
		case '}':
			level--;

			/* we are finished copying */
			if(level == 0) {
				Bprint(ftable, " YYSTYPE;\n");
				if(fdefine != 0)
					Bprint(fdefine, "\tYYSTYPE;\nextern\tYYSTYPE\tyylval;\n");
				return;
			}
		}
	}
}

/*
 * copies code between \{ and \}
 */
void
cpycode(void)
{

	long c;

	c = Bgetrune(finput);
	if(c == '\n') {
		c = Bgetrune(finput);
		lineno++;
	}
	Bprint(ftable, "\n#line\t%d\t\"%s\"\n", lineno, infile);
	while(c != Beof) {
		if(c == '\\') {
			if((c=Bgetrune(finput)) == '}')
				return;
			Bputc(ftable, '\\');
		}
		if(c == '%') {
			if((c=Bgetrune(finput)) == '}')
				return;
			Bputc(ftable, '%');
		}
		Bputrune(ftable, c);
		if(c == '\n')
			lineno++;
		c = Bgetrune(finput);
	}
	error("eof before %%}");
}

/*
 * skip over comments
 * skipcom is called after reading a '/'
 */
int
skipcom(void)
{
	long c;
	int i;

	/* i is the number of lines skipped */
	i = 0;
	if(Bgetrune(finput) != '*')
		error("illegal comment");
	c = Bgetrune(finput);
	while(c != Beof) {
		while(c == '*')
			if((c=Bgetrune(finput)) == '/')
				return i;
		if(c == '\n')
			i++;
		c = Bgetrune(finput);
	}
	error("EOF inside comment");
	return 0;
}

/*
 * copy C action to the next ; or closing }
 */
void
cpyact(int offset)
{
	long c;
	int brac, match, j, s, fnd, tok;

	Bprint(faction, "\n#line\t%d\t\"%s\"\n", lineno, infile);
	brac = 0;

loop:
	c = Bgetrune(finput);
swt:
	switch(c) {
	case ';':
		if(brac == 0) {
			Bputrune(faction, c);
			return;
		}
		goto lcopy;

	case '{':
		brac++;
		goto lcopy;

	case '$':
		s = 1;
		tok = -1;
		c = Bgetrune(finput);

		/* type description */
		if(c == '<') {
			Bungetrune(finput);
			if(gettok() != TYPENAME)
				error("bad syntax on $<ident> clause");
			tok = numbval;
			c = Bgetrune(finput);
		}
		if(c == '$') {
			Bprint(faction, "yyval");

			/* put out the proper tag... */
			if(ntypes) {
				if(tok < 0)
					tok = fdtype(*prdptr[nprod]);
				Bprint(faction, ".%s", typeset[tok]);
			}
			goto loop;
		}
		if(c == '-') {
			s = -s;
			c = Bgetrune(finput);
		}
		if(isdigit(c)) {
			j = 0;
			while(isdigit(c)) {
				j = j*10 + (c-'0');
				c = Bgetrune(finput);
			}
			Bungetrune(finput);
			j = j*s - offset;
			if(j > 0)
				error("Illegal use of $%d", j+offset);

		dollar:
			Bprint(faction, "yypt[-%d].yyv", -j);

			/* put out the proper tag */
			if(ntypes) {
				if(j+offset <= 0 && tok < 0)
					error("must specify type of $%d", j+offset);
				if(tok < 0)
					tok = fdtype(prdptr[nprod][j+offset]);
				Bprint(faction, ".%s", typeset[tok]);
			}
			goto loop;
		}
		if(isupper(c) || islower(c) || c == '_' || c == '.') {
			int tok; /* tok used oustide for type info */

			/* look for $name */
			Bungetrune(finput);
			if(gettok() != IDENTIFIER)
				error("$ must be followed by an identifier");
			tok = chfind(2, tokname);
			if((c = Bgetrune(finput)) != '#') {
				Bungetrune(finput);
				fnd = -1;
			} else
				if(gettok() != NUMBER) {
					error("# must be followed by number");
					fnd = -1;
				} else
					fnd = numbval;
			for(j=1; j<=offset; ++j)
				if(tok == prdptr[nprod][j]) {
					if(--fnd <= 0) {
						j -= offset;
						goto dollar;
					}
				}
			error("$name or $name#number not found");
		}
		Bputc(faction, '$');
		if(s < 0 )
			Bputc(faction, '-');
		goto swt;

	case '}':
		brac--;
		if(brac)
			goto lcopy;
		Bputrune(faction, c);
		return;

	case '/':
		/* look for comments */
		Bputrune(faction, c);
		c = Bgetrune(finput);
		if(c != '*')
			goto swt;

		/* it really is a comment */
		Bputrune(faction, c);
		c = Bgetrune(finput);
		while(c >= 0) {
			while(c == '*') {
				Bputrune(faction, c);
				if((c=Bgetrune(finput)) == '/')
					goto lcopy;
			}
			Bputrune(faction, c);
			if(c == '\n')
				lineno++;
			c = Bgetrune(finput);
		}
		error("EOF inside comment");

	case '\'':
		/* character constant */
		match = '\'';
		goto string;

	case '"':
		/* character string */
		match = '"';

	string:
		Bputrune(faction, c);
		while(c = Bgetrune(finput)) {
			if(c == '\\') {
				Bputrune(faction, c);
				c = Bgetrune(finput);
				if(c == '\n')
					lineno++;
			} else
				if(c == match)
					goto lcopy;
				if(c == '\n')
					error("newline in string or char. const.");
			Bputrune(faction, c);
		}
		error("EOF in string or character constant");

	case Beof:
		error("action does not terminate");

	case '\n':
		lineno++;
		goto lcopy;
	}

lcopy:
	Bputrune(faction, c);
	goto loop;
}

void
openup(char *stem, int dflag, int vflag, int ytab, char *ytabc)
{
	char buf[256];

	if(vflag) {
		snprint(buf, sizeof buf, "%s.%s", stem, FILEU);
		foutput = Bopen(buf, OWRITE);
		if(foutput == 0)
			error("cannot open %s", buf);
	}
	if(yydebug) {
		snprint(buf, sizeof buf, "%s.%s", stem, FILEDEBUG);
		if((fdebug = Bopen(buf, OWRITE)) == 0)
			error("can't open %s", buf);
	}
	if(dflag) {
		snprint(buf, sizeof buf, "%s.%s", stem, FILED);
		fdefine = Bopen(buf, OWRITE);
		if(fdefine == 0)
			error("can't create %s", buf);
	}
	if(ytab == 0)
		snprint(buf, sizeof buf, "%s.%s", stem, OFILE);
	else
		strecpy(buf, buf+sizeof buf, ytabc);
	ftable = Bopen(buf, OWRITE);
	if(ftable == 0)
		error("cannot open table file %s", buf);
}

/*
 * print the output for the states
 */
void
output(void)
{
	int i, k, c;
	Wset *u, *v;

	Bprint(ftable, "short	yyexca[] =\n{");
	if(fdebug)
		Bprint(fdebug, "char*	yystates[] =\n{\n");

	/* output the stuff for state i */
	SLOOP(i) {
		nolook = tystate[i]!=MUSTLOOKAHEAD;
		closure(i);

		/* output actions */
		nolook = 1;
		aryfil(temp1, ntokens+nnonter+1, 0);
		WSLOOP(wsets, u) {
			c = *(u->pitem);
			if(c > 1 && c < NTBASE && temp1[c] == 0) {
				WSLOOP(u, v)
					if(c == *(v->pitem))
						putitem(v->pitem+1, (Lkset*)0);
				temp1[c] = state(c);
			} else
				if(c > NTBASE && temp1[(c -= NTBASE) + ntokens] == 0)
					temp1[c+ntokens] = amem[indgo[i]+c];
		}
		if(i == 1)
			temp1[1] = ACCEPTCODE;

		/* now, we have the shifts; look at the reductions */
		lastred = 0;
		WSLOOP(wsets, u) {
			c = *u->pitem;

			/* reduction */
			if(c <= 0) {
				lastred = -c;
				TLOOP(k)
					if(BIT(u->ws.lset, k)) {
						if(temp1[k] == 0)
							temp1[k] = c;
						else
						if(temp1[k] < 0) { /* reduce/reduce conflict */
							if(foutput)
								Bprint(foutput,
									"\n%d: reduce/reduce conflict"
									" (red'ns %d and %d ) on %s",
									i, -temp1[k], lastred,
									symnam(k));
							if(-temp1[k] > lastred)
								temp1[k] = -lastred;
							zzrrconf++;
						} else
							/* potential shift/reduce conflict */
							precftn( lastred, k, i );
					}
				}