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