yacc.c

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

#include <u.h>
#include <libc.h>
#include <bio.h>
#include <ctype.h>

#define	Bungetrune	Bungetc		/* ok for now. */

/*
 * all these are 32 bit
 */
#define TBITSET		((32+NTERMS)/32)	/* BOTCH?? +31 */
#define BIT(a,i)	((a)[(i)>>5] & (1<<((i)&037)))
#define SETBIT(a,i)	((a)[(i)>>5] |= (1<<((i)&037)))
#define NWORDS(n)	(((n)+32)/32)

#define PARSER		"/sys/lib/yaccpar"
#define PARSERS		"/sys/lib/yaccpars"
#define TEMPNAME	"y.tmp.XXXXXX"
#define ACTNAME		"y.acts.XXXXXX"
#define OFILE		"tab.c"
#define FILEU		"output"
#define FILED		"tab.h"
#define FILEDEBUG	"debug"

enum
{
/*
 * the following are adjustable
 * according to memory size
 */
	ACTSIZE		= 40000,
	MEMSIZE		= 40000,
	NSTATES		= 2000,
	NTERMS		= 511,
	NPROD		= 1600,
	NNONTERM	= 600,
	TEMPSIZE	= 2000,
	CNAMSZ		= 10000,
	LSETSIZE	= 2400,
	WSETSIZE	= 350,

	NAMESIZE	= 50,
	NTYPES		= 63,
	ISIZE		= 400,

	PRIVATE		= 0xE000,	/* unicode private use */

	/* relationships which must hold:
		TBITSET ints must hold NTERMS+1 bits...
		WSETSIZE >= NNONTERM
		LSETSIZE >= NNONTERM
		TEMPSIZE >= NTERMS + NNONTERM + 1
		TEMPSIZE >= NSTATES
	*/

	NTBASE		= 010000,
	ERRCODE		= 8190,
	ACCEPTCODE	= 8191,

	NOASC		= 0,	/* no assoc. */
	LASC		= 1,	/* left assoc. */
	RASC		= 2,	/* right assoc. */
	BASC		= 3,	/* binary assoc. */

	/* flags for state generation */

	DONE		= 0,
	MUSTDO		= 1,
	MUSTLOOKAHEAD	= 2,

	/* flags for a rule having an action, and being reduced */

	ACTFLAG		= 04,
	REDFLAG		= 010,

	/* output parser flags */
	YYFLAG1		= -1000,

	/* parse tokens */
	IDENTIFIER	= PRIVATE,
	MARK,
	TERM,
	LEFT,
	RIGHT,
	BINARY,
	PREC,
	LCURLY,
	IDENTCOLON,
	NUMBER,
	START,
	TYPEDEF,
	TYPENAME,
	UNION,

	ENDFILE		= 0,

	EMPTY		= 1,
	WHOKNOWS	= 0,
	OK		= 1,
	NOMORE		= -1000,
};

	/* macros for getting associativity and precedence levels */

#define ASSOC(i)	((i)&03)
#define PLEVEL(i)	(((i)>>4)&077)
#define TYPE(i)		(((i)>>10)&077)

	/* macros for setting associativity and precedence levels */

#define SETASC(i,j)	i |= j
#define SETPLEV(i,j)	i |= (j<<4)
#define SETTYPE(i,j)	i |= (j<<10)

	/* looping macros */

#define TLOOP(i)	for(i=1; i<=ntokens; i++)
#define NTLOOP(i)	for(i=0; i<=nnonter; i++)
#define PLOOP(s,i)	for(i=s; i<nprod; i++)
#define SLOOP(i)	for(i=0; i<nstate; i++)
#define WSBUMP(x)	x++
#define WSLOOP(s,j)	for(j=s; j<cwp; j++)
#define ITMLOOP(i,p,q)	for(q=pstate[i+1], p=pstate[i]; p<q; p++)
#define SETLOOP(i)	for(i=0; i<tbitset; i++)

	/* command to clobber tempfiles after use */

#define	ZAPFILE(x)	if(x) remove(x)

	/* I/O descriptors */

