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