6 #define Bungetrune Bungetc /* ok for now. */
11 #define TBITSET ((32+NTERMS)/32) /* BOTCH?? +31 */
12 #define BIT(a,i) ((a)[(i)>>5] & (1<<((i)&037)))
13 #define SETBIT(a,i) ((a)[(i)>>5] |= (1<<((i)&037)))
14 #define NWORDS(n) (((n)+32)/32)
16 char *PARSER = "#9/lib/yaccpar";
17 char *PARSERS = "#9/lib/yaccpars";
19 #define TEMPNAME "y.tmp.XXXXXX"
20 #define ACTNAME "y.acts.XXXXXX"
22 #define FILEU "output"
24 #define FILEDEBUG "debug"
29 * the following are adjustable
30 * according to memory size
47 PRIVATE = 0xE000, /* unicode private use */
49 /* relationships which must hold:
50 TBITSET ints must hold NTERMS+1 bits...
53 TEMPSIZE >= NTERMS + NNONTERM + 1
61 NOASC = 0, /* no assoc. */
62 LASC = 1, /* left assoc. */
63 RASC = 2, /* right assoc. */
64 BASC = 3, /* binary assoc. */
66 /* flags for state generation */
72 /* flags for a rule having an action, and being reduced */
77 /* output parser flags */
104 /* macros for getting associativity and precedence levels */
106 #define ASSOC(i) ((i)&03)
107 #define PLEVEL(i) (((i)>>4)&077)
108 #define TYPE(i) (((i)>>10)&077)
110 /* macros for setting associativity and precedence levels */
112 #define SETASC(i,j) i |= j
113 #define SETPLEV(i,j) i |= (j<<4)
114 #define SETTYPE(i,j) i |= (j<<10)
118 #define TLOOP(i) for(i=1; i<=ntokens; i++)
119 #define NTLOOP(i) for(i=0; i<=nnonter; i++)
120 #define PLOOP(s,i) for(i=s; i<nprod; i++)
121 #define SLOOP(i) for(i=0; i<nstate; i++)
122 #define WSBUMP(x) x++
123 #define WSLOOP(s,j) for(j=s; j<cwp; j++)
124 #define ITMLOOP(i,p,q) for(q=pstate[i+1], p=pstate[i]; p<q; p++)
125 #define SETLOOP(i) for(i=0; i<tbitset; i++)
127 /* command to clobber tempfiles after use */
129 #define ZAPFILE(x) if(x) remove(x)
131 /* I/O descriptors */
133 Biobuf* faction; /* file for saving actions */
134 Biobuf* fdefine; /* file for #defines */
135 Biobuf* fdebug; /* y.debug for strings for debugging */
136 Biobuf* ftable; /* y.tab.c file */
137 Biobuf* ftemp; /* tempfile to pass 2 */
138 Biobuf* finput; /* input file */
139 Biobuf* foutput; /* y.output file */
141 /* communication variables between various I/O routines */
143 char* infile; /* input file name */
144 int numbval; /* value of an input number */
145 char tokname[NAMESIZE+4]; /* input token name, slop for runes and 0 */
147 /* structure declarations */
177 /* storage of names */
179 char cnames[CNAMSZ]; /* place where token and nonterminal names are stored */
180 int cnamsz = CNAMSZ; /* size of cnames */
181 char* cnamp = cnames; /* place where next name is to be put in */
182 int ndefout = 4; /* number of defined symbols output */
185 char ttempname[] = TEMPNAME;
186 char tactname[] = ACTNAME;
192 /* storage of types */
193 int ntypes; /* number of types defined */
194 char* typeset[NTYPES]; /* pointers to type tags */
196 /* token information */
198 int ntokens = 0 ; /* number of tokens */
200 int toklev[NTERMS]; /* vector with the precedence of the terminals */
202 /* nonterminal information */
204 int nnonter = -1; /* the number of nonterminals */
205 Symb nontrst[NNONTERM];
206 int start; /* start symbol */
208 /* assigned token type values */
211 char* ytabc = OFILE; /* name of y.tab.c */
213 /* grammar rule information */
215 int mem0[MEMSIZE] ; /* production storage */
217 int nprod = 1; /* number of productions */
218 int* prdptr[NPROD]; /* pointers to descriptions of productions */
219 int levprd[NPROD]; /* precedence levels for the productions */
220 int rlines[NPROD]; /* line number for this rule */
222 /* state information */
224 int nstate = 0; /* number of states */
225 Item* pstate[NSTATES+2]; /* pointers to the descriptions of the states */
226 int tystate[NSTATES]; /* contains type information about the states */
227 int defact[NSTATES]; /* the default actions of states */
228 int tstates[NTERMS]; /* states generated by terminal gotos */
229 int ntstates[NNONTERM]; /* states generated by nonterminal gotos */
230 int mstates[NSTATES]; /* chain of overflows of term/nonterm generation lists */
231 int lastred; /* the number of the last reduction of a state */
233 /* lookahead set information */
235 Lkset lkst[LSETSIZE];
236 int nolook; /* flag to turn off lookahead computations */
237 int tbitset; /* size of lookahead sets */
238 int nlset = 0; /* next lookahead set index */
239 int nolook = 0; /* flag to suppress lookahead computations */
240 Lkset clset; /* temporary storage for lookahead computations */
242 /* working set information */
244 Wset wsets[WSETSIZE];
247 /* storage for action table */
249 int amem[ACTSIZE]; /* action table storage */
250 int* memp = amem; /* next free action table position */
251 int indgo[NSTATES]; /* index to the stored goto table */
253 /* temporary vector, indexable by states, terms, or ntokens */
255 int temp1[TEMPSIZE]; /* temporary storage, indexed by terms + ntokens or states */
256 int lineno = 1; /* current input line number */
257 int fatfl = 1; /* if on, error is fatal */
258 int nerrors = 0; /* number of errors */
260 /* statistics collection variables */
270 int* ggreed = lkst[0].lset;
271 int* pgo = wsets[0].ws.lset;
272 int* yypgo = &nontrst[0].value;
274 int maxspr = 0; /* maximum spread of any entry */
275 int maxoff = 0; /* maximum offset into a array */
282 /* storage for information about the nonterminals */
284 int** pres[NNONTERM+2]; /* vector of pointers to productions yielding each nonterminal */
285 Lkset* pfirst[NNONTERM+2]; /* vector of pointers to first sets for each nonterminal */
286 int pempty[NNONTERM+1]; /* vector of nonterminals nontrivially deriving e */
288 /* random stuff picked out from between functions */
300 int pidebug = 0; /* debugging flag for putitem */
302 int cldebug = 0; /* debugging flag for closure */
325 /* define functions */
327 void main(int, char**);
329 char* chcopy(char*, char*);
333 void error(char*, ...);
334 void aryfil(int*, int, int);
335 int setunion(int*, int*);
340 void putitem(int*, Lkset*);
344 Lkset* flset(Lkset*);
347 void setup(int, char**);
349 int defin(int, char*);
352 int isvalidchar(long);
355 int chfind(int, char*);
360 void openup(char*, int, int, int, char*);
362 int apack(int*, int);
365 void precftn(int, int, int);
368 void warray(char*, int*, int);
376 void arout(char*, int*, int);
380 main(int argc, char *argv[])
382 PARSER = unsharp(PARSER);
383 PARSERS = unsharp(PARSERS);
386 setup(argc, argv); /* initialize and read productions */
387 tbitset = NWORDS(ntokens);
388 cpres(); /* make table of which productions yield a given nonterminal */
389 cempty(); /* make a table of which nonterminals can match the empty string */
390 cpfir(); /* make a table of firsts of nonterminals */
391 stagen(); /* generate the states */
392 output(); /* write the states and the tables */
402 * put out other arrays, copy the parsers
409 finput = Bopen(parser, OREAD);
411 error("cannot open parser %s: %r", parser);
412 warray("yyr1", levprd, nprod);
413 aryfil(temp1, nprod, 0);
415 temp1[i] = prdptr[i+1]-prdptr[i]-2;
416 warray("yyr2", temp1, nprod);
418 aryfil(temp1, nstate, -1000);
420 for(j=tstates[i]; j!=0; j=mstates[j])
423 for(j=ntstates[i]; j!=0; j=mstates[j])
425 warray("yychk", temp1, nstate);
426 warray("yydef", defact, nstate);
428 /* put out token translation tables */
429 /* table 1 has 0-256 */
430 aryfil(temp1, 256, 0);
434 if(j >= 0 && j < 256) {
436 print("yacc bug -- cant have 2 different Ts with same value\n");
437 print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name);
445 warray("yytok1", temp1, c+1);
447 /* table 2 has PRIVATE-PRIVATE+256 */
448 aryfil(temp1, 256, 0);
451 j = tokset[i].value - PRIVATE;
452 if(j >= 0 && j < 256) {
454 print("yacc bug -- cant have 2 different Ts with same value\n");
455 print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name);
463 warray("yytok2", temp1, c+1);
465 /* table 3 has everything else */
466 Bprint(ftable, "static\tconst\tlong yytok3[] =\n{\n");
470 if(j >= 0 && j < 256)
472 if(j >= PRIVATE && j < 256+PRIVATE)
475 Bprint(ftable, "%4d,%4d,", j, i);
478 Bprint(ftable, "\n");
480 Bprint(ftable, "%4d\n};\n", 0);
482 /* copy parser text */
483 while((c=Bgetrune(finput)) != Beof) {
485 if((c = Bgetrune(finput)) != 'A')
486 Bputrune(ftable, '$');
487 else { /* copy actions */
488 faction = Bopen(actname, OREAD);
490 error("cannot reopen action tempfile");
491 while((c=Bgetrune(faction)) != Beof)
495 c = Bgetrune(finput);
504 * copies string q into p, returning next free char ptr
507 chcopy(char* p, char* q)
522 * creates output string for item pointed to by pp
528 static char sarr[ISIZE];
534 q = chcopy(sarr, nontrst[*p-NTBASE].name);
546 q = chcopy(q, symnam(i));
547 if(q > &sarr[ISIZE-30])
548 error("item too big");
551 /* an item calling for a reduction */
555 sprint(q, "%d)", -i);
561 * return a pointer to the name of symbol i
568 cp = (i >= NTBASE)? nontrst[i-NTBASE].name: tokset[i].name;
575 * output the summary on y.output
582 Bprint(foutput, "\n%d/%d terminals, %d/%d nonterminals\n",
583 ntokens, NTERMS, nnonter, NNONTERM);
584 Bprint(foutput, "%d/%d grammar rules, %d/%d states\n",
585 nprod, NPROD, nstate, NSTATES);
586 Bprint(foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n",
588 Bprint(foutput, "%d/%d working sets used\n",
589 (int)(zzcwp-wsets), WSETSIZE);
590 Bprint(foutput, "memory: states,etc. %d/%d, parser %d/%d\n",
591 (int)(zzmemsz-mem0), MEMSIZE, (int)(memp-amem), ACTSIZE);
592 Bprint(foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE);
593 Bprint(foutput, "%d extra closures\n", zzclose - 2*nstate);
594 Bprint(foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp);
595 Bprint(foutput, "%d goto entries\n", zzgoent);
596 Bprint(foutput, "%d entries saved by goto default\n", zzgobest);
598 if(zzsrconf != 0 || zzrrconf != 0) {
599 print("\nconflicts: ");
601 print("%d shift/reduce", zzsrconf);
602 if(zzsrconf && zzrrconf)
605 print("%d reduce/reduce", zzrrconf);
619 * write out error comment -- NEEDS WORK
627 fprint(2, "\n fatal error:");
631 fprint(2, ", %s:%d\n", infile, lineno);
640 * set elements 0 through n-1 to c
643 aryfil(int *v, int n, int c)
652 * set a to the union of a and b
653 * return 1 if b is not a subset of a, 0 otherwise
656 setunion(int *a, int *b)
679 Bprint(foutput, "\tNULL");
681 Bprint(foutput, " { ");
684 Bprint(foutput, "%s ", symnam(j));
685 Bprint(foutput, "}");
690 * compute an array with the beginnings of productions yielding given nonterminals
691 * The array pres points to these lists
692 * the array pyield has the lists: the total size is only NPROD+1
698 static int *pyield[NPROD];
704 fatfl = 0; /* make undefined symbols nonfatal */
707 *pmem++ = prdptr[j]+1;
709 error("nonterminal %s not defined!", nontrst[i].name);
718 if(pmem != &pyield[nprod])
719 error("internal Yacc error: pyield %d", pmem-&pyield[nprod]);
723 * compute an array with the first of nonterminals
728 int *p, **s, i, **t, ch, changes;
730 zzcwp = &wsets[nnonter];
732 aryfil(wsets[i].ws.lset, tbitset, 0);
734 /* initially fill the sets */
735 for(s=pres[i]; s<t; ++s)
736 for(p = *s; (ch = *p) > 0; ++p) {
738 SETBIT(wsets[i].ws.lset, ch);
741 if(!pempty[ch-NTBASE])
746 /* now, reflect transitivity */
752 for(s = pres[i]; s < t; ++s)
753 for(p = *s; (ch = (*p-NTBASE)) >= 0; ++p) {
754 changes |= setunion(wsets[i].ws.lset, wsets[ch].ws.lset);
762 pfirst[i] = flset(&wsets[i].ws);
767 Bprint(foutput, "\n%s: ", nontrst[i].name);
769 Bprint(foutput, " %d\n", pempty[i]);
774 * sorts last state,and sees if it equals earlier ones. returns state number
779 Item *p1, *p2, *k, *l, *q1, *q2;
783 p2 = pstate[nstate+1];
785 return 0; /* null state */
787 for(k = p2-1; k > p1; k--) /* make k the biggest */
788 for(l = k-1; l >= p1; --l)
789 if(l->pitem > k->pitem) {
800 size1 = p2 - p1; /* size of state */
802 for(i = (c>=NTBASE)? ntstates[c-NTBASE]: tstates[c]; i != 0; i = mstates[i]) {
810 for(l = q1; l < q2; l++) {
811 if(l->pitem != k->pitem)
818 pstate[nstate+1] = pstate[nstate]; /* delete last state */
819 /* fix up lookaheads */
822 for(l = q1, k = p1; l < q2; ++l, ++k ) {
826 clset.lset[s] = l->look->lset[s];
827 if(setunion(clset.lset, k->look->lset)) {
829 /* register the new set */
830 l->look = flset( &clset );
837 error("yacc state/nolook error");
838 pstate[nstate+2] = p2;
839 if(nstate+1 >= NSTATES)
840 error("too many states");
842 mstates[nstate] = ntstates[c-NTBASE];
843 ntstates[c-NTBASE] = nstate;
845 mstates[nstate] = tstates[c];
848 tystate[nstate] = MUSTDO;
853 putitem(int *ptr, Lkset *lptr)
857 if(pidebug && foutput != 0)
858 Bprint(foutput, "putitem(%s), state %d\n", writem(ptr), nstate);
859 j = pstate[nstate+1];
862 j->look = flset(lptr);
863 pstate[nstate+1] = ++j;
864 if((int*)j > zzmemsz) {
866 if(zzmemsz >= &mem0[MEMSIZE])
867 error("out of state space");
872 * mark nonterminals which derive the empty string
873 * also, look for nonterminals which don't derive any token strings
881 /* first, use the array pempty to detect productions that can never be reduced */
882 /* set pempty to WHONOWS */
883 aryfil(pempty, nnonter+1, WHOKNOWS);
885 /* now, look at productions, marking nonterminals which derive something */
888 if(pempty[*prdptr[i] - NTBASE])
890 for(p = prdptr[i]+1; *p >= 0; ++p)
891 if(*p >= NTBASE && pempty[*p-NTBASE] == WHOKNOWS)
893 /* production can be derived */
895 pempty[*prdptr[i]-NTBASE] = OK;
900 /* now, look at the nonterminals, to see if they are all OK */
902 /* the added production rises or falls as the start symbol ... */
905 if(pempty[i] != OK) {
907 error("nonterminal %s never derives any token string", nontrst[i].name);
917 /* now, compute the pempty array, to see which nonterminals derive the empty string */
918 /* set pempty to WHOKNOWS */
919 aryfil( pempty, nnonter+1, WHOKNOWS);
921 /* loop as long as we keep finding empty nonterminals */
925 /* not known to be empty */
926 if(pempty[*prdptr[i]-NTBASE] == WHOKNOWS) {
927 for(p = prdptr[i]+1; *p >= NTBASE && pempty[*p-NTBASE] == EMPTY ; ++p)
929 /* we have a nontrivially empty nonterminal */
931 pempty[*prdptr[i]-NTBASE] = EMPTY;
932 /* got one ... try for another */
940 * generate the states
952 /* THIS IS FUNNY from the standpoint of portability
953 * it represents the magic moment when the mem0 array, which has
954 * been holding the productions, starts to hold item pointers, of a
956 * someday, alloc should be used to allocate all this stuff... for now, we
957 * accept that if pointers don't fit in integers, there is a problem...
960 pstate[0] = pstate[1] = (Item*)mem;
961 aryfil(clset.lset, tbitset, 0);
962 putitem(prdptr[0]+1, &clset);
965 pstate[2] = pstate[1];
967 aryfil(amem, ACTSIZE, 0);
969 /* now, the main state generation loop */
973 if(tystate[i] != MUSTDO)
976 aryfil(temp1, nnonter+1, 0);
977 /* take state i, close it, and do gotos */
979 /* generate goto's */
986 if(pstate[i+1]-pstate[i] <= p-wsets)
987 tystate[i] = MUSTLOOKAHEAD;
992 /* this item contributes to the goto */
993 if(c == *(q->pitem)) {
994 putitem(q->pitem+1, &q->ws);
998 state(c); /* register new state */
1000 temp1[c-NTBASE] = state(c);
1002 if(gsdebug && foutput != 0) {
1003 Bprint(foutput, "%d: ", i);
1006 Bprint(foutput, "%s %d, ",
1007 nontrst[j].name, temp1[j]);
1008 Bprint(foutput, "\n");
1010 indgo[i] = apack(&temp1[1], nnonter-1) - 1;
1018 * generate the closure of state i
1026 int c, ch, work, k, *pi, **s, **t;
1030 /* first, copy kernel of state i to wsets */
1033 cwp->pitem = p->pitem;
1034 cwp->flag = 1; /* this item must get closed */
1036 cwp->ws.lset[k] = p->look->lset[k];
1040 /* now, go through the loop, closing each item */
1047 /* dot is before c */
1051 /* only interesting case is where . is before nonterminal */
1055 /* compute the lookahead */
1056 aryfil(clset.lset, tbitset, 0);
1058 /* find items involving c */
1060 if(v->flag == 1 && *(pi=v->pitem) == c) {
1064 while((ch = *++pi) > 0) {
1065 /* terminal symbol */
1067 SETBIT(clset.lset, ch);
1070 /* nonterminal symbol */
1071 setunion(clset.lset, pfirst[ch-NTBASE]->lset);
1072 if(!pempty[ch-NTBASE])
1076 setunion(clset.lset, v->ws.lset);
1080 * now loop over productions derived from c
1081 * c is now nonterminal number
1085 for(s = pres[c]; s < t; ++s) {
1087 * put these items into the closure
1091 /* yes, it is there */
1092 if(v->pitem == *s) {
1095 if(setunion(v->ws.lset, clset.lset))
1100 /* not there; make a new entry */
1101 if(cwp-wsets+1 >= WSETSIZE)
1102 error( "working set overflow");
1107 SETLOOP(k) cwp->ws.lset[k] = clset.lset[k];
1116 /* have computed closure; flags are reset; return */
1119 if(cldebug && foutput != 0) {
1120 Bprint(foutput, "\nState %d, nolook = %d\n", i, nolook);
1123 Bprint(foutput, "flag set!\n");
1125 Bprint(foutput, "\t%s", writem(u->pitem));
1127 Bprint(foutput, "\n");
1133 * decide if the lookahead set pointed to by p is known
1134 * return pointer to a perminent location for the set
1142 for(q = &lkst[nlset]; q-- > lkst;) {
1149 /* we have matched */
1155 if(nlset >= LSETSIZE)
1156 error("too many lookahead sets");
1158 q->lset[j] = p->lset[j];
1173 exits("interrupted");
1177 setup(int argc, char *argv[])
1180 int i, j, fd, lev, ty, ytab, *p;
1181 int vflag, dflag, stem;
1182 char actnm[8], *stemc, *s, dirbuf[128];
1222 error("illegal option: %c", ARGC());
1224 openup(stemc, dflag, vflag, ytab, ytabc);
1225 fout = dflag?fdefine:ftable;
1227 Bprint(ftable, "#define\tYYARG\t1\n\n");
1229 if((fd = mkstemp(ttempname)) >= 0){
1230 tempname = ttempname;
1231 ftemp = Bfdopen(fd, OWRITE);
1233 if((fd = mkstemp(tactname)) >= 0){
1235 faction = Bfdopen(fd, OWRITE);
1237 if(ftemp == 0 || faction == 0)
1238 error("cannot open temp file");
1240 error("no input file");
1242 if(infile[0] != '/' && getwd(dirbuf, sizeof dirbuf)!=nil){
1243 i = strlen(infile)+1+strlen(dirbuf)+1+10;
1246 snprint(s, i, "%s/%s", dirbuf, infile);
1251 finput = Bopen(infile, OREAD);
1253 error("cannot open '%s'", argv[0]);
1257 extval = PRIVATE; /* tokens start in unicode 'private use' */
1259 defin(1, "$accept");
1264 for(t = gettok(); t != MARK && t != ENDFILE;)
1271 if(gettok() != IDENTIFIER)
1272 error("bad %%start construction");
1273 start = chfind(1, tokname);
1278 if(gettok() != TYPENAME)
1279 error("bad syntax in %%type");
1285 if((t=chfind(1, tokname)) < NTBASE) {
1286 j = TYPE(toklev[t]);
1287 if(j != 0 && j != ty)
1288 error("type redeclaration of token %s",
1291 SETTYPE(toklev[t], ty);
1293 j = nontrst[t-NTBASE].value;
1294 if(j != 0 && j != ty)
1295 error("type redeclaration of nonterminal %s",
1296 nontrst[t-NTBASE].name );
1298 nontrst[t-NTBASE].value = ty;
1312 /* copy the union declaration to the output */
1323 /* nonzero means new prec. and assoc. */
1327 /* get identifiers so defined */
1330 /* there is a type defined */
1345 j = chfind(0, tokname);
1347 error("%s defined earlier as nonterminal", tokname);
1349 if(ASSOC(toklev[j]))
1350 error("redeclaration of precedence of %s", tokname);
1351 SETASC(toklev[j], lev);
1352 SETPLEV(toklev[j], i);
1356 error("redeclaration of type of %s", tokname);
1357 SETTYPE(toklev[j],ty);
1361 tokset[j].value = numbval;
1362 if(j < ndefout && j > 3)
1363 error("please define type number of %s earlier",
1380 error("syntax error");
1383 error("unexpected EOF before %%");
1387 Bprint(ftable, "extern int yyerrflag;\n");
1388 Bprint(ftable, "#ifndef YYMAXDEPTH\n");
1389 Bprint(ftable, "#define YYMAXDEPTH 150\n");
1390 Bprint(ftable, "#endif\n" );
1392 Bprint(ftable, "#ifndef YYSTYPE\n");
1393 Bprint(ftable, "#define YYSTYPE int\n");
1394 Bprint(ftable, "#endif\n");
1397 Bprint(ftable, "YYSTYPE yylval;\n");
1398 Bprint(ftable, "YYSTYPE yyval;\n");
1401 Bprint(ftable, "#include \"%s.%s\"\n\n", stemc, FILED);
1402 Bprint(fout, "struct Yyarg {\n");
1403 Bprint(fout, "\tint\tyynerrs;\n");
1404 Bprint(fout, "\tint\tyyerrflag;\n");
1405 Bprint(fout, "\tvoid*\targ;\n");
1406 Bprint(fout, "\tYYSTYPE\tyyval;\n");
1407 Bprint(fout, "\tYYSTYPE\tyylval;\n");
1408 Bprint(fout, "};\n\n");
1412 /* added production */
1415 /* if start is 0, we will overwrite with the lhs of the first rule */
1420 while((t=gettok()) == LCURLY)
1423 error("bad syntax on first rule");
1426 prdptr[0][1] = chfind(1, tokname);
1429 while(t != MARK && t != ENDFILE) {
1430 /* process a rule */
1431 rlines[nprod] = lineno;
1433 *mem++ = *prdptr[nprod-1];
1435 if(t == IDENTCOLON) {
1436 *mem = chfind(1, tokname);
1438 error("token illegal on LHS of grammar rule");
1441 error("illegal rule: missing semicolon or | ?");
1442 /* read rule body */
1446 while(t == IDENTIFIER) {
1447 *mem = chfind(1, tokname);
1449 levprd[nprod] = toklev[*mem];
1454 if(gettok() != IDENTIFIER)
1455 error("illegal %%prec syntax");
1456 j = chfind(2, tokname);
1458 error("nonterminal %s illegal after %%prec",
1459 nontrst[j-NTBASE].name);
1460 levprd[nprod] = toklev[j];
1464 levprd[nprod] |= ACTFLAG;
1465 Bprint(faction, "\ncase %d:", nprod);
1466 cpyact(mem-prdptr[nprod]-1);
1467 Bprint(faction, " break;");
1468 if((t=gettok()) == IDENTIFIER) {
1470 /* action within rule... */
1471 sprint(actnm, "$$%d", nprod);
1473 /* make it a nonterminal */
1474 j = chfind(1, actnm);
1477 * the current rule will become rule number nprod+1
1478 * move the contents down, and make room for the null
1480 for(p = mem; p >= prdptr[nprod]; --p)
1484 /* enter null production for action */
1489 /* update the production information */
1490 levprd[nprod+1] = levprd[nprod] & ~ACTFLAG;
1491 levprd[nprod] = ACTFLAG;
1492 if(++nprod >= NPROD)
1493 error("more than %d rules", NPROD);
1496 /* make the action appear in the original rule */
1499 /* get some more of the rule */
1508 /* check that default action is reasonable */
1509 if(ntypes && !(levprd[nprod]&ACTFLAG) && nontrst[*prdptr[nprod]-NTBASE].value) {
1511 /* no explicit action, LHS has value */
1514 tempty = prdptr[nprod][1];
1516 error("must return a value, since LHS has a type");
1518 if(tempty >= NTBASE)
1519 tempty = nontrst[tempty-NTBASE].value;
1521 tempty = TYPE(toklev[tempty]);
1522 if(tempty != nontrst[*prdptr[nprod]-NTBASE].value)
1523 error("default action causes potential type clash");
1527 error("more than %d rules", NPROD);
1528 prdptr[nprod] = mem;
1532 /* end of all rules */
1537 Bprint(ftable, "\n");
1539 Bprint(ftable, "#line\t%d\t\"%s\"\n", lineno, infile);
1540 while((c=Bgetrune(finput)) != Beof)
1541 Bputrune(ftable, c);
1547 * finish action routine
1554 Bprint(ftable, "#define YYEOFCODE %d\n", 1);
1555 Bprint(ftable, "#define YYERRCODE %d\n", 2);
1559 * define s to be a terminal if t=0
1560 * or a nonterminal if t=1
1563 defin(int nt, char *s)
1571 if(nnonter >= NNONTERM)
1572 error("too many nonterminals, limit %d",NNONTERM);
1573 nontrst[nnonter].name = cstash(s);
1574 return NTBASE + nnonter;
1577 /* must be a token */
1579 if(ntokens >= NTERMS)
1580 error("too many terminals, limit %d", NTERMS);
1581 tokset[ntokens].name = cstash(s);
1583 /* establish value for token */
1584 /* single character literal */
1586 val = chartorune(&rune, &s[1]);
1593 /* escape sequence */
1594 if(s[0] == ' ' && s[1] == '\\') {
1596 /* single character escape sequence */
1598 case 'n': val = '\n'; break;
1599 case 'r': val = '\r'; break;
1600 case 'b': val = '\b'; break;
1601 case 't': val = '\t'; break;
1602 case 'f': val = '\f'; break;
1603 case '\'': val = '\''; break;
1604 case '"': val = '"'; break;
1605 case '\\': val = '\\'; break;
1606 default: error("invalid escape");
1612 if(s[2] >= '0' && s[2] <= '7') {
1618 error("illegal \\nnn construction");
1619 val = 64*s[2] + 8*s[3] + s[4] - 73*'0';
1621 error("'\\000' is illegal");
1624 error("unknown escape");
1629 tokset[ntokens].value = val;
1630 toklev[ntokens] = 0;
1635 * write out the defines (at the end of the declaration section)
1641 char sar[NAMESIZE+10];
1643 for(i=ndefout; i<=ntokens; i++) {
1645 c = tokset[i].name[0];
1646 if(c != ' ' && c != '$') {
1647 Bprint(ftable, "#define %s %d\n",
1648 tokset[i].name, tokset[i].value);
1650 Bprint(fdefine, "#define\t%s\t%d\n",
1651 tokset[i].name, tokset[i].value);
1654 ndefout = ntokens+1;
1655 if(last && fdebug) {
1656 Bprint(fdebug, "static char* yytoknames[] =\n{\n");
1658 if(tokset[i].name) {
1659 chcopy(sar, tokset[i].name);
1660 Bprint(fdebug, "\t\"%s\",\n", sar);
1663 Bprint(fdebug, "\t0,\n");
1665 Bprint(fdebug, "};\n");
1676 if(cnamp >= &cnames[cnamsz])
1677 error("too many characters in id's and literals");
1687 return (i & ~0xffUL) == 0;
1695 int i, base, match, reserve;
1696 static int peekline;
1702 c = Bgetrune(finput);
1703 while(c == ' ' || c == '\n' || c == '\t' || c == '\f') {
1706 c = Bgetrune(finput);
1711 lineno += skipcom();
1723 /* get, and look up, a type name (union member name) */
1725 while((c=Bgetrune(finput)) != '>' && c >= 0 && c != '\n') {
1727 c = runetochar(&tokname[i], &rune);
1732 error("unterminated < ... > clause");
1734 for(i=1; i<=ntypes; i++)
1735 if(!strcmp(typeset[i], tokname)) {
1741 typeset[numbval] = cstash(tokname);
1750 c = Bgetrune(finput);
1751 if(c == '\n' || c <= 0)
1752 error("illegal or missing ' or \"" );
1757 c = Bgetrune(finput);
1762 c = runetochar(&tokname[i], &rune);
1770 switch(c = Bgetrune(finput)) {
1771 case '0': return TERM;
1772 case '<': return LEFT;
1773 case '2': return BINARY;
1774 case '>': return RIGHT;
1776 case '\\': return MARK;
1777 case '=': return PREC;
1778 case '{': return LCURLY;
1779 default: reserve = 1;
1788 base = (c=='0')? 8: 10;
1789 for(c = Bgetrune(finput); isdigit(c); c = Bgetrune(finput))
1790 numbval = numbval*base + (c-'0');
1794 if(islower(c) || isupper(c) || c=='_' || c=='.' || c=='$') {
1796 while(isvalidchar(c) && (islower(c) || isupper(c) || isdigit(c) ||
1797 c == '-' || c=='_' || c=='.' || c=='$')) {
1798 if(reserve && isupper(c))
1801 c = runetochar(&tokname[i], &rune);
1804 c = Bgetrune(finput);
1814 /* find a reserved word */
1816 for(c=0; resrv[c].name; c++)
1817 if(strcmp(tokname, resrv[c].name) == 0)
1818 return resrv[c].value;
1819 error("invalid escape, or illegal reserved word: %s", tokname);
1822 /* look ahead to distinguish IDENTIFIER from IDENTCOLON */
1823 c = Bgetrune(finput);
1824 while(c == ' ' || c == '\t'|| c == '\n' || c == '\f' || c == '/') {
1827 /* look for comments */
1829 peekline += skipcom();
1830 c = Bgetrune(finput);
1839 * determine the type of a symbol
1847 v = nontrst[t-NTBASE].value;
1849 v = TYPE(toklev[t]);
1851 error("must specify type for %s", (t>=NTBASE)?
1852 nontrst[t-NTBASE].name: tokset[t].name);
1857 chfind(int t, char *s)
1864 if(!strcmp(s, tokset[i].name))
1867 if(!strcmp(s, nontrst[i].name))
1870 /* cannot find name */
1872 error("%s should have been defined earlier", s);
1877 * copy the union declaration to the output, and the define file if present
1885 Bprint(ftable, "\n");
1887 Bprint(ftable, "#line\t%d\t\"%s\"\n", lineno, infile);
1888 Bprint(ftable, "typedef union ");
1890 Bprint(fdefine, "\ntypedef union ");
1894 if((c=Bgetrune(finput)) == Beof)
1895 error("EOF encountered while processing %%union");
1896 Bputrune(ftable, c);
1898 Bputrune(fdefine, c);
1909 /* we are finished copying */
1911 Bprint(ftable, " YYSTYPE;\n");
1913 Bprint(fdefine, "\tYYSTYPE;\n");
1915 Bprint(fdefine, "extern\tYYSTYPE\tyylval;\n");
1924 * copies code between \{ and \}
1931 c = Bgetrune(finput);
1933 c = Bgetrune(finput);
1936 Bprint(ftable, "\n");
1938 Bprint(ftable, "#line\t%d\t\"%s\"\n", lineno, infile);
1941 if((c=Bgetrune(finput)) == '}')
1943 Bputc(ftable, '\\');
1946 if((c=Bgetrune(finput)) == '}')
1950 Bputrune(ftable, c);
1953 c = Bgetrune(finput);
1955 error("eof before %%}");
1959 * skip over comments
1960 * skipcom is called after reading a '/'
1968 /* i is the number of lines skipped */
1970 if(Bgetrune(finput) != '*')
1971 error("illegal comment");
1972 c = Bgetrune(finput);
1975 if((c=Bgetrune(finput)) == '/')
1979 c = Bgetrune(finput);
1981 error("EOF inside comment");
1986 * copy C action to the next ; or closing }
1992 int brac, match, j, s, fnd, tok;
1994 Bprint(faction, "\n");
1996 Bprint(faction, "#line\t%d\t\"%s\"\n", lineno, infile);
2000 c = Bgetrune(finput);
2005 Bputrune(faction, c);
2017 c = Bgetrune(finput);
2019 /* type description */
2022 if(gettok() != TYPENAME)
2023 error("bad syntax on $<ident> clause");
2025 c = Bgetrune(finput);
2028 Bprint(faction, "yyval");
2030 /* put out the proper tag... */
2033 tok = fdtype(*prdptr[nprod]);
2034 Bprint(faction, ".%s", typeset[tok]);
2040 c = Bgetrune(finput);
2042 if(isvalidchar(c) && isdigit(c)) {
2046 c = Bgetrune(finput);
2051 error("Illegal use of $%d", j+offset);
2054 Bprint(faction, "yypt[-%d].yyv", -j);
2056 /* put out the proper tag */
2058 if(j+offset <= 0 && tok < 0)
2059 error("must specify type of $%d", j+offset);
2061 tok = fdtype(prdptr[nprod][j+offset]);
2062 Bprint(faction, ".%s", typeset[tok]);
2066 if(isvalidchar(c) && (isupper(c) || islower(c) || c == '_' || c == '.')) {
2067 int tok; /* tok used oustide for type info */
2069 /* look for $name */
2071 if(gettok() != IDENTIFIER)
2072 error("$ must be followed by an identifier");
2073 tok = chfind(2, tokname);
2074 if((c = Bgetrune(finput)) != '#') {
2078 if(gettok() != NUMBER) {
2079 error("# must be followed by number");
2083 for(j=1; j<=offset; ++j)
2084 if(tok == prdptr[nprod][j]) {
2090 error("$name or $name#number not found");
2092 Bputc(faction, '$');
2094 Bputc(faction, '-');
2101 Bputrune(faction, c);
2105 /* look for comments */
2106 Bputrune(faction, c);
2107 c = Bgetrune(finput);
2111 /* it really is a comment */
2112 Bputrune(faction, c);
2113 c = Bgetrune(finput);
2116 Bputrune(faction, c);
2117 if((c=Bgetrune(finput)) == '/')
2120 Bputrune(faction, c);
2123 c = Bgetrune(finput);
2125 error("EOF inside comment");
2128 /* character constant */
2133 /* character string */
2137 Bputrune(faction, c);
2138 while((c = Bgetrune(finput)) >= 0) {
2140 Bputrune(faction, c);
2141 c = Bgetrune(finput);
2148 error("newline in string or char. const.");
2150 Bputrune(faction, c);
2152 error("EOF in string or character constant");
2155 error("action does not terminate");
2163 Bputrune(faction, c);
2168 openup(char *stem, int dflag, int vflag, int ytab, char *ytabc)
2173 sprint(buf, "%s.%s", stem, FILEU);
2174 foutput = Bopen(buf, OWRITE);
2176 error("cannot open %s", buf);
2179 sprint(buf, "%s.%s", stem, FILEDEBUG);
2180 if((fdebug = Bopen(buf, OWRITE)) == 0)
2181 error("can't open %s", buf);
2184 sprint(buf, "%s.%s", stem, FILED);
2185 fdefine = Bopen(buf, OWRITE);
2187 error("can't create %s", buf);
2190 sprint(buf, "%s.%s", stem, OFILE);
2193 ftable = Bopen(buf, OWRITE);
2195 error("cannot open table file %s", buf);
2199 * print the output for the states
2207 Bprint(ftable, "static\tconst\tshort yyexca[] =\n{");
2209 Bprint(fdebug, "static\tconst\tchar* yystates[] =\n{\n");
2211 /* output the stuff for state i */
2213 nolook = tystate[i]!=MUSTLOOKAHEAD;
2216 /* output actions */
2218 aryfil(temp1, ntokens+nnonter+1, 0);
2221 if(c > 1 && c < NTBASE && temp1[c] == 0) {
2223 if(c == *(v->pitem))
2224 putitem(v->pitem+1, (Lkset*)0);
2225 temp1[c] = state(c);
2227 if(c > NTBASE && temp1[(c -= NTBASE) + ntokens] == 0)
2228 temp1[c+ntokens] = amem[indgo[i]+c];
2231 temp1[1] = ACCEPTCODE;
2233 /* now, we have the shifts; look at the reductions */
2242 if(BIT(u->ws.lset, k)) {
2246 if(temp1[k] < 0) { /* reduce/reduce conflict */
2249 "\n%d: reduce/reduce conflict"
2250 " (red'ns %d and %d ) on %s",
2251 i, -temp1[k], lastred,
2253 if(-temp1[k] > lastred)
2254 temp1[k] = -lastred;
2257 /* potential shift/reduce conflict */
2258 precftn( lastred, k, i );
2266 Bprint(fdebug, "};\n");
2267 Bprint(ftable, "};\n");
2268 Bprint(ftable, "#define YYNPROD %d\n", nprod);
2269 Bprint(ftable, "#define YYPRIVATE %d\n", PRIVATE);
2271 Bprint(ftable, "#define yydebug %s\n", yydebug);
2275 * pack state i from temp1 into amem
2278 apack(int *p, int n)
2280 int *pp, *qq, *rr, off, *q, *r;
2282 /* we don't need to worry about checking because
2283 * we will only look at entries known to be there...
2284 * eliminate leading and trailing 0's
2288 for(pp = p, off = 0; *pp == 0 && pp <= q; ++pp, --off)
2295 /* now, find a place for the elements from p to q, inclusive */
2296 r = &amem[ACTSIZE-1];
2297 for(rr = amem; rr <= r; rr++, off++) {
2298 for(qq = rr, pp = p; pp <= q; pp++, qq++)
2300 if(*pp != *qq && *qq != 0)
2303 /* we have found an acceptable k */
2304 if(pkdebug && foutput != 0)
2305 Bprint(foutput, "off = %d, k = %d\n", off, (int)(rr-amem));
2306 for(qq = rr, pp = p; pp <= q; pp++, qq++)
2309 error("action table overflow");
2314 if(pkdebug && foutput != 0)
2315 for(pp = amem; pp <= memp; pp += 10) {
2316 Bprint(foutput, "\t");
2317 for(qq = pp; qq <= pp+9; qq++)
2318 Bprint(foutput, "%d ", *qq);
2319 Bprint(foutput, "\n");
2324 error("no space in action table");
2329 * output the gotos for the nontermninals
2334 int i, j, k, best, count, cbest, times;
2336 /* mark begining of gotos */
2337 Bprint(ftemp, "$\n");
2338 for(i = 1; i <= nnonter; i++) {
2341 /* find the best one to make default */
2345 /* is j the most frequent */
2346 for(j = 0; j <= nstate; j++) {
2349 if(tystate[j] == best)
2352 /* is tystate[j] the most frequent */
2355 for(k = j; k <= nstate; k++)
2356 if(tystate[k] == cbest)
2364 /* best is now the default entry */
2365 zzgobest += times-1;
2366 for(j = 0; j <= nstate; j++)
2367 if(tystate[j] != 0 && tystate[j] != best) {
2368 Bprint(ftemp, "%d,%d,", j, tystate[j]);
2372 /* now, the default */
2376 Bprint(ftemp, "%d\n", best);
2381 * output the gotos for nonterminal c
2390 /* first, find nonterminals with gotos on c */
2391 aryfil(temp1, nnonter+1, 0);
2398 /* cc is a nonterminal */
2399 if((cc=prdptr[i][1]-NTBASE) >= 0)
2400 /* cc has a goto on c */
2401 if(temp1[cc] != 0) {
2403 /* thus, the left side of production i does too */
2404 cc = *prdptr[i]-NTBASE;
2405 if(temp1[cc] == 0) {
2412 /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
2413 if(g2debug && foutput != 0) {
2414 Bprint(foutput, "%s: gotos on ", nontrst[c].name);
2417 Bprint(foutput, "%s ", nontrst[i].name);
2418 Bprint(foutput, "\n");
2421 /* now, go through and put gotos into tystate */
2422 aryfil(tystate, nstate, 0);
2425 if((cc = *p->pitem) >= NTBASE)
2426 /* goto on c is possible */
2427 if(temp1[cc-NTBASE]) {
2428 tystate[i] = amem[indgo[i]+c];
2434 * decide a shift/reduce conflict by precedence.
2435 * r is a rule number, t a token number
2436 * the conflict is in state s
2437 * temp1[t] is changed to reflect the action
2440 precftn(int r, int t, int s)
2446 if(PLEVEL(lt) == 0 || PLEVEL(lp) == 0) {
2451 "\n%d: shift/reduce conflict (shift %d(%d), red'n %d(%d)) on %s",
2452 s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), symnam(t));
2456 if(PLEVEL(lt) == PLEVEL(lp))
2459 if(PLEVEL(lt) > PLEVEL(lp))
2460 action = RASC; /* shift */
2462 action = LASC; /* reduce */
2464 case BASC: /* error action */
2467 case LASC: /* reduce */
2475 * temp1 has the actions, lastred the default
2480 int p, p0, p1, ntimes, tred, count, j, flag;
2482 /* find the best choice for lastred */
2488 if(temp1[j]+lastred == 0)
2490 /* count the number of appearances of temp1[j] */
2493 levprd[tred] |= REDFLAG;
2495 if(temp1[p]+tred == 0)
2497 if(count > ntimes) {
2504 * for error recovery, arrange that, if there is a shift on the
2505 * error recovery token, `error', that the default be the error action
2510 /* clear out entries in temp1 which equal lastred */
2512 if(temp1[p]+lastred == 0)
2516 defact[i] = lastred;
2519 if((p1=temp1[p0]) != 0) {
2524 if(p1 == ACCEPTCODE) {
2532 Bprint(ftable, "-1, %d,\n", i);
2533 Bprint(ftable, "\t%d, %d,\n", p0, p1);
2537 Bprint(ftemp, "%d,%d,", p0, p1);
2542 Bprint(ftable, "\t-2, %d,\n", lastred);
2544 Bprint(ftemp, "\n");
2559 Bprint(fdebug, " 0, /*%d*/\n", i);
2561 Bprint(fdebug, " \"");
2563 Bprint(fdebug, "%s\\n", writem(pp->pitem));
2564 if(tystate[i] == MUSTLOOKAHEAD)
2565 WSLOOP(wsets + (pstate[i+1] - pstate[i]), u)
2567 Bprint(fdebug, "%s\\n", writem(u->pitem));
2568 Bprint(fdebug, "\", /*%d*/\n", i);
2573 Bprint(foutput, "\nstate %d\n", i);
2575 Bprint(foutput, "\t%s\n", writem(pp->pitem));
2576 if(tystate[i] == MUSTLOOKAHEAD)
2577 /* print out empty productions in closure */
2578 WSLOOP(wsets+(pstate[i+1]-pstate[i]), u)
2580 Bprint(foutput, "\t%s\n", writem(u->pitem));
2582 /* check for state equal to another */
2584 if((j1=temp1[j0]) != 0) {
2585 Bprint(foutput, "\n\t%s ", symnam(j0));
2586 /* shift, error, or accept */
2588 if(j1 == ACCEPTCODE)
2589 Bprint(foutput, "accept");
2592 Bprint(foutput, "error");
2594 Bprint(foutput, "shift %d", j1);
2596 Bprint(foutput, "reduce %d (src line %d)", -j1, rlines[-j1]);
2599 /* output the final production */
2601 Bprint(foutput, "\n\t. reduce %d (src line %d)\n\n",
2602 lastred, rlines[lastred]);
2604 Bprint(foutput, "\n\t. error\n\n");
2606 /* now, output nonterminal actions */
2608 for(j0 = 1; j0 <= nnonter; j0++) {
2611 Bprint(foutput, "\t%s goto %d\n", symnam(j0+NTBASE), temp1[j1]);
2616 warray(char *s, int *v, int n)
2620 Bprint(ftable, "static\tconst\tshort %s[] =\n{", s);
2623 Bprint(ftable, "\n");
2624 Bprint(ftable, "%4d", v[i]);
2627 Bprint(ftable, "\n};\n");
2630 Bprint(ftable, ",");
2635 * in order to free up the mem and amem arrays for the optimizer,
2636 * and still be able to output yyr1, etc., after the sizes of
2637 * the action array is known, we hide the nonterminals
2638 * derived by productions in levprd.
2649 if(!(levprd[i] & REDFLAG)) {
2652 Bprint(foutput, "Rule not reduced: %s\n", writem(prdptr[i]));
2654 levprd[i] = *prdptr[i] - NTBASE;
2657 print("%d rules never reduced\n", j);
2663 int i, *p, j, k, *q;
2665 /* read the arrays from tempfile and set parameters */
2666 finput = Bopen(tempname, OREAD);
2668 error("optimizer cannot open tempfile");
2679 temp1[nstate] = pmem - mem0;
2685 error("bad tempfile %s", tempname);
2691 temp1[nstate] = yypgo[0] = pmem - mem0;
2696 yypgo[nnonter] = pmem-mem0;
2702 error("bad tempfile");
2707 yypgo[nnonter--] = pmem - mem0;
2708 for(i = 0; i < nstate; i++) {
2711 q = mem0 + temp1[i+1];
2712 for(p = mem0 + temp1[i]; p < q ; p += 2) {
2718 /* nontrivial situation */
2720 /* j is now the range */
2721 /* j -= k; *//* call scj */
2725 tystate[i] = (temp1[i+1]-temp1[i]) + 2*j;
2730 /* initialize ggreed table */
2731 for(i = 1; i <= nnonter; i++) {
2735 /* minimum entry index is always 0 */
2736 q = mem0 + yypgo[i+1] - 1;
2737 for(p = mem0+yypgo[i]; p < q ; p += 2) {
2742 ggreed[i] = ggreed[i] + 2*j;
2747 /* now, prepare to put the shift actions into the amem array */
2748 for(i = 0; i < ACTSIZE; i++)
2751 for(i = 0; i < nstate; i++) {
2752 if(tystate[i] == 0 && adb > 1)
2753 Bprint(ftable, "State %d: null\n", i);
2756 while((i = nxti()) != NOMORE)
2762 /* print amem array */
2764 for(p = amem; p <= maxa; p += 10) {
2765 Bprint(ftable, "%4d ", (int)(p-amem));
2766 for(i = 0; i < 10; ++i)
2767 Bprint(ftable, "%4d ", p[i]);
2768 Bprint(ftable, "\n");
2771 /* write out the output appropriate to the language */
2780 int *p, *r, *s, *q1, *q2;
2782 /* enter gotos on nonterminal i into array amem */
2785 q2 = mem0+ yypgo[i+1] - 1;
2786 q1 = mem0 + yypgo[i];
2788 /* now, find amem place for it */
2789 for(p = amem; p < &amem[ACTSIZE]; p++) {
2792 for(r = q1; r < q2; r += 2) {
2797 if((maxa = s) > &amem[ACTSIZE])
2798 error("a array overflow");
2800 /* we have found amem spot */
2803 if((maxa = p) > &amem[ACTSIZE])
2804 error("a array overflow");
2805 for(r = q1; r < q2; r += 2) {
2811 Bprint(ftable, "Nonterminal %d, entry at %d\n", i, pgo[i]);
2816 error("cannot place goto %d\n", i);
2822 int *r, *s, n, flag, j, *q1, *q2;
2826 /* enter state i into the amem array */
2827 q2 = mem0+temp1[i+1];
2829 /* find an acceptable place */
2830 for(n = -maxoff; n < ACTSIZE; n++) {
2832 for(r = q1; r < q2; r += 2) {
2843 /* check that the position equals another only if the states are identical */
2844 for(j=0; j<nstate; j++) {
2847 /* we have some disagreement */
2850 if(temp1[j+1]+temp1[i] == temp1[j]+temp1[i+1]) {
2852 /* states are equal */
2856 "State %d: entry at %d equals state %d\n",
2861 /* we have some disagreement */
2866 for(r = q1; r < q2; r += 2) {
2867 if((s = *r+n+amem) >= &amem[ACTSIZE])
2868 error("out of space in optimizer a array");
2871 if(*s != 0 && *s != r[1])
2872 error("clobber of a array, pos'n %d, by %d", s-amem, r[1]);
2877 Bprint(ftable, "State %d: entry at %d\n", i, indgo[i]);
2881 error("Error; failure to place state %d\n", i);
2894 for(i = 1; i <= nnonter; i++)
2895 if(ggreed[i] >= max) {
2899 for(i = 0; i < nstate; ++i)
2900 if(tystate[i] >= max) {
2905 Bprint(ftable, "nxti = %d, max = %d\n", maxi, max);
2923 for(p = maxa; p >= amem; p--)
2927 Bprint(foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
2928 (int)(pmem-mem0+1), MEMSIZE, (int)(maxa-amem+1), ACTSIZE);
2929 Bprint(foutput, "%d table entries, %d zero\n", (int)(maxa-amem+1), i);
2930 Bprint(foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff);
2934 * this version is for C
2935 * write out the optimized parser
2940 Bprint(ftable, "#define\tYYLAST\t%d\n", (int)(maxa-amem+1));
2941 arout("yyact", amem, (maxa-amem)+1);
2942 arout("yypact", indgo, nstate);
2943 arout("yypgo", pgo, nnonter+1);
2947 arout(char *s, int *v, int n)
2951 Bprint(ftable, "static\tconst\tshort %s[] =\n{", s);
2952 for(i = 0; i < n;) {
2954 Bprint(ftable, "\n");
2955 Bprint(ftable, "%4d", v[i]);
2958 Bprint(ftable, "\n};\n");
2960 Bprint(ftable, ",");
2965 * read and convert an integer from the standard input
2966 * return the terminating character
2967 * blanks, tabs, and newlines are ignored
2976 while((c=Bgetrune(finput)) != Beof) {
2977 if(isvalidchar(c) && isdigit(c)) {
2978 val = val*10 + c-'0';
2990 if(pmem >= &mem0[MEMSIZE])
2991 error("out of space");