qbe-backend/minic/yacc.c

/*% clang -g -Wall -Wextra % -o #
 * miniyacc - LALR(1) grammars for C
 * See LICENSE for copyright and license details.
 */
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int Sym;
typedef struct Rule Rule;
typedef struct TSet TSet;
typedef struct Info Info;
typedef struct Term Term;
typedef struct Item Item;
typedef struct Row Row;

#define S ((Sym) -1)
#define Red(n) (- (n+2)) /* involutive, Red(Red(x)) == x */
#define GetBit(s,n) (s[n/32] & (1<<(n%32)))
#define SetBit(s,n) (s[n/32] |= 1<<(n%32))

enum {
	IdntSz = 64,
	MaxRhs = 32,
	MaxTk = 500,
	MaxNt = 500,
	MaxRl = 800,
	MaxTm = 1000,

	TSetSz = (MaxTk+31)/32,
	Sym0 = MaxTk
};

struct Rule {
	Sym lhs;
	Sym rhs[MaxRhs];
	char *act;
	int actln;
	int prec;
};

struct TSet {
	unsigned t[TSetSz];
};

struct Info {
	int nul;
	TSet fst;
	int prec;
	enum {
		ANone,
		ALeft,
		ARight,
		ANonassoc
	} assoc;
	char name[IdntSz];
	char type[IdntSz];
};

struct Term {
	Rule *rule;
	int dot;
	TSet lk;
};

struct Item {
	int id;
	int nt;
	Term ts[MaxTm];
	Item **gtbl;
	int dirty;
};

struct Row {
	int def;
	int ndef;
	int *t;
};

char srs[] = "shift/reduce conflict state %d token %s\n";
char rrs[] = "reduce/reduce conflict state %d token %s\n";

Item i0; /* temporary item */

int nrl, nsy, nst, ntk;
Rule rs[MaxRl]; /* grammar rules (ordered, rcmp) */
Info is[MaxTk+MaxNt]; /* symbol information */
Item **st; /* LALR(1) states (ordered, icmp) */
Row *as;   /* action table [state][tok] */
Row *gs;   /* goto table   [sym][state] */
Sym sstart;/* start symbol */
Item *ini; /* initial state */
int doty;  /* type-checking enabled */

int srconf, rrconf;
int actsz;
int *act;
int *chk;
int *adsp;
int *gdsp;

int lineno = 1;
char *srca;
FILE *fin;
FILE *fout;
FILE *fgrm;
FILE *fhdr;

void
die(char *s)
{
	fprintf(stderr, "%s (on line %d)\n", s, lineno);
	exit(1);
}

void *
yalloc(size_t n, size_t o)
{
	void *p;

	p = calloc(n, o);
	if (!p)
		die("out of memory");
	return p;
}

int
rcmp(const void *a, const void *b)
{
	return ((Rule *)a)->lhs - ((Rule *)b)->lhs;
}

Rule *
rfind(Sym lhs)
{
	Rule *r;
	Rule k;

	k.lhs = lhs;
	r = bsearch(&k, rs, nrl, sizeof *r, rcmp);
	if (r != 0)
		while (r > rs && r[-1].lhs == lhs)
			r--;
	return r;
}

int
slen(Sym *l)
{
	int n;

	for (n=0; *l!=S; n++, l++);
	return n;
}

void
tszero(TSet *ts)
{
	memset(ts, 0, sizeof *ts);
}

int
tsunion(TSet *tsa, TSet *tsb)
{
	int n;
	unsigned *a, *b, c, t;

	c = 0;
	a = tsa->t;
	b = tsb->t;
	n = (31+ntk)/32;
	while (n-- > 0) {
		t = *a;
		*a |= *b++;
		c |= t ^ *a++;
	}
	return !!c;
}

void
first(TSet *ts, Sym *stnc, TSet *last)
{
	Sym f;

	f = stnc[0];
	if (f == S) {
		if (last)
			tsunion(ts, last);
		return;
	}
	if (f < ntk) {
		SetBit(ts->t, f);
		return;
	}
	if (is[f].nul)
		first(ts, stnc+1, last);
	tsunion(ts, &is[f].fst);
}

void
ginit()
{
	int chg;
	Rule *r;
	Info *i;
	Sym *s;
	TSet ts;

	do {
		chg = 0;
		for (r=rs; r-rs<nrl; r++) {
			i = &is[r->lhs];
			for (s=r->rhs; *s!=S; s++)
				if (!is[*s].nul)
					goto nonul;
			chg |= i->nul == 0;
			i->nul = 1;
		nonul:
			tszero(&ts);
			first(&ts, r->rhs, 0);
			chg |= tsunion(&i->fst, &ts);
		}
	} while (chg);
}