Biobuf*	faction;	/* file for saving actions */
Biobuf*	fdefine;	/* file for #defines */
Biobuf*	fdebug;		/* y.debug for strings for debugging */
Biobuf*	ftable;		/* y.tab.c file */
Biobuf*	ftemp;		/* tempfile to pass 2 */
Biobuf*	finput;		/* input file */
Biobuf*	foutput;	/* y.output file */

	/* communication variables between various I/O routines */

char*	infile;			/* input file name */
int	numbval;		/* value of an input number */
char	tokname[NAMESIZE+4];	/* input token name, slop for runes and 0 */

	/* structure declarations */

typedef
struct
{
	int	lset[TBITSET];
} Lkset;

typedef
struct
{
	int*	pitem;
	Lkset*	look;
} Item;

typedef
struct
{
	char*	name;
	int	value;
} Symb;

typedef
struct
{
	int*	pitem;
	int	flag;
	Lkset	ws;
} Wset;

	/* storage of names */

char	cnames[CNAMSZ];		/* place where token and nonterminal names are stored */
int	cnamsz = CNAMSZ;	/* size of cnames */
char*	cnamp = cnames;		/* place where next name is to be put in */
int	ndefout = 4;		/* number of defined symbols output */
char*	tempname;
char*	actname;
char	ttempname[] = TEMPNAME;
char	tactname[] = ACTNAME;
char*	parser = PARSER;
char*	yydebug;

	/* storage of types */
int	ntypes;			/* number of types defined */
char*	typeset[NTYPES];	/* pointers to type tags */

	/* token information */

int	ntokens = 0 ;		/* number of tokens */
Symb	tokset[NTERMS];
int	toklev[NTERMS];		/* vector with the precedence of the terminals */

	/* nonterminal information */

int	nnonter = -1;		/* the number of nonterminals */
Symb	nontrst[NNONTERM];
int	start;			/* start symbol */

	/* assigned token type values */
int	extval = 0;

char*	ytabc = OFILE;	/* name of y.tab.c */

	/* grammar rule information */

int	mem0[MEMSIZE] ;		/* production storage */
int*	mem = mem0;
int	nprod = 1;		/* number of productions */
int*	prdptr[NPROD];		/* pointers to descriptions of productions */
int	levprd[NPROD];		/* precedence levels for the productions */
int	rlines[NPROD];		/* line number for this rule */

	/* state information */

int	nstate = 0;		/* number of states */
Item*	pstate[NSTATES+2];	/* pointers to the descriptions of the states */
int	tystate[NSTATES];	/* contains type information about the states */
int	defact[NSTATES];	/* the default actions of states */
int	tstates[NTERMS];	/* states generated by terminal gotos */
int	ntstates[NNONTERM]; 	/* states generated by nonterminal gotos */
int	mstates[NSTATES];	/* chain of overflows of term/nonterm generation lists  */
int	lastred; 		/* the number of the last reduction of a state */

	/* lookahead set information */

Lkset	lkst[LSETSIZE];
int	nolook;			/* flag to turn off lookahead computations */
int	tbitset;		/* size of lookahead sets */
int	nlset = 0;		/* next lookahead set index */
int	nolook = 0;		/* flag to suppress lookahead computations */
Lkset	clset;  		/* temporary storage for lookahead computations */

	/* working set information */

Wset	wsets[WSETSIZE];
Wset*	cwp;

	/* storage for action table */

int	amem[ACTSIZE];		/* action table storage */
int*	memp = amem;		/* next free action table position */
int	indgo[NSTATES];		/* index to the stored goto table */

	/* temporary vector, indexable by states, terms, or ntokens */

int	temp1[TEMPSIZE];	/* temporary storage, indexed by terms + ntokens or states */
int	lineno = 1;		/* current input line number */
int	fatfl = 1;  		/* if on, error is fatal */
int	nerrors = 0;		/* number of errors */

	/* statistics collection variables */

int	zzgoent;
int	zzgobest;
int	zzacent;
int	zzexcp;
int	zzclose;
int	zzrrconf;
int	zzsrconf;

int*	ggreed = lkst[0].lset;
int*	pgo = wsets[0].ws.lset;
int*	yypgo = &nontrst[0].value;

