diff options
| -rw-r--r-- | minic/LICENSE | 21 | ||||
| -rw-r--r-- | minic/Makefile | 8 | ||||
| -rw-r--r-- | minic/minic.y | 629 | ||||
| -rw-r--r-- | minic/test.minic | 9 | ||||
| -rw-r--r-- | minic/yacc.c | 1365 |
5 files changed, 2032 insertions, 0 deletions
diff --git a/minic/LICENSE b/minic/LICENSE new file mode 100644 index 0000000..7866b82 --- /dev/null +++ b/minic/LICENSE @@ -0,0 +1,21 @@ +MIT/X Consortium License + +© 2015 Quentin Carbonneaux + +Permission is hereby granted, free of charge, to any person obtaining a +copy of this software and associated documentation files (the "Software"), +to deal in the Software without restriction, including without limitation +the rights to use, copy, modify, merge, publish, distribute, sublicense, +and/or sell copies of the Software, and to permit persons to whom the +Software is furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/minic/Makefile b/minic/Makefile new file mode 100644 index 0000000..39b2946 --- /dev/null +++ b/minic/Makefile @@ -0,0 +1,8 @@ +CFLAGS=-g -Wall + +minic: yacc minic.y + ./yacc minic.y + $(CC) $(CFLAGS) -o $@ y.tab.c +clean: + rm -f yacc minic y.* +.PHONY: clean diff --git a/minic/minic.y b/minic/minic.y new file mode 100644 index 0000000..00351e1 --- /dev/null +++ b/minic/minic.y @@ -0,0 +1,629 @@ +%{ + +#include <ctype.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +enum { + NString = 16, + NVar = 256, +}; + + +enum { /* minic types */ + INT = 0, + LNG = 1, + PTR = 2, +}; + +#define IDIR(x) (((x) << 2) + PTR) +#define DREF(x) ((x) >> 2) +#define KIND(x) ((x) & 3) +#define SIZE(x) (KIND(x) == INT ? 4 : 8) + +typedef struct Node Node; +typedef struct Symb Symb; +typedef struct Stmt Stmt; + +struct Node { + char op; + union { + int n; + char v[NString]; + } u; + Node *l, *r; +}; + +struct Symb { + enum { + Con, + Tmp, + Var, + } t; + union { + int n; + char v[NString]; + } u; + unsigned long ctyp; +}; + +struct Stmt { + enum { + If, + While, + Seq, + Expr, + } t; + void *p1, *p2, *p3; +}; + +int yylex(void), yyerror(char *); +Symb expr(Node *), lval(Node *); + +FILE *of; +int lbl, tmp; +struct { + char v[NString]; + unsigned ctyp; +} varh[NVar]; + +void +die(char *s) +{ + fprintf(stderr, "error: %s\n", s); + exit(1); +} + +void * +alloc(size_t s) +{ + void *p; + + p = malloc(s); + if (!p) + die("out of memory"); + return p; +} + +unsigned +hash(char *s) +{ + unsigned h; + + h = 42; + while (*s) + h += 11 * h + *s++; + return h % NVar; +} + +void +varclr() +{ + unsigned h; + + for (h=0; h<NVar; h++) + varh[h].v[0] = 0; +} + +void +varadd(char *v, unsigned ctyp) +{ + unsigned h0, h; + + h0 = hash(v); + h = h0; + do { + if (varh[h].v[0] == 0) { + strcpy(varh[h].v, v); + varh[h].ctyp = ctyp; + return; + } + if (strcmp(varh[h].v, v) == 0) + die("double definition"); + } while(++h != h0); + die("too many variables"); +} + +unsigned +varctyp(char *v) +{ + unsigned h0, h; + + h0 = hash(v); + h = h0; + do { + if (strcmp(varh[h].v, v) == 0) + return varh[h].ctyp; + } while (++h != h0 && varh[h].v[0] != 0); + die("undeclared variable"); + return -1; +} + +char +irtyp(unsigned ctyp) +{ + switch (KIND(ctyp)) { + default: + die("internal error"); + case INT: + return 'w'; + case PTR: + case LNG: + return 'l'; + } +} + +void +psymb(Symb s) +{ + switch (s.t) { + case Tmp: + fprintf(of, "%%t%d", s.u.n); + break; + case Var: + fprintf(of, "%%%s", s.u.v); + break; + case Con: + fprintf(of, "%d", s.u.n); + break; + } +} + +void +sext(Symb *s) +{ + fprintf(of, "\t%%t%d =l sext ", tmp); + psymb(*s); + fprintf(of, "\n"); + s->t = Tmp; + s->ctyp = LNG; + s->u.n = tmp++; +} + +unsigned +prom(int op, Symb *l, Symb *r) +{ + Symb *t; + int sz; + + if (l->ctyp == r->ctyp && KIND(l->ctyp) != PTR) + return l->ctyp; + + if (l->ctyp == LNG && r->ctyp == INT) { + sext(r); + return LNG; + } + if (l->ctyp == INT && r->ctyp == LNG) { + sext(l); + return LNG; + } + + if (op == '+') { + if (KIND(r->ctyp) == PTR) { + t = l; + l = r; + r = t; + } + if (KIND(r->ctyp) == PTR) + die("pointers added"); + goto Scale; + } + + if (op == '-') { + if (KIND(l->ctyp) != PTR) + die("pointer substracted from integer"); + if (KIND(r->ctyp) != PTR) + goto Scale; + if (l->ctyp != r->ctyp) + die("non-homogeneous pointers in substraction"); + return LNG; + } + +Scale: + if (irtyp(r->ctyp) != 'l') + sext(r); + sz = SIZE(DREF(l->ctyp)); + fprintf(of, "\t%%t%d =l mul %d, ", sz, tmp); + psymb(*r); + fprintf(of, "\n"); + r->u.n = tmp++; + return l->ctyp; +} + +Symb +expr(Node *n) +{ + static char *otoa[] = { + ['+'] = "add", + ['-'] = "sub", + ['*'] = "mul", + ['/'] = "div", + ['%'] = "rem", + ['<'] = "cslt", /* meeeeh, careful with pointers */ + ['l'] = "csle", + ['e'] = "cseq", + ['n'] = "csne", + }; + Symb sr, s0, s1; + + sr.t = Tmp; + sr.u.n = tmp++; + + switch (n->op) { + + case 'V': + sr.ctyp = varctyp(n->u.v); + fprintf(of, "\t"); + psymb(sr); + fprintf(of, " =%c ", irtyp(sr.ctyp)); + fprintf(of, "load %%%s\n", n->u.v); + break; + + case 'N': + sr.t = Con; + sr.u.n = n->u.n; + sr.ctyp = INT; + break; + + case '@': + s0 = expr(n->l); + if (KIND(s0.ctyp) != PTR) + die("dereference of a non-pointer"); + sr.ctyp = DREF(s0.ctyp); + fprintf(of, "\t"); + psymb(sr); + fprintf(of, " =%c load ", irtyp(sr.ctyp)); + psymb(s0); + fprintf(of, "\n"); + break; + + case '&': + sr = lval(n->l); + sr.ctyp = IDIR(sr.ctyp); + break; + + case '=': + s0 = expr(n->r); + s1 = lval(n->l); + sr = s0; + if (s1.ctyp == LNG && s0.ctyp == INT) + sext(&s0); + if (s1.ctyp != s0.ctyp) + die("invalid assignment"); + fprintf(of, "\tstore%c ", irtyp(s1.ctyp)); + goto Args; + + case 'P': + case 'M': + die("unimplemented ++ and --"); + break; + + default: + s0 = expr(n->l); + s1 = expr(n->r); + sr.ctyp = prom(n->op, &s0, &s1); + if (strchr("ne<l", n->op)) + sr.ctyp = INT; + fprintf(of, "\t"); + psymb(sr); + fprintf(of, " =%c", irtyp(sr.ctyp)); + fprintf(of, " %s ", otoa[(int)n->op]); + Args: + psymb(s0); + fprintf(of, ", "); + psymb(s1); + fprintf(of, "\n"); + break; + + } + if (n->op == '-' + && KIND(s0.ctyp) == PTR + && KIND(s1.ctyp) == PTR) { + fprintf(of, "\t%%t%d =l div ", tmp); + psymb(sr); + fprintf(of, ", %d\n", SIZE(DREF(s0.ctyp))); + sr.u.n = tmp++; + } + return sr; +} + +Symb +lval(Node *n) +{ + Symb sr; + + switch (n->op) { + default: + die("invalid lvalue"); + case 'V': + sr.t = Var; + sr.ctyp = varctyp(n->u.v); + strcpy(sr.u.v, n->u.v); + break; + case '@': + sr = expr(n->l); + if (KIND(sr.ctyp) != PTR) + die("dereference of a non-pointer"); + sr.ctyp = DREF(sr.ctyp); + break; + } + return sr; +} + +void +stmt(Stmt *s) +{ + int l; + Symb x; +Again: + if (!s) + return; + + switch (s->t) { + case Expr: + expr(s->p1); + break; + case Seq: + stmt(s->p1); + s = s->p2; + goto Again; + case If: + x = expr(s->p1); + fprintf(of, "\tjnz "); /* to be clean, a comparison to 0 should be inserted here */ + psymb(x); + l = lbl; + lbl += 3; + fprintf(of, ", @l%d, @l%d\n", l, l+1); + fprintf(of, "@l%d\n", l); + stmt(s->p2); + if (s->p3) + fprintf(of, "\tjmp @l%d\n", l+2); + fprintf(of, "@l%d\n", l+1); + if (s->p3) { + stmt(s->p3); + fprintf(of, "@l%d\n", l+2); + } + break; + case While: + x = expr(s->p1); + l = lbl; + lbl += 3; + fprintf(of, "@l%d\n", l); + fprintf(of, "\tjnz "); /* ditto */ + psymb(x); + fprintf(of, ", @l%d, @l%d\n", l+1, l+2); + fprintf(of, "@l%d\n", l+1); + stmt(s->p2); + fprintf(of, "\tjmp @l%d\n", l); + fprintf(of, "@l%d\n", l+2); + break; + } +} + +Node * +mknode(char op, Node *l, Node *r) +{ + Node *n; + + n = alloc(sizeof *n); + n->op = op; + n->l = l; + n->r = r; + return n; +} + +Node * +mkidx(Node *a, Node *i) +{ + Node *n; + + n = mknode('+', a, i); + n = mknode('@', n, 0); + return n; +} + +Stmt * +mkstmt(int t, void *p1, void *p2, void *p3) +{ + Stmt *s; + + s = alloc(sizeof *s); + s->t = t; + s->p1 = p1; + s->p2 = p2; + s->p3 = p3; + return s; +} + +%} + +%union { + Node *n; + Stmt *s; + unsigned u; +} + +%token <n> NUM +%token <n> IDENT +%token PP MM LE GE + +%token TINT TLNG +%token IF ELSE WHILE + +%right '=' +%left '+' '-' +%left '*' '/' '%' +%nonassoc '&' +%left EQ NE +%left '<' '>' LE GE +%nonassoc PP MM +%nonassoc '[' + +%type <u> type +%type <s> stmt stmts +%type <n> expr + +%% + +prog: init '{' dcls stmts '}' +{ + stmt($4); + fprintf(of, "\tret\n"); +}; + +init: +{ + varclr(); + lbl = 0; + tmp = 0; + fprintf(of, "@l%d\n", lbl++); +}; + +dcls: | dcls type IDENT ';' +{ + int s; + char *v; + + v = $3->u.v; + s = SIZE($2); + varadd(v, $2); + fprintf(of, "\t%%%s =l alloc%d %d\n", v, s, s); +}; + +type: type '*' { $$ = IDIR($1); } + | TINT { $$ = INT; } + | TLNG { $$ = LNG; } + ; + +stmt: ';' { $$ = 0; } + | '{' stmts '}' { $$ = $2; } + | expr ';' { $$ = mkstmt(Expr, $1, 0, 0); } + | WHILE '(' expr ')' stmt { $$ = mkstmt(While, $3, $5, 0); } + | IF '(' expr ')' stmt ELSE stmt { $$ = mkstmt(If, $3, $5, $7); } + | IF '(' expr ')' stmt { $$ = mkstmt(If, $3, $5, 0); } + ; + +stmts: stmts stmt { $$ = mkstmt(Seq, $1, $2, 0); } + | { $$ = 0; } + ; + +expr: NUM + | IDENT + | expr '[' expr ']' { $$ = mkidx($1, $3); } + | '(' expr ')' { $$ = $2; } + | '*' expr { $$ = mknode('@', $2, 0); } + | '&' expr { $$ = mknode('&', $2, 0); } + | expr '=' expr { $$ = mknode('=', $1, $3); } + | expr '+' expr { $$ = mknode('+', $1, $3); } + | expr '-' expr { $$ = mknode('-', $1, $3); } + | expr '*' expr { $$ = mknode('*', $1, $3); } + | expr '/' expr { $$ = mknode('/', $1, $3); } + | expr '%' expr { $$ = mknode('%', $1, $3); } + | expr '<' expr { $$ = mknode('<', $1, $3); } + | expr '>' expr { $$ = mknode('<', $3, $1); } + | expr LE expr { $$ = mknode('l', $1, $3); } + | expr GE expr { $$ = mknode('l', $3, $1); } + | expr EQ expr { $$ = mknode('e', $1, $3); } + | expr NE expr { $$ = mknode('n', $1, $3); } + | expr PP { $$ = mknode('P', $1, 0); } + | expr MM { $$ = mknode('M', $1, 0); } + ; + +%% + +int +yylex() +{ + struct { + char *s; + int t; + } kwds[] = { + { "int", TINT }, + { "long", TLNG }, + { "if", IF }, + { "else", ELSE }, + { "while", WHILE }, + { 0, 0 } + }; + int i, c, c1, n, sgn; + char v[NString], *p; + + do + c = getchar(); + while (isspace(c)); + + if (c == EOF) + return 0; + + if (isdigit(c) || c == '-') { + n = 0; + sgn = 1; + if (c == '-') { + sgn = -1; + c = getchar(); + if (!isdigit(c)) { + ungetc(c, stdin); + return '-'; + } + } + do { + n *= 10; + n += c-'0'; + c = getchar(); + } while (isdigit(c)); + ungetc(c, stdin); + yylval.n = mknode('N', 0, 0); + yylval.n->u.n = n * sgn; + return NUM; + } + + if (isalpha(c)) { + p = v; + do { + if (p == &v[NString-1]) + die("ident too long"); + *p++ = c; + c = getchar(); + } while (isalpha(c)); + *p = 0; + ungetc(c, stdin); + for (i=0; kwds[i].s; i++) + if (strcmp(v, kwds[i].s) == 0) + return kwds[i].t; + yylval.n = mknode('V', 0, 0); + strcpy(yylval.n->u.v, v); + return IDENT; + } + + c1 = getchar(); +#define DI(a, b) a + b*256 + switch (DI(c,c1)) { + case DI('!','='): return NE; + case DI('=','='): return EQ; + case DI('<','='): return LE; + case DI('>','='): return GE; + case DI('+','+'): return PP; + case DI('-','-'): return MM; + } +#undef DI + ungetc(c1, stdin); + + return c; +} + +int +yyerror(char *err) +{ + die("parse error"); + return 0; +} + +int +main() +{ + of = stdout; + if (yyparse() != 0) + die("parse error"); + return 0; +} diff --git a/minic/test.minic b/minic/test.minic new file mode 100644 index 0000000..8d30eb1 --- /dev/null +++ b/minic/test.minic @@ -0,0 +1,9 @@ +{ + int x; + int *p; + + x = 0; + p = &x; + while (x < 10) + *p = x + 1; +} diff --git a/minic/yacc.c b/minic/yacc.c new file mode 100644 index 0000000..52fd891 --- /dev/null +++ b/minic/yacc.c @@ -0,0 +1,1365 @@ +/*% 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, len, pos; + char *s; + + len = 64; + s = yalloc(len+1, 1); + s[0] = '{'; + pos = 1; + nest = 1; + + while (nest) { + c = fgetc(fin); + 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); + } + } + } + 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 +}; |