int
tcmp(Term *a, Term *b)
{
	int c;

	c = a->rule - b->rule;
	if (c==0)
		c = a->dot - b->dot;
	return c;
}

int
tcmpv(const void *a, const void *b)
{
	return tcmp((Term *)a, (Term *)b);
}

void
iclose(Item *i)
{
	int smap[MaxNt];
	Rule *r;
	Term *t, t1;
	Sym s, *rem;
	int chg, n, m;

	t1.dot = 0;
	memset(smap, 0, sizeof smap);
	for (n=0; n<i->nt; n++) {
		t = &i->ts[n];
		s = t->rule->lhs-Sym0;
		if (t->dot==0)
		if (smap[s]==0)
			smap[s] = n;
	}
	do {
		chg = 0;
		for (n=0; n<i->nt; n++) {
			t = &i->ts[n];
			rem = &t->rule->rhs[t->dot];
			s = *rem++;
			if (s < Sym0 || s == S)
				continue;
			r = rfind(s);
			if (!r)
				die("some non-terminals are not defined");
			tszero(&t1.lk);
			first(&t1.lk, rem, &t->lk);
			m = smap[s-Sym0];
			if (m)
				for (; r-rs<nrl && r->lhs==s; r++, m++)
					chg |= tsunion(&i->ts[m].lk, &t1.lk);
			else {
				m = i->nt;
				smap[s-Sym0] = m;
				for (; r-rs<nrl && r->lhs==s; r++, m++) {
					if (m>=MaxTm)
						die("too many terms in item");
					t1.rule = r;
					i->ts[m] = t1;
				}
				i->nt = m;
				chg = 1;
			}
		}
	} while (chg);
}

void
igoto(Item *i, Sym s)
{
	Term *t, *t1;
	int n;

	i0.nt = 0;
	for (n=0, t=i->ts; n<i->nt; n++, t++) {
		if (t->rule->rhs[t->dot] != s)
			continue;
		t1 = &i0.ts[i0.nt++];
		*t1 = *t;
		t1->dot++;
	}
	qsort(i0.ts, i0.nt, sizeof i0.ts[0], tcmpv);
}

int
icmp(Item *a, Item *b)
{
	Term *ta, *tb, *ma, *mb;
	int c;

	ta = a->ts;
	tb = b->ts;
	ma = ta+a->nt;
	mb = tb+b->nt;
	for (;;) {
		if (ta==ma || ta->dot==0)
			return -(tb<mb && tb->dot);
		if (tb==mb || tb->dot==0)
			return +(ta<ma && ta->dot);
		if ((c=tcmp(ta++, tb++)))
			return c;
	}
}

int
stadd(Item **pi)
{
	Item *i, *i1;
	int lo, hi, mid, n, chg;

	/* http://www.iq0.com/duffgram/bsearch.c */
	i = *pi;
	lo = 0;
	hi = nst - 1;
	if (hi<0 || icmp(i, st[hi])>0)
		hi++;
	else if (icmp(i, st[lo])<=0)
		hi = lo;
	else
		while (hi-lo!=1) {
			mid = (lo+hi)/2;
			if (icmp(st[mid], i)<0)
				lo = mid;
			else
				hi = mid;
		}
	if (hi<nst && icmp(st[hi], i)==0) {
		chg = 0;
		i1 = st[hi];
		for (n=0; n<i->nt; n++)
			chg |= tsunion(&i1->ts[n].lk, &i->ts[n].lk);
		i1->dirty |= chg;
		*pi = i1;
		return chg;
	} else {
		st = realloc(st, ++nst * sizeof st[0]);
		if (!st)
			die("out of memory");
		memmove(&st[hi+1], &st[hi], (nst-1 - hi) * sizeof st[0]);
		i->gtbl = yalloc(nsy, sizeof i->gtbl[0]);
		i->dirty = 1;
		i1 = yalloc(1, sizeof *i1);
		*i1 = *i;
		*pi = st[hi] = i1;
		return 1;
	}
}

