#include #include #include #include /* * all these are 32 bit */ #define TBITSET ((32+NTERMS)/32) #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 "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" #define NTBASE 010000 #define ERRCODE 8190 #define ACCEPTCODE 8191 /* * the following are adjustable * according to memory size */ # define ACTSIZE 20000 # define MEMSIZE 20000 # define NSTATES 750 # define NTERMS 255 # define NPROD 600 # define NNONTERM 300 # define TEMPSIZE 1200 # define CNAMSZ 5000 # define LSETSIZE 600 # define WSETSIZE 350 #define NAMESIZE 50 #define NTYPES 63 #define ISIZE 400 /* relationships which must hold: TBITSET ints must hold NTERMS+1 bits... WSETSIZE >= NNONTERM LSETSIZE >= NNONTERM TEMPSIZE >= NTERMS + NNONTERMs + 1 TEMPSIZE >= NSTATES */ #define NOASC 0 /* no assoc. */ #define LASC 1 /* left assoc. */ #define RASC 2 /* right assoc. */ #define BASC 3 /* binary assoc. */ /* flags for state generation */ #define DONE 0 #define MUSTDO 1 #define MUSTLOOKAHEAD 2 /* flags for a rule having an action, and being reduced */ #define ACTFLAG 04 #define REDFLAG 010 /* output parser flags */ #define YYFLAG1 (-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;i0; ++p) ; p = prdptr[-*p]; q = chcopy(sarr, nontrst[*p-NTBASE].name); q = chcopy(q, " : "); for(;;) { *q++ = (++p==pp)? '.': ' '; *q = '\0'; if((i = *p) <= 0) break; q = chcopy(q, symnam(i)); if(q > &sarr[ISIZE-30]) error("item too big"); } /* an item calling for a reduction */ if((i = *pp) < 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", zzcwp-wsets, WSETSIZE); Bprint(foutput, "memory: states,etc. %d/%d, parser %d/%d\n", zzmemsz-mem0, MEMSIZE, 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); if(fdefine != 0) Bterm(fdefine); } /* * write out error comment -- NEEDS WORK */ void error(char *s, ...) { ++nerrors; fprint(2, "\n fatal error:"); fprint(2, s, (&s)[1]); fprint(2, ", line %d\n", 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; ilset; 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 0; ++p) { if(ch < NTBASE) { SETBIT(wsets[i].ws.lset, ch); break; } if(!pempty[ch-NTBASE]) break; } } /* now, reflect transitivity */ changes = 1; while(changes) { changes = 0; NTLOOP(i) { t = pres[i+1]; for(s = pres[i]; s < t; ++s) for(p = *s; (ch = (*p-NTBASE)) >= 0; ++p) { changes |= setunion(wsets[i].ws.lset, wsets[ch].ws.lset); if(!pempty[ch]) break; } } } NTLOOP(i) pfirst[i] = flset(&wsets[i].ws); if(!indebug) return; if(foutput != 0) NTLOOP(i) { Bprint(foutput, "\n%s: ", nontrst[i].name); prlook(pfirst[i]); Bprint(foutput, " %d\n", pempty[i]); } } /* * sorts last state,and sees if it equals earlier ones. returns state number */ state(int c) { Item *p1, *p2, *k, *l, *q1, *q2; int size1, size2, i; p1 = pstate[nstate]; p2 = pstate[nstate+1]; if(p1 == p2) return 0; /* null state */ /* sort the items */ for(k = p2-1; k > p1; k--) /* make k the biggest */ for(l = k-1; l >= p1; --l) if(l->pitem > k->pitem) { int *s; Lookset *ss; s = k->pitem; k->pitem = l->pitem; l->pitem = s; ss = k->look; k->look = l->look; l->look = ss; } size1 = p2 - p1; /* size of state */ for(i = (c>=NTBASE)? ntstates[c-NTBASE]: tstates[c]; i != 0; i = mstates[i]) { /* get ith state */ q1 = pstate[i]; q2 = pstate[i+1]; size2 = q2 - q1; if(size1 != size2) continue; k = p1; for(l = q1; l < q2; l++) { if(l->pitem != k->pitem) break; ++k; } if(l != q2) continue; /* found it */ pstate[nstate+1] = pstate[nstate]; /* delete last state */ /* fix up lookaheads */ if(nolook) return i; for(l = q1, k = p1; l < q2; ++l, ++k ) { int s; SETLOOP(s) clset.lset[s] = l->look->lset[s]; if(setunion(clset.lset, k->look->lset)) { tystate[i] = MUSTDO; /* register the new set */ l->look = flset( &clset ); } } return i; } /* state is new */ if(nolook) error("yacc state/nolook error"); pstate[nstate+2] = p2; if(nstate+1 >= NSTATES) error("too many states"); if(c >= NTBASE) { mstates[nstate] = ntstates[c-NTBASE]; ntstates[c-NTBASE] = nstate; } else { mstates[nstate] = tstates[c]; tstates[c] = nstate; } tystate[nstate] = MUSTDO; return nstate++; } void putitem(int *ptr, Lookset *lptr) { Item *j; if(pidebug && foutput != 0) Bprint(foutput, "putitem(%s), state %d\n", writem(ptr), nstate); j = pstate[nstate+1]; j->pitem = ptr; if(!nolook) j->look = flset(lptr); pstate[nstate+1] = ++j; if((int*)j > zzmemsz) { zzmemsz = (int*)j; if(zzmemsz >= &mem0[MEMSIZE]) error("out of state space"); } } /* * mark nonterminals which derive the empty string * also, look for nonterminals which don't derive any token strings */ void cempty(void) { int i, *p; /* first, use the array pempty to detect productions that can never be reduced */ /* set pempty to WHONOWS */ aryfil(pempty, nnonter+1, WHOKNOWS); /* now, look at productions, marking nonterminals which derive something */ more: PLOOP(0, i) { if(pempty[*prdptr[i] - NTBASE]) continue; for(p = prdptr[i]+1; *p >= 0; ++p) if(*p >= NTBASE && pempty[*p-NTBASE] == WHOKNOWS) break; /* production can be derived */ if(*p < 0) { pempty[*prdptr[i]-NTBASE] = OK; goto more; } } /* now, look at the nonterminals, to see if they are all OK */ NTLOOP(i) { /* the added production rises or falls as the start symbol ... */ if(i == 0) continue; if(pempty[i] != OK) { fatfl = 0; error("nonterminal %s never derives any token string", nontrst[i].name); } } if(nerrors) { summary(); cleantmp(); exits("error"); } /* now, compute the pempty array, to see which nonterminals derive the empty string */ /* set pempty to WHOKNOWS */ aryfil( pempty, nnonter+1, WHOKNOWS); /* loop as long as we keep finding empty nonterminals */ again: PLOOP(1, i) { /* not known to be empty */ if(pempty[*prdptr[i]-NTBASE] == WHOKNOWS) { for(p = prdptr[i]+1; *p >= NTBASE && pempty[*p-NTBASE] == EMPTY ; ++p) ; /* we have a nontrivially empty nonterminal */ if(*p < 0) { pempty[*prdptr[i]-NTBASE] = EMPTY; /* got one ... try for another */ goto again; } } } } /* * generate the states */ void stagen(void) { int c, i, j; Wset *p, *q; /* initialize */ nstate = 0; /* THIS IS FUNNY from the standpoint of portability * it represents the magic moment when the mem0 array, which has * been holding the productions, starts to hold item pointers, of a * different type... * someday, alloc should be used to allocate all this stuff... for now, we * accept that if pointers don't fit in integers, there is a problem... */ pstate[0] = pstate[1] = (Item*)mem; aryfil(clset.lset, tbitset, 0); putitem(prdptr[0]+1, &clset); tystate[0] = MUSTDO; nstate = 1; pstate[2] = pstate[1]; aryfil(amem, ACTSIZE, 0); /* now, the main state generation loop */ more: SLOOP(i) { if(tystate[i] != MUSTDO) continue; tystate[i] = DONE; aryfil(temp1, nnonter+1, 0); /* take state i, close it, and do gotos */ closure(i); /* generate goto's */ WSLOOP(wsets, p) { if(p->flag) continue; p->flag = 1; c = *(p->pitem); if(c <= 1) { if(pstate[i+1]-pstate[i] <= p-wsets) tystate[i] = MUSTLOOKAHEAD; continue; } /* do a goto on c */ WSLOOP(p, q) /* this item contributes to the goto */ if(c == *(q->pitem)) { putitem(q->pitem+1, &q->ws); q->flag = 1; } if(c < NTBASE) state(c); /* register new state */ else temp1[c-NTBASE] = state(c); } if(gsdebug && foutput != 0) { Bprint(foutput, "%d: ", i); NTLOOP(j) if(temp1[j]) Bprint(foutput, "%s %d, ", nontrst[j].name, temp1[j]); Bprint(foutput, "\n"); } indgo[i] = apack(&temp1[1], nnonter-1) - 1; /* we have done one goto; do some more */ goto more; } /* no more to do... stop */ } /* * generate the closure of state i */ void closure(int i) { Wset *u, *v; Item *p, *q; int c, ch, work, k, *pi, **s, **t; ++zzclose; /* first, copy kernel of state i to wsets */ cwp = wsets; ITMLOOP(i, p, q) { cwp->pitem = p->pitem; cwp->flag = 1; /* this item must get closed */ SETLOOP(k) cwp->ws.lset[k] = p->look->lset[k]; WSBUMP(cwp); } /* now, go through the loop, closing each item */ work = 1; while(work) { work = 0; WSLOOP(wsets, u) { if(u->flag == 0) continue; /* dot is before c */ c = *(u->pitem); if(c < NTBASE) { u->flag = 0; /* only interesting case is where . is before nonterminal */ continue; } /* compute the lookahead */ aryfil(clset.lset, tbitset, 0); /* find items involving c */ WSLOOP(u, v) if(v->flag == 1 && *(pi=v->pitem) == c) { v->flag = 0; if(nolook) continue; while((ch = *++pi) > 0) { /* terminal symbol */ if(ch < NTBASE) { SETBIT(clset.lset, ch); break; } /* nonterminal symbol */ setunion(clset.lset, pfirst[ch-NTBASE]->lset); if(!pempty[ch-NTBASE]) break; } if(ch <= 0) setunion(clset.lset, v->ws.lset); } /* * now loop over productions derived from c * c is now nonterminal number */ c -= NTBASE; t = pres[c+1]; for(s = pres[c]; s < t; ++s) { /* * put these items into the closure * is the item there */ WSLOOP(wsets, v) /* yes, it is there */ if(v->pitem == *s) { if(nolook) goto nexts; if(setunion(v->ws.lset, clset.lset)) v->flag = work = 1; goto nexts; } /* not there; make a new entry */ if(cwp-wsets+1 >= WSETSIZE) error( "working set overflow"); cwp->pitem = *s; cwp->flag = 1; if(!nolook) { work = 1; SETLOOP(k) cwp->ws.lset[k] = clset.lset[k]; } WSBUMP(cwp); nexts:; } } } /* have computed closure; flags are reset; return */ if(cwp > zzcwp) zzcwp = cwp; if(cldebug && foutput != 0) { Bprint(foutput, "\nState %d, nolook = %d\n", i, nolook); WSLOOP(wsets, u) { if(u->flag) Bprint(foutput, "flag set!\n"); u->flag = 0; Bprint(foutput, "\t%s", writem(u->pitem)); prlook(&u->ws); Bprint(foutput, "\n"); } } } /* *decide if the lookahead set pointed to by p is known * return pointer to a perminent location for the set */ Lookset* flset(Lookset *p) { Lookset *q; int *u, *v, *w, j; for(q = &lkst[nlset]; q-- > lkst;) { u = p->lset; v = q->lset; w = &v[tbitset]; while(v < w) if(*u++ != *v++) goto more; /* we have matched */ return q; more:; } /* add a new one */ q = &lkst[nlset++]; if(nlset >= LSETSIZE) error("too many lookahead sets"); SETLOOP(j) q->lset[j] = p->lset[j]; return q; } void cleantmp(void) { ZAPFILE(actname); ZAPFILE(tempname); } void intr(void) { cleantmp(); exits("interrupted"); } void setup(int argc, char *argv[]) { int i, j, t, lev, ty, c, ytab, *p; int vflag, Dflag, dflag, stem; char actnm[8], *stemc; ytab = 0; vflag = 0; Dflag = 0; dflag = 0; stem = 0; stemc = "y"; foutput = 0; fdefine = 0; fdebug = 0; ARGBEGIN{ case 'v': case 'V': vflag++; break; case 'D': Dflag++; break; case 'd': dflag++; break; case 'o': ytab++; ytabc = ARGF(); break; case 's': stem++; stemc = ARGF(); break; default: error("illegal option: %c", ARGC()); }ARGEND openup(stemc, Dflag, dflag, vflag, ytab, ytabc); ftemp = Bopen(tempname = mktemp(ttempname), OWRITE); faction = Bopen(actname = mktemp(tactname), OWRITE); if(ftemp == 0 || faction == 0) error("cannot open temp file"); if(argc < 1) error("no input file"); if((finput=Bopen(infile=argv[0], OREAD)) == 0) error("cannot open '%s'", argv[0]); cnamp = cnames; defin(0, "$end"); /* this junky number is known where fdebug is used */ extval = 0400; defin(0, "error"); defin(1, "$accept"); mem = mem0; i = 0; /* sorry -- no yacc parser here..... we must bootstrap somehow... */ for(t = gettok(); t != MARK && t != ENDFILE;) switch(t) { case ';': t = gettok(); break; case START: if(gettok() != IDENTIFIER) error("bad %%start construction"); start = chfind(1, tokname); t = gettok(); continue; case TYPEDEF: if(gettok() != TYPENAME) error("bad syntax in %%type"); ty = numbval; for(;;) { t = gettok(); switch(t) { case IDENTIFIER: if((t=chfind(1, tokname)) < NTBASE) { j = TYPE(toklev[t]); if(j != 0 && j != ty) error("type redeclaration of token %s", tokset[t].name); else SETTYPE(toklev[t], ty); } else { j = nontrst[t-NTBASE].tvalue; if(j != 0 && j != ty) error("type redeclaration of nonterminal %s", nontrst[t-NTBASE].name ); else nontrst[t-NTBASE].tvalue = ty; } case ',': continue; case ';': t = gettok(); default: break; } break; } continue; case UNION: /* copy the union declaration to the output */ cpyunion(); t = gettok(); continue; case LEFT: case BINARY: case RIGHT: ++i; case TERM: /* nonzero means new prec. and assoc. */ lev = t-TERM; ty = 0; /* get identifiers so defined */ t = gettok(); /* there is a type defined */ if(t == TYPENAME) { ty = numbval; t = gettok(); } for(;;) { switch(t) { case ',': t = gettok(); continue; case ';': break; case IDENTIFIER: j = chfind(0, tokname); if(j >= NTBASE) error("%s defined earlier as nonterminal", tokname); if(lev) { if(ASSOC(toklev[j])) error("redeclaration of precedence of %s", tokname); SETASC(toklev[j], lev); SETPLEV(toklev[j], i); } if(ty) { if(TYPE(toklev[j])) error("redeclaration of type of %s", tokname); SETTYPE(toklev[j],ty); } if((t=gettok()) == NUMBER) { tokset[j].value = numbval; if(j < ndefout && j > 2) error("please define type number of %s earlier", tokset[j].name); t = gettok(); } continue; } break; } continue; case LCURLY: defout(0); cpycode(); t = gettok(); continue; default: error("syntax error"); } if(t == ENDFILE) error("unexpected EOF before %%"); /* t is MARK */ defout(1); Bprint(ftable, "#define yyclearin yychar = -1\n"); Bprint(ftable, "#define yyerrok yyerrflag = 0\n"); Bprint(ftable, "extern int yychar;\nextern short yyerrflag;\n"); Bprint(ftable, "#ifndef YYMAXDEPTH\n#define YYMAXDEPTH 150\n#endif\n" ); if(!ntypes) Bprint(ftable, "#ifndef YYSTYPE\n#define YYSTYPE int\n#endif\n"); Bprint(ftable, "YYSTYPE yylval, yyval;\n"); prdptr[0] = mem; /* added production */ *mem++ = NTBASE; /* if start is 0, we will overwrite with the lhs of the first rule */ *mem++ = start; *mem++ = 1; *mem++ = 0; prdptr[1] = mem; while((t=gettok()) == LCURLY) cpycode(); if(t != C_IDENTIFIER) error("bad syntax on first rule"); if(!start) prdptr[0][1] = chfind(1, tokname); /* read rules */ while(t != MARK && t != ENDFILE) { /* process a rule */ rlines[nprod] = lineno; if(t == '|') *mem++ = *prdptr[nprod-1]; else if(t == C_IDENTIFIER) { *mem = chfind(1, tokname); if(*mem < NTBASE) error("token illegal on LHS of grammar rule"); ++mem; } else error("illegal rule: missing semicolon or | ?"); /* read rule body */ t = gettok(); more_rule: while(t == IDENTIFIER) { *mem = chfind(1, tokname); if(*mem < NTBASE) levprd[nprod] = toklev[*mem]; ++mem; t = gettok(); } if(t == PREC) { if(gettok() != IDENTIFIER) error("illegal %%prec syntax"); j = chfind(2, tokname); if(j >= NTBASE) error("nonterminal %s illegal after %%prec", nontrst[j-NTBASE].name); levprd[nprod] = toklev[j]; t = gettok(); } if(t == '=') { levprd[nprod] |= ACTFLAG; Bprint(faction, "\ncase %d:", nprod); cpyact(mem-prdptr[nprod]-1); Bprint(faction, " break;"); if((t=gettok()) == IDENTIFIER) { /* action within rule... */ sprint(actnm, "$$%d", nprod); /* make it a nonterminal */ j = chfind(1, actnm); /* * the current rule will become rule number nprod+1 * move the contents down, and make room for the null */ for(p = mem; p >= prdptr[nprod]; --p) p[2] = *p; mem += 2; /* enter null production for action */ p = prdptr[nprod]; *p++ = j; *p++ = -nprod; /* update the production information */ levprd[nprod+1] = levprd[nprod] & ~ACTFLAG; levprd[nprod] = ACTFLAG; if(++nprod >= NPROD) error("more than %d rules", NPROD); prdptr[nprod] = p; /* make the action appear in the original rule */ *mem++ = j; /* get some more of the rule */ goto more_rule; } } while(t == ';') t = gettok(); *mem++ = -nprod; /* check that default action is reasonable */ if(ntypes && !(levprd[nprod]&ACTFLAG) && nontrst[*prdptr[nprod]-NTBASE].tvalue) { /* 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].tvalue; else tempty = TYPE(toklev[tempty]); if(tempty != nontrst[*prdptr[nprod]-NTBASE].tvalue) error("default action causes potential type clash"); } if(++nprod >= NPROD) error("more than %d rules", NPROD); prdptr[nprod] = mem; levprd[nprod] = 0; } /* end of all rules */ finact(); if(t == MARK) { Bprint(ftable, "\n# line %d \"%s\"\n", lineno, infile); while((c=Bgetc(finput)) != Beof) Bputc(ftable, c); } Bterm(finput); } /* * finish action routine */ void finact(void) { Bterm(faction); Bprint(ftable, "# define YYERRCODE %d\n", tokset[2].value); } /* * define s to be a terminal if t=0 * or a nonterminal if t=1 */ defin(int t, char *s) { int val; val = 0; if(t) { if(++nnonter >= NNONTERM) error("too many nonterminals, limit %d",NNONTERM); nontrst[nnonter].name = cstash(s); return NTBASE + nnonter; } /* must be a token */ 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] == ' ' && s[2] == 0) { val = s[1]; goto out; } /* escape sequence */ if(s[0] == ' ' && s[1] == '\\' && 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] <= '7' && s[2] >= '0') { 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; } 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; char *cp; static int beenhere = 0; if(!beenhere++ && fdebug != 0) for(i = 0; i < sizeof(tmpx)/sizeof(tmpx[0]); i++) tmpx[i] = -1; for(i = ndefout; i <= ntokens; ++i) { cp = tokset[i].name; /* literals */ if(*cp == ' ') tmpx[tokset[i].value] = i; else { Bprint(ftable, "# define %s %d\n", tokset[i].name, tokset[i].value); if(fdefine != 0) Bprint(fdefine, "# define %s %d\n", tokset[i].name, tokset[i].value); tmpx[tokset[i].value] = i; } } ndefout = ntokens+1; if(last && fdebug != 0) { Bprint(fdebug, "char *yytoknames[] = {\n"); for(i = 0; i < sizeof(tmpx)/sizeof(tmpx[0]); i++) if(tmpx[i] == -1) Bprint(fdebug, "0,"); else Bprint(fdebug, "\"%s\",\n", tokset[tmpx[i]].name); 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; } gettok(void) { int i, base, c, match, reserve; static int peekline; begin: reserve = 0; lineno += peekline; peekline = 0; c = Bgetc(finput); while(c == ' ' || c == '\n' || c == '\t' || c == '\f') { if(c == '\n') ++lineno; c = Bgetc(finput); } /* skip comment */ if(c == '/') { lineno += skipcom(); goto begin; } switch(c) { case Beof: return ENDFILE; case '{': Bungetc(finput); /* action ... */ return '='; case '<': /* get, and look up, a type name (union member name) */ i = 0; while((c=Bgetc(finput)) != '>' && c >= 0 && c != '\n') { tokname[i] = c; if(++i >= NAMESIZE) --i; } if(c != '>') error("unterminated < ... > clause"); tokname[i] = 0; for(i = 1; i <= ntypes; ++i) if(!strcmp(typeset[i], tokname)) { numbval = i; return TYPENAME; } typeset[numbval = ++ntypes] = cstash(tokname); return TYPENAME; case '"': case '\'': match = c; tokname[0] = ' '; i = 1; for(;;) { c = Bgetc(finput); if(c == '\n' || c <= 0) error("illegal or missing ' or \"" ); if(c == '\\') { c = Bgetc(finput); tokname[i] = '\\'; if(++i >= NAMESIZE) --i; } else if(c == match) break; tokname[i] = c; if(++i >= NAMESIZE) --i; } break; case '%': case '\\': switch(c = Bgetc(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 = Bgetc(finput); isdigit(c); c = Bgetc(finput)) numbval = numbval*base + c - '0'; Bungetc(finput); return NUMBER; } if(islower(c) || isupper(c) || c=='_' || c=='.' || c=='$') { i = 0; while(islower(c) || isupper(c) || isdigit(c) || c == '-' || c=='_' || c=='.' || c=='$') { tokname[i] = c; if(reserve && isupper(c)) tokname[i] += 'a'-'A'; if(++i >= NAMESIZE) --i; c = Bgetc(finput); } } else return c; Bungetc(finput); } tokname[i] = 0; /* find a reserved word */ if(reserve) { if(!strcmp(tokname,"term")) return TERM; if(!strcmp(tokname,"token")) return TERM; if(!strcmp(tokname,"left")) return LEFT; if(!strcmp(tokname,"nonassoc")) return BINARY; if(!strcmp(tokname,"binary")) return BINARY; if(!strcmp(tokname,"right")) return RIGHT; if(!strcmp(tokname,"prec")) return PREC; if(!strcmp(tokname,"start")) return START; if(!strcmp(tokname,"type")) return TYPEDEF; if(!strcmp(tokname,"union")) return UNION; error("invalid escape, or illegal reserved word: %s", tokname); } /* look ahead to distinguish IDENTIFIER from C_IDENTIFIER */ c = Bgetc(finput); while(c == ' ' || c == '\t'|| c == '\n' || c == '\f' || c == '/') { if(c == '\n') ++peekline; /* look for comments */ if(c == '/') peekline += skipcom(); c = Bgetc(finput); } if(c == ':') return C_IDENTIFIER; Bungetc(finput); return IDENTIFIER; } /* * determine the type of a symbol */ fdtype(int t) { int v; if(t >= NTBASE) v = nontrst[t-NTBASE].tvalue; 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; } 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) { int level, c; Bprint(ftable, "\n# line %d \"%s\"\n", lineno, infile); Bprint(ftable, "typedef union "); if(fdefine != 0) Bprint(fdefine, "\ntypedef union "); level = 0; for(;;) { if((c=Bgetc(finput)) == Beof) error("EOF encountered while processing %%union"); Bputc(ftable, c); if(fdefine != 0) Bputc(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, " YYSTYPE;\nextern YYSTYPE yylval;\n"); return; } } } } /* * copies code between \{ and \} */ void cpycode(void) { int c; c = Bgetc(finput); if(c == '\n') { c = Bgetc(finput); lineno++; } Bprint(ftable, "\n# line %d \"%s\"\n", lineno, infile); while(c != Beof) { if(c == '\\') { if((c=Bgetc(finput)) == '}') return; Bputc(ftable , '\\'); } if(c == '%') { if((c=Bgetc(finput)) == '}') return; Bputc(ftable , '%'); } Bputc(ftable , c); if(c == '\n') ++lineno; c = Bgetc(finput); } error("eof before %%}"); } /* * skip over comments * skipcom is called after reading a '/' */ skipcom(void) { int c, i; /* i is the number of lines skipped */ i = 0; if(Bgetc(finput) != '*') error("illegal comment"); c = Bgetc(finput); while(c != Beof) { while(c == '*') if((c=Bgetc(finput)) == '/') return i; if(c == '\n') ++i; c = Bgetc(finput); } error("EOF inside comment"); } /* * copy C action to the next ; or closing } */ void cpyact(int offset) { int brac, c, match, j, s, tok, fnd; Bprint(faction, "\n# line %d \"%s\"\n", lineno, infile); brac = 0; loop: c = Bgetc(finput); swt: switch(c) { case ';': if(brac == 0) { Bputc(faction , c); return; } goto lcopy; case '{': brac++; goto lcopy; case '$': s = 1; tok = -1; c = Bgetc(finput); /* type description */ if(c == '<') { Bungetc(finput); if(gettok() != TYPENAME) error("bad syntax on $ clause"); tok = numbval; c = Bgetc(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 = Bgetc(finput); } if(isdigit(c)) { j = 0; while(isdigit(c)) { j= j*10 + c-'0'; c = Bgetc(finput); } Bungetc(finput); j = j*s - offset; if(j > 0) error("Illegal use of $%d", j+offset); dollar: Bprint(faction, "yypvt[-%d]", -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 */ Bungetc(finput); if(gettok() != IDENTIFIER) error("$ must be followed by an identifier"); tok = chfind(2, tokname); if((c = Bgetc(finput)) != '#') { Bungetc(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 '}': if(--brac) goto lcopy; Bputc(faction, c); return; case '/': /* look for comments */ Bputc(faction , c); c = Bgetc(finput); if(c != '*') goto swt; /* it really is a comment */ Bputc(faction, c); c = Bgetc(finput); while(c >= 0) { while(c == '*') { Bputc(faction, c); if((c=Bgetc(finput)) == '/') goto lcopy; } Bputc(faction , c); if(c == '\n') ++lineno; c = Bgetc(finput); } error("EOF inside comment"); case '\'': /* character constant */ match = '\''; goto string; case '"': /* character string */ match = '"'; string: Bputc(faction , c); while(c=Bgetc(finput)) { if(c == '\\') { Bputc(faction , c); c = Bgetc(finput); if(c == '\n') ++lineno; } else if(c == match) goto lcopy; else if(c == '\n') error("newline in string or char. const."); Bputc(faction , c); } error("EOF in string or character constant"); case Beof: error("action does not terminate"); case '\n': ++lineno; goto lcopy; } lcopy: Bputc(faction, c); goto loop; } void openup(char *stem, int Dflag, int dflag, int vflag, int ytab, char *ytabc) { char buf[256]; if(vflag) { sprint(buf, "%s.%s", stem, FILEU); foutput = Bopen(buf, OWRITE); if(foutput == 0) error("cannot open %s", buf); } if(Dflag) { sprint(buf, "%s.%s", stem, FILEDEBUG); if((fdebug = Bopen(buf, OWRITE)) == 0) error("can't open %s", buf); Bprint(fdebug, "#ifdef YYDEBUG\n"); } if(dflag) { sprint(buf, "%s.%s", stem, FILED); fdefine = Bopen(buf, OWRITE); if(fdefine == 0) error("can't create %s", buf); } if(ytab == 0) sprint(buf, "%s.%s", stem, OFILE); else strcpy(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 != 0) Bprint(fdebug, "char *yystates[] = {\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, (Lookset*)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 != 0) 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 ); } } } } wract(i); } if(fdebug != 0) Bprint(fdebug, "};\n#endif\n"); Bprint(ftable, "\t};\n"); wdef("YYNPROD", nprod); } /* * pack state i from temp1 into amem */ apack(int *p, int n) { int *pp, *qq, *rr, off, *q, *r; /* we don't need to worry about checking because * we will only look at entries known to be there... * eliminate leading and trailing 0's */ q = p+n; for(pp = p, off = 0; *pp == 0 && pp <= q; ++pp, --off) ; /* no actions */ if(pp > q) return 0; p = pp; /* now, find a place for the elements from p to q, inclusive */ r = &amem[ACTSIZE-1]; for(rr = amem; rr <= r; ++rr, ++off) { for(qq = rr, pp = p; pp <= q; ++pp, ++qq) if(*pp != 0) if(*pp != *qq && *qq != 0) goto nextk; /* we have found an acceptable k */ if(pkdebug && foutput != 0) Bprint(foutput, "off = %d, k = %d\n", off, rr-amem); for(qq = rr ,pp = p; pp <= q; ++pp, ++qq ) if(*pp) { if(qq > r) error("action table overflow"); if(qq > memp) memp = qq; *qq = *pp; } if(pkdebug && foutput != 0) for(pp = amem; pp <= memp; pp += 10) { Bprint(foutput, "\t"); for(qq = pp; qq <= pp+9; ++qq) Bprint(foutput, "%d ", *qq); Bprint(foutput, "\n"); } return(off); nextk:; } error("no space in action table"); } /* * output the gotos for the nontermninals */ void go2out(void) { int i, j, k, best, count, cbest, times; /* mark begining of gotos */ Bprint(ftemp, "$\n"); for(i = 1; i <= nnonter; ++i) { go2gen(i); /* find the best one to make default */ best = -1; times = 0; /* is j the most frequent */ for(j = 0; j <= nstate; ++j) { if(tystate[j] == 0) continue; if(tystate[j] == best) continue; /* is tystate[j] the most frequent */ count = 0; cbest = tystate[j]; for(k = j; k <= nstate; ++k) if(tystate[k] == cbest) ++count; if(count > times) { best = cbest; times = count; } } /* best is now the default entry */ zzgobest += times-1; for(j = 0; j <= nstate; ++j) if(tystate[j] != 0 && tystate[j] != best) { Bprint(ftemp, "%d,%d,", j, tystate[j]); zzgoent++; } /* now, the default */ zzgoent++; Bprint(ftemp, "%d\n", best); } } /* * output the gotos for nonterminal c */ void go2gen(int c) { int i, work, cc; Item *p, *q; /* first, find nonterminals with gotos on c */ aryfil(temp1, nnonter+1, 0); temp1[c] = 1; work = 1; while(work) { work = 0; PLOOP(0, i) /* cc is a nonterminal */ if((cc=prdptr[i][1]-NTBASE) >= 0) /* cc has a goto on c */ if(temp1[cc] != 0) { /* thus, the left side of production i does too */ cc = *prdptr[i]-NTBASE; if(temp1[cc] == 0) { work = 1; temp1[cc] = 1; } } } /* now, we have temp1[c] = 1 if a goto on c in closure of cc */ if(g2debug && foutput != 0) { Bprint(foutput, "%s: gotos on ", nontrst[c].name); NTLOOP(i) if(temp1[i]) Bprint(foutput, "%s ", nontrst[i].name); Bprint(foutput, "\n"); } /* now, go through and put gotos into tystate */ aryfil(tystate, nstate, 0); SLOOP(i) ITMLOOP(i, p, q) if((cc = *p->pitem) >= NTBASE) /* goto on c is possible */ if(temp1[cc-NTBASE]) { tystate[i] = amem[indgo[i]+c]; break; } } /* * decide a shift/reduce conflict by precedence. * r is a rule number, t a token number * the conflict is in state s * temp1[t] is changed to reflect the action */ void precftn(int r, int t, int s) { int lp, lt, action; lp = levprd[r]; lt = toklev[t]; if(PLEVEL(lt) == 0 || PLEVEL(lp) == 0) { /* conflict */ if(foutput != 0) Bprint(foutput, "\n%d: shift/reduce conflict (shift %d(%d), red'n %d(%d)) on %s", s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), symnam(t)); ++zzsrconf; return; } if(PLEVEL(lt) == PLEVEL(lp)) action = ASSOC(lt); else if(PLEVEL(lt) > PLEVEL(lp)) action = RASC; /* shift */ else action = LASC; /* reduce */ switch(action) { case BASC: /* error action */ temp1[t] = ERRCODE; break; case LASC: /* reduce */ temp1[t] = -r; break; } } /* * output state i * temp1 has the actions, lastred the default */ void wract(int i) { int p, p0, p1, ntimes, tred, count, j, flag; /* find the best choice for lastred */ lastred = 0; ntimes = 0; TLOOP(j) { if(temp1[j] >= 0) continue; if(temp1[j]+lastred == 0) continue; /* count the number of appearances of temp1[j] */ count = 0; tred = -temp1[j]; levprd[tred] |= REDFLAG; TLOOP(p) if(temp1[p]+tred == 0) ++count; if(count > ntimes) { lastred = tred; ntimes = count; } } /* * for error recovery, arrange that, if there is a shift on the * error recovery token, `error', that the default be the error action */ if(temp1[2] > 0) lastred = 0; /* clear out entries in temp1 which equal lastred */ TLOOP(p) if(temp1[p]+lastred == 0) temp1[p] = 0; wrstate(i); defact[i] = lastred; flag = 0; TLOOP(p0) if((p1=temp1[p0]) != 0) { if(p1 < 0) { p1 = -p1; goto exc; } if(p1 == ACCEPTCODE) { p1 = -1; goto exc; } if(p1 == ERRCODE) { p1 = 0; exc: if(flag++ == 0) Bprint(ftable, "-1, %d,\n", i); Bprint(ftable, "\t%d, %d,\n", tokset[p0].value, p1); ++zzexcp; continue; } Bprint(ftemp, "%d,%d,", tokset[p0].value, p1); ++zzacent; } if(flag) { defact[i] = -2; Bprint(ftable, "\t-2, %d,\n", lastred); } Bprint(ftemp, "\n"); } /* * writes state i */ void wrstate(int i) { int j0, j1; Item *pp, *qq; Wset *u; if(fdebug != 0) { Bprint(fdebug, "\""); if(lastred) goto nullmsg; ITMLOOP(i, pp, qq) Bprint(fdebug, "%s\\n", writem(pp->pitem)); if(tystate[i] == MUSTLOOKAHEAD) WSLOOP(wsets + (pstate[i+1] - pstate[i]), u) if(*u->pitem < 0) Bprint(fdebug, "%s\\n", writem(u->pitem)); nullmsg: Bprint(fdebug, "\", /*%d*/\n", i); } if(foutput == 0) return; Bprint(foutput, "\nstate %d\n", i); ITMLOOP(i, pp, qq) Bprint(foutput, "\t%s\n", writem(pp->pitem)); if(tystate[i] == MUSTLOOKAHEAD) /* print out empty productions in closure */ WSLOOP(wsets+(pstate[i+1]-pstate[i]), u) if(*u->pitem < 0) Bprint(foutput, "\t%s\n", writem(u->pitem)); /* check for state equal to another */ TLOOP(j0) if((j1=temp1[j0]) != 0) { Bprint(foutput, "\n\t%s ", symnam(j0)); /* shift, error, or accept */ if(j1 > 0) { if(j1 == ACCEPTCODE) Bprint(foutput, "accept"); else if(j1 == ERRCODE) Bprint(foutput, "error"); else Bprint(foutput, "shift %d", j1); } else Bprint(foutput, "reduce %d (src line %d)", -j1, rlines[-j1]); } /* output the final production */ if(lastred) Bprint(foutput, "\n\t. reduce %d (src line %d)\n\n", lastred, rlines[lastred]); else Bprint(foutput, "\n\t. error\n\n"); /* now, output nonterminal actions */ j1 = ntokens; for(j0 = 1; j0 <= nnonter; ++j0) if(temp1[++j1]) Bprint(foutput, "\t%s goto %d\n", symnam(j0+NTBASE), temp1[j1]); } /* * output a definition of s to the value n */ void wdef(char *s, int n) { Bprint(ftable, "# define %s %d\n", s, n); } void warray(char *s, int *v, int n) { int i; Bprint(ftable, "short %s[]={\n", s); for(i = 0; i < n;) { if(i%10 == 0) Bprint(ftable, "\n"); Bprint(ftable, "%4d", v[i]); if(++i == n) Bprint(ftable, " };\n"); else Bprint(ftable, ","); } } /* * in order to free up the mem and amem arrays for the optimizer, * and still be able to output yyr1, etc., after the sizes of * the action array is known, we hide the nonterminals * derived by productions in levprd. */ void hideprod(void) { int i, j; j = 0; levprd[0] = 0; PLOOP(1, i) { if(!(levprd[i] & REDFLAG)) { ++j; if(foutput != 0) Bprint(foutput, "Rule not reduced: %s\n", writem(prdptr[i])); } levprd[i] = *prdptr[i] - NTBASE; } if(j) print("%d rules never reduced\n", j); } void callopt(void) { int i, *p, j, k, *q; /* read the arrays from tempfile and set parameters */ if((finput=Bopen(tempname, OREAD)) == 0) error("optimizer cannot open tempfile"); pgo[0] = 0; temp1[0] = 0; nstate = 0; nnonter = 0; for(;;) { switch(gtnm()) { case '\n': temp1[++nstate] = --pmem - mem0; case ',': continue; case '$': break; default: error("bad tempfile"); } break; } temp1[nstate] = yypgo[0] = --pmem - mem0; for(;;) { switch(gtnm()) { case '\n': yypgo[++nnonter] = pmem-mem0; case ',': continue; case -1: break; default: error("bad tempfile"); } break; } yypgo[nnonter--] = --pmem - mem0; for(i = 0; i < nstate; ++i) { k = 32000; j = 0; q = mem0 + temp1[i+1]; for(p = mem0 + temp1[i]; p < q ; p += 2) { if(*p > j) j = *p; if(*p < k) k = *p; } /* nontrivial situation */ if(k <= j) { /* j is now the range */ /* j -= k; /* call scj */ if(k > maxoff) maxoff = k; } tystate[i] = (temp1[i+1]-temp1[i]) + 2*j; if(j > maxspr) maxspr = j; } /* initialize ggreed table */ for(i = 1; i <= nnonter; ++i) { ggreed[i] = 1; j = 0; /* minimum entry index is always 0 */ q = mem0 + yypgo[i+1] - 1; for(p = mem0+yypgo[i]; p < q ; p += 2) { ggreed[i] += 2; if(*p > j) j = *p; } ggreed[i] = ggreed[i] + 2*j; if(j > maxoff) maxoff = j; } /* now, prepare to put the shift actions into the amem array */ for(i = 0; i < ACTSIZE; ++i) amem[i] = 0; maxa = amem; for(i = 0; i < nstate; ++i) { if(tystate[i] == 0 && adb > 1) Bprint(ftable, "State %d: null\n", i); indgo[i] = YYFLAG1; } while((i = nxti()) != NOMORE) if(i >= 0) stin(i); else gin(-i); /* print amem array */ if(adb > 2 ) for(p = amem; p <= maxa; p += 10) { Bprint(ftable, "%4d ", p-amem); for(i = 0; i < 10; ++i) Bprint(ftable, "%4d ", p[i]); Bprint(ftable, "\n"); } /* write out the output appropriate to the language */ aoutput(); osummary(); ZAPFILE(tempname); } void gin(int i) { int *p, *r, *s, *q1, *q2; /* enter gotos on nonterminal i into array amem */ ggreed[i] = 0; q2 = mem0+ yypgo[i+1] - 1; q1 = mem0 + yypgo[i]; /* now, find amem place for it */ for(p = amem; p < &amem[ACTSIZE]; ++p) { if(*p) continue; for(r = q1; r < q2; r += 2) { s = p + *r + 1; if(*s) goto nextgp; if(s > maxa) if((maxa = s) > &amem[ACTSIZE]) error("a array overflow"); } /* we have found amem spot */ *p = *q2; if(p > maxa) if((maxa = p) > &amem[ACTSIZE]) error("a array overflow"); for(r = q1; r < q2; r += 2) { s = p + *r + 1; *s = r[1]; } pgo[i] = p-amem; if(adb > 1) Bprint(ftable, "Nonterminal %d, entry at %d\n", i, pgo[i]); return; nextgp:; } error("cannot place goto %d\n", i); } void stin(int i) { int *r, *s, n, flag, j, *q1, *q2; tystate[i] = 0; /* enter state i into the amem array */ q2 = mem0+temp1[i+1]; q1 = mem0+temp1[i]; /* find an acceptable place */ for(n = -maxoff; n < ACTSIZE; ++n) { flag = 0; for(r = q1; r < q2; r += 2) { if((s = *r + n + amem) < amem) goto nextn; if(*s == 0) ++flag; else if(*s != r[1]) goto nextn; } /* check that the position equals another only if the states are identical */ for(j=0; j 1) Bprint(ftable, "State %d: entry at %d equals state %d\n", i, n, j); return; } /* we have some disagreement */ goto nextn; } } for(r = q1; r < q2; r += 2) { if((s = *r+n+amem) >= &amem[ACTSIZE]) error("out of space in optimizer a array"); if(s > maxa) maxa = s; if(*s != 0 && *s != r[1]) error("clobber of a array, pos'n %d, by %d", s-amem, r[1]); *s = r[1]; } indgo[i] = n; if(adb > 1) Bprint(ftable, "State %d: entry at %d\n", i, indgo[i]); return; nextn:; } error("Error; failure to place state %d\n", i); } /* * finds the next i */ nxti(void) { int i, max, maxi; max = 0; maxi = 0; for(i = 1; i <= nnonter; ++i) if(ggreed[i] >= max) { max = ggreed[i]; maxi = -i; } for(i = 0; i < nstate; ++i) if(tystate[i] >= max) { max = tystate[i]; maxi = i; } if(nxdb) Bprint(ftable, "nxti = %d, max = %d\n", maxi, max); if(max == 0) return NOMORE; return maxi; } /* * write summary */ void osummary(void) { int i, *p; if(foutput == 0) return; i = 0; for(p = maxa; p >= amem; p--) if(*p == 0) i++; Bprint(foutput, "Optimizer space used: input %d/%d, output %d/%d\n", pmem-mem0+1, MEMSIZE, maxa-amem+1, ACTSIZE); Bprint(foutput, "%d table entries, %d zero\n", (maxa-amem)+1, i); Bprint(foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff); } /* * this version is for C * write out the optimized parser */ void aoutput(void) { Bprint(ftable, "# define YYLAST %d\n", maxa-amem+1); arout("yyact", amem, (maxa-amem)+1); arout("yypact", indgo, nstate); arout("yypgo", pgo, nnonter+1); } void arout(char *s, int *v, int n) { int i; Bprint(ftable, "short %s[]={\n", s); for(i = 0; i < n;) { if(i%10 == 0) Bprint(ftable, "\n"); Bprint(ftable, "%4d", v[i]); if(++i == n) Bprint(ftable, " };\n"); else Bprint(ftable, ","); } } /* * read and convert an integer from the standard input * return the terminating character * blanks, tabs, and newlines are ignored */ gtnm(void) { int s, val, c; s = 1; val = 0; while((c=Bgetc(finput)) != Beof) { if(isdigit(c)) val = val*10 + c-'0'; else if(c == '-') s = -1; else break; } *pmem++ = s*val; if(pmem > &mem0[MEMSIZE]) error("out of space"); return c; }