int	maxspr = 0;  		/* maximum spread of any entry */
int	maxoff = 0;  		/* maximum offset into a array */
int*	pmem = mem0;
int*	maxa;
int	nxdb = 0;
int	adb = 0;


	/* storage for information about the nonterminals */

int**	pres[NNONTERM+2];  	/* vector of pointers to productions yielding each nonterminal */
Lkset*	pfirst[NNONTERM+2];	/* vector of pointers to first sets for each nonterminal */
int	pempty[NNONTERM+1];	/* vector of nonterminals nontrivially deriving e */

	/* random stuff picked out from between functions */

int	indebug = 0;
Wset*	zzcwp = wsets;
int	zzgoent = 0;
int	zzgobest = 0;
int	zzacent = 0;
int	zzexcp = 0;
int	zzclose = 0;
int	zzsrconf = 0;
int*	zzmemsz = mem0;
int	zzrrconf = 0;
int	pidebug = 0;		/* debugging flag for putitem */
int	gsdebug = 0;
int	cldebug = 0;		/* debugging flag for closure */
int	pkdebug = 0;
int	g2debug = 0;

struct
{
	char*	name;
	long	value;
} resrv[] =
{
	"binary",	BINARY,
	"left",		LEFT,
	"nonassoc",	BINARY,
	"prec",		PREC,
	"right",	RIGHT,
	"start",	START,
	"term",		TERM,
	"token",	TERM,
	"type",		TYPEDEF,
	"union",	UNION,
	0,
};

	/* define functions */

void	main(int, char**);
void	others(void);
char*	chcopy(char*, char*);
char*	writem(int*);
char*	symnam(int);
void	summary(void);
void	error(char*, ...);
void	aryfil(int*, int, int);
int	setunion(int*, int*);
void	prlook(Lkset*);
void	cpres(void);
void	cpfir(void);
int	state(int);
void	putitem(int*, Lkset*);
void	cempty(void);
void	stagen(void);
void	closure(int);
Lkset*	flset(Lkset*);
void	cleantmp(void);
void	intr(void);
void	setup(int, char**);
void	finact(void);
int	defin(int, char*);
void	defout(int);
char*	cstash(char*);
long	gettok(void);
int	fdtype(int);
int	chfind(int, char*);
void	cpyunion(void);
void	cpycode(void);
int	skipcom(void);
void	cpyact(int);
void	openup(char*, int, int, int, char*);
void	output(void);
int	apack(int*, int);
void	go2out(void);
void	go2gen(int);
void	precftn(int, int, int);
void	wract(int);
void	wrstate(int);
void	warray(char*, int*, int);
void	hideprod(void);
void	callopt(void);
void	gin(int);
void	stin(int);
int	nxti(void);
void	osummary(void);
void	aoutput(void);
void	arout(char*, int*, int);
int	gtnm(void);

void
main(int argc, char *argv[])
{

	setup(argc, argv);	/* initialize and read productions */
	tbitset = NWORDS(ntokens);
	cpres();		/* make table of which productions yield a given nonterminal */
	cempty();		/* make a table of which nonterminals can match the empty string */
	cpfir();		/* make a table of firsts of nonterminals */
	stagen();		/* generate the states */
	output();		/* write the states and the tables */
	go2out();
	hideprod();
	summary();
	callopt();
	others();
	exits(0);
}

/*
 * put out other arrays, copy the parsers
 */