void
stgen()
{
	Sym s;
	Rule *r;
	Item *i, *i1;
	Term tini;
	int n, chg;

	ini = &i0;
	r = rfind(Sym0);
	tini.rule = r;
	tini.dot = 0;
	tszero(&tini.lk);
	SetBit(tini.lk.t, 0);
	i0.nt = 0;
	i0.ts[i0.nt++] = tini;
	stadd(&ini);
	do {
		chg = 0;
		for (n=0; n<nst; n++) {
			i = st[n];
			if (!i->dirty)
				continue;
			i->dirty = 0;
			iclose(i);
			for (s=0; s<nsy; s++) {
				igoto(i, s);
				i1 = &i0;
				if (!i1->nt) {
					i->gtbl[s] = 0;
					continue;
				}
				chg |= stadd(&i1);
				i->gtbl[s] = i1;
			}
		}
	} while (chg);
}

int
resolve(Rule *r, Sym s, int st)
{
	if (!r->prec || !is[s].prec) {
	conflict:
		if (fgrm)
			fprintf(fgrm, srs, st, is[s].name);
		srconf++;
		return ARight;
	}
	if (r->prec==is[s].prec) {
		if (is[s].assoc == ANone)
			goto conflict;
		return is[s].assoc;
	} else
		if (r->prec<is[s].prec)
			return ARight;
		else
			return ALeft;
}

void
tblset(int *tbl, Item *i, Term *t)
{
	int act;
	Sym s;

	s = t->rule->rhs[t->dot];
	if (s!=S) {
		/* shift */
		if (s>=ntk)
			return;
		assert(i->gtbl[s]);
		act = ARight;
		if (tbl[s] && tbl[s] != i->gtbl[s]->id) {
			assert(tbl[s]<=0);
			act = resolve(&rs[Red(tbl[s])], s, i->id-1);
		}
		switch (act) {
		case ARight:
			tbl[s] = i->gtbl[s]->id;
			break;
		case ANonassoc:
			tbl[s] = -1;
			break;
		}
	} else
		/* reduce */
		for (s=0; s<ntk; s++) {
			if (!GetBit(t->lk.t, s))
				continue;
			/* default to shift if conflict occurs */
			if (!tbl[s])
				act = ALeft;
			else if (tbl[s]<0) {
				if (fgrm)
					fprintf(fgrm, rrs, i->id-1, is[s].name);
				rrconf++;
				act = ARight;
			} else
				act = resolve(t->rule, s, i->id-1);
			switch (act) {
			case ALeft:
				tbl[s] = Red(t->rule-rs);
				break;
			case ANonassoc:
				tbl[s] = -1;
				break;
			}
		}
}

void
setdef(Row *r, int w, int top)
{
	int n, m, x, cnt, def, max;

	max = 0;
	def = -1;
	r->ndef = 0;
	for (n=0; n<w; n++) {
		x = r->t[n];
		if (x==0)
			r->ndef++;
		if (x>=top || x==0)
			continue;
		cnt = 1;
		for (m=n+1; m<w; m++)
			if (r->t[m]==x)
				cnt++;
		if (cnt>max) {
			def = x;
			max = cnt;
		}
	}
	r->def = def;
	if (max!=0)
		/* zero out the most frequent entry */
		for (n=0; n<w; n++)
			if (r->t[n]==def) {
				r->t[n] = 0;
				r->ndef++;
			}
}

void
tblgen()
{
	Row *r;
	Item *i;
	int n, m;

	for (n=0; n<nst; n++)
		st[n]->id = n+1;
	as = yalloc(nst, sizeof as[0]);
	gs = yalloc(nsy-MaxTk, sizeof gs[0]);
	/* fill action table */
	for (n=0; n<nst; n++) {
		r = &as[n];
		r->t = yalloc(ntk, sizeof r->t[0]);
		for (i=st[n], m=0; m<i->nt; m++)
			tblset(r->t, i, &i->ts[m]);
		setdef(r, ntk, -1);
		r->def = Red(r->def); /* Red(-1) == -1 */
	}
	/* fill goto table */
	for (n=MaxTk; n<nsy; n++) {
		r = &gs[n-MaxTk];
		r->t = yalloc(nst, sizeof r->t[0]);
		for (m=0; m<nst; m++)
			if (st[m]->gtbl[n])
				r->t[m] = st[m]->gtbl[n]->id;
		setdef(r, nst, nst+1);
	}
}

int
prcmp(const void *a, const void *b)
{
	return (*(Row **)a)->ndef - (*(Row **)b)->ndef;
}

