xref: /illumos-gate/usr/src/cmd/sgs/yacc/common/y1.c (revision caeaa75185132c7efab72ba0c9e7256bae1b9b95)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*
22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
23  * Use is subject to license terms.
24  */
25 
26 /* Copyright (c) 1988 AT&T */
27 /* All Rights Reserved */
28 
29 #include "dextern.h"
30 #include <sys/param.h>
31 #include <sys/errno.h>
32 #include <unistd.h>
33 #include <locale.h>
34 #include <stdarg.h>	/* For error() */
35 
36 static void mktbls(void);
37 static void others(void);
38 static void summary(void);
39 static wchar_t *chcopy(wchar_t *, wchar_t *);
40 static int setunion(int *, int *);
41 static void prlook(LOOKSETS *);
42 static void cpres(void);
43 static void cpfir(void);
44 static void cempty(void);
45 static void stagen(void);
46 static LOOKSETS *flset(LOOKSETS *);
47 static void exp_lkst(void);
48 static void exp_wsets(void);
49 static void exp_states(void);
50 static void exp_psmem(void);
51 
52 	/* lookahead computations */
53 
54 int TBITSET;
55 static int tbitset;	/* size of lookahead sets */
56 LOOKSETS *lkst;
57 static int lsetsize;
58 
59 static int nlset = 0;	/* next lookahead set index */
60 int nolook = 0;		/* flag to suppress lookahead computations */
61 static LOOKSETS clset;  /* temporary storage for lookahead computations */
62 
63 static ITEM *psmem, *zzmemsz;
64 static int new_pstsize = PSTSIZE;
65 
66 	/* working set computations */
67 
68 WSET *wsets;
69 int cwp;
70 static int wsetsz = 0;		/* number of WSET items in wsets block */
71 
72 	/* state information */
73 
74 int nstate = 0;			/* number of states */
75 static int nstatesz = NSTATES;	/* number of state space allocated	*/
76 ITEM **pstate;			/* ptr to descriptions of the states	*/
77 int *tystate;			/* contains type info about the states	*/
78 int *indgo;			/* index to the stored goto table	*/
79 static int *tmp_lset;
80 static int *tstates;		/* states generated by terminal gotos	*/
81 static int *ntstates;		/* states generated by non-term gotos	*/
82 static int *mstates;		/* chain of overflows of term/nonterm	*/
83 				/* generation lists			*/
84 
85 	/* storage for the actions in the parser */
86 
87 int *amem, *memp;		/* next free action table position */
88 int new_actsize = ACTSIZE;
89 
90 	/* other storage areas */
91 
92 int *temp1;		/* temp storate, indexed by terms+ntokens or states */
93 int lineno = 0;		/* current input line number */
94 int size;
95 static int fatfl = 1;	/* if on, error is fatal */
96 static int nerrors = 0;	/* number of errors */
97 
98 	/* storage for information about the nonterminals */
99 
100 static int ***pres;		/* vector of pointers to productions	*/
101 				/* yielding each nonterminal		*/
102 static LOOKSETS **pfirst;	/* vector of pointers to first sets for	*/
103 				/* each nonterminal			*/
104 static int *pempty;		/* vector of nonterminals nontrivially	*/
105 				/* deriving e				*/
106 extern int nprodsz;
107 
108 int
main(int argc,char * argv[])109 main(int argc, char *argv[])
110 {
111 	(void) setlocale(LC_ALL, "");
112 #if !defined(TEXT_DOMAIN)	/* Should be defined by cc -D */
113 #define	TEXT_DOMAIN "SYS_TEST"	/* Use this only if it weren't */
114 #endif
115 	(void) textdomain(TEXT_DOMAIN);
116 
117 	setup(argc, argv);		/* initialize and read productions */
118 	TBITSET = NWORDS(ntoksz*LKFACTOR);
119 	tbitset = NWORDS(ntokens*LKFACTOR);
120 	mktbls();
121 	cpres();	/* make table of which productions yield a */
122 			/* given nonterminal */
123 	cempty();	/* make a table of which nonterminals can match	*/
124 			/* the empty string */
125 	cpfir();	/* make a table of firsts of nonterminals */
126 	stagen();	/* generate the states	*/
127 	output();	/* write the states and the tables */
128 	go2out();
129 	hideprod();
130 	summary();
131 	callopt();
132 	others();
133 	return (0);
134 }
135 
136 
137 static void
mktbls(void)138 mktbls(void)
139 {
140 	int i;
141 
142 	size = ntoksz + nnontersz +1;
143 	if (size < nstatesz)
144 		size = nstatesz;
145 	if (size < new_memsize)
146 		size = new_memsize;
147 
148 	amem = (int *) malloc(sizeof (int) * new_actsize);
149 	psmem = (ITEM *) malloc(sizeof (ITEM) * new_pstsize);
150 	if ((psmem == NULL) || (amem == NULL))
151 /*
152  * TRANSLATION_NOTE  -- This is a message from yacc.
153  *	This message is passed to error() function.
154  *	This error happens when yacc could not allocate
155  *	initial memory to be used for internal tables.
156  *
157  *	You may just translate this as:
158  *	'Could not allocate internally used memory.'
159  */
160 		error(gettext(
161 		"couldn't allocate initial table"));
162 	zzmemsz = psmem;
163 	memp = amem;
164 
165 	/*
166 	 * For lkst
167 	 */
168 #define	INIT_LSIZE	nnontersz * LKFACTOR
169 
170 	tmp_lset = (int *)
171 	    calloc((size_t)(TBITSET * (INIT_LSIZE+1)), sizeof (int));
172 	if (tmp_lset == NULL)
173 /*
174  * TRANSLATION_NOTE  -- This is a message from yacc.
175  *	This message is passed to error() function.
176  *	Yacc could not allocate memory for table named lookset.
177  *	Do not translate 'lookset'.
178  *
179  *	You may just translate this as:
180  *	'Could not allocate internally used memory.'
181  */
182 		error(gettext(
183 		"could not allocate lookset array"));
184 	lkst = (LOOKSETS *) malloc(sizeof (LOOKSETS) * (INIT_LSIZE + 1));
185 	for (i = 0; i <= INIT_LSIZE; ++i)
186 		lkst[i].lset = tmp_lset + TBITSET * i;
187 	tmp_lset = NULL;
188 
189 	/*
190 	 * For wsets
191 	 */
192 	tmp_lset = (int *)
193 	    calloc((size_t)(TBITSET * (nnontersz+1)), sizeof (int));
194 	if (tmp_lset == NULL)
195 		error(gettext(
196 		"could not allocate lookset array"));
197 	wsets = (WSET *) malloc(sizeof (WSET) * (nnontersz + 1));
198 	for (i = 0; i <= nnontersz; ++i)
199 		wsets[i].ws.lset = tmp_lset + TBITSET * i;
200 	tmp_lset = NULL;
201 
202 	clset.lset = (int *)malloc(sizeof (int)*TBITSET);
203 	tstates = (int *)malloc(sizeof (int)*(ntoksz + 1));
204 	ntstates = (int *)malloc(sizeof (int)*(nnontersz + 1));
205 	temp1 = (int *)malloc(sizeof (int)*size);
206 	pres = (int ***)malloc(sizeof (int **)*(nnontersz + 2));
207 	pfirst = (LOOKSETS **)malloc(sizeof (LOOKSETS *)*(nnontersz + 2));
208 	pempty = (int *)malloc(sizeof (int)*(nnontersz + 1));
209 
210 	pstate = (ITEM **)malloc(sizeof (ITEM *)*(nstatesz+2));
211 	tystate = (int *)malloc(sizeof (int)*nstatesz);
212 	indgo = (int *)malloc(sizeof (int)*nstatesz);
213 	mstates = (int *)malloc(sizeof (int)*nstatesz);
214 	defact = (int *)malloc(sizeof (int)*nstatesz);
215 
216 	if ((lkst == NULL) || (wsets == NULL) || (tstates == NULL) ||
217 	    (ntstates == NULL) || (temp1 == NULL) || (pres == NULL) ||
218 	    (pfirst == NULL) || (pempty == NULL) || (pstate == NULL) ||
219 	    (tystate == NULL) || (indgo == NULL) || (mstates == NULL) ||
220 	    (defact == NULL) || (clset.lset == NULL))
221 /*
222  * TRANSLATION_NOTE  -- This is a message from yacc.
223  *	This message is passed to error() function.
224  *	Do not translate mktbls(). It is a function name.
225  *
226  *	You may just translate this as:
227  *	'Could not allocate internally used memory.'
228  */
229 			error(gettext(
230 			"cannot allocate tables in mktbls()"));
231 
232 	aryfil(ntstates, nnontersz+1, 0);
233 	aryfil(tstates, ntoksz+1, 0);
234 	wsetsz = nnontersz + 1;
235 	lsetsize = INIT_LSIZE + 1;
236 }
237 
238 /* put out other arrays, copy the parsers */
239 static void
others(void)240 others(void)
241 {
242 	extern int gen_lines;
243 	int c, i, j;
244 	int tmpline;
245 
246 	finput = fopen(parser, "r");
247 	if (finput == NULL)
248 /*
249  * TRANSLATION_NOTE  -- This is a message from yacc.
250  *	This message is passed to error() function.
251  *	This error message is issued when yacc can not find
252  *	the parser to be copied.
253  */
254 		error(gettext(
255 		"cannot find parser %s"),
256 		    parser);
257 
258 	warray(L"yyr1", levprd, nprod);
259 
260 	aryfil(temp1, nprod, 0);
261 					/* had_act[i] is either 1 or 0 */
262 	PLOOP(1, i)
263 		temp1[i] = ((prdptr[i+1] - prdptr[i]-2) << 1) | had_act[i];
264 	warray(L"yyr2", temp1, nprod);
265 
266 	aryfil(temp1, nstate, -10000000);
267 	TLOOP(i)
268 		for (j = tstates[i]; j != 0; j = mstates[j])
269 			temp1[j] = tokset[i].value;
270 	NTLOOP(i)
271 		for (j = ntstates[i]; j != 0; j = mstates[j])
272 			temp1[j] = -i;
273 	warray(L"yychk", temp1, nstate);
274 
275 	warray(L"yydef", defact, nstate);
276 
277 	if ((fdebug = fopen(DEBUGNAME, "r")) == NULL)
278 		error("cannot open yacc.debug");
279 	while ((c = getwc(fdebug)) != EOF)
280 		(void) putwc(c, ftable);
281 	(void) fclose(fdebug);
282 	ZAPFILE(DEBUGNAME);
283 
284 	if (gen_lines)
285 		(void) fprintf(ftable, "# line\t1 \"%s\"\n", parser);
286 	tmpline = 1;
287 	/* copy parser text */
288 	while ((c = getwc(finput)) != EOF) {
289 		if (c == '\n')
290 			tmpline++;
291 		if (c == L'$') {
292 			if ((c = getwc(finput)) != L'A')
293 				(void) putwc(L'$', ftable);
294 			else { /* copy actions */
295 				tmpline++;
296 				faction = fopen(ACTNAME, "r");
297 				if (faction == NULL)
298 /*
299  * TRANSLATION_NOTE  -- This is a message from yacc.
300  *	This message is passed to error() function.
301  *	This error is issued when yacc can not open a
302  *	temporary file to be used. You do not need to
303  *	use the word 'tempfile'. You can translate it to
304  *	mean 'temporary file'.
305  */
306 					error(gettext(
307 					"cannot open action tempfile"));
308 				while ((c = getwc(faction)) != EOF)
309 					(void) putwc(c, ftable);
310 				(void) fclose(faction);
311 				if (gen_lines)
312 					(void) fprintf(ftable,
313 					    "\n# line\t%d \"%s\"",
314 					    tmpline,
315 					    parser);
316 				ZAPFILE(ACTNAME);
317 				c = getwc(finput);
318 			}
319 		}
320 		(void) putwc(c, ftable);
321 	}
322 	(void) fclose(ftable);
323 }
324 
325 
326 /* copies string q into p, returning next free char ptr */
327 static wchar_t *
chcopy(wchar_t * p,wchar_t * q)328 chcopy(wchar_t *p, wchar_t *q)
329 {
330 	while ((*p = *q++) != L'\0')
331 		++p;
332 	return (p);
333 }
334 
335 #define	ISIZE 400
336 /* creates output string for item pointed to by pp */
337 wchar_t *
writem(int * pp)338 writem(int *pp)
339 {
340 	int i, *p;
341 	static int isize = ISIZE;
342 	static wchar_t *sarr = NULL;
343 	wchar_t *q;
344 
345 	if (sarr == NULL) {
346 		sarr = (wchar_t *)malloc(sizeof (wchar_t) * isize);
347 		if (sarr == NULL)
348 /*
349  * TRANSLATION_NOTE  -- This is a message from yacc.
350  *	This message is passed to error() function.
351  *	This error is issued when yacc could not allocate
352  *	memory for internally used array.
353  *
354  *	You may just translate this as:
355  *	'Could not allocate internally used memory.'
356  */
357 			error(gettext(
358 			"could not allocate output string array"));
359 		for (i = 0; i < isize; ++i)
360 			sarr[i] = L' ';
361 	}
362 	for (p = pp; *p > 0; ++p) /* NULL */
363 		;
364 	p = prdptr[-*p];
365 	q = chcopy(sarr, nontrst[*p-NTBASE].name);
366 	q = chcopy(q, L" : ");
367 
368 	for (;;) {
369 		*q++ = ++p == pp ? L'_' : L' ';
370 		*q = 0;
371 		if ((i = *p) <= 0)
372 			break;
373 		q = chcopy(q, symnam(i));
374 		while (q > &sarr[isize-30]) {
375 			static wchar_t *sarrbase;
376 
377 			sarrbase = sarr;
378 			isize += ISIZE;
379 			sarr = (wchar_t *)
380 			    realloc((char *)sarr, sizeof (*sarr) * isize);
381 			if (sarr == NULL)
382 /*
383  * TRANSLATION_NOTE  -- This is a message from yacc.
384  *	This message is passed to error() function.
385  *	This error is issued when yacc could not allocate
386  *	memory for internally used array.
387  *
388  *	You may just translate this as:
389  *	'Could not allocate internally used memory.'
390  */
391 				error(gettext(
392 				    "cannot expand sarr arrays"));
393 			q = q - sarrbase + sarr;
394 		}
395 	}
396 
397 	/* an item calling for a reduction */
398 	if ((i = *pp) < 0) {
399 		q = chcopy(q, L"    (");
400 		(void) wsprintf(q, "%d)", -i);
401 	}
402 	return (sarr);
403 }
404 
405 /* return a pointer to the name of symbol i */
406 wchar_t *
symnam(int i)407 symnam(int i)
408 {
409 	wchar_t *cp;
410 
411 	cp = (i >= NTBASE) ? nontrst[i-NTBASE].name : tokset[i].name;
412 	if (*cp == L' ')
413 		++cp;
414 	return (cp);
415 }
416 
417 static int zzcwp = 0;
418 static int zzclose = 0;
419 int zzgoent = 0;
420 int zzgobest = 0;
421 int zzacent = 0;
422 int zzexcp = 0;
423 int zzsrconf = 0;
424 int zzrrconf = 0;
425 
426 /* output the summary on the tty */
427 static void
summary(void)428 summary(void)
429 {
430 	if (foutput != NULL) {
431 		(void) fprintf(foutput,
432 		    "\n%d/%d terminals, %d/%d nonterminals\n",
433 		    ntokens, ntoksz, nnonter, nnontersz);
434 		(void) fprintf(foutput,
435 		    "%d/%d grammar rules, %d/%d states\n",
436 		    nprod, nprodsz, nstate, nstatesz);
437 		(void) fprintf(foutput,
438 		"%d shift/reduce, %d reduce/reduce conflicts reported\n",
439 		    zzsrconf, zzrrconf);
440 		(void) fprintf(foutput,
441 		    "%d/%d working sets used\n", zzcwp, wsetsz);
442 		(void) fprintf(foutput,
443 		    "memory: states,etc. %" PRIdPTR
444 		    "/%d, parser %" PRIdPTR "/%d\n",
445 		    mem-tracemem, new_memsize,
446 		    memp-amem, new_actsize);
447 		(void) fprintf(foutput,
448 		    "%d/%d distinct lookahead sets\n", nlset, lsetsize);
449 		(void) fprintf(foutput,
450 		    "%d extra closures\n", zzclose - 2*nstate);
451 		(void) fprintf(foutput,
452 		    "%d shift entries, %d exceptions\n", zzacent, zzexcp);
453 		(void) fprintf(foutput,
454 		    "%d goto entries\n", zzgoent);
455 		(void) fprintf(foutput,
456 		    "%d entries saved by goto default\n", zzgobest);
457 	}
458 	if (zzsrconf != 0 || zzrrconf != 0) {
459 /*
460  * TRANSLATION_NOTE  -- This is a message from yacc.
461  *	You may just leave this message un-translated.
462  *	This message only makes sense to those who knows
463  *	how yacc works, and the person should know what
464  *	this message means in English.
465  */
466 		(void) fprintf(stderr, gettext(
467 		    "\nconflicts: "));
468 		if (zzsrconf)
469 			(void) fprintf(stderr, "%d shift/reduce", zzsrconf);
470 		if (zzsrconf && zzrrconf)
471 			(void) fprintf(stderr, ", ");
472 		if (zzrrconf)
473 			(void) fprintf(stderr, "%d reduce/reduce", zzrrconf);
474 		(void) fprintf(stderr, "\n");
475 	}
476 
477 	if (ftemp != NULL)
478 		(void) fclose(ftemp);
479 	if (fdefine != NULL)
480 		(void) fclose(fdefine);
481 }
482 
483 /* write out error comment */
484 /*PRINTFLIKE1*/
485 void
error(char * s,...)486 error(char *s, ...)
487 {
488 	extern char *infile;
489 	va_list	ap;
490 
491 	va_start(ap, s);
492 
493 	++nerrors;
494 	if (!lineno)
495 /*
496  * TRANSLATION_NOTE  -- This is a message from yacc.
497  *	This message is a prefix to the error messages
498  *	passed to error() function.
499  */
500 		(void) fprintf(stderr, gettext(
501 		    "command line: fatal: "));
502 	else {
503 		(void) fprintf(stderr, "\"%s\", ", infile);
504 /*
505  * TRANSLATION_NOTE  -- This is a message from yacc.
506  *	This message is a prefix to the error messages
507  *	passed to error() function.
508  */
509 		(void) fprintf(stderr, gettext(
510 		    "line %d: fatal: "),
511 		    lineno);
512 	}
513 	(void) vfprintf(stderr, s, ap);
514 	(void) fprintf(stderr, "\n");
515 	va_end(ap);
516 	if (!fatfl)
517 		return;
518 	summary();
519 	exit(1);
520 }
521 
522 /*
523  * Print out a warning message.
524  */
525 /*PRINTFLIKE2*/
526 void
warning(int flag,char * s,...)527 warning(int flag, char *s, ...)
528 {
529 	extern char *infile;
530 	va_list	ap;
531 	va_start(ap, s);
532 
533 	(void) fprintf(stderr, "\"%s\", ", infile);
534 	/*
535 	 * If flag, print lineno as well.
536 	 */
537 	if (flag == 0)
538 /*
539  * TRANSLATION_NOTE  -- This is a message from yacc.
540  *	This message is a prefix to the warning messages
541  *	passed to warning() function.
542  */
543 		(void) fprintf(stderr, gettext(
544 		    "warning: "));
545 	else
546 /*
547  * TRANSLATION_NOTE  -- This is a message from yacc.
548  *	This message is a prefix to the warning messages
549  *	passed to warning() function.
550  */
551 		(void) fprintf(stderr, gettext(
552 		    "line %d: warning: "),
553 		    lineno);
554 	(void) vfprintf(stderr, s, ap);
555 	(void) fprintf(stderr, "\n");
556 	va_end(ap);
557 }
558 
559 /* set elements 0 through n-1 to c */
560 void
aryfil(int * v,int n,int c)561 aryfil(int *v, int n, int c)
562 {
563 	int i;
564 	for (i = 0; i < n; ++i)
565 		v[i] = c;
566 }
567 
568 /* set a to the union of a and b */
569 /* return 1 if b is not a subset of a, 0 otherwise */
570 static int
setunion(int * a,int * b)571 setunion(int *a, int *b)
572 {
573 	int i, x, sub;
574 
575 	sub = 0;
576 	SETLOOP(i) {
577 		*a = (x = *a) | *b++;
578 		if (*a++ != x)
579 			sub = 1;
580 	}
581 	return (sub);
582 }
583 
584 static void
prlook(LOOKSETS * p)585 prlook(LOOKSETS *p)
586 {
587 	int j, *pp;
588 	pp = p->lset;
589 	if (pp == 0)
590 		(void) fprintf(foutput, "\tNULL");
591 	else {
592 		(void) fprintf(foutput, " { ");
593 		TLOOP(j) {
594 			if (BIT(pp, j))
595 				(void) fprintf(foutput, "%ws ", symnam(j));
596 		}
597 		(void) fprintf(foutput,  "}");
598 	}
599 }
600 
601 /*
602  * compute an array with the beginnings of  productions yielding
603  * given nonterminals
604  * The array pres points to these lists
605  * the array pyield has the lists: the total size is only NPROD+1
606  */
607 static void
cpres(void)608 cpres(void)
609 {
610 	int **ptrpy;
611 	int **pyield;
612 	int c, j, i;
613 
614 	/*
615 	 * 2/29/88 -
616 	 * nprodsz is the size of the tables describing the productions.
617 	 * Normally this will be NPROD unless the production tables have
618 	 * been expanded, in which case the tables will be NPROD * N(where
619 	 * N is the number of times the tables had to be expanded.)
620 	 */
621 	if ((pyield = (int **) malloc(sizeof (int *) * nprodsz)) == NULL)
622 /*
623  * TRANSLATION_NOTE  -- This is a message from yacc.
624  *	This message is passed to error() function.
625  *	This error is issued when yacc could not allocate
626  *	memory for internally used array.
627  *
628  *	pyield is name of an array. You should not try to translate
629  *	this word.
630  *
631  *	You may just translate this as:
632  *	'Could not allocate internally used memory.'
633  */
634 		error(gettext(
635 		"cannot allocate space for pyield array"));
636 
637 	ptrpy = pyield;
638 
639 	NTLOOP(i) {
640 		c = i+NTBASE;
641 		pres[i] = ptrpy;
642 		fatfl = 0;  /* make undefined  symbols  nonfatal */
643 		PLOOP(0, j) {
644 			if (*prdptr[j] == c)	/* linear search for all c's */
645 				*ptrpy++ =  prdptr[j] + 1;
646 		}
647 		if (pres[i] == ptrpy) {		/* c not found */
648 /*
649  * TRANSLATION_NOTE  -- This is a message from yacc.
650  *	This message is passed to error() function.
651  *	Ask somebody who knows yacc how to translate nonterminal or
652  *	look at translated yacc document.
653  */
654 			error(gettext(
655 			"undefined nonterminal: %ws"),
656 			    nontrst[i].name);
657 		}
658 	}
659 	pres[i] = ptrpy;
660 	fatfl = 1;
661 	if (nerrors) {
662 		summary();
663 		exit(1);
664 	}
665 	if (ptrpy != &pyield[nprod])
666 /*
667  * TRANSLATION_NOTE  -- This is a message from yacc.
668  *	This message is passed to error() function.
669  *	This is an internal error message.
670  *	Very little use to user. You may leave it
671  *	un-translated.
672  *
673  *	pyied is name of an array. Do not translate it.
674  */
675 		error(gettext(
676 		"internal Yacc error: pyield %d"),
677 		    ptrpy-&pyield[nprod]);
678 }
679 
680 static int indebug = 0;
681 /* compute an array with the first of nonterminals */
682 static void
cpfir(void)683 cpfir(void)
684 {
685 	int *p, **s, i, **t, ch, changes;
686 
687 	zzcwp = nnonter;
688 	NTLOOP(i) {
689 		aryfil(wsets[i].ws.lset, tbitset, 0);
690 		t = pres[i+1];
691 		/* initially fill the sets */
692 		for (s = pres[i]; s < t; ++s) {
693 			/* check if ch is non-terminal */
694 			for (p = *s; (ch = *p) > 0; ++p) {
695 				if (ch < NTBASE) {	/* should be token */
696 					SETBIT(wsets[i].ws.lset, ch);
697 					break;
698 				} else if (!pempty[ch-NTBASE])
699 					break;
700 			}
701 		}
702 	}
703 
704 	/* now, reflect transitivity */
705 
706 	changes = 1;
707 	while (changes) {
708 		changes = 0;
709 		NTLOOP(i) {
710 			t = pres[i+1];
711 			for (s = pres[i]; s < t; ++s) {
712 				for (p = *s; (ch = (*p-NTBASE)) >= 0; ++p) {
713 					changes |= setunion(wsets[i].ws.lset,
714 					    wsets[ch].ws.lset);
715 					if (!pempty[ch])
716 						break;
717 				}
718 			}
719 		}
720 	}
721 
722 	NTLOOP(i)
723 		pfirst[i] = flset(&wsets[i].ws);
724 	if (!indebug)
725 		return;
726 	if ((foutput != NULL)) {
727 		NTLOOP(i) {
728 			(void) fprintf(foutput, "\n%ws: ", nontrst[i].name);
729 			prlook(pfirst[i]);
730 			(void) fprintf(foutput, " %d\n", pempty[i]);
731 		}
732 	}
733 }
734 
735 /* sorts last state,and sees if it equals earlier ones. returns state number */
736 int
state(int c)737 state(int c)
738 {
739 	int size1, size2;
740 	int i;
741 	ITEM *p1, *p2, *k, *l, *q1, *q2;
742 	p1 = pstate[nstate];
743 	p2 = pstate[nstate+1];
744 	if (p1 == p2)
745 		return (0); /* null state */
746 	/* sort the items */
747 	for (k = p2 - 1; k > p1; k--) {	/* make k the biggest */
748 		for (l = k-1; l >= p1; --l)
749 			if (l->pitem > k->pitem) {
750 				int *s;
751 				LOOKSETS *ss;
752 				s = k->pitem;
753 				k->pitem = l->pitem;
754 				l->pitem = s;
755 				ss = k->look;
756 				k->look = l->look;
757 				l->look = ss;
758 			}
759 	}
760 	size1 = p2 - p1; /* size of state */
761 
762 	for (i = (c >= NTBASE) ? ntstates[c-NTBASE] : tstates[c];
763 	    i != 0; i = mstates[i]) {
764 		/* get ith state */
765 		q1 = pstate[i];
766 		q2 = pstate[i+1];
767 		size2 = q2 - q1;
768 		if (size1 != size2)
769 			continue;
770 		k = p1;
771 		for (l = q1; l < q2; l++) {
772 			if (l->pitem != k->pitem)
773 				break;
774 			++k;
775 		}
776 		if (l != q2)
777 			continue;
778 		/* found it */
779 		pstate[nstate+1] = pstate[nstate]; /* delete last state */
780 		/* fix up lookaheads */
781 		if (nolook)
782 			return (i);
783 		for (l = q1, k = p1; l < q2; ++l, ++k) {
784 			int s;
785 			SETLOOP(s)
786 				clset.lset[s] = l->look->lset[s];
787 			if (setunion(clset.lset, k->look->lset)) {
788 				tystate[i] = MUSTDO;
789 				/* register the new set */
790 				l->look = flset(&clset);
791 			}
792 		}
793 		return (i);
794 	}
795 	/* state is new */
796 	if (nolook)
797 /*
798  * TRANSLATION_NOTE  -- This is a message from yacc.
799  *	This message is passed to error() function.
800  *	You may leave this untranslated. Leave
801  *	state/nolook un-translated.
802  */
803 		error(gettext(
804 		"yacc state/nolook error"));
805 	pstate[nstate+2] = p2;
806 	if (nstate+1 >= nstatesz)
807 		exp_states();
808 	if (c >= NTBASE) {
809 		mstates[nstate] = ntstates[c - NTBASE];
810 		ntstates[c - NTBASE] = nstate;
811 	} else {
812 		mstates[nstate] = tstates[c];
813 		tstates[c] = nstate;
814 	}
815 	tystate[nstate] = MUSTDO;
816 	return (nstate++);
817 }
818 
819 static int pidebug = 0;
820 
821 void
putitem(int * ptr,LOOKSETS * lptr)822 putitem(int *ptr, LOOKSETS *lptr)
823 {
824 	register ITEM *j;
825 
826 	if (pidebug && (foutput != NULL))
827 		(void) fprintf(foutput,
828 		    "putitem(%ws), state %d\n", writem(ptr), nstate);
829 	j = pstate[nstate+1];
830 	j->pitem = ptr;
831 	if (!nolook)
832 		j->look = flset(lptr);
833 	pstate[nstate+1] = ++j;
834 	if (j > zzmemsz) {
835 		zzmemsz = j;
836 		if (zzmemsz >=  &psmem[new_pstsize])
837 			exp_psmem();
838 			/* error("out of state space"); */
839 	}
840 }
841 
842 /*
843  * mark nonterminals which derive the empty string
844  * also, look for nonterminals which don't derive any token strings
845  */
846 static void
cempty(void)847 cempty(void)
848 {
849 #define	EMPTY 1
850 #define	WHOKNOWS 0
851 #define	OK 1
852 	int i, *p;
853 
854 	/*
855 	 * first, use the array pempty to detect productions
856 	 * that can never be reduced
857 	 */
858 
859 	/* set pempty to WHONOWS */
860 	aryfil(pempty, nnonter+1, WHOKNOWS);
861 
862 	/*
863 	 * now, look at productions, marking nonterminals which
864 	 * derive something
865 	 */
866 	more:
867 	PLOOP(0, i) {
868 		if (pempty[*prdptr[i] - NTBASE])
869 			continue;
870 		for (p = prdptr[i] + 1; *p >= 0; ++p)
871 			if (*p >= NTBASE && pempty[*p-NTBASE] == WHOKNOWS)
872 				break;
873 		if (*p < 0) { /* production can be derived */
874 			pempty[*prdptr[i]-NTBASE] = OK;
875 			goto more;
876 		}
877 	}
878 
879 	/* now, look at the nonterminals, to see if they are all OK */
880 
881 	NTLOOP(i) {
882 		/*
883 		 * the added production rises or falls as the
884 		 * start symbol ...
885 		 */
886 		if (i == 0)
887 			continue;
888 		if (pempty[i] != OK) {
889 			fatfl = 0;
890 /*
891  * TRANSLATION_NOTE  -- This is a message from yacc.
892  *	This message is passed to error() function.
893  *	Ask somebody who knows yacc how to translate nonterminal or
894  *	look at translated yacc document. Check how 'derive' is
895  *	translated in these documents also.
896  */
897 			error(gettext(
898 			"nonterminal %ws never derives any token string"),
899 			    nontrst[i].name);
900 		}
901 	}
902 
903 	if (nerrors) {
904 		summary();
905 		exit(1);
906 	}
907 
908 	/*
909 	 * now, compute the pempty array, to see which nonterminals
910 	 * derive the empty string
911 	 */
912 
913 	/* set pempty to WHOKNOWS */
914 
915 	aryfil(pempty, nnonter+1, WHOKNOWS);
916 
917 	/* loop as long as we keep finding empty nonterminals */
918 
919 again:
920 	PLOOP(1, i) {
921 		/* not known to be empty */
922 		if (pempty[*prdptr[i]-NTBASE] == WHOKNOWS) {
923 			for (p = prdptr[i]+1;
924 			    *p >= NTBASE && pempty[*p-NTBASE] == EMPTY; ++p)
925 				;
926 			/* we have a nontrivially empty nonterminal */
927 			if (*p < 0) {
928 				pempty[*prdptr[i]-NTBASE] = EMPTY;
929 				goto again; /* got one ... try for another */
930 			}
931 		}
932 	}
933 }
934 
935 /* generate the states */
936 static int gsdebug = 0;
937 static void
stagen(void)938 stagen(void)
939 {
940 	int i, j;
941 	int c;
942 	register WSET *p, *q;
943 
944 	/* initialize */
945 
946 	nstate = 0;
947 
948 	pstate[0] = pstate[1] = psmem;
949 	aryfil(clset.lset, tbitset, 0);
950 	putitem(prdptr[0] + 1, &clset);
951 	tystate[0] = MUSTDO;
952 	nstate = 1;
953 	pstate[2] = pstate[1];
954 
955 	aryfil(amem, new_actsize, 0);
956 
957 	/* now, the main state generation loop */
958 
959 	more:
960 	SLOOP(i) {
961 		if (tystate[i] != MUSTDO)
962 			continue;
963 		tystate[i] = DONE;
964 		aryfil(temp1, nnonter + 1, 0);
965 		/* take state i, close it, and do gotos */
966 		closure(i);
967 		WSLOOP(wsets, p) { /* generate goto's */
968 			if (p->flag)
969 				continue;
970 			p->flag = 1;
971 			c = *(p->pitem);
972 			if (c <= 1) {
973 				if (pstate[i+1]-pstate[i] <= p-wsets)
974 					tystate[i] = MUSTLOOKAHEAD;
975 				continue;
976 			}
977 			/* do a goto on c */
978 			WSLOOP(p, q) {
979 				/* this item contributes to the goto */
980 				if (c == *(q->pitem)) {
981 					putitem(q->pitem + 1, &q->ws);
982 					q->flag = 1;
983 				}
984 			}
985 			if (c < NTBASE)
986 				(void) state(c);  /* register new state */
987 			else temp1[c-NTBASE] = state(c);
988 		}
989 		if (gsdebug && (foutput != NULL)) {
990 			(void) fprintf(foutput,  "%d: ", i);
991 			NTLOOP(j) {
992 				if (temp1[j])
993 					(void) fprintf(foutput,
994 					    "%ws %d, ", nontrst[j].name,
995 					    temp1[j]);
996 			}
997 			(void) fprintf(foutput, "\n");
998 		}
999 		indgo[i] = apack(&temp1[1], nnonter - 1) - 1;
1000 		goto more; /* we have done one goto; do some more */
1001 	}
1002 	/* no more to do... stop */
1003 }
1004 
1005 /* generate the closure of state i */
1006 static int cldebug = 0; /* debugging flag for closure */
1007 
1008 void
closure(int i)1009 closure(int i)
1010 {
1011 	int c, ch, work, k;
1012 	register WSET *u, *v;
1013 	int *pi;
1014 	int **s, **t;
1015 	ITEM *q;
1016 	register ITEM *p;
1017 	int idx1 = 0;
1018 
1019 	++zzclose;
1020 
1021 	/* first, copy kernel of state i to wsets */
1022 	cwp = 0;
1023 	ITMLOOP(i, p, q) {
1024 		wsets[cwp].pitem = p->pitem;
1025 		wsets[cwp].flag = 1;    /* this item must get closed */
1026 		SETLOOP(k)
1027 			wsets[cwp].ws.lset[k] = p->look->lset[k];
1028 		WSBUMP(cwp);
1029 	}
1030 
1031 	/* now, go through the loop, closing each item */
1032 
1033 	work = 1;
1034 	while (work) {
1035 		work = 0;
1036 		/*
1037 		 * WSLOOP(wsets, u) {
1038 		 */
1039 		for (idx1 = 0; idx1 < cwp; idx1++) {
1040 			u = &wsets[idx1];
1041 			if (u->flag == 0)
1042 				continue;
1043 			c = *(u->pitem);  /* dot is before c */
1044 			if (c < NTBASE) {
1045 				u->flag = 0;
1046 				/*
1047 				 * only interesting case is where . is
1048 				 * before nonterminal
1049 				 */
1050 				continue;
1051 			}
1052 
1053 			/* compute the lookahead */
1054 			aryfil(clset.lset, tbitset, 0);
1055 
1056 			/* find items involving c */
1057 
1058 			WSLOOP(u, v) {
1059 				if (v->flag == 1 && *(pi = v->pitem) == c) {
1060 					v->flag = 0;
1061 					if (nolook)
1062 						continue;
1063 					while ((ch = *++pi) > 0) {
1064 						/* terminal symbol */
1065 						if (ch < NTBASE) {
1066 							SETBIT(clset.lset, ch);
1067 							break;
1068 						}
1069 						/* nonterminal symbol */
1070 						(void) setunion(clset.lset,
1071 						    pfirst[ch-NTBASE]->lset);
1072 						if (!pempty[ch-NTBASE])
1073 							break;
1074 					}
1075 					if (ch <= 0)
1076 						(void) setunion(clset.lset,
1077 						    v->ws.lset);
1078 				}
1079 			}
1080 
1081 			/*  now loop over productions derived from c */
1082 
1083 			c -= NTBASE; /* c is now nonterminal number */
1084 
1085 			t = pres[c+1];
1086 			for (s = pres[c]; s < t; ++s) {
1087 				/* put these items into the closure */
1088 				WSLOOP(wsets, v) { /* is the item there */
1089 					/* yes, it is there */
1090 					if (v->pitem == *s) {
1091 						if (nolook)
1092 							goto nexts;
1093 						if (setunion(v->ws.lset,
1094 						    clset.lset))
1095 							v->flag = work = 1;
1096 						goto nexts;
1097 					}
1098 				}
1099 
1100 				/*  not there; make a new entry */
1101 				if (cwp + 1 >= wsetsz)
1102 					exp_wsets();
1103 
1104 				wsets[cwp].pitem = *s;
1105 				wsets[cwp].flag = 1;
1106 				if (!nolook) {
1107 					work = 1;
1108 					SETLOOP(k)
1109 						wsets[cwp].ws.lset[k] =
1110 						    clset.lset[k];
1111 				}
1112 				WSBUMP(cwp);
1113 				nexts:;
1114 			}
1115 		}
1116 	}
1117 
1118 	/* have computed closure; flags are reset; return */
1119 
1120 	if (&wsets[cwp] > &wsets[zzcwp])
1121 		zzcwp = cwp;
1122 	if (cldebug && (foutput != NULL)) {
1123 		(void) fprintf(foutput, "\nState %d, nolook = %d\n", i, nolook);
1124 		WSLOOP(wsets, u) {
1125 			if (u->flag)
1126 				(void) fprintf(foutput, "flag set!\n");
1127 			u->flag = 0;
1128 			(void) fprintf(foutput, "\t%ws", writem(u->pitem));
1129 			prlook(&u->ws);
1130 			(void) fprintf(foutput,  "\n");
1131 		}
1132 	}
1133 }
1134 
1135 static LOOKSETS *
flset(LOOKSETS * p)1136 flset(LOOKSETS *p)
1137 {
1138 	/* decide if the lookahead set pointed to by p is known */
1139 	/* return pointer to a perminent location for the set */
1140 
1141 	int j, *w;
1142 	int *u, *v;
1143 	register LOOKSETS *q;
1144 
1145 	for (q = &lkst[nlset]; q-- > lkst; ) {
1146 		u = p->lset;
1147 		v = q->lset;
1148 		w = & v[tbitset];
1149 		while (v < w)
1150 			if (*u++ != *v++)
1151 				goto more;
1152 		/* we have matched */
1153 		return (q);
1154 		more:;
1155 	}
1156 	/* add a new one */
1157 	q = &lkst[nlset++];
1158 	if (nlset >= lsetsize) {
1159 		exp_lkst();
1160 		q = &lkst[nlset++];
1161 	}
1162 	SETLOOP(j) q->lset[j] = p->lset[j];
1163 	return (q);
1164 }
1165 
1166 static void
exp_lkst(void)1167 exp_lkst(void)
1168 {
1169 	int i, j;
1170 	static LOOKSETS *lookbase;
1171 
1172 	lookbase = lkst;
1173 	lsetsize += LSETSIZE;
1174 	tmp_lset = (int *)
1175 	    calloc((size_t)(TBITSET * (lsetsize-LSETSIZE)), sizeof (int));
1176 	if (tmp_lset == NULL)
1177 /*
1178  * TRANSLATION_NOTE  -- This is a message from yacc.
1179  *	This message is passed to error() function.
1180  *	Memory allocation error. Do not translate lookset.
1181  *
1182  *	You may just translate this as:
1183  *	'Could not allocate internally used memory.'
1184  */
1185 		error(gettext(
1186 		"could not expand lookset array"));
1187 	lkst = (LOOKSETS *) realloc((char *)lkst, sizeof (LOOKSETS) * lsetsize);
1188 	for (i = lsetsize-LSETSIZE, j = 0; i < lsetsize; ++i, ++j)
1189 		lkst[i].lset = tmp_lset + TBITSET * j;
1190 	tmp_lset = NULL;
1191 	if (lkst == NULL)
1192 /*
1193  * TRANSLATION_NOTE  -- This is a message from yacc.
1194  *	This message is passed to error() function.
1195  *	Memory allocation error. Do not translate lookset.
1196  *
1197  *	You may just translate this as:
1198  *	'Could not allocate internally used memory.'
1199  */
1200 		error(gettext(
1201 		"could not expand lookahead sets"));
1202 	for (i = 0; i <= nnonter; ++i)
1203 		pfirst[i] = pfirst[i] - lookbase + lkst;
1204 	for (i = 0; i <= nstate+1; ++i) {
1205 		if (psmem[i].look)
1206 			psmem[i].look = psmem[i].look - lookbase + lkst;
1207 		if (pstate[i]->look)
1208 			pstate[i]->look = pstate[i]->look - lookbase + lkst;
1209 	}
1210 }
1211 
1212 static void
exp_wsets(void)1213 exp_wsets(void)
1214 {
1215 	int i, j;
1216 
1217 	wsetsz += WSETSIZE;
1218 	tmp_lset = (int *)
1219 	    calloc((size_t)(TBITSET * (wsetsz-WSETSIZE)), sizeof (int));
1220 	if (tmp_lset == NULL)
1221 /*
1222  * TRANSLATION_NOTE  -- This is a message from yacc.
1223  *	This message is passed to error() function.
1224  *	Memory allocation error. Do not translate lookset.
1225  *
1226  *	You may just translate this as:
1227  *	'Could not allocate internally used memory.'
1228  */
1229 		error(gettext(
1230 		"could not expand lookset array"));
1231 	wsets = (WSET *) realloc((char *)wsets, sizeof (WSET) * wsetsz);
1232 	for (i = wsetsz-WSETSIZE, j = 0; i < wsetsz; ++i, ++j)
1233 		wsets[i].ws.lset = tmp_lset + TBITSET * j;
1234 	tmp_lset = NULL;
1235 	if (wsets == NULL)
1236 /*
1237  * TRANSLATION_NOTE  -- This is a message from yacc.
1238  *	This message is passed to error() function.
1239  *	Memory allocation error. You may just transltate
1240  *	this as 'Could not allocate internally used memory.'
1241  *
1242  *	You may just translate this as:
1243  *	'Could not allocate internally used memory.'
1244  */
1245 		error(gettext(
1246 		"could not expand working sets"));
1247 }
1248 
1249 static void
exp_states(void)1250 exp_states(void)
1251 {
1252 	nstatesz += NSTATES;
1253 
1254 	pstate = (ITEM **)
1255 	    realloc((char *)pstate, sizeof (ITEM *)*(nstatesz+2));
1256 	mstates = (int *)realloc((char *)mstates, sizeof (int)*nstatesz);
1257 	defact = (int *)realloc((char *)defact, sizeof (int)*nstatesz);
1258 	tystate = (int *)realloc((char *)tystate, sizeof (int)*nstatesz);
1259 	indgo = (int *)realloc((char *)indgo, sizeof (int)*nstatesz);
1260 
1261 	if ((*pstate == NULL) || (tystate == NULL) || (defact == NULL) ||
1262 	    (indgo == NULL) || (mstates == NULL))
1263 /*
1264  * TRANSLATION_NOTE  -- This is a message from yacc.
1265  *	This message is passed to error() function.
1266  *	Memory allocation error.
1267  *
1268  *	You may just translate this as:
1269  *	'Could not allocate internally used memory.'
1270  */
1271 		error(gettext(
1272 		"cannot expand table of states"));
1273 }
1274 
1275 static void
exp_psmem(void)1276 exp_psmem(void)
1277 {
1278 	int i;
1279 
1280 	new_pstsize += PSTSIZE;
1281 	psmem = (ITEM *) realloc((char *)psmem, sizeof (ITEM) * new_pstsize);
1282 	if (psmem == NULL)
1283 /*
1284  * TRANSLATION_NOTE  -- This is a message from yacc.
1285  *	This message is passed to error() function.
1286  *	Memory allocation error.
1287  *
1288  *	You may just translate this as:
1289  *	'Could not allocate internally used memory.'
1290  */
1291 		error(gettext(
1292 		"cannot expand pstate memory"));
1293 
1294 	zzmemsz = zzmemsz - pstate[0] + psmem;
1295 	for (i = 1; i <= nstate+1; ++i)
1296 		pstate[i] = pstate[i] - pstate[0] + psmem;
1297 	pstate[0] = psmem;
1298 }
1299