void
others(void)
{
	int c, i, j;

	finput = Bopen(parser, OREAD);
	if(finput == 0)
		error("cannot find parser %s", parser);
	warray("yyr1", levprd, nprod);
	aryfil(temp1, nprod, 0);
	PLOOP(1, i)
		temp1[i] = prdptr[i+1]-prdptr[i]-2;
	warray("yyr2", temp1, nprod);

	aryfil(temp1, nstate, -1000);
	TLOOP(i)
		for(j=tstates[i]; j!=0; j=mstates[j])
			temp1[j] = i;
	NTLOOP(i)
		for(j=ntstates[i]; j!=0; j=mstates[j])
			temp1[j] = -i;
	warray("yychk", temp1, nstate);
	warray("yydef", defact, nstate);

	/* put out token translation tables */
	/* table 1 has 0-256 */
	aryfil(temp1, 256, 0);
	c = 0;
	TLOOP(i) {
		j = tokset[i].value;
		if(j >= 0 && j < 256) {
			if(temp1[j]) {
				print("yacc bug -- cant have 2 different Ts with same value\n");
				print("	%s and %s\n", tokset[i].name, tokset[temp1[j]].name);
				nerrors++;
			}
			temp1[j] = i;
			if(j > c)
				c = j;
		}
	}
	warray("yytok1", temp1, c+1);

	/* table 2 has PRIVATE-PRIVATE+256 */
	aryfil(temp1, 256, 0);
	c = 0;
	TLOOP(i) {
		j = tokset[i].value - PRIVATE;
		if(j >= 0 && j < 256) {
			if(temp1[j]) {
				print("yacc bug -- cant have 2 different Ts with same value\n");
				print("	%s and %s\n", tokset[i].name, tokset[temp1[j]].name);
				nerrors++;
			}
			temp1[j] = i;
			if(j > c)
				c = j;
		}
	}
	warray("yytok2", temp1, c+1);

	/* table 3 has everything else */
	Bprint(ftable, "long	yytok3[] =\n{\n");
	c = 0;
	TLOOP(i) {
		j = tokset[i].value;
		if(j >= 0 && j < 256)
			continue;
		if(j >= PRIVATE && j < 256+PRIVATE)
			continue;

		Bprint(ftable, "%4d,%4d,", j, i);
		c++;
		if(c%5 == 0)
			Bprint(ftable, "\n");
	}
	Bprint(ftable, "%4d\n};\n", 0);

	/* copy parser text */
	while((c=Bgetrune(finput)) != Beof) {
		if(c == '$') {
			if((c = Bgetrune(finput)) != 'A')
				Bputrune(ftable, '$');
			else { /* copy actions */
				faction = Bopen(actname, OREAD);
				if(faction == 0)
					error("cannot reopen action tempfile");
				while((c=Bgetrune(faction)) != Beof)
					Bputrune(ftable, c);
				Bterm(faction);
				ZAPFILE(actname);
				c = Bgetrune(finput);
			}
		}
		Bputrune(ftable, c);
	}
	Bterm(ftable);
}

/*
 * copies string q into p, returning next free char ptr
 */
char*
chcopy(char* p, char* q)
{
	int c;

	while(c = *q) {
		if(c == '"')
			*p++ = '\\';
		*p++ = c;
		q++;
	}
	*p = 0;
	return p;
}

/*
 * creates output string for item pointed to by pp
 */
char*
writem(int *pp)
{
	int i,*p;
	static char sarr[ISIZE];
	char* q;

	for(p=pp; *p>0; p++)
		;
	p = prdptr[-*p];
	q = chcopy(sarr, nontrst[*p-NTBASE].name);
	q = chcopy(q, ": ");
	for(;;) {
		*q = ' ';
		p++;
		if(p == pp)
			*q = '.';
		q++;
		*q = '\0';
		i = *p;
		if(i <= 0)
			break;
		q = chcopy(q, symnam(i));
		if(q > &sarr[ISIZE-30])
			error("item too big");
	}

	/* an item calling for a reduction */
	i = *pp;
	if(i < 0 ) {
		q = chcopy(q, "    (");
		sprint(q, "%d)", -i);
	}
	return sarr;
}

/*
 * return a pointer to the name of symbol i
 */
char*
symnam(int i)
{
	char* cp;

	cp = (i >= NTBASE)? nontrst[i-NTBASE].name: tokset[i].name;
	if(*cp == ' ')
		cp++;
	return cp;
}

/*
 * output the summary on y.output
 */