void
actgen()
{
	Row **o, *r;
	int n, m, t, dsp, nnt;

	actsz = 0;
	o = yalloc(nst+nsy, sizeof o[0]);
	act = yalloc(nst*nsy, sizeof act[0]);
	chk = yalloc(nst*nsy, sizeof chk[0]);
	adsp = yalloc(nst, sizeof adsp[0]);
	for (n=0; n<nst*nsy; n++)
		chk[n] = -1;
	/* fill in actions */
	for (n=0; n<nst; n++)
		o[n] = &as[n];
	qsort(o, nst, sizeof o[0], prcmp);
	for (n=0; n<nst; n++) {
		r = o[n];
		dsp = 0;
		for (m=0; m<ntk && r->t[m]==0; m++)
			dsp--;
	retrya:
		/* The invariant here is even
		 * trickier than it looks.
		 */
		for (t=0; t<ntk; t++)
			if ((m=dsp+t)>=0 && chk[m]>=0)
			if ((r->t[t] && (chk[m]!=t || act[m]!=r->t[t]))
			|| (!r->t[t] && chk[m]==t)) {
				dsp++;
				goto retrya;
			}
		adsp[r-as] = dsp;
		for (t=0; t<ntk; t++)
			if (r->t[t]) {
				chk[dsp+t] = t;
				act[dsp+t] = r->t[t];
				if (dsp+t>=actsz)
					actsz = dsp+t+1;
			}
	}
	/* fill in gotos */
	nnt = nsy-MaxTk;
	gdsp = yalloc(nnt, sizeof gdsp[0]);
	for (n=0; n<nnt; n++)
		o[n] = &gs[n];
	qsort(o, nnt, sizeof o[0], prcmp);
	for (n=0; n<nnt; n++) {
		r = o[n];
		dsp = 0;
		for (m=0; m<nst && r->t[m]==0; m++)
			dsp--;
	retryg:
		for (t=m; t<nst; t++)
			if (chk[dsp+t]>=0 && r->t[t]) {
				dsp++;
				goto retryg;
			}
		gdsp[r-gs] = dsp;
		for (t=m; t<nst; t++)
			if (r->t[t]) {
				chk[dsp+t] = ntk+(r-gs);
				act[dsp+t] = r->t[t];
				if (dsp+t>=actsz)
					actsz = dsp+t+1;
			}
	}
	free(o);
}

void
aout(char *name, int *t, int n)
{
	int i;

	fprintf(fout, "short %s[] = {", name);
	for (i=0; i<n; i++) {
		if (i % 10 == 0)
			fprintf(fout, "\n");
		fprintf(fout, "%4d", t[i]);
		if (i != n-1)
			fprintf(fout, ",");
	}
	fprintf(fout, "\n};\n");
}

void
tblout()
{
	int *o, n, m;

	fprintf(fout, "short yyini = %d;\n", ini->id-1);
	fprintf(fout, "short yyntoks = %d;\n", ntk);
	o = yalloc(nrl+nst+nsy, sizeof o[0]);
	for (n=0; n<nrl; n++)
		o[n] = slen(rs[n].rhs);
	aout("yyr1", o, nrl);
	for (n=0; n<nrl; n++)
		o[n] = rs[n].lhs-MaxTk;
	aout("yyr2", o, nrl);
	for (n=0; n<nst; n++)
		o[n] = as[n].def;
	aout("yyadef", o, nst);
	for (n=0; n<nsy-MaxTk; n++) {
		o[n] = gs[n].def;
		assert(o[n]>0 || o[n]==-1);
		if (o[n]>0)
			o[n]--;
	}
	aout("yygdef", o, nsy-MaxTk);
	aout("yyadsp", adsp, nst);
	aout("yygdsp", gdsp, nsy-MaxTk);
	for (n=0; n<actsz; n++)
		if (act[n]>=0)
			act[n]--;
	aout("yyact", act, actsz);
	aout("yychk", chk, actsz);
	for (n=0; n<128; n++) {
		o[n] = 0;
		for (m=0; m<ntk; m++)
			if (is[m].name[0]=='\'')
			if (is[m].name[1]==n)
				assert(!o[n]), o[n] = m;
	}
	m = 128;
	for (n=1; n<ntk; n++) {
		if (is[n].name[0]=='\'')
			continue;
		fprintf(fout, "#define %s %d\n", is[n].name, m);
		if (fhdr)
			fprintf(fhdr, "#define %s %d\n", is[n].name, m);
		o[m++] = n;
	}
	aout("yytrns", o, m);
	if (fhdr) {
		fputs("int yyparse(void);\n", fhdr);
		fputs("#ifndef YYSTYPE\n", fhdr);
		fputs("#define YYSTYPE int\n", fhdr);
		fputs("#endif\n", fhdr);
		fputs("extern YYSTYPE yylval;\n", fhdr);
		fputs("#endif\n", fhdr);
	}
	free(o);
}

