GopherProxy

	yacc.c - 9base - revived minimalist port of Plan 9 userland to Unix
	git clone git://git.suckless.org/9base
	Log
	Files
	Refs
	README
	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 debuggi…
	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 ru…
	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 nont…
	180 int cnamsz = CNAMSZ; /* size of cnames */
	181 char* cnamp = cnames; /* place where next name is …
	182 int ndefout = 4; /* number of defined symbols outp…
	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 …
	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…
	219 int levprd[NPROD]; /* precedence levels for the pr…
	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 o…
	226 int tystate[NSTATES]; /* contains type information about t…
	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 nontermina…
	230 int mstates[NSTATES]; /* chain of overflows of term/nonter…
	231 int lastred; /* the number of the last reduction …
	232
	233 /* lookahead set information */
	234
	235 Lkset lkst[LSETSIZE];
	236 int nolook; /* flag to turn off lookahead …
	237 int tbitset; /* size of lookahead sets */
	238 int nlset = 0; /* next lookahead set index */
	239 int nolook = 0; /* flag to suppress lookahead comp…
	240 Lkset clset; /* temporary storage for lookahead …
	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 positi…
	251 int indgo[NSTATES]; /* index to the stored goto ta…
	252
	253 /* temporary vector, indexable by states, terms, or ntokens */
	254
	255 int temp1[TEMPSIZE]; /* temporary storage, indexed by term…
	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 product…
	285 Lkset* pfirst[NNONTERM+2]; /* vector of pointers to first …
	286 int pempty[NNONTERM+1]; /* vector of nonterminals nontrivi…
	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…
	388 cempty(); /* make a table of which nonterminals c…
	389 cpfir(); /* make a table of firsts of nonterminal…
	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…
	436 print(" %s and %s\n", tokset[i].n…
	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…
	454 print(" %s and %s\n", tokset[i].n…
	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 temp…
	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 confl…
	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…
	590 (int)(zzmemsz-mem0), MEMSIZE, (int)(memp-amem), …
	591 Bprint(foutput, "%d/%d distinct lookahead sets\n", nlset…
	592 Bprint(foutput, "%d extra closures\n", zzclose - 2*nstat…
	593 Bprint(foutput, "%d shift entries, %d exceptions\n", zza…
	594 Bprint(foutput, "%d goto entries\n", zzgoent);
	595 Bprint(foutput, "%d entries saved by goto default\n", zz…
	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 n…
	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].…
	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[npr…
	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.…
	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 nu…
	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 =…
	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…
	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), …
	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 ne…
	881 /* set pempty to WHONOWS */
	882 aryfil(pempty, nnonter+1, WHOKNOWS);
	883
	884 /* now, look at productions, marking nonterminals which derive s…
	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 symb…
	902 if(i == 0)
	903 continue;
	904 if(pempty[i] != OK) {
	905 fatfl = 0;
	906 error("nonterminal %s never derives any token st…
	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 deri…
	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-N…
	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, o…
	954 * different type...
	955 * someday, alloc should be used to allocate all this stuff... f…
	956 * accept that if pointers don't fit in integers, there is a pro…
	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-ws…
	986 tystate[i] = MUSTLOOKAHE…
	987 continue;
	988 }
	989 /* do a goto on c */
	990 WSLOOP(p, q)
	991 /* this item contributes to the …
	992 if(c == *(q->pitem)) {
	993 putitem(q->pitem+1, &q->…
	994 q->flag = 1;
	995 }
	996 if(c < NTBASE)
	997 state(c); /* register new…
	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 …
	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 b…
	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.lse…
	1067 break;
	1068 }
	1069 /* nonterminal symbol */
	1070 setunion(clset.lset, pfi…
	1071 if(!pempty[ch-NTBASE])
	1072 break;
	1073 }
	1074 if(ch <= 0)
	1075 setunion(clset.lset, v->…
	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, …
	1095 v->flag = work =…
	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] = cls…
	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 redeclaratio…
	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 redeclaratio…
	1295 nontrst[t-NTBASE…
	1296 else
	1297 nontrst[t-NTBASE].value …
	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 non…
	1347 if(lev) {
	1348 if(ASSOC(toklev[j]))
	1349 error("redeclaration of …
	1350 SETASC(toklev[j], lev);
	1351 SETPLEV(toklev[j], i);
	1352 }
	1353 if(ty) {
	1354 if(TYPE(toklev[j]))
	1355 error("redeclaration of …
	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 typ…
	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, …
	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 ru…
	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 g…
	1438 mem++;
	1439 } else
	1440 error("illegal rule: missing semicolon o…
	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 %%pr…
	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 num…
	1477 * move the contents down, and make room…
	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] & ~ACTFL…
	1490 levprd[nprod] = ACTFLAG;
	1491 if(++nprod >= NPROD)
	1492 error("more than %d rules", NPRO…
	1493 prdptr[nprod] = p;
	1494
	1495 /* make the action appear in the origina…
	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…
	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 ha…
	1516 else
	1517 if(tempty >= NTBASE)
	1518 tempty = nontrst[tempty-NTBASE].…
	1519 else
	1520 tempty = TYPE(toklev[tempty]);
	1521 if(tempty != nontrst[*prdptr[nprod]-NTBASE].valu…
	1522 error("default action causes potential t…
	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, in…
	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 = 64s[2] + 8s[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[] …
	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 = Bgetru…
	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", to…
	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 pres…
	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\…
	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"…
	2049 if(tok < 0)
	2050 tok = fdtype(prdptr[nprod][j+off…
	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 identifi…
	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 num…
	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…
	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[] =…
	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, (Lks…
	2213 temp1[c] = state(c);
	2214 } else
	2215 if(c > NTBASE && temp1[(c -= NTBASE) + n…
	2216 temp1[c+ntokens] = amem[indgo[i]…
	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) { /* re…
	2235 if(foutput)
	2236 Bprint(f…
	2237 …
	2238 …
	2239 …
	2240 …
	2241 if(-temp1[k] > l…
	2242 temp1[k]…
	2243 zzrrconf++;
	2244 } else
	2245 /* potential shi…
	2246 precftn( lastred…
	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", yyd…
	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)…
	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 produc…
	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(%…
	2440 s, temp1[t], PLEVEL(lt), r, PLEVEL(lp), …
	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 …
	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])…
	2554 if(*u->pitem < 0)
	2555 Bprint(fdebug, "%s\\n", …
	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->pite…
	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 %…
	2583 } else
	2584 Bprint(foutput, "reduce %d (src line %d)…
	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+NTB…
	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\…
	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", …
	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 st…
	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…
	2838
	2839 /* states are equal */
	2840 indgo[i] = n;
	2841 if(adb > 1)
	2842 Bprint(ftable,
	2843 "State %d: entry at %d e…
	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 …
	2860 *s = r[1];
	2861 }
	2862 indgo[i] = n;
	2863 if(adb > 1)
	2864 Bprint(ftable, "State %d: entry at %d\n", i, ind…
	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…
	2915 (int)(pmem-mem0+1), MEMSIZE, (int)(maxa-amem+1), ACTSIZE…
	2916 Bprint(foutput, "%d table entries, %d zero\n", (int)(maxa-amem+1…
	2917 Bprint(foutput, "maximum spread: %d, maximum offset: %d\n", maxs…
	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 }