yacc.c - 9base - revived minimalist port of Plan 9 userland to Unix
(HTM) git clone git://git.suckless.org/9base
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
yacc.c (58914B)
---
1 #include <u.h>
2 #include <libc.h>
3 #include <bio.h>
4 #include <ctype.h>
5
6 #define Bungetrune Bungetc /* ok for now. */
7
8 /*
9 * all these are 32 bit
10 */
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)
15
16 char *PARSER = "#9/yacc/yaccpar";
17 char *PARSERS = "#9/yacc/yaccpars";
18
19 #define TEMPNAME "y.tmp.XXXXXX"
20 #define ACTNAME "y.acts.XXXXXX"
21 #define OFILE "tab.c"
22 #define FILEU "output"
23 #define FILED "tab.h"
24 #define FILEDEBUG "debug"
25
26 enum
27 {
28 /*
29 * the following are adjustable
30 * according to memory size
31 */
32 ACTSIZE = 40000,
33 MEMSIZE = 40000,
34 NSTATES = 2000,
35 NTERMS = 511,
36 NPROD = 1600,
37 NNONTERM = 600,
38 TEMPSIZE = 2000,
39 CNAMSZ = 10000,
40 LSETSIZE = 2400,
41 WSETSIZE = 350,
42
43 NAMESIZE = 50,
44 NTYPES = 63,
45 ISIZE = 400,
46
47 PRIVATE = 0xE000, /* unicode private use */
48
49 /* relationships which must hold:
50 TBITSET ints must hold NTERMS+1 bits...
51 WSETSIZE >= NNONTERM
52 LSETSIZE >= NNONTERM
53 TEMPSIZE >= NTERMS + NNONTERM + 1
54 TEMPSIZE >= NSTATES
55 */
56
57 NTBASE = 010000,
58 ERRCODE = 8190,
59 ACCEPTCODE = 8191,
60
61 NOASC = 0, /* no assoc. */
62 LASC = 1, /* left assoc. */
63 RASC = 2, /* right assoc. */
64 BASC = 3, /* binary assoc. */
65
66 /* flags for state generation */
67
68 DONE = 0,
69 MUSTDO = 1,
70 MUSTLOOKAHEAD = 2,
71
72 /* flags for a rule having an action, and being reduced */
73
74 ACTFLAG = 04,
75 REDFLAG = 010,
76
77 /* output parser flags */
78 YYFLAG1 = -1000,
79
80 /* parse tokens */
81 IDENTIFIER = PRIVATE,
82 MARK,
83 TERM,
84 LEFT,
85 RIGHT,
86 BINARY,
87 PREC,
88 LCURLY,
89 IDENTCOLON,
90 NUMBER,
91 START,
92 TYPEDEF,
93 TYPENAME,
94 UNION,
95
96 ENDFILE = 0,
97
98 EMPTY = 1,
99 WHOKNOWS = 0,
100 OK = 1,
101 NOMORE = -1000
102 };
103
104 /* macros for getting associativity and precedence levels */
105
106 #define ASSOC(i) ((i)&03)
107 #define PLEVEL(i) (((i)>>4)&077)
108 #define TYPE(i) (((i)>>10)&077)
109
110 /* macros for setting associativity and precedence levels */
111
112 #define SETASC(i,j) i |= j
113 #define SETPLEV(i,j) i |= (j<<4)
114 #define SETTYPE(i,j) i |= (j<<10)
115
116 /* looping macros */
117
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++)
126
127 /* command to clobber tempfiles after use */
128
129 #define ZAPFILE(x) if(x) remove(x)
130
131 /* I/O descriptors */
132
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 */
140
141 /* communication variables between various I/O routines */
142
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 */
146
147 /* structure declarations */
148
149 typedef
150 struct
151 {
152 int lset[TBITSET];
153 } Lkset;
154
155 typedef
156 struct
157 {
158 int* pitem;
159 Lkset* look;
160 } Item;
161
162 typedef
163 struct
164 {
165 char* name;
166 int value;
167 } Symb;
168
169 typedef
170 struct
171 {
172 int* pitem;
173 int flag;
174 Lkset ws;
175 } Wset;
176
177 /* storage of names */
178
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 */
183 char* tempname;
184 char* actname;
185 char ttempname[] = TEMPNAME;
186 char tactname[] = ACTNAME;
187 char* parser;
188 char* yydebug;
189 int yyarg;
190 int yyline = 1;
191
192 /* storage of types */
193 int ntypes; /* number of types defined */
194 char* typeset[NTYPES]; /* pointers to type tags */
195
196 /* token information */
197
198 int ntokens = 0 ; /* number of tokens */
199 Symb tokset[NTERMS];
200 int toklev[NTERMS]; /* vector with the precedence of the terminals */
201
202 /* nonterminal information */
203
204 int nnonter = -1; /* the number of nonterminals */
205 Symb nontrst[NNONTERM];
206 int start; /* start symbol */
207
208 /* assigned token type values */
209 int extval = 0;
210
211 char* ytabc = OFILE; /* name of y.tab.c */
212
213 /* grammar rule information */
214
215 int mem0[MEMSIZE] ; /* production storage */
216 int* mem = mem0;
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 */
221
222 /* state information */
223
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 */
232
233 /* lookahead set information */
234
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 */
241
242 /* working set information */
243
244 Wset wsets[WSETSIZE];
245 Wset* cwp;
246
247 /* storage for action table */
248
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 */
252
253 /* temporary vector, indexable by states, terms, or ntokens */
254
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 */
259
260 /* statistics collection variables */
261
262 int zzgoent;
263 int zzgobest;
264 int zzacent;
265 int zzexcp;
266 int zzclose;
267 int zzrrconf;
268 int zzsrconf;
269
270 int* ggreed = lkst[0].lset;
271 int* pgo = wsets[0].ws.lset;
272 int* yypgo = &nontrst[0].value;
273
274 int maxspr = 0; /* maximum spread of any entry */
275 int maxoff = 0; /* maximum offset into a array */
276 int* pmem = mem0;
277 int* maxa;
278 int nxdb = 0;
279 int adb = 0;
280
281
282 /* storage for information about the nonterminals */
283
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 */
287
288 /* random stuff picked out from between functions */
289
290 int indebug = 0;
291 Wset* zzcwp = wsets;
292 int zzgoent = 0;
293 int zzgobest = 0;
294 int zzacent = 0;
295 int zzexcp = 0;
296 int zzclose = 0;
297 int zzsrconf = 0;
298 int* zzmemsz = mem0;
299 int zzrrconf = 0;
300 int pidebug = 0; /* debugging flag for putitem */
301 int gsdebug = 0;
302 int cldebug = 0; /* debugging flag for closure */
303 int pkdebug = 0;
304 int g2debug = 0;
305
306 struct
307 {
308 char* name;
309 long value;
310 } resrv[] =
311 {
312 "binary", BINARY,
313 "left", LEFT,
314 "nonassoc", BINARY,
315 "prec", PREC,
316 "right", RIGHT,
317 "start", START,
318 "term", TERM,
319 "token", TERM,
320 "type", TYPEDEF,
321 "union", UNION,
322 0,
323 };
324
325 /* define functions */
326
327 void main(int, char**);
328 void others(void);
329 char* chcopy(char*, char*);
330 char* writem(int*);
331 char* symnam(int);
332 void summary(void);
333 void error(char*, ...);
334 void aryfil(int*, int, int);
335 int setunion(int*, int*);
336 void prlook(Lkset*);
337 void cpres(void);
338 void cpfir(void);
339 int state(int);
340 void putitem(int*, Lkset*);
341 void cempty(void);
342 void stagen(void);
343 void closure(int);
344 Lkset* flset(Lkset*);
345 void cleantmp(void);
346 void intr(void);
347 void setup(int, char**);
348 void finact(void);
349 int defin(int, char*);
350 void defout(int);
351 char* cstash(char*);
352 long gettok(void);
353 int fdtype(int);
354 int chfind(int, char*);
355 void cpyunion(void);
356 void cpycode(void);
357 int skipcom(void);
358 void cpyact(int);
359 void openup(char*, int, int, int, char*);
360 void output(void);
361 int apack(int*, int);
362 void go2out(void);
363 void go2gen(int);
364 void precftn(int, int, int);
365 void wract(int);
366 void wrstate(int);
367 void warray(char*, int*, int);
368 void hideprod(void);
369 void callopt(void);
370 void gin(int);
371 void stin(int);
372 int nxti(void);
373 void osummary(void);
374 void aoutput(void);
375 void arout(char*, int*, int);
376 int gtnm(void);
377
378 void
379 main(int argc, char *argv[])
380 {
381 PARSER = unsharp(PARSER);
382 PARSERS = unsharp(PARSERS);
383 parser = PARSER;
384
385 setup(argc, argv); /* initialize and read productions */
386 tbitset = NWORDS(ntokens);
387 cpres(); /* make table of which productions yield a given nonterminal */
388 cempty(); /* make a table of which nonterminals can match the empty string */
389 cpfir(); /* make a table of firsts of nonterminals */
390 stagen(); /* generate the states */
391 output(); /* write the states and the tables */
392 go2out();
393 hideprod();
394 summary();
395 callopt();
396 others();
397 exits(0);
398 }
399
400 /*
401 * put out other arrays, copy the parsers
402 */
403 void
404 others(void)
405 {
406 int c, i, j;
407
408 finput = Bopen(parser, OREAD);
409 if(finput == 0)
410 error("cannot open parser %s: %r", parser);
411 warray("yyr1", levprd, nprod);
412 aryfil(temp1, nprod, 0);
413 PLOOP(1, i)
414 temp1[i] = prdptr[i+1]-prdptr[i]-2;
415 warray("yyr2", temp1, nprod);
416
417 aryfil(temp1, nstate, -1000);
418 TLOOP(i)
419 for(j=tstates[i]; j!=0; j=mstates[j])
420 temp1[j] = i;
421 NTLOOP(i)
422 for(j=ntstates[i]; j!=0; j=mstates[j])
423 temp1[j] = -i;
424 warray("yychk", temp1, nstate);
425 warray("yydef", defact, nstate);
426
427 /* put out token translation tables */
428 /* table 1 has 0-256 */
429 aryfil(temp1, 256, 0);
430 c = 0;
431 TLOOP(i) {
432 j = tokset[i].value;
433 if(j >= 0 && j < 256) {
434 if(temp1[j]) {
435 print("yacc bug -- cant have 2 different Ts with same value\n");
436 print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name);
437 nerrors++;
438 }
439 temp1[j] = i;
440 if(j > c)
441 c = j;
442 }
443 }
444 warray("yytok1", temp1, c+1);
445
446 /* table 2 has PRIVATE-PRIVATE+256 */
447 aryfil(temp1, 256, 0);
448 c = 0;
449 TLOOP(i) {
450 j = tokset[i].value - PRIVATE;
451 if(j >= 0 && j < 256) {
452 if(temp1[j]) {
453 print("yacc bug -- cant have 2 different Ts with same value\n");
454 print(" %s and %s\n", tokset[i].name, tokset[temp1[j]].name);
455 nerrors++;
456 }
457 temp1[j] = i;
458 if(j > c)
459 c = j;
460 }
461 }
462 warray("yytok2", temp1, c+1);
463
464 /* table 3 has everything else */
465 Bprint(ftable, "static\tconst\tlong yytok3[] =\n{\n");
466 c = 0;
467 TLOOP(i) {
468 j = tokset[i].value;
469 if(j >= 0 && j < 256)
470 continue;
471 if(j >= PRIVATE && j < 256+PRIVATE)
472 continue;
473
474 Bprint(ftable, "%4d,%4d,", j, i);
475 c++;
476 if(c%5 == 0)
477 Bprint(ftable, "\n");
478 }
479 Bprint(ftable, "%4d\n};\n", 0);
480
481 /* copy parser text */
482 while((c=Bgetrune(finput)) != Beof) {
483 if(c == '$') {
484 if((c = Bgetrune(finput)) != 'A')
485 Bputrune(ftable, '$');
486 else { /* copy actions */
487 faction = Bopen(actname, OREAD);
488 if(faction == 0)
489 error("cannot reopen action tempfile");
490 while((c=Bgetrune(faction)) != Beof)
491 Bputrune(ftable, c);
492 Bterm(faction);
493 ZAPFILE(actname);
494 c = Bgetrune(finput);
495 }
496 }
497 Bputrune(ftable, c);
498 }
499 Bterm(ftable);
500 }
501
502 /*
503 * copies string q into p, returning next free char ptr
504 */
505 char*
506 chcopy(char* p, char* q)
507 {
508 int c;
509
510 while(c = *q) {
511 if(c == '"')
512 *p++ = '\\';
513 *p++ = c;
514 q++;
515 }
516 *p = 0;
517 return p;
518 }
519
520 /*
521 * creates output string for item pointed to by pp
522 */
523 char*
524 writem(int *pp)
525 {
526 int i,*p;
527 static char sarr[ISIZE];
528 char* q;
529
530 for(p=pp; *p>0; p++)
531 ;
532 p = prdptr[-*p];
533 q = chcopy(sarr, nontrst[*p-NTBASE].name);
534 q = chcopy(q, ": ");
535 for(;;) {
536 *q = ' ';
537 p++;
538 if(p == pp)
539 *q = '.';
540 q++;
541 *q = '\0';
542 i = *p;
543 if(i <= 0)
544 break;
545 q = chcopy(q, symnam(i));
546 if(q > &sarr[ISIZE-30])
547 error("item too big");
548 }
549
550 /* an item calling for a reduction */
551 i = *pp;
552 if(i < 0 ) {
553 q = chcopy(q, " (");
554 sprint(q, "%d)", -i);
555 }
556 return sarr;
557 }
558
559 /*
560 * return a pointer to the name of symbol i
561 */
562 char*
563 symnam(int i)
564 {
565 char* cp;
566
567 cp = (i >= NTBASE)? nontrst[i-NTBASE].name: tokset[i].name;
568 if(*cp == ' ')
569 cp++;
570 return cp;
571 }
572
573 /*
574 * output the summary on y.output
575 */
576 void
577 summary(void)
578 {
579
580 if(foutput != 0) {
581 Bprint(foutput, "\n%d/%d terminals, %d/%d nonterminals\n",
582 ntokens, NTERMS, nnonter, NNONTERM);
583 Bprint(foutput, "%d/%d grammar rules, %d/%d states\n",
584 nprod, NPROD, nstate, NSTATES);
585 Bprint(foutput, "%d shift/reduce, %d reduce/reduce conflicts reported\n",
586 zzsrconf, zzrrconf);
587 Bprint(foutput, "%d/%d working sets used\n",
588 (int)(zzcwp-wsets), WSETSIZE);
589 Bprint(foutput, "memory: states,etc. %d/%d, parser %d/%d\n",
590 (int)(zzmemsz-mem0), MEMSIZE, (int)(memp-amem), ACTSIZE);
591 Bprint(foutput, "%d/%d distinct lookahead sets\n", nlset, LSETSIZE);
592 Bprint(foutput, "%d extra closures\n", zzclose - 2*nstate);
593 Bprint(foutput, "%d shift entries, %d exceptions\n", zzacent, zzexcp);
594 Bprint(foutput, "%d goto entries\n", zzgoent);
595 Bprint(foutput, "%d entries saved by goto default\n", zzgobest);
596 }
597 if(zzsrconf != 0 || zzrrconf != 0) {
598 print("\nconflicts: ");
599 if(zzsrconf)
600 print("%d shift/reduce", zzsrconf);
601 if(zzsrconf && zzrrconf)
602 print(", ");
603 if(zzrrconf)
604 print("%d reduce/reduce", zzrrconf);
605 print("\n");
606 }
607 if(ftemp != 0) {
608 Bterm(ftemp);
609 ftemp = 0;
610 }
611 if(fdefine != 0) {
612 Bterm(fdefine);
613 fdefine = 0;
614 }
615 }
616
617 /*
618 * write out error comment -- NEEDS WORK
619 */
620 void
621 error(char *s, ...)
622 {
623 va_list arg;
624
625 nerrors++;
626 fprint(2, "\n fatal error:");
627 va_start(arg, s);
628 vfprint(2, s, arg);
629 va_end(arg);
630 fprint(2, ", %s:%d\n", infile, lineno);
631 if(!fatfl)
632 return;
633 summary();
634 cleantmp();
635 exits("error");
636 }
637
638 /*
639 * set elements 0 through n-1 to c
640 */
641 void
642 aryfil(int *v, int n, int c)
643 {
644 int i;
645
646 for(i=0; i<n; i++)
647 v[i] = c;
648 }
649
650 /*
651 * set a to the union of a and b
652 * return 1 if b is not a subset of a, 0 otherwise
653 */
654 int
655 setunion(int *a, int *b)
656 {
657 int i, x, sub;
658
659 sub = 0;
660 SETLOOP(i) {
661 x = *a;
662 *a |= *b;
663 if(*a != x)
664 sub = 1;
665 a++;
666 b++;
667 }
668 return sub;
669 }
670
671 void
672 prlook(Lkset* p)
673 {
674 int j, *pp;
675
676 pp = p->lset;
677 if(pp == 0)
678 Bprint(foutput, "\tNULL");
679 else {
680 Bprint(foutput, " { ");
681 TLOOP(j)
682 if(BIT(pp,j))
683 Bprint(foutput, "%s ", symnam(j));
684 Bprint(foutput, "}");
685 }
686 }
687
688 /*
689 * compute an array with the beginnings of productions yielding given nonterminals
690 * The array pres points to these lists
691 * the array pyield has the lists: the total size is only NPROD+1
692 */
693 void
694 cpres(void)
695 {
696 int c, j, i, **pmem;
697 static int *pyield[NPROD];
698
699 pmem = pyield;
700 NTLOOP(i) {
701 c = i+NTBASE;
702 pres[i] = pmem;
703 fatfl = 0; /* make undefined symbols nonfatal */
704 PLOOP(0, j)
705 if(*prdptr[j] == c)
706 *pmem++ = prdptr[j]+1;
707 if(pres[i] == pmem)
708 error("nonterminal %s not defined!", nontrst[i].name);
709 }
710 pres[i] = pmem;
711 fatfl = 1;
712 if(nerrors) {
713 summary();
714 cleantmp();
715 exits("error");
716 }
717 if(pmem != &pyield[nprod])
718 error("internal Yacc error: pyield %d", pmem-&pyield[nprod]);
719 }
720
721 /*
722 * compute an array with the first of nonterminals
723 */
724 void
725 cpfir(void)
726 {
727 int *p, **s, i, **t, ch, changes;
728
729 zzcwp = &wsets[nnonter];
730 NTLOOP(i) {
731 aryfil(wsets[i].ws.lset, tbitset, 0);
732 t = pres[i+1];
733 /* initially fill the sets */
734 for(s=pres[i]; s<t; ++s)
735 for(p = *s; (ch = *p) > 0; ++p) {
736 if(ch < NTBASE) {
737 SETBIT(wsets[i].ws.lset, ch);
738 break;
739 }
740 if(!pempty[ch-NTBASE])
741 break;
742 }
743 }
744
745 /* now, reflect transitivity */
746 changes = 1;
747 while(changes) {
748 changes = 0;
749 NTLOOP(i) {
750 t = pres[i+1];
751 for(s = pres[i]; s < t; ++s)
752 for(p = *s; (ch = (*p-NTBASE)) >= 0; ++p) {
753 changes |= setunion(wsets[i].ws.lset, wsets[ch].ws.lset);
754 if(!pempty[ch])
755 break;
756 }
757 }
758 }
759
760 NTLOOP(i)
761 pfirst[i] = flset(&wsets[i].ws);
762 if(!indebug)
763 return;
764 if(foutput != 0)
765 NTLOOP(i) {
766 Bprint(foutput, "\n%s: ", nontrst[i].name);
767 prlook(pfirst[i]);
768 Bprint(foutput, " %d\n", pempty[i]);
769 }
770 }
771
772 /*
773 * sorts last state,and sees if it equals earlier ones. returns state number
774 */
775 int
776 state(int c)
777 {
778 Item *p1, *p2, *k, *l, *q1, *q2;
779 int size1, size2, i;
780
781 p1 = pstate[nstate];
782 p2 = pstate[nstate+1];
783 if(p1 == p2)
784 return 0; /* null state */
785 /* sort the items */
786 for(k = p2-1; k > p1; k--) /* make k the biggest */
787 for(l = k-1; l >= p1; --l)
788 if(l->pitem > k->pitem) {
789 int *s;
790 Lkset *ss;
791
792 s = k->pitem;
793 k->pitem = l->pitem;
794 l->pitem = s;
795 ss = k->look;
796 k->look = l->look;
797 l->look = ss;
798 }
799 size1 = p2 - p1; /* size of state */
800
801 for(i = (c>=NTBASE)? ntstates[c-NTBASE]: tstates[c]; i != 0; i = mstates[i]) {
802 /* get ith state */
803 q1 = pstate[i];
804 q2 = pstate[i+1];
805 size2 = q2 - q1;
806 if(size1 != size2)
807 continue;
808 k = p1;
809 for(l = q1; l < q2; l++) {
810 if(l->pitem != k->pitem)
811 break;
812 k++;
813 }
814 if(l != q2)
815 continue;
816 /* found it */
817 pstate[nstate+1] = pstate[nstate]; /* delete last state */
818 /* fix up lookaheads */
819 if(nolook)
820 return i;
821 for(l = q1, k = p1; l < q2; ++l, ++k ) {
822 int s;
823
824 SETLOOP(s)
825 clset.lset[s] = l->look->lset[s];
826 if(setunion(clset.lset, k->look->lset)) {
827 tystate[i] = MUSTDO;
828 /* register the new set */
829 l->look = flset( &clset );
830 }
831 }
832 return i;
833 }
834 /* state is new */
835 if(nolook)
836 error("yacc state/nolook error");
837 pstate[nstate+2] = p2;
838 if(nstate+1 >= NSTATES)
839 error("too many states");
840 if(c >= NTBASE) {
841 mstates[nstate] = ntstates[c-NTBASE];
842 ntstates[c-NTBASE] = nstate;
843 } else {
844 mstates[nstate] = tstates[c];
845 tstates[c] = nstate;
846 }
847 tystate[nstate] = MUSTDO;
848 return nstate++;
849 }
850
851 void
852 putitem(int *ptr, Lkset *lptr)
853 {
854 Item *j;
855
856 if(pidebug && foutput != 0)
857 Bprint(foutput, "putitem(%s), state %d\n", writem(ptr), nstate);
858 j = pstate[nstate+1];
859 j->pitem = ptr;
860 if(!nolook)
861 j->look = flset(lptr);
862 pstate[nstate+1] = ++j;
863 if((int*)j > zzmemsz) {
864 zzmemsz = (int*)j;
865 if(zzmemsz >= &mem0[MEMSIZE])
866 error("out of state space");
867 }
868 }
869
870 /*
871 * mark nonterminals which derive the empty string
872 * also, look for nonterminals which don't derive any token strings
873 */
874 void
875 cempty(void)
876 {
877
878 int i, *p;
879
880 /* first, use the array pempty to detect productions that can never be reduced */
881 /* set pempty to WHONOWS */
882 aryfil(pempty, nnonter+1, WHOKNOWS);
883
884 /* now, look at productions, marking nonterminals which derive something */
885 more:
886 PLOOP(0, i) {
887 if(pempty[*prdptr[i] - NTBASE])
888 continue;
889 for(p = prdptr[i]+1; *p >= 0; ++p)
890 if(*p >= NTBASE && pempty[*p-NTBASE] == WHOKNOWS)
891 break;
892 /* production can be derived */
893 if(*p < 0) {
894 pempty[*prdptr[i]-NTBASE] = OK;
895 goto more;
896 }
897 }
898
899 /* now, look at the nonterminals, to see if they are all OK */
900 NTLOOP(i) {
901 /* the added production rises or falls as the start symbol ... */
902 if(i == 0)
903 continue;
904 if(pempty[i] != OK) {
905 fatfl = 0;
906 error("nonterminal %s never derives any token string", nontrst[i].name);
907 }
908 }
909
910 if(nerrors) {
911 summary();
912 cleantmp();
913 exits("error");
914 }
915
916 /* now, compute the pempty array, to see which nonterminals derive the empty string */
917 /* set pempty to WHOKNOWS */
918 aryfil( pempty, nnonter+1, WHOKNOWS);
919
920 /* loop as long as we keep finding empty nonterminals */
921
922 again:
923 PLOOP(1, i) {
924 /* not known to be empty */
925 if(pempty[*prdptr[i]-NTBASE] == WHOKNOWS) {
926 for(p = prdptr[i]+1; *p >= NTBASE && pempty[*p-NTBASE] == EMPTY ; ++p)
927 ;
928 /* we have a nontrivially empty nonterminal */
929 if(*p < 0) {
930 pempty[*prdptr[i]-NTBASE] = EMPTY;
931 /* got one ... try for another */
932 goto again;
933 }
934 }
935 }
936 }
937
938 /*
939 * generate the states
940 */
941 void
942 stagen(void)
943 {
944
945 int c, i, j, more;
946 Wset *p, *q;
947
948 /* initialize */
949 nstate = 0;
950
951 /* THIS IS FUNNY from the standpoint of portability
952 * it represents the magic moment when the mem0 array, which has
953 * been holding the productions, starts to hold item pointers, of a
954 * different type...
955 * someday, alloc should be used to allocate all this stuff... for now, we
956 * accept that if pointers don't fit in integers, there is a problem...
957 */
958
959 pstate[0] = pstate[1] = (Item*)mem;
960 aryfil(clset.lset, tbitset, 0);
961 putitem(prdptr[0]+1, &clset);
962 tystate[0] = MUSTDO;
963 nstate = 1;
964 pstate[2] = pstate[1];
965
966 aryfil(amem, ACTSIZE, 0);
967
968 /* now, the main state generation loop */
969 for(more=1; more;) {
970 more = 0;
971 SLOOP(i) {
972 if(tystate[i] != MUSTDO)
973 continue;
974 tystate[i] = DONE;
975 aryfil(temp1, nnonter+1, 0);
976 /* take state i, close it, and do gotos */
977 closure(i);
978 /* generate goto's */
979 WSLOOP(wsets, p) {
980 if(p->flag)
981 continue;
982 p->flag = 1;
983 c = *(p->pitem);
984 if(c <= 1) {
985 if(pstate[i+1]-pstate[i] <= p-wsets)
986 tystate[i] = MUSTLOOKAHEAD;
987 continue;
988 }
989 /* do a goto on c */
990 WSLOOP(p, q)
991 /* this item contributes to the goto */
992 if(c == *(q->pitem)) {
993 putitem(q->pitem+1, &q->ws);
994 q->flag = 1;
995 }
996 if(c < NTBASE)
997 state(c); /* register new state */
998 else
999 temp1[c-NTBASE] = state(c);
1000 }
1001 if(gsdebug && foutput != 0) {
1002 Bprint(foutput, "%d: ", i);
1003 NTLOOP(j)
1004 if(temp1[j])
1005 Bprint(foutput, "%s %d, ",
1006 nontrst[j].name, temp1[j]);
1007 Bprint(foutput, "\n");
1008 }
1009 indgo[i] = apack(&temp1[1], nnonter-1) - 1;
1010 /* do some more */
1011 more = 1;
1012 }
1013 }
1014 }
1015
1016 /*
1017 * generate the closure of state i
1018 */
1019 void
1020 closure(int i)
1021 {
1022
1023 Wset *u, *v;
1024 Item *p, *q;
1025 int c, ch, work, k, *pi, **s, **t;
1026
1027 zzclose++;
1028
1029 /* first, copy kernel of state i to wsets */
1030 cwp = wsets;
1031 ITMLOOP(i, p, q) {
1032 cwp->pitem = p->pitem;
1033 cwp->flag = 1; /* this item must get closed */
1034 SETLOOP(k)
1035 cwp->ws.lset[k] = p->look->lset[k];
1036 WSBUMP(cwp);
1037 }
1038
1039 /* now, go through the loop, closing each item */
1040 work = 1;
1041 while(work) {
1042 work = 0;
1043 WSLOOP(wsets, u) {
1044 if(u->flag == 0)
1045 continue;
1046 /* dot is before c */
1047 c = *(u->pitem);
1048 if(c < NTBASE) {
1049 u->flag = 0;
1050 /* only interesting case is where . is before nonterminal */
1051 continue;
1052 }
1053
1054 /* compute the lookahead */
1055 aryfil(clset.lset, tbitset, 0);
1056
1057 /* find items involving c */
1058 WSLOOP(u, v)
1059 if(v->flag == 1 && *(pi=v->pitem) == c) {
1060 v->flag = 0;
1061 if(nolook)
1062 continue;
1063 while((ch = *++pi) > 0) {
1064 /* terminal symbol */
1065 if(ch < NTBASE) {
1066 SETBIT(clset.lset, ch);
1067 break;
1068 }
1069 /* nonterminal symbol */
1070 setunion(clset.lset, pfirst[ch-NTBASE]->lset);
1071 if(!pempty[ch-NTBASE])
1072 break;
1073 }
1074 if(ch <= 0)
1075 setunion(clset.lset, v->ws.lset);
1076 }
1077
1078 /*
1079 * now loop over productions derived from c
1080 * c is now nonterminal number
1081 */
1082 c -= NTBASE;
1083 t = pres[c+1];
1084 for(s = pres[c]; s < t; ++s) {
1085 /*
1086 * put these items into the closure
1087 * is the item there
1088 */
1089 WSLOOP(wsets, v)
1090 /* yes, it is there */
1091 if(v->pitem == *s) {
1092 if(nolook)
1093 goto nexts;
1094 if(setunion(v->ws.lset, clset.lset))
1095 v->flag = work = 1;
1096 goto nexts;
1097 }
1098
1099 /* not there; make a new entry */
1100 if(cwp-wsets+1 >= WSETSIZE)
1101 error( "working set overflow");
1102 cwp->pitem = *s;
1103 cwp->flag = 1;
1104 if(!nolook) {
1105 work = 1;
1106 SETLOOP(k) cwp->ws.lset[k] = clset.lset[k];
1107 }
1108 WSBUMP(cwp);
1109
1110 nexts:;
1111 }
1112 }
1113 }
1114
1115 /* have computed closure; flags are reset; return */
1116 if(cwp > zzcwp)
1117 zzcwp = cwp;
1118 if(cldebug && foutput != 0) {
1119 Bprint(foutput, "\nState %d, nolook = %d\n", i, nolook);
1120 WSLOOP(wsets, u) {
1121 if(u->flag)
1122 Bprint(foutput, "flag set!\n");
1123 u->flag = 0;
1124 Bprint(foutput, "\t%s", writem(u->pitem));
1125 prlook(&u->ws);
1126 Bprint(foutput, "\n");
1127 }
1128 }
1129 }
1130
1131 /*
1132 * decide if the lookahead set pointed to by p is known
1133 * return pointer to a perminent location for the set
1134 */
1135 Lkset*
1136 flset(Lkset *p)
1137 {
1138 Lkset *q;
1139 int *u, *v, *w, j;
1140
1141 for(q = &lkst[nlset]; q-- > lkst;) {
1142 u = p->lset;
1143 v = q->lset;
1144 w = &v[tbitset];
1145 while(v < w)
1146 if(*u++ != *v++)
1147 goto more;
1148 /* we have matched */
1149 return q;
1150 more:;
1151 }
1152 /* add a new one */
1153 q = &lkst[nlset++];
1154 if(nlset >= LSETSIZE)
1155 error("too many lookahead sets");
1156 SETLOOP(j)
1157 q->lset[j] = p->lset[j];
1158 return q;
1159 }
1160
1161 void
1162 cleantmp(void)
1163 {
1164 ZAPFILE(actname);
1165 ZAPFILE(tempname);
1166 }
1167
1168 void
1169 intr(void)
1170 {
1171 cleantmp();
1172 exits("interrupted");
1173 }
1174
1175 void
1176 setup(int argc, char *argv[])
1177 {
1178 long c, t;
1179 int i, j, fd, lev, ty, ytab, *p;
1180 int vflag, dflag, stem;
1181 char actnm[8], *stemc, *s, dirbuf[128];
1182 Biobuf *fout;
1183
1184 ytab = 0;
1185 vflag = 0;
1186 dflag = 0;
1187 stem = 0;
1188 stemc = "y";
1189 foutput = 0;
1190 fdefine = 0;
1191 fdebug = 0;
1192 ARGBEGIN{
1193 case 'v':
1194 case 'V':
1195 vflag++;
1196 break;
1197 case 'D':
1198 yydebug = ARGF();
1199 break;
1200 case 'a':
1201 yyarg = 1;
1202 break;
1203 case 'd':
1204 dflag++;
1205 break;
1206 case 'l':
1207 yyline = 0;
1208 break;
1209 case 'o':
1210 ytab++;
1211 ytabc = ARGF();
1212 break;
1213 case 's':
1214 stem++;
1215 stemc = ARGF();
1216 break;
1217 case 'S':
1218 parser = PARSERS;
1219 break;
1220 default:
1221 error("illegal option: %c", ARGC());
1222 }ARGEND
1223 openup(stemc, dflag, vflag, ytab, ytabc);
1224 fout = dflag?fdefine:ftable;
1225 if(yyarg){
1226 Bprint(ftable, "#define\tYYARG\t1\n\n");
1227 }
1228 if((fd = mkstemp(ttempname)) >= 0){
1229 tempname = ttempname;
1230 ftemp = Bfdopen(fd, OWRITE);
1231 }
1232 if((fd = mkstemp(tactname)) >= 0){
1233 actname = tactname;
1234 faction = Bfdopen(fd, OWRITE);
1235 }
1236 if(ftemp == 0 || faction == 0)
1237 error("cannot open temp file");
1238 if(argc < 1)
1239 error("no input file");
1240 infile = argv[0];
1241 if(infile[0] != '/' && getwd(dirbuf, sizeof dirbuf)!=nil){
1242 i = strlen(infile)+1+strlen(dirbuf)+1+10;
1243 s = malloc(i);
1244 if(s != nil){
1245 snprint(s, i, "%s/%s", dirbuf, infile);
1246 cleanname(s);
1247 infile = s;
1248 }
1249 }
1250 finput = Bopen(infile, OREAD);
1251 if(finput == 0)
1252 error("cannot open '%s'", argv[0]);
1253 cnamp = cnames;
1254
1255 defin(0, "$end");
1256 extval = PRIVATE; /* tokens start in unicode 'private use' */
1257 defin(0, "error");
1258 defin(1, "$accept");
1259 defin(0, "$unk");
1260 mem = mem0;
1261 i = 0;
1262
1263 for(t = gettok(); t != MARK && t != ENDFILE;)
1264 switch(t) {
1265 case ';':
1266 t = gettok();
1267 break;
1268
1269 case START:
1270 if(gettok() != IDENTIFIER)
1271 error("bad %%start construction");
1272 start = chfind(1, tokname);
1273 t = gettok();
1274 continue;
1275
1276 case TYPEDEF:
1277 if(gettok() != TYPENAME)
1278 error("bad syntax in %%type");
1279 ty = numbval;
1280 for(;;) {
1281 t = gettok();
1282 switch(t) {
1283 case IDENTIFIER:
1284 if((t=chfind(1, tokname)) < NTBASE) {
1285 j = TYPE(toklev[t]);
1286 if(j != 0 && j != ty)
1287 error("type redeclaration of token %s",
1288 tokset[t].name);
1289 else
1290 SETTYPE(toklev[t], ty);
1291 } else {
1292 j = nontrst[t-NTBASE].value;
1293 if(j != 0 && j != ty)
1294 error("type redeclaration of nonterminal %s",
1295 nontrst[t-NTBASE].name );
1296 else
1297 nontrst[t-NTBASE].value = ty;
1298 }
1299 case ',':
1300 continue;
1301 case ';':
1302 t = gettok();
1303 default:
1304 break;
1305 }
1306 break;
1307 }
1308 continue;
1309
1310 case UNION:
1311 /* copy the union declaration to the output */
1312 cpyunion();
1313 t = gettok();
1314 continue;
1315
1316 case LEFT:
1317 case BINARY:
1318 case RIGHT:
1319 i++;
1320
1321 case TERM:
1322 /* nonzero means new prec. and assoc. */
1323 lev = t-TERM;
1324 ty = 0;
1325
1326 /* get identifiers so defined */
1327 t = gettok();
1328
1329 /* there is a type defined */
1330 if(t == TYPENAME) {
1331 ty = numbval;
1332 t = gettok();
1333 }
1334 for(;;) {
1335 switch(t) {
1336 case ',':
1337 t = gettok();
1338 continue;
1339
1340 case ';':
1341 break;
1342
1343 case IDENTIFIER:
1344 j = chfind(0, tokname);
1345 if(j >= NTBASE)
1346 error("%s defined earlier as nonterminal", tokname);
1347 if(lev) {
1348 if(ASSOC(toklev[j]))
1349 error("redeclaration of precedence of %s", tokname);
1350 SETASC(toklev[j], lev);
1351 SETPLEV(toklev[j], i);
1352 }
1353 if(ty) {
1354 if(TYPE(toklev[j]))
1355 error("redeclaration of type of %s", tokname);
1356 SETTYPE(toklev[j],ty);
1357 }
1358 t = gettok();
1359 if(t == NUMBER) {
1360 tokset[j].value = numbval;
1361 if(j < ndefout && j > 3)
1362 error("please define type number of %s earlier",
1363 tokset[j].name);
1364 t = gettok();
1365 }
1366 continue;
1367 }
1368 break;
1369 }
1370 continue;
1371
1372 case LCURLY:
1373 defout(0);
1374 cpycode();
1375 t = gettok();
1376 continue;
1377
1378 default:
1379 error("syntax error");
1380 }
1381 if(t == ENDFILE)
1382 error("unexpected EOF before %%");
1383
1384 /* t is MARK */
1385 if(!yyarg)
1386 Bprint(ftable, "extern int yyerrflag;\n");
1387 Bprint(ftable, "#ifndef YYMAXDEPTH\n");
1388 Bprint(ftable, "#define YYMAXDEPTH 150\n");
1389 Bprint(ftable, "#endif\n" );
1390 if(!ntypes) {
1391 Bprint(ftable, "#ifndef YYSTYPE\n");
1392 Bprint(ftable, "#define YYSTYPE int\n");
1393 Bprint(ftable, "#endif\n");
1394 }
1395 if(!yyarg){
1396 Bprint(ftable, "YYSTYPE yylval;\n");
1397 Bprint(ftable, "YYSTYPE yyval;\n");
1398 }else{
1399 if(dflag)
1400 Bprint(ftable, "#include \"%s.%s\"\n\n", stemc, FILED);
1401 Bprint(fout, "struct Yyarg {\n");
1402 Bprint(fout, "\tint\tyynerrs;\n");
1403 Bprint(fout, "\tint\tyyerrflag;\n");
1404 Bprint(fout, "\tvoid*\targ;\n");
1405 Bprint(fout, "\tYYSTYPE\tyyval;\n");
1406 Bprint(fout, "\tYYSTYPE\tyylval;\n");
1407 Bprint(fout, "};\n\n");
1408 }
1409 prdptr[0] = mem;
1410
1411 /* added production */
1412 *mem++ = NTBASE;
1413
1414 /* if start is 0, we will overwrite with the lhs of the first rule */
1415 *mem++ = start;
1416 *mem++ = 1;
1417 *mem++ = 0;
1418 prdptr[1] = mem;
1419 while((t=gettok()) == LCURLY)
1420 cpycode();
1421 if(t != IDENTCOLON)
1422 error("bad syntax on first rule");
1423
1424 if(!start)
1425 prdptr[0][1] = chfind(1, tokname);
1426
1427 /* read rules */
1428 while(t != MARK && t != ENDFILE) {
1429 /* process a rule */
1430 rlines[nprod] = lineno;
1431 if(t == '|')
1432 *mem++ = *prdptr[nprod-1];
1433 else
1434 if(t == IDENTCOLON) {
1435 *mem = chfind(1, tokname);
1436 if(*mem < NTBASE)
1437 error("token illegal on LHS of grammar rule");
1438 mem++;
1439 } else
1440 error("illegal rule: missing semicolon or | ?");
1441 /* read rule body */
1442 t = gettok();
1443
1444 more_rule:
1445 while(t == IDENTIFIER) {
1446 *mem = chfind(1, tokname);
1447 if(*mem < NTBASE)
1448 levprd[nprod] = toklev[*mem];
1449 mem++;
1450 t = gettok();
1451 }
1452 if(t == PREC) {
1453 if(gettok() != IDENTIFIER)
1454 error("illegal %%prec syntax");
1455 j = chfind(2, tokname);
1456 if(j >= NTBASE)
1457 error("nonterminal %s illegal after %%prec",
1458 nontrst[j-NTBASE].name);
1459 levprd[nprod] = toklev[j];
1460 t = gettok();
1461 }
1462 if(t == '=') {
1463 levprd[nprod] |= ACTFLAG;
1464 Bprint(faction, "\ncase %d:", nprod);
1465 cpyact(mem-prdptr[nprod]-1);
1466 Bprint(faction, " break;");
1467 if((t=gettok()) == IDENTIFIER) {
1468
1469 /* action within rule... */
1470 sprint(actnm, "$$%d", nprod);
1471
1472 /* make it a nonterminal */
1473 j = chfind(1, actnm);
1474
1475 /*
1476 * the current rule will become rule number nprod+1
1477 * move the contents down, and make room for the null
1478 */
1479 for(p = mem; p >= prdptr[nprod]; --p)
1480 p[2] = *p;
1481 mem += 2;
1482
1483 /* enter null production for action */
1484 p = prdptr[nprod];
1485 *p++ = j;
1486 *p++ = -nprod;
1487
1488 /* update the production information */
1489 levprd[nprod+1] = levprd[nprod] & ~ACTFLAG;
1490 levprd[nprod] = ACTFLAG;
1491 if(++nprod >= NPROD)
1492 error("more than %d rules", NPROD);
1493 prdptr[nprod] = p;
1494
1495 /* make the action appear in the original rule */
1496 *mem++ = j;
1497
1498 /* get some more of the rule */
1499 goto more_rule;
1500 }
1501 }
1502
1503 while(t == ';')
1504 t = gettok();
1505 *mem++ = -nprod;
1506
1507 /* check that default action is reasonable */
1508 if(ntypes && !(levprd[nprod]&ACTFLAG) && nontrst[*prdptr[nprod]-NTBASE].value) {
1509
1510 /* no explicit action, LHS has value */
1511 int tempty;
1512
1513 tempty = prdptr[nprod][1];
1514 if(tempty < 0)
1515 error("must return a value, since LHS has a type");
1516 else
1517 if(tempty >= NTBASE)
1518 tempty = nontrst[tempty-NTBASE].value;
1519 else
1520 tempty = TYPE(toklev[tempty]);
1521 if(tempty != nontrst[*prdptr[nprod]-NTBASE].value)
1522 error("default action causes potential type clash");
1523 }
1524 nprod++;
1525 if(nprod >= NPROD)
1526 error("more than %d rules", NPROD);
1527 prdptr[nprod] = mem;
1528 levprd[nprod] = 0;
1529 }
1530
1531 /* end of all rules */
1532 defout(1);
1533
1534 finact();
1535 if(t == MARK) {
1536 Bprint(ftable, "\n");
1537 if(yyline)
1538 Bprint(ftable, "#line\t%d\t\"%s\"\n", lineno, infile);
1539 while((c=Bgetrune(finput)) != Beof)
1540 Bputrune(ftable, c);
1541 }
1542 Bterm(finput);
1543 }
1544
1545 /*
1546 * finish action routine
1547 */
1548 void
1549 finact(void)
1550 {
1551
1552 Bterm(faction);
1553 Bprint(ftable, "#define YYEOFCODE %d\n", 1);
1554 Bprint(ftable, "#define YYERRCODE %d\n", 2);
1555 }
1556
1557 /*
1558 * define s to be a terminal if t=0
1559 * or a nonterminal if t=1
1560 */
1561 int
1562 defin(int nt, char *s)
1563 {
1564 int val;
1565 Rune rune;
1566
1567 val = 0;
1568 if(nt) {
1569 nnonter++;
1570 if(nnonter >= NNONTERM)
1571 error("too many nonterminals, limit %d",NNONTERM);
1572 nontrst[nnonter].name = cstash(s);
1573 return NTBASE + nnonter;
1574 }
1575
1576 /* must be a token */
1577 ntokens++;
1578 if(ntokens >= NTERMS)
1579 error("too many terminals, limit %d", NTERMS);
1580 tokset[ntokens].name = cstash(s);
1581
1582 /* establish value for token */
1583 /* single character literal */
1584 if(s[0] == ' ') {
1585 val = chartorune(&rune, &s[1]);
1586 if(s[val+1] == 0) {
1587 val = rune;
1588 goto out;
1589 }
1590 }
1591
1592 /* escape sequence */
1593 if(s[0] == ' ' && s[1] == '\\') {
1594 if(s[3] == 0) {
1595 /* single character escape sequence */
1596 switch(s[2]) {
1597 case 'n': val = '\n'; break;
1598 case 'r': val = '\r'; break;
1599 case 'b': val = '\b'; break;
1600 case 't': val = '\t'; break;
1601 case 'f': val = '\f'; break;
1602 case '\'': val = '\''; break;
1603 case '"': val = '"'; break;
1604 case '\\': val = '\\'; break;
1605 default: error("invalid escape");
1606 }
1607 goto out;
1608 }
1609
1610 /* \nnn sequence */
1611 if(s[2] >= '0' && s[2] <= '7') {
1612 if(s[3] < '0' ||
1613 s[3] > '7' ||
1614 s[4] < '0' ||
1615 s[4] > '7' ||
1616 s[5] != 0)
1617 error("illegal \\nnn construction");
1618 val = 64*s[2] + 8*s[3] + s[4] - 73*'0';
1619 if(val == 0)
1620 error("'\\000' is illegal");
1621 goto out;
1622 }
1623 error("unknown escape");
1624 }
1625 val = extval++;
1626
1627 out:
1628 tokset[ntokens].value = val;
1629 toklev[ntokens] = 0;
1630 return ntokens;
1631 }
1632
1633 /*
1634 * write out the defines (at the end of the declaration section)
1635 */
1636 void
1637 defout(int last)
1638 {
1639 int i, c;
1640 char sar[NAMESIZE+10];
1641
1642 for(i=ndefout; i<=ntokens; i++) {
1643 /* non-literals */
1644 c = tokset[i].name[0];
1645 if(c != ' ' && c != '$') {
1646 Bprint(ftable, "#define %s %d\n",
1647 tokset[i].name, tokset[i].value);
1648 if(fdefine)
1649 Bprint(fdefine, "#define\t%s\t%d\n",
1650 tokset[i].name, tokset[i].value);
1651 }
1652 }
1653 ndefout = ntokens+1;
1654 if(last && fdebug) {
1655 Bprint(fdebug, "static char* yytoknames[] =\n{\n");
1656 TLOOP(i) {
1657 if(tokset[i].name) {
1658 chcopy(sar, tokset[i].name);
1659 Bprint(fdebug, "\t\"%s\",\n", sar);
1660 continue;
1661 }
1662 Bprint(fdebug, "\t0,\n");
1663 }
1664 Bprint(fdebug, "};\n");
1665 }
1666 }
1667
1668 char*
1669 cstash(char *s)
1670 {
1671 char *temp;
1672
1673 temp = cnamp;
1674 do {
1675 if(cnamp >= &cnames[cnamsz])
1676 error("too many characters in id's and literals");
1677 else
1678 *cnamp++ = *s;
1679 } while(*s++);
1680 return temp;
1681 }
1682
1683 long
1684 gettok(void)
1685 {
1686 long c;
1687 Rune rune;
1688 int i, base, match, reserve;
1689 static int peekline;
1690
1691 begin:
1692 reserve = 0;
1693 lineno += peekline;
1694 peekline = 0;
1695 c = Bgetrune(finput);
1696 while(c == ' ' || c == '\n' || c == '\t' || c == '\f') {
1697 if(c == '\n')
1698 lineno++;
1699 c = Bgetrune(finput);
1700 }
1701
1702 /* skip comment */
1703 if(c == '/') {
1704 lineno += skipcom();
1705 goto begin;
1706 }
1707 switch(c) {
1708 case Beof:
1709 return ENDFILE;
1710
1711 case '{':
1712 Bungetrune(finput);
1713 return '=';
1714
1715 case '<':
1716 /* get, and look up, a type name (union member name) */
1717 i = 0;
1718 while((c=Bgetrune(finput)) != '>' && c >= 0 && c != '\n') {
1719 rune = c;
1720 c = runetochar(&tokname[i], &rune);
1721 if(i < NAMESIZE)
1722 i += c;
1723 }
1724 if(c != '>')
1725 error("unterminated < ... > clause");
1726 tokname[i] = 0;
1727 for(i=1; i<=ntypes; i++)
1728 if(!strcmp(typeset[i], tokname)) {
1729 numbval = i;
1730 return TYPENAME;
1731 }
1732 ntypes++;
1733 numbval = ntypes;
1734 typeset[numbval] = cstash(tokname);
1735 return TYPENAME;
1736
1737 case '"':
1738 case '\'':
1739 match = c;
1740 tokname[0] = ' ';
1741 i = 1;
1742 for(;;) {
1743 c = Bgetrune(finput);
1744 if(c == '\n' || c <= 0)
1745 error("illegal or missing ' or \"" );
1746 if(c == '\\') {
1747 tokname[i] = '\\';
1748 if(i < NAMESIZE)
1749 i++;
1750 c = Bgetrune(finput);
1751 } else
1752 if(c == match)
1753 break;
1754 rune = c;
1755 c = runetochar(&tokname[i], &rune);
1756 if(i < NAMESIZE)
1757 i += c;
1758 }
1759 break;
1760
1761 case '%':
1762 case '\\':
1763 switch(c = Bgetrune(finput)) {
1764 case '0': return TERM;
1765 case '<': return LEFT;
1766 case '2': return BINARY;
1767 case '>': return RIGHT;
1768 case '%':
1769 case '\\': return MARK;
1770 case '=': return PREC;
1771 case '{': return LCURLY;
1772 default: reserve = 1;
1773 }
1774
1775 default:
1776 /* number */
1777 if(isdigit(c)) {
1778 numbval = c-'0';
1779 base = (c=='0')? 8: 10;
1780 for(c = Bgetrune(finput); isdigit(c); c = Bgetrune(finput))
1781 numbval = numbval*base + (c-'0');
1782 Bungetrune(finput);
1783 return NUMBER;
1784 }
1785 if(islower(c) || isupper(c) || c=='_' || c=='.' || c=='$') {
1786 i = 0;
1787 while(islower(c) || isupper(c) || isdigit(c) ||
1788 c == '-' || c=='_' || c=='.' || c=='$') {
1789 if(reserve && isupper(c))
1790 c += 'a'-'A';
1791 rune = c;
1792 c = runetochar(&tokname[i], &rune);
1793 if(i < NAMESIZE)
1794 i += c;
1795 c = Bgetrune(finput);
1796 }
1797 } else
1798 return c;
1799 Bungetrune(finput);
1800 }
1801 tokname[i] = 0;
1802
1803 /* find a reserved word */
1804 if(reserve) {
1805 for(c=0; resrv[c].name; c++)
1806 if(strcmp(tokname, resrv[c].name) == 0)
1807 return resrv[c].value;
1808 error("invalid escape, or illegal reserved word: %s", tokname);
1809 }
1810
1811 /* look ahead to distinguish IDENTIFIER from IDENTCOLON */
1812 c = Bgetrune(finput);
1813 while(c == ' ' || c == '\t'|| c == '\n' || c == '\f' || c == '/') {
1814 if(c == '\n')
1815 peekline++;
1816 /* look for comments */
1817 if(c == '/')
1818 peekline += skipcom();
1819 c = Bgetrune(finput);
1820 }
1821 if(c == ':')
1822 return IDENTCOLON;
1823 Bungetrune(finput);
1824 return IDENTIFIER;
1825 }
1826
1827 /*
1828 * determine the type of a symbol
1829 */
1830 int
1831 fdtype(int t)
1832 {
1833 int v;
1834
1835 if(t >= NTBASE)
1836 v = nontrst[t-NTBASE].value;
1837 else
1838 v = TYPE(toklev[t]);
1839 if(v <= 0)
1840 error("must specify type for %s", (t>=NTBASE)?
1841 nontrst[t-NTBASE].name: tokset[t].name);
1842 return v;
1843 }
1844
1845 int
1846 chfind(int t, char *s)
1847 {
1848 int i;
1849
1850 if(s[0] == ' ')
1851 t = 0;
1852 TLOOP(i)
1853 if(!strcmp(s, tokset[i].name))
1854 return i;
1855 NTLOOP(i)
1856 if(!strcmp(s, nontrst[i].name))
1857 return NTBASE+i;
1858
1859 /* cannot find name */
1860 if(t > 1)
1861 error("%s should have been defined earlier", s);
1862 return defin(t, s);
1863 }
1864
1865 /*
1866 * copy the union declaration to the output, and the define file if present
1867 */
1868 void
1869 cpyunion(void)
1870 {
1871 long c;
1872 int level;
1873
1874 Bprint(ftable, "\n");
1875 if(yyline)
1876 Bprint(ftable, "#line\t%d\t\"%s\"\n", lineno, infile);
1877 Bprint(ftable, "typedef union ");
1878 if(fdefine != 0)
1879 Bprint(fdefine, "\ntypedef union ");
1880
1881 level = 0;
1882 for(;;) {
1883 if((c=Bgetrune(finput)) == Beof)
1884 error("EOF encountered while processing %%union");
1885 Bputrune(ftable, c);
1886 if(fdefine != 0)
1887 Bputrune(fdefine, c);
1888 switch(c) {
1889 case '\n':
1890 lineno++;
1891 break;
1892 case '{':
1893 level++;
1894 break;
1895 case '}':
1896 level--;
1897
1898 /* we are finished copying */
1899 if(level == 0) {
1900 Bprint(ftable, " YYSTYPE;\n");
1901 if(fdefine != 0){
1902 Bprint(fdefine, "\tYYSTYPE;\n");
1903 if(!yyarg)
1904 Bprint(fdefine, "extern\tYYSTYPE\tyylval;\n");
1905 }
1906 return;
1907 }
1908 }
1909 }
1910 }
1911
1912 /*
1913 * copies code between \{ and \}
1914 */
1915 void
1916 cpycode(void)
1917 {
1918 long c;
1919
1920 c = Bgetrune(finput);
1921 if(c == '\n') {
1922 c = Bgetrune(finput);
1923 lineno++;
1924 }
1925 Bprint(ftable, "\n");
1926 if(yyline)
1927 Bprint(ftable, "#line\t%d\t\"%s\"\n", lineno, infile);
1928 while(c != Beof) {
1929 if(c == '\\') {
1930 if((c=Bgetrune(finput)) == '}')
1931 return;
1932 Bputc(ftable, '\\');
1933 }
1934 if(c == '%') {
1935 if((c=Bgetrune(finput)) == '}')
1936 return;
1937 Bputc(ftable, '%');
1938 }
1939 Bputrune(ftable, c);
1940 if(c == '\n')
1941 lineno++;
1942 c = Bgetrune(finput);
1943 }
1944 error("eof before %%}");
1945 }
1946
1947 /*
1948 * skip over comments
1949 * skipcom is called after reading a '/'
1950 */
1951 int
1952 skipcom(void)
1953 {
1954 long c;
1955 int i;
1956
1957 /* i is the number of lines skipped */
1958 i = 0;
1959 if(Bgetrune(finput) != '*')
1960 error("illegal comment");
1961 c = Bgetrune(finput);
1962 while(c != Beof) {
1963 while(c == '*')
1964 if((c=Bgetrune(finput)) == '/')
1965 return i;
1966 if(c == '\n')
1967 i++;
1968 c = Bgetrune(finput);
1969 }
1970 error("EOF inside comment");
1971 return 0;
1972 }
1973
1974 /*
1975 * copy C action to the next ; or closing }
1976 */
1977 void
1978 cpyact(int offset)
1979 {
1980 long c;
1981 int brac, match, j, s, fnd, tok;
1982
1983 Bprint(faction, "\n");
1984 if(yyline)
1985 Bprint(faction, "#line\t%d\t\"%s\"\n", lineno, infile);
1986 brac = 0;
1987
1988 loop:
1989 c = Bgetrune(finput);
1990 swt:
1991 switch(c) {
1992 case ';':
1993 if(brac == 0) {
1994 Bputrune(faction, c);
1995 return;
1996 }
1997 goto lcopy;
1998
1999 case '{':
2000 brac++;
2001 goto lcopy;
2002
2003 case '$':
2004 s = 1;
2005 tok = -1;
2006 c = Bgetrune(finput);
2007
2008 /* type description */
2009 if(c == '<') {
2010 Bungetrune(finput);
2011 if(gettok() != TYPENAME)
2012 error("bad syntax on $<ident> clause");
2013 tok = numbval;
2014 c = Bgetrune(finput);
2015 }
2016 if(c == '$') {
2017 Bprint(faction, "yyval");
2018
2019 /* put out the proper tag... */
2020 if(ntypes) {
2021 if(tok < 0)
2022 tok = fdtype(*prdptr[nprod]);
2023 Bprint(faction, ".%s", typeset[tok]);
2024 }
2025 goto loop;
2026 }
2027 if(c == '-') {
2028 s = -s;
2029 c = Bgetrune(finput);
2030 }
2031 if(isdigit(c)) {
2032 j = 0;
2033 while(isdigit(c)) {
2034 j = j*10 + (c-'0');
2035 c = Bgetrune(finput);
2036 }
2037 Bungetrune(finput);
2038 j = j*s - offset;
2039 if(j > 0)
2040 error("Illegal use of $%d", j+offset);
2041
2042 dollar:
2043 Bprint(faction, "yypt[-%d].yyv", -j);
2044
2045 /* put out the proper tag */
2046 if(ntypes) {
2047 if(j+offset <= 0 && tok < 0)
2048 error("must specify type of $%d", j+offset);
2049 if(tok < 0)
2050 tok = fdtype(prdptr[nprod][j+offset]);
2051 Bprint(faction, ".%s", typeset[tok]);
2052 }
2053 goto loop;
2054 }
2055 if(isupper(c) || islower(c) || c == '_' || c == '.') {
2056 int tok; /* tok used oustide for type info */
2057
2058 /* look for $name */
2059 Bungetrune(finput);
2060 if(gettok() != IDENTIFIER)
2061 error("$ must be followed by an identifier");
2062 tok = chfind(2, tokname);
2063 if((c = Bgetrune(finput)) != '#') {
2064 Bungetrune(finput);
2065 fnd = -1;
2066 } else
2067 if(gettok() != NUMBER) {
2068 error("# must be followed by number");
2069 fnd = -1;
2070 } else
2071 fnd = numbval;
2072 for(j=1; j<=offset; ++j)
2073 if(tok == prdptr[nprod][j]) {
2074 if(--fnd <= 0) {
2075 j -= offset;
2076 goto dollar;
2077 }
2078 }
2079 error("$name or $name#number not found");
2080 }
2081 Bputc(faction, '$');
2082 if(s < 0 )
2083 Bputc(faction, '-');
2084 goto swt;
2085
2086 case '}':
2087 brac--;
2088 if(brac)
2089 goto lcopy;
2090 Bputrune(faction, c);
2091 return;
2092
2093 case '/':
2094 /* look for comments */
2095 Bputrune(faction, c);
2096 c = Bgetrune(finput);
2097 if(c != '*')
2098 goto swt;
2099
2100 /* it really is a comment */
2101 Bputrune(faction, c);
2102 c = Bgetrune(finput);
2103 while(c >= 0) {
2104 while(c == '*') {
2105 Bputrune(faction, c);
2106 if((c=Bgetrune(finput)) == '/')
2107 goto lcopy;
2108 }
2109 Bputrune(faction, c);
2110 if(c == '\n')
2111 lineno++;
2112 c = Bgetrune(finput);
2113 }
2114 error("EOF inside comment");
2115
2116 case '\'':
2117 /* character constant */
2118 match = '\'';
2119 goto string;
2120
2121 case '"':
2122 /* character string */
2123 match = '"';
2124
2125 string:
2126 Bputrune(faction, c);
2127 while(c = Bgetrune(finput)) {
2128 if(c == '\\') {
2129 Bputrune(faction, c);
2130 c = Bgetrune(finput);
2131 if(c == '\n')
2132 lineno++;
2133 } else
2134 if(c == match)
2135 goto lcopy;
2136 if(c == '\n')
2137 error("newline in string or char. const.");
2138 Bputrune(faction, c);
2139 }
2140 error("EOF in string or character constant");
2141
2142 case Beof:
2143 error("action does not terminate");
2144
2145 case '\n':
2146 lineno++;
2147 goto lcopy;
2148 }
2149
2150 lcopy:
2151 Bputrune(faction, c);
2152 goto loop;
2153 }
2154
2155 void
2156 openup(char *stem, int dflag, int vflag, int ytab, char *ytabc)
2157 {
2158 char buf[256];
2159
2160 if(vflag) {
2161 sprint(buf, "%s.%s", stem, FILEU);
2162 foutput = Bopen(buf, OWRITE);
2163 if(foutput == 0)
2164 error("cannot open %s", buf);
2165 }
2166 if(yydebug) {
2167 sprint(buf, "%s.%s", stem, FILEDEBUG);
2168 if((fdebug = Bopen(buf, OWRITE)) == 0)
2169 error("can't open %s", buf);
2170 }
2171 if(dflag) {
2172 sprint(buf, "%s.%s", stem, FILED);
2173 fdefine = Bopen(buf, OWRITE);
2174 if(fdefine == 0)
2175 error("can't create %s", buf);
2176 }
2177 if(ytab == 0)
2178 sprint(buf, "%s.%s", stem, OFILE);
2179 else
2180 strcpy(buf, ytabc);
2181 ftable = Bopen(buf, OWRITE);
2182 if(ftable == 0)
2183 error("cannot open table file %s", buf);
2184 }
2185
2186 /*
2187 * print the output for the states
2188 */
2189 void
2190 output(void)
2191 {
2192 int i, k, c;
2193 Wset *u, *v;
2194
2195 Bprint(ftable, "static\tconst\tshort yyexca[] =\n{");
2196 if(fdebug)
2197 Bprint(fdebug, "static\tconst\tchar* yystates[] =\n{\n");
2198
2199 /* output the stuff for state i */
2200 SLOOP(i) {
2201 nolook = tystate[i]!=MUSTLOOKAHEAD;
2202 closure(i);
2203
2204 /* output actions */
2205 nolook = 1;
2206 aryfil(temp1, ntokens+nnonter+1, 0);
2207 WSLOOP(wsets, u) {
2208 c = *(u->pitem);
2209 if(c > 1 && c < NTBASE && temp1[c] == 0) {
2210 WSLOOP(u, v)
2211 if(c == *(v->pitem))
2212 putitem(v->pitem+1, (Lkset*)0);
2213 temp1[c] = state(c);
2214 } else
2215 if(c > NTBASE && temp1[(c -= NTBASE) + ntokens] == 0)
2216 temp1[c+ntokens] = amem[indgo[i]+c];
2217 }
2218 if(i == 1)
2219 temp1[1] = ACCEPTCODE;
2220
2221 /* now, we have the shifts; look at the reductions */
2222 lastred = 0;
2223 WSLOOP(wsets, u) {
2224 c = *u->pitem;
2225
2226 /* reduction */
2227 if(c <= 0) {
2228 lastred = -c;
2229 TLOOP(k)
2230 if(BIT(u->ws.lset, k)) {
2231 if(temp1[k] == 0)
2232 temp1[k] = c;
2233 else
2234 if(temp1[k] < 0) { /* reduce/reduce conflict */
2235 if(foutput)
2236 Bprint(foutput,
2237 "\n%d: reduce/reduce conflict"
2238 " (red'ns %d and %d ) on %s",
2239 i, -temp1[k], lastred,
2240 symnam(k));
2241 if(-temp1[k] > lastred)
2242 temp1[k] = -lastred;
2243 zzrrconf++;
2244 } else
2245 /* potential shift/reduce conflict */
2246 precftn( lastred, k, i );
2247 }
2248 }
2249 }
2250 wract(i);
2251 }
2252
2253 if(fdebug)
2254 Bprint(fdebug, "};\n");
2255 Bprint(ftable, "};\n");
2256 Bprint(ftable, "#define YYNPROD %d\n", nprod);
2257 Bprint(ftable, "#define YYPRIVATE %d\n", PRIVATE);
2258 if(yydebug)
2259 Bprint(ftable, "#define yydebug %s\n", yydebug);
2260 }
2261
2262 /*
2263 * pack state i from temp1 into amem
2264 */
2265 int
2266 apack(int *p, int n)
2267 {
2268 int *pp, *qq, *rr, off, *q, *r;
2269
2270 /* we don't need to worry about checking because
2271 * we will only look at entries known to be there...
2272 * eliminate leading and trailing 0's
2273 */
2274
2275 q = p+n;
2276 for(pp = p, off = 0; *pp == 0 && pp <= q; ++pp, --off)
2277 ;
2278 /* no actions */
2279 if(pp > q)
2280 return 0;
2281 p = pp;
2282
2283 /* now, find a place for the elements from p to q, inclusive */
2284 r = &amem[ACTSIZE-1];
2285 for(rr = amem; rr <= r; rr++, off++) {
2286 for(qq = rr, pp = p; pp <= q; pp++, qq++)
2287 if(*pp != 0)
2288 if(*pp != *qq && *qq != 0)
2289 goto nextk;
2290
2291 /* we have found an acceptable k */
2292 if(pkdebug && foutput != 0)
2293 Bprint(foutput, "off = %d, k = %d\n", off, (int)(rr-amem));
2294 for(qq = rr, pp = p; pp <= q; pp++, qq++)
2295 if(*pp) {
2296 if(qq > r)
2297 error("action table overflow");
2298 if(qq > memp)
2299 memp = qq;
2300 *qq = *pp;
2301 }
2302 if(pkdebug && foutput != 0)
2303 for(pp = amem; pp <= memp; pp += 10) {
2304 Bprint(foutput, "\t");
2305 for(qq = pp; qq <= pp+9; qq++)
2306 Bprint(foutput, "%d ", *qq);
2307 Bprint(foutput, "\n");
2308 }
2309 return(off);
2310 nextk:;
2311 }
2312 error("no space in action table");
2313 return 0;
2314 }
2315
2316 /*
2317 * output the gotos for the nontermninals
2318 */
2319 void
2320 go2out(void)
2321 {
2322 int i, j, k, best, count, cbest, times;
2323
2324 /* mark begining of gotos */
2325 Bprint(ftemp, "$\n");
2326 for(i = 1; i <= nnonter; i++) {
2327 go2gen(i);
2328
2329 /* find the best one to make default */
2330 best = -1;
2331 times = 0;
2332
2333 /* is j the most frequent */
2334 for(j = 0; j <= nstate; j++) {
2335 if(tystate[j] == 0)
2336 continue;
2337 if(tystate[j] == best)
2338 continue;
2339
2340 /* is tystate[j] the most frequent */
2341 count = 0;
2342 cbest = tystate[j];
2343 for(k = j; k <= nstate; k++)
2344 if(tystate[k] == cbest)
2345 count++;
2346 if(count > times) {
2347 best = cbest;
2348 times = count;
2349 }
2350 }
2351
2352 /* best is now the default entry */
2353 zzgobest += times-1;
2354 for(j = 0; j <= nstate; j++)
2355 if(tystate[j] != 0 && tystate[j] != best) {
2356 Bprint(ftemp, "%d,%d,", j, tystate[j]);
2357 zzgoent++;
2358 }
2359
2360 /* now, the default */
2361 if(best == -1)
2362 best = 0;
2363 zzgoent++;
2364 Bprint(ftemp, "%d\n", best);
2365 }
2366 }
2367
2368 /*
2369 * output the gotos for nonterminal c
2370 */
2371 void
2372 go2gen(int c)
2373 {
2374 int i, work, cc;
2375 Item *p, *q;
2376
2377
2378 /* first, find nonterminals with gotos on c */
2379 aryfil(temp1, nnonter+1, 0);
2380 temp1[c] = 1;
2381 work = 1;
2382 while(work) {
2383 work = 0;
2384 PLOOP(0, i)
2385
2386 /* cc is a nonterminal */
2387 if((cc=prdptr[i][1]-NTBASE) >= 0)
2388 /* cc has a goto on c */
2389 if(temp1[cc] != 0) {
2390
2391 /* thus, the left side of production i does too */
2392 cc = *prdptr[i]-NTBASE;
2393 if(temp1[cc] == 0) {
2394 work = 1;
2395 temp1[cc] = 1;
2396 }
2397 }
2398 }
2399
2400 /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
2401 if(g2debug && foutput != 0) {
2402 Bprint(foutput, "%s: gotos on ", nontrst[c].name);
2403 NTLOOP(i)
2404 if(temp1[i])
2405 Bprint(foutput, "%s ", nontrst[i].name);
2406 Bprint(foutput, "\n");
2407 }
2408
2409 /* now, go through and put gotos into tystate */
2410 aryfil(tystate, nstate, 0);
2411 SLOOP(i)
2412 ITMLOOP(i, p, q)
2413 if((cc = *p->pitem) >= NTBASE)
2414 /* goto on c is possible */
2415 if(temp1[cc-NTBASE]) {
2416 tystate[i] = amem[indgo[i]+c];
2417 break;
2418 }
2419 }
2420
2421 /*
2422 * decide a shift/reduce conflict by precedence.
2423 * r is a rule number, t a token number
2424 * the conflict is in state s
2425 * temp1[t] is changed to reflect the action
2426 */
2427 void
2428 precftn(int r, int t, int s)
2429 {
2430 int lp, lt, action;
2431
2432 lp = levprd[r];
2433 lt = toklev[t];
2434 if(PLEVEL(lt) == 0 || PLEVEL(lp) == 0) {
2435
2436 /* conflict */
2437 if(foutput != 0)
2438 Bprint(foutput,
2439 "\n%d: shift/reduce conflict (shift %d(%d), red'n %d(%d)) on %s",
2440 s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), symnam(t));
2441 zzsrconf++;
2442 return;
2443 }
2444 if(PLEVEL(lt) == PLEVEL(lp))
2445 action = ASSOC(lt);
2446 else
2447 if(PLEVEL(lt) > PLEVEL(lp))
2448 action = RASC; /* shift */
2449 else
2450 action = LASC; /* reduce */
2451 switch(action) {
2452 case BASC: /* error action */
2453 temp1[t] = ERRCODE;
2454 break;
2455 case LASC: /* reduce */
2456 temp1[t] = -r;
2457 break;
2458 }
2459 }
2460
2461 /*
2462 * output state i
2463 * temp1 has the actions, lastred the default
2464 */
2465 void
2466 wract(int i)
2467 {
2468 int p, p0, p1, ntimes, tred, count, j, flag;
2469
2470 /* find the best choice for lastred */
2471 lastred = 0;
2472 ntimes = 0;
2473 TLOOP(j) {
2474 if(temp1[j] >= 0)
2475 continue;
2476 if(temp1[j]+lastred == 0)
2477 continue;
2478 /* count the number of appearances of temp1[j] */
2479 count = 0;
2480 tred = -temp1[j];
2481 levprd[tred] |= REDFLAG;
2482 TLOOP(p)
2483 if(temp1[p]+tred == 0)
2484 count++;
2485 if(count > ntimes) {
2486 lastred = tred;
2487 ntimes = count;
2488 }
2489 }
2490
2491 /*
2492 * for error recovery, arrange that, if there is a shift on the
2493 * error recovery token, `error', that the default be the error action
2494 */
2495 if(temp1[2] > 0)
2496 lastred = 0;
2497
2498 /* clear out entries in temp1 which equal lastred */
2499 TLOOP(p)
2500 if(temp1[p]+lastred == 0)
2501 temp1[p] = 0;
2502
2503 wrstate(i);
2504 defact[i] = lastred;
2505 flag = 0;
2506 TLOOP(p0)
2507 if((p1=temp1[p0]) != 0) {
2508 if(p1 < 0) {
2509 p1 = -p1;
2510 goto exc;
2511 }
2512 if(p1 == ACCEPTCODE) {
2513 p1 = -1;
2514 goto exc;
2515 }
2516 if(p1 == ERRCODE) {
2517 p1 = 0;
2518 exc:
2519 if(flag++ == 0)
2520 Bprint(ftable, "-1, %d,\n", i);
2521 Bprint(ftable, "\t%d, %d,\n", p0, p1);
2522 zzexcp++;
2523 continue;
2524 }
2525 Bprint(ftemp, "%d,%d,", p0, p1);
2526 zzacent++;
2527 }
2528 if(flag) {
2529 defact[i] = -2;
2530 Bprint(ftable, "\t-2, %d,\n", lastred);
2531 }
2532 Bprint(ftemp, "\n");
2533 }
2534
2535 /*
2536 * writes state i
2537 */
2538 void
2539 wrstate(int i)
2540 {
2541 int j0, j1;
2542 Item *pp, *qq;
2543 Wset *u;
2544
2545 if(fdebug) {
2546 if(lastred) {
2547 Bprint(fdebug, " 0, /*%d*/\n", i);
2548 } else {
2549 Bprint(fdebug, " \"");
2550 ITMLOOP(i, pp, qq)
2551 Bprint(fdebug, "%s\\n", writem(pp->pitem));
2552 if(tystate[i] == MUSTLOOKAHEAD)
2553 WSLOOP(wsets + (pstate[i+1] - pstate[i]), u)
2554 if(*u->pitem < 0)
2555 Bprint(fdebug, "%s\\n", writem(u->pitem));
2556 Bprint(fdebug, "\", /*%d*/\n", i);
2557 }
2558 }
2559 if(foutput == 0)
2560 return;
2561 Bprint(foutput, "\nstate %d\n", i);
2562 ITMLOOP(i, pp, qq)
2563 Bprint(foutput, "\t%s\n", writem(pp->pitem));
2564 if(tystate[i] == MUSTLOOKAHEAD)
2565 /* print out empty productions in closure */
2566 WSLOOP(wsets+(pstate[i+1]-pstate[i]), u)
2567 if(*u->pitem < 0)
2568 Bprint(foutput, "\t%s\n", writem(u->pitem));
2569
2570 /* check for state equal to another */
2571 TLOOP(j0)
2572 if((j1=temp1[j0]) != 0) {
2573 Bprint(foutput, "\n\t%s ", symnam(j0));
2574 /* shift, error, or accept */
2575 if(j1 > 0) {
2576 if(j1 == ACCEPTCODE)
2577 Bprint(foutput, "accept");
2578 else
2579 if(j1 == ERRCODE)
2580 Bprint(foutput, "error");
2581 else
2582 Bprint(foutput, "shift %d", j1);
2583 } else
2584 Bprint(foutput, "reduce %d (src line %d)", -j1, rlines[-j1]);
2585 }
2586
2587 /* output the final production */
2588 if(lastred)
2589 Bprint(foutput, "\n\t. reduce %d (src line %d)\n\n",
2590 lastred, rlines[lastred]);
2591 else
2592 Bprint(foutput, "\n\t. error\n\n");
2593
2594 /* now, output nonterminal actions */
2595 j1 = ntokens;
2596 for(j0 = 1; j0 <= nnonter; j0++) {
2597 j1++;
2598 if(temp1[j1])
2599 Bprint(foutput, "\t%s goto %d\n", symnam(j0+NTBASE), temp1[j1]);
2600 }
2601 }
2602
2603 void
2604 warray(char *s, int *v, int n)
2605 {
2606 int i;
2607
2608 Bprint(ftable, "static\tconst\tshort %s[] =\n{", s);
2609 for(i=0;;) {
2610 if(i%10 == 0)
2611 Bprint(ftable, "\n");
2612 Bprint(ftable, "%4d", v[i]);
2613 i++;
2614 if(i >= n) {
2615 Bprint(ftable, "\n};\n");
2616 break;
2617 }
2618 Bprint(ftable, ",");
2619 }
2620 }
2621
2622 /*
2623 * in order to free up the mem and amem arrays for the optimizer,
2624 * and still be able to output yyr1, etc., after the sizes of
2625 * the action array is known, we hide the nonterminals
2626 * derived by productions in levprd.
2627 */
2628
2629 void
2630 hideprod(void)
2631 {
2632 int i, j;
2633
2634 j = 0;
2635 levprd[0] = 0;
2636 PLOOP(1, i) {
2637 if(!(levprd[i] & REDFLAG)) {
2638 j++;
2639 if(foutput != 0)
2640 Bprint(foutput, "Rule not reduced: %s\n", writem(prdptr[i]));
2641 }
2642 levprd[i] = *prdptr[i] - NTBASE;
2643 }
2644 if(j)
2645 print("%d rules never reduced\n", j);
2646 }
2647
2648 void
2649 callopt(void)
2650 {
2651 int i, *p, j, k, *q;
2652
2653 /* read the arrays from tempfile and set parameters */
2654 finput = Bopen(tempname, OREAD);
2655 if(finput == 0)
2656 error("optimizer cannot open tempfile");
2657
2658 pgo[0] = 0;
2659 temp1[0] = 0;
2660 nstate = 0;
2661 nnonter = 0;
2662 for(;;) {
2663 switch(gtnm()) {
2664 case '\n':
2665 nstate++;
2666 pmem--;
2667 temp1[nstate] = pmem - mem0;
2668 case ',':
2669 continue;
2670 case '$':
2671 break;
2672 default:
2673 error("bad tempfile %s", tempname);
2674 }
2675 break;
2676 }
2677
2678 pmem--;
2679 temp1[nstate] = yypgo[0] = pmem - mem0;
2680 for(;;) {
2681 switch(gtnm()) {
2682 case '\n':
2683 nnonter++;
2684 yypgo[nnonter] = pmem-mem0;
2685 case ',':
2686 continue;
2687 case -1:
2688 break;
2689 default:
2690 error("bad tempfile");
2691 }
2692 break;
2693 }
2694 pmem--;
2695 yypgo[nnonter--] = pmem - mem0;
2696 for(i = 0; i < nstate; i++) {
2697 k = 32000;
2698 j = 0;
2699 q = mem0 + temp1[i+1];
2700 for(p = mem0 + temp1[i]; p < q ; p += 2) {
2701 if(*p > j)
2702 j = *p;
2703 if(*p < k)
2704 k = *p;
2705 }
2706 /* nontrivial situation */
2707 if(k <= j) {
2708 /* j is now the range */
2709 /* j -= k; *//* call scj */
2710 if(k > maxoff)
2711 maxoff = k;
2712 }
2713 tystate[i] = (temp1[i+1]-temp1[i]) + 2*j;
2714 if(j > maxspr)
2715 maxspr = j;
2716 }
2717
2718 /* initialize ggreed table */
2719 for(i = 1; i <= nnonter; i++) {
2720 ggreed[i] = 1;
2721 j = 0;
2722
2723 /* minimum entry index is always 0 */
2724 q = mem0 + yypgo[i+1] - 1;
2725 for(p = mem0+yypgo[i]; p < q ; p += 2) {
2726 ggreed[i] += 2;
2727 if(*p > j)
2728 j = *p;
2729 }
2730 ggreed[i] = ggreed[i] + 2*j;
2731 if(j > maxoff)
2732 maxoff = j;
2733 }
2734
2735 /* now, prepare to put the shift actions into the amem array */
2736 for(i = 0; i < ACTSIZE; i++)
2737 amem[i] = 0;
2738 maxa = amem;
2739 for(i = 0; i < nstate; i++) {
2740 if(tystate[i] == 0 && adb > 1)
2741 Bprint(ftable, "State %d: null\n", i);
2742 indgo[i] = YYFLAG1;
2743 }
2744 while((i = nxti()) != NOMORE)
2745 if(i >= 0)
2746 stin(i);
2747 else
2748 gin(-i);
2749
2750 /* print amem array */
2751 if(adb > 2 )
2752 for(p = amem; p <= maxa; p += 10) {
2753 Bprint(ftable, "%4d ", (int)(p-amem));
2754 for(i = 0; i < 10; ++i)
2755 Bprint(ftable, "%4d ", p[i]);
2756 Bprint(ftable, "\n");
2757 }
2758
2759 /* write out the output appropriate to the language */
2760 aoutput();
2761 osummary();
2762 ZAPFILE(tempname);
2763 }
2764
2765 void
2766 gin(int i)
2767 {
2768 int *p, *r, *s, *q1, *q2;
2769
2770 /* enter gotos on nonterminal i into array amem */
2771 ggreed[i] = 0;
2772
2773 q2 = mem0+ yypgo[i+1] - 1;
2774 q1 = mem0 + yypgo[i];
2775
2776 /* now, find amem place for it */
2777 for(p = amem; p < &amem[ACTSIZE]; p++) {
2778 if(*p)
2779 continue;
2780 for(r = q1; r < q2; r += 2) {
2781 s = p + *r + 1;
2782 if(*s)
2783 goto nextgp;
2784 if(s > maxa)
2785 if((maxa = s) > &amem[ACTSIZE])
2786 error("a array overflow");
2787 }
2788 /* we have found amem spot */
2789 *p = *q2;
2790 if(p > maxa)
2791 if((maxa = p) > &amem[ACTSIZE])
2792 error("a array overflow");
2793 for(r = q1; r < q2; r += 2) {
2794 s = p + *r + 1;
2795 *s = r[1];
2796 }
2797 pgo[i] = p-amem;
2798 if(adb > 1)
2799 Bprint(ftable, "Nonterminal %d, entry at %d\n", i, pgo[i]);
2800 return;
2801
2802 nextgp:;
2803 }
2804 error("cannot place goto %d\n", i);
2805 }
2806
2807 void
2808 stin(int i)
2809 {
2810 int *r, *s, n, flag, j, *q1, *q2;
2811
2812 tystate[i] = 0;
2813
2814 /* enter state i into the amem array */
2815 q2 = mem0+temp1[i+1];
2816 q1 = mem0+temp1[i];
2817 /* find an acceptable place */
2818 for(n = -maxoff; n < ACTSIZE; n++) {
2819 flag = 0;
2820 for(r = q1; r < q2; r += 2) {
2821 if((s = *r + n + amem) < amem)
2822 goto nextn;
2823 if(*s == 0)
2824 flag++;
2825 else
2826 if(*s != r[1])
2827 goto nextn;
2828 }
2829
2830 /* check that the position equals another only if the states are identical */
2831 for(j=0; j<nstate; j++) {
2832 if(indgo[j] == n) {
2833
2834 /* we have some disagreement */
2835 if(flag)
2836 goto nextn;
2837 if(temp1[j+1]+temp1[i] == temp1[j]+temp1[i+1]) {
2838
2839 /* states are equal */
2840 indgo[i] = n;
2841 if(adb > 1)
2842 Bprint(ftable,
2843 "State %d: entry at %d equals state %d\n",
2844 i, n, j);
2845 return;
2846 }
2847
2848 /* we have some disagreement */
2849 goto nextn;
2850 }
2851 }
2852
2853 for(r = q1; r < q2; r += 2) {
2854 if((s = *r+n+amem) >= &amem[ACTSIZE])
2855 error("out of space in optimizer a array");
2856 if(s > maxa)
2857 maxa = s;
2858 if(*s != 0 && *s != r[1])
2859 error("clobber of a array, pos'n %d, by %d", s-amem, r[1]);
2860 *s = r[1];
2861 }
2862 indgo[i] = n;
2863 if(adb > 1)
2864 Bprint(ftable, "State %d: entry at %d\n", i, indgo[i]);
2865 return;
2866 nextn:;
2867 }
2868 error("Error; failure to place state %d\n", i);
2869 }
2870
2871 /*
2872 * finds the next i
2873 */
2874 int
2875 nxti(void)
2876 {
2877 int i, max, maxi;
2878
2879 max = 0;
2880 maxi = 0;
2881 for(i = 1; i <= nnonter; i++)
2882 if(ggreed[i] >= max) {
2883 max = ggreed[i];
2884 maxi = -i;
2885 }
2886 for(i = 0; i < nstate; ++i)
2887 if(tystate[i] >= max) {
2888 max = tystate[i];
2889 maxi = i;
2890 }
2891 if(nxdb)
2892 Bprint(ftable, "nxti = %d, max = %d\n", maxi, max);
2893 if(max == 0)
2894 return NOMORE;
2895 return maxi;
2896 }
2897
2898 /*
2899 * write summary
2900 */
2901 void
2902 osummary(void)
2903 {
2904
2905 int i, *p;
2906
2907 if(foutput == 0)
2908 return;
2909 i = 0;
2910 for(p = maxa; p >= amem; p--)
2911 if(*p == 0)
2912 i++;
2913
2914 Bprint(foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
2915 (int)(pmem-mem0+1), MEMSIZE, (int)(maxa-amem+1), ACTSIZE);
2916 Bprint(foutput, "%d table entries, %d zero\n", (int)(maxa-amem+1), i);
2917 Bprint(foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff);
2918 }
2919
2920 /*
2921 * this version is for C
2922 * write out the optimized parser
2923 */
2924 void
2925 aoutput(void)
2926 {
2927 Bprint(ftable, "#define\tYYLAST\t%d\n", (int)(maxa-amem+1));
2928 arout("yyact", amem, (maxa-amem)+1);
2929 arout("yypact", indgo, nstate);
2930 arout("yypgo", pgo, nnonter+1);
2931 }
2932
2933 void
2934 arout(char *s, int *v, int n)
2935 {
2936 int i;
2937
2938 Bprint(ftable, "static\tconst\tshort %s[] =\n{", s);
2939 for(i = 0; i < n;) {
2940 if(i%10 == 0)
2941 Bprint(ftable, "\n");
2942 Bprint(ftable, "%4d", v[i]);
2943 i++;
2944 if(i == n)
2945 Bprint(ftable, "\n};\n");
2946 else
2947 Bprint(ftable, ",");
2948 }
2949 }
2950
2951 /*
2952 * read and convert an integer from the standard input
2953 * return the terminating character
2954 * blanks, tabs, and newlines are ignored
2955 */
2956 int
2957 gtnm(void)
2958 {
2959 int sign, val, c;
2960
2961 sign = 0;
2962 val = 0;
2963 while((c=Bgetrune(finput)) != Beof) {
2964 if(isdigit(c)) {
2965 val = val*10 + c-'0';
2966 continue;
2967 }
2968 if(c == '-') {
2969 sign = 1;
2970 continue;
2971 }
2972 break;
2973 }
2974 if(sign)
2975 val = -val;
2976 *pmem++ = val;
2977 if(pmem >= &mem0[MEMSIZE])
2978 error("out of space");
2979 return c;
2980 }