void
stdump()
{
	Term *t;
	Sym *s1;
	int n, m, d, act;
	Rule *r;
	Row *ar;

	if (!fgrm)
		return;
	for (r=rs; r-rs<nrl; r++) {
		fprintf(fgrm, "\n%03d: %s ->", (int)(r-rs), is[r->lhs].name);
		for (s1=r->rhs; *s1!=S; s1++)
			fprintf(fgrm, " %s", is[*s1].name);
	}
	fprintf(fgrm, "\n");
	for (m=0; m<nst; m++) {
		fprintf(fgrm, "\nState %d:\n", m);
		for (t=st[m]->ts; t-st[m]->ts<st[m]->nt; t++) {
			r = t->rule;
			d = t->dot;
			if (d==0 && t!=st[m]->ts)
				continue;
			fprintf(fgrm, "  %s ->", is[r->lhs].name);
			for (s1=r->rhs; *s1!=S; s1++, d--)
				fprintf(fgrm, " %s%s", d ? "" : ". ", is[*s1].name);
			if (!d)
				fprintf(fgrm, " .");
			fprintf(fgrm, "\n");
		}
		fprintf(fgrm, "\n");
		ar = &as[m];
		for (n=0; n<ntk; n++) {
			act = ar->t[n];
			if (!act)
				continue;
			if (act==-1)
				fprintf(fgrm, "  %s error (nonassoc)\n", is[n].name);
			else if (act<0)
				fprintf(fgrm, "  %s reduce with rule %d\n", is[n].name, Red(act));
			else
				fprintf(fgrm, "  %s shift and go to %d\n", is[n].name, act-1);
		}
		if (ar->def != -1)
			fprintf(fgrm, "  * reduce with rule %d\n", ar->def);
	}
}

enum {
	TIdnt,
	TTokchr, /* 'c' */
	TPP, /* %% */
	TLL, /* %{ */
	TLangle, /* < */
	TRangle, /* > */
	TSemi, /* ; */
	TBar, /* | */
	TColon, /* : */
	TLBrack, /* { */
	TUnion,
	TType,
	TToken,
	TRight,
	TLeft,
	TNonassoc,
	TPrec,
	TStart,
	TEof
};

struct {
	char *name;
	int tok;
} words[] = {
	{ "%%", TPP },
	{ "%union", TUnion },
	{ "%type", TType },
	{ "%token", TToken },
	{ "%right", TRight },
	{ "%left", TLeft },
	{ "%nonassoc", TNonassoc },
	{ "%prec", TPrec },
	{ "%start", TStart },
	{ 0, 0 }
};

char idnt[IdntSz];

int
istok(int c)
{
	return isalnum(c) || c=='_' || c=='%';
}

int
nexttk()
{
	int n;
	char c, *p;

	while (isspace(c=fgetc(fin)))
		if (c == '\n')
			lineno++;
	switch (c) {
	case '<':
		return TLangle;
	case '>':
		return TRangle;
	case ';':
		return TSemi;
	case '|':
		return TBar;
	case ':':
		return TColon;
	case '{':
		return TLBrack;
	case EOF:
		return TEof;
	case '\'':
		idnt[0] = '\'';
		idnt[1] = fgetc(fin);
		idnt[2] = '\'';
		idnt[3] = 0;
		if (fgetc(fin)!='\'')
			die("syntax error, invalid char token");
		return TTokchr;
	}
	p = idnt;
	while (istok(c)) {
		*p++ = c;
		if (p-idnt >= IdntSz-1)
			die("identifier too long");
		c = fgetc(fin);
	}
	*p = 0;
	if (strcmp(idnt, "%")==0)
	if (c=='{')
		return TLL;
	ungetc(c, fin);
	for (n=0; words[n].name; n++)
		if (strcmp(idnt, words[n].name) == 0)
			return words[n].tok;
	return TIdnt;
}