void
summary(void)
{

	if(foutput != 0) {
		Bprint(foutput, "\n%d/%d terminals, %d/%d nonterminals\n",
			ntokens, NTERMS, nnonter, NNONTERM);
		Bprint(foutput, "%d/%d grammar rules, %d/%d states\n",
			nprod, NPROD, nstate, NSTATES);
		Bprint(foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n",
			zzsrconf, zzrrconf);
		Bprint(foutput, "%d/%d working sets used\n",
			(int)(zzcwp-wsets), WSETSIZE);
		Bprint(foutput, "memory: states,etc. %d/%d, parser %d/%d\n",
			(int)(zzmemsz-mem0), MEMSIZE, (int)(memp-amem), ACTSIZE);
		Bprint(foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE);
		Bprint(foutput, "%d extra closures\n", zzclose - 2*nstate);
		Bprint(foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp);
		Bprint(foutput, "%d goto entries\n", zzgoent);
		Bprint(foutput, "%d entries saved by goto default\n", zzgobest);
	}
	if(zzsrconf != 0 || zzrrconf != 0) {
		print("\nconflicts: ");
		if(zzsrconf)
			print("%d shift/reduce", zzsrconf);
		if(zzsrconf && zzrrconf)
			print(", ");
		if(zzrrconf)
			print("%d reduce/reduce", zzrrconf);
		print("\n");
	}
	if(ftemp != 0) {
		Bterm(ftemp);
		ftemp = 0;
	}
	if(fdefine != 0) {
		Bterm(fdefine);
		fdefine = 0;
	}
}

/*
 * write out error comment -- NEEDS WORK
 */
void
error(char *s, ...)
{

	nerrors++;
	fprint(2, "\n fatal error:");
	fprint(2, s, (&s)[1]);
	fprint(2, ", %s:%d\n", infile, lineno);
	if(!fatfl)
		return;
	summary();
	cleantmp();
	exits("error");
}

/*
 * set elements 0 through n-1 to c
 */
void
aryfil(int *v, int n, int c)
{
	int i;

	for(i=0; i<n; i++)
		v[i] = c;
}

/*
 * set a to the union of a and b
 * return 1 if b is not a subset of a, 0 otherwise
 */
int
setunion(int *a, int *b)
{
	int i, x, sub;

	sub = 0;
	SETLOOP(i) {
		x = *a;
		*a |= *b;
		if(*a != x)
			sub = 1;
		a++;
		b++;
	}
	return sub;
}

void
prlook(Lkset* p)
{
	int j, *pp;

	pp = p->lset;
	if(pp == 0)
		Bprint(foutput, "\tNULL");
	else {
		Bprint(foutput, " { ");
		TLOOP(j)
			if(BIT(pp,j))
				Bprint(foutput, "%s ", symnam(j));
		Bprint(foutput, "}");
	}
}

/*
 * compute an array with the beginnings of  productions yielding given nonterminals
 * The array pres points to these lists
 * the array pyield has the lists: the total size is only NPROD+1
 */
void
cpres(void)
{
	int c, j, i, **pmem;
	static int *pyield[NPROD];

	pmem = pyield;
	NTLOOP(i) {
		c = i+NTBASE;
		pres[i] = pmem;
		fatfl = 0;  	/* make undefined  symbols  nonfatal */
		PLOOP(0, j)
			if(*prdptr[j] == c)
				*pmem++ =  prdptr[j]+1;
		if(pres[i] == pmem)
			error("nonterminal %s not defined!", nontrst[i].name);
	}
	pres[i] = pmem;
	fatfl = 1;
	if(nerrors) {
		summary();
		cleantmp();
		exits("error");
	}
	if(pmem != &pyield[nprod])
		error("internal Yacc error: pyield %d", pmem-&pyield[nprod]);
}

/*
 * compute an array with the first of nonterminals
 */
void
cpfir(void)
{
	int *p, **s, i, **t, ch, changes;

	zzcwp = &wsets[nnonter];
	NTLOOP(i) {
		aryfil(wsets[i].ws.lset, tbitset, 0);
		t = pres[i+1];
		/* initially fill the sets */
		for(s=pres[i]; s<t; ++s)
			for(p = *s; (ch = *p) > 0; ++p) {
				if(ch < NTBASE) {
					SETBIT(wsets[i].ws.lset, ch);
					break;
				}
				if(!pempty[ch-NTBASE])
					break;
			}
	}

	/* now, reflect transitivity */