char *
cpycode()
{
	int c, nest, in, len, pos;
	char *s;

	len = 64;
	s = yalloc(len+1, 1);
	s[0] = '{';
	pos = 1;
	nest = 1;
	in = 0;

	while (nest) {
		c = fgetc(fin);
		if (in) {
			if (c == in)
			if (s[pos-1] != '\\')
				in = 0;
		} else {
			if (c == '"' || c == '\'')
				in = c;
			if (c == '{')
				nest++;
			if (c == '}')
				nest--;
			if (c == EOF)
				die("syntax error, unclosed code block");
			if (c == '\n')
				lineno++;
		}
		if (pos>=len)
		if (!(s=realloc(s, len=2*len+1)))
			die("out of memory");
		s[pos++] = c;
	}
	s[pos] = 0;
	return s;
}

int
gettype(char *type)
{
	int tk;

	tk = nexttk();
	if (tk==TLangle) {
		if (nexttk()!=TIdnt)
			die("syntax error, ident expected after <");
		strcpy(type, idnt);
		if (nexttk()!=TRangle)
			die("syntax error, unclosed <");
		return nexttk();
	} else {
		type[0] = 0;
		return tk;
	}
}

Sym
findsy(char *name, int add)
{
	int n;

	for (n=0; n<nsy; n++) {
		if (n == ntk) {
			if (name[0]=='\'') {
				if (ntk>=MaxTk)
					die("too many tokens");
				ntk++;
				strcpy(is[n].name, name);
				return n;
			}
			n = MaxTk;
		}
		if (strcmp(is[n].name, name)==0)
			return n;
	}
	if (add) {
		if (nsy>=MaxTk+MaxNt)
			die("too many non-terminals");
		strcpy(is[nsy].name, name);
		return nsy++;
	} else
		return nsy;
}

void
getdecls()
{
	int tk, prec, p, a, c, c1, n;
	Info *si;
	char type[IdntSz], *s;

	strcpy(is[0].name, "$");
	ntk = 1;
	strcpy(is[Sym0].name, "@start");
	nsy = MaxTk+1;
	sstart = S;
	prec = 0;
	tk = nexttk();
	for (;;)
	switch (tk) {
	case TStart:
		tk = nexttk();
		if (tk!=TIdnt)
			die("syntax error, ident expected after %start");
		sstart = findsy(idnt, 1);
		if (sstart<ntk)
			die("%start cannot specify a token");
		tk = nexttk();
		break;
	case TUnion:
		tk = nexttk();
		if (tk!=TLBrack)
			die("syntax error, { expected after %union");
		fprintf(fout, "#line %d \"%s\"\n", lineno, srca);
		s = cpycode();
		fprintf(fout, "typedef union %s yyunion;\n", s);
		fprintf(fout, "#define YYSTYPE yyunion\n");
		if (fhdr) {
			fprintf(fhdr, "typedef union %s yyunion;\n", s);
			fprintf(fhdr, "#define YYSTYPE yyunion\n");
		}
		free(s);
		doty = 1;
		tk = nexttk();
		break;
	case TLeft:
		p = ++prec;
		a = ALeft;
		goto addtoks;
	case TRight:
		p = ++prec;
		a = ARight;
		goto addtoks;
	case TNonassoc:
		p = ++prec;
		a = ANonassoc;
		goto addtoks;
	case TToken:
		p = 0;
		a = ANone;
	addtoks:
		tk = gettype(type);
		while (tk==TIdnt || tk==TTokchr) {
			si = 0;
			n = findsy(idnt, 0);
			if (n>=MaxTk && n<nsy)
				die("non-terminal redeclared as token");
			if (n==nsy) {
				if (ntk>=MaxTk)
					die("too many tokens");
				n = ntk++;
			}
			si = &is[n];
			strcpy(si->name, idnt);
			strcpy(si->type, type);
			si->prec = p;
			si->assoc = a;
			tk = nexttk();
		}
		break;
	case TType:
		tk = gettype(type);
		if (type[0]==0)
			die("syntax error, type expected");
		while (tk==TIdnt) {
			si = 0;
			n = findsy(idnt, 1);
			if (n<ntk)
				die("token redeclared as non-terminal");
			if (n==nsy) {
				nsy++;
			}
			si = &is[n];
			strcpy(si->name, idnt);
			strcpy(si->type, type);
			tk = nexttk();
		}
		break;
	case TLL:
		fprintf(fout, "#line %d \"%s\"\n", lineno, srca);
		for (;;) {
			c = fgetc(fin);
			if (c == EOF)
				die("syntax error, unclosed %{");
			if (c == '%') {
				c1 = fgetc(fin);
				if (c1 == '}') {
					fputs("\n", fout);
					break;
				}
				ungetc(c1, fin);
			}
			if (c == '\n')
				lineno++;
			fputc(c, fout);
		}
		tk = nexttk();
		break;
	case TPP:
		return;
	case TEof:
		die("syntax error, unfinished declarations");
	default:
		die("syntax error, declaration expected");
	}
}

void
getgram()
{
	extern char *retcode;
	int tk;
	Sym hd, *p, s;
	Rule *r;

	for (;;) {
		tk = nexttk();
		if (tk==TPP || tk==TEof) {
			if (sstart==S)
				die("syntax error, empty grammar");
			r = &rs[nrl++];
			r->lhs = Sym0;
			r->rhs[0] = sstart;
			r->rhs[1] = 0;
			r->rhs[2] = S;
			r->act = retcode;
			qsort(rs, nrl, sizeof rs[0], rcmp);
			return;
		}
		if (tk!=TIdnt)
			die("syntax error, production rule expected");
		if (nexttk()!=TColon)
			die("syntax error, colon expected after production's head");
		hd = findsy(idnt, 1);
		if (sstart==S)
			sstart = hd;
		do {
			if (nrl>=MaxRl-1)
				die("too many rules");
			r = &rs[nrl++];
			r->lhs = hd;
			r->act = 0;
			p = r->rhs;
			while ((tk=nexttk())==TIdnt || tk==TTokchr || tk==TPrec) {
				if (tk==TPrec) {
					tk = nexttk();
					if (tk!=TIdnt
					|| (s=findsy(idnt, 0))>=ntk)
						die("token expected after %prec");
					r->prec = is[s].prec;
					continue;
				}
				s = findsy(idnt, 1);
				*p++ = s;
				if (s<ntk && is[s].prec>0)
					r->prec = is[s].prec;
				if (p-r->rhs >= MaxRhs-1)
					die("production rule too long");
			}
			*p = S;
			if (tk==TLBrack) {
				r->actln = lineno;
				r->act = cpycode();
				tk = nexttk();
			}
		} while (tk==TBar);
		if (tk!=TSemi)
			die("syntax error, ; or | expected");
	}
}

void
actout(Rule *r)
{
	long l;
	int i, ar;
	char c, *p, *ty, tya[IdntSz];

	ar = slen(r->rhs);
	p = r->act;
	i = r->actln;
	if (!p)
		return;
	while ((c=*p++))
	switch (c) {
	case '\n':
		i++;
	default:
		fputc(c, fout);
		break;
	case '$':
		c = *p++;
		if (c == '$') {
			fprintf(fout, "yyval");
			if (doty) {
				ty = is[r->lhs].type;
				if (!ty[0]) {
					lineno = i;
					die("$$ has no type");
				}
				fprintf(fout, ".%s", ty);
			}
		}
		else if (c == '<') {
			ty = tya;
			while (istok(*p) && ty-tya<IdntSz-1)
				*ty++ = *p++;
			*ty = 0;
			if (*p++!='>') {
				lineno = i;
				die("unclosed tag field");
			}
			ty = tya;
			c = *p++;
			if (c == '$') {
				fprintf(fout, "yyval.%s", ty);
			} else {
				if (!isdigit(c)) {
					lineno = i;
					die("number or $ expected afer tag field");
				}
				goto readnum;
			}
		}
		else if (isdigit(c)) {
			ty = 0;
		readnum:
			l = strtol(p-1, &p, 10);
			if (l > ar) {
				lineno = i;
				die("invalid $n");
			}
			fprintf(fout, "ps[%d].val", (int)l);
			if (doty) {
				if (!ty && l>0)
					ty = is[r->rhs[l-1]].type;
				if (!ty || !ty[0]) {
					lineno = i;
					die("$n has no type");
				}
				fprintf(fout, ".%s", ty);
			}
		}
		else {
			fputc('$', fout);
			fputc(c, fout);
		}
	}
	fputs("\n", fout);
}

void
codeout()
{
	extern char *code0[], *code1[];
	char **p;
	Rule *r;
	int n, c;

	for (p=code0; *p; p++)
		fputs(*p, fout);
	for (n=0; n<nrl; n++) {
		fprintf(fout, "\tcase %d:\n", n);
		r = &rs[n];
		fprintf(fout, "#line %d \"%s\"\n", r->actln, srca);
		actout(r);
		fputs("\t\tbreak;\n", fout);
	}
	for (p=code1; *p; p++)
		fputs(*p, fout);
	fprintf(fout, "#line %d \"%s\"\n", lineno, srca);
	while ((c=fgetc(fin))!=EOF)
		fputc(c, fout);
}

void
init(int ac, char *av[])
{
	int c, vf, df;
	char *pref, buf[100], *opt;

	(void) ac;
	pref = "y";
	vf = df = 0;
	for (av++; av[0] && av[0][0]=='-'; av++)
		for (opt = &av[0][1]; (c = *opt); opt++)
			switch (c) {
			case 'v':
				vf = 1;
				break;
			case 'd':
				df = 1;
				break;
			case 'b':
				if ((pref = *++av))
					break;
			default:
			usage:
				fputs("usage: myacc [-vd] [-b file_prefix] grammar\n", stderr);
				exit(1);
			}

	if (!(srca = *av))
		goto usage;
	fin = fopen(srca, "r");
	if (strlen(pref) + 10 > sizeof buf)
		die("-b prefix too long");
	sprintf(buf, "%s.tab.c", pref);
	fout = fopen(buf, "w");
	if (vf) {
		sprintf(buf, "%s.output", pref);
		fgrm = fopen(buf, "w");
	}
	if (df) {
		sprintf(buf, "%s.tab.h", pref);
		fhdr = fopen(buf, "w");
		if (fhdr) {
			fprintf(fhdr, "#ifndef Y_TAB_H_\n");
			fprintf(fhdr, "#define Y_TAB_H_\n");
		}
	}
	if (!fin || !fout || (!fgrm && vf) || (!fhdr && df))
		die("cannot open work files");
}

int
main(int ac, char *av[])
{

	init(ac, av);
	getdecls();
	getgram();
	ginit();
	stgen();
	tblgen();
	stdump();
	actgen();
	tblout();
	codeout();

	if (srconf)
		fprintf(stderr, "%d shift/reduce conflicts\n", srconf);
	if (rrconf)
		fprintf(stderr, "%d reduce/reduce conflicts\n", rrconf);

	exit(0);
}

/* Glorious macros.
	|sed 's|.*|"&\\n",|'
*/

char *retcode = "\t\tyyval = ps[1].val; return 0;";

char *code0[] = {
"\n",
"#ifndef YYSTYPE\n",
"#define YYSTYPE int\n",
"#endif\n",
"YYSTYPE yylval;\n",
"\n",
"int\n",
"yyparse()\n",
"{\n",
"	enum {\n",
"		StackSize = 100,\n",
"		ActSz = sizeof yyact / sizeof yyact[0],\n",
"	};\n",
"	struct {\n",
"		YYSTYPE val;\n",
"		int state;\n",
"	} stk[StackSize], *ps;\n",
"	int r, h, n, s, tk;\n",
"	YYSTYPE yyval;\n",
"\n",
"	ps = stk;\n",
"	ps->state = s = yyini;\n",
"	tk = -1;\n",
"loop:\n",
"	n = yyadsp[s];\n",
"	if (tk < 0 && n > -yyntoks)\n",
"		tk = yytrns[yylex()];\n",
"	n += tk;\n",
"	if (n < 0 || n >= ActSz || yychk[n] != tk) {\n",
"		r = yyadef[s];\n",
"		if (r < 0)\n",
"			return -1;\n",
"		goto reduce;\n",
"	}\n",
"	n = yyact[n];\n",
"	if (n == -1)\n",
"		return -1;\n",
"	if (n < 0) {\n",
"		r = - (n+2);\n",
"		goto reduce;\n",
"	}\n",
"	tk = -1;\n",
"	yyval = yylval;\n",
"stack:\n",
"	ps++;\n",
"	if (ps-stk >= StackSize)\n",
"		return -2;\n",
"	s = n;\n",
"	ps->state = s;\n",
"	ps->val = yyval;\n",
"	goto loop;\n",
"reduce:\n",
"	ps -= yyr1[r];\n",
"	h = yyr2[r];\n",
"	s = ps->state;\n",
"	n = yygdsp[h] + s;\n",
"	if (n < 0 || n >= ActSz || yychk[n] != yyntoks+h)\n",
"		n = yygdef[h];\n",
"	else\n",
"		n = yyact[n];\n",
"	switch (r) {\n",
0
};

char *code1[] = {
"	}\n",
"	goto stack;\n",
"}\n",
0
};