![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to y1.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / b / bin / yacc|
Return to y1.c CVS log | Up to [MW Coherent from dump] / coherent / b / bin / yacc |
1.1 root 1: /*
2: * LALR-1 parser generator
3: */
4:
5: #include <string.h>
6: #include "yacc.h"
7:
8: main(argc,argv)
9: char *argv[];
10: {
11: options(argc,argv);
12: getfiles();
13: readrules();
14: ntprod();
15: ntderive();
16: listgram();
17: if( nerrors )
18: cleanup(1);
19: ntempty();
20: if( nerrors )
21: cleanup(1);
22: genstates();
23: genslist();
24: sttrans();
25: genlook();
26: go2out();
27: paout();
28: callopt();
29: cleanup(0);
30: }
31:
32: getfiles()
33: {
34: if( gramy==NULL )
35: usage();
36: if( strcmp(gramy,"-")==0 )
37: defin = stdin;
38: else
39: if( (defin = fopen(gramy,"r")) == NULL )
40: yyerror(!FATAL, "cannot open grammar file %s", gramy);
41: mktemp(acttmp);
42: mktemp(opttmp);
43: if( (actout = fopen(acttmp,"w")) == NULL )
44: yyerror(!FATAL, "cannot create action temp file %s", acttmp);
45: if( (tabout = fopen(ytabc,"w")) == NULL )
46: yyerror(!FATAL, "cannot create output file %s", ytabc);
47: if( (fhdr = fopen(ytabh, "w")) == NULL )
48: yyerror(!FATAL, "cannot create %s", ytabh);
49: if( verbose )
50: if( (listout = fopen(youtput,"w")) == NULL )
51: yyerror(NLNO, "cannot open listing file %s", youtput);
52: if ((optout = fopen(opttmp, "wb")) == NULL
53: || (optout = freopen(opttmp, "rwb", optout)) == NULL)
54: yyerror(NLNO, "open error temp %s", opttmp);
55: if( nerrors )
56: cleanup(2);
57: }
58:
59: rewopt()
60: {
61: fseek(optout, 0L, 0);
62: }
63:
64: /*
65: * for each non-terminal, generate a list of productions which the
66: * the non terminal derives
67: */
68: ntprod()
69: {
70: register i;
71: register struct sym *sp;
72:
73: /* first run down the production table, counting references to
74: all the non terminals. */
75: for(i=0; i<nnonterm; i++)
76: ntrmptr[i]->s_nprods = 0;
77: for(i=0; i<nprod; i++)
78: ntrmptr[-prdptr[i]->p_left-NTBASE]->s_nprods++;
79: for(i=0; i<nnonterm; i++)
80: if( ntrmptr[i]->s_nprods==0 )
81: yyerror(NLNO|!FATAL, "non terminal %s not defined",
82: ntrmptr[i]->s_name);
83: if( nerrors )
84: cleanup(1);
85: /* now allocate list pointers for each non-terminal */
86: for(i=0; i<nnonterm; i++) {
87: sp = ntrmptr[i];
88: sp->s_prods = (struct prod **)
89: yalloc (sp->s_nprods, sizeof (* sp->s_prods));
90: sp->s_nprods = 0; /* il sera recharge a la suite */
91: }
92: /* finally, run down the production table again filling in the
93: list pointers for the corresponding non terminal */
94: for(i=0; i<nprod; i++) {
95: sp = ntrmptr[ -prdptr[i]->p_left-NTBASE ];
96: sp->s_prods[sp->s_nprods++] = prdptr[i];
97: }
98: }
99:
100: /*
101: * assure that all non-terminals generate a token string
102: * algorithm:
103: * assume a priori that no non-terminal generates a token string
104: * if a non terminal contains a production which consists only
105: * of non-terminals generating a token string, and terminals
106: * then it generates a token string
107: * cycle on this until no new non terminals are found
108: * - a similar procedure applies for finding out which non terminals
109: * generate the empty string
110: */
111:
112: ntderive()
113: {
114: register i, j;
115: register struct sym *sp;
116: register struct prod *pp;
117: int *ip;
118: int changed;
119:
120: for(i=0; i<nnonterm; i++)
121: ntrmptr[i]->s_flags &= ~DERIV;
122: do {
123: changed = 0;
124: for(i=0; i<nnonterm; i++) {
125: sp = ntrmptr[i];
126: if( sp->s_flags&DERIV )
127: continue;
128: for(j=0; j<sp->s_nprods; j++) {
129: pp = sp->s_prods[j];
130: for(ip = PROD_RIGHT (pp); *ip != -1; ip ++)
131: if( *ip>=NTBASE &&
132: (ntrmptr[*ip-NTBASE]->s_flags&DERIV)==0 )
133: break;
134: if( *ip == -1 ) {
135: sp->s_flags |= DERIV;
136: changed++;
137: break;
138: }
139: }
140: }
141: } while( changed );
142: for(i=0; i<nnonterm; i++)
143: if( (ntrmptr[i]->s_flags&DERIV)==0 )
144: yyerror(NLNO|!FATAL, "nonterminal %s derives no token string",
145: ntrmptr[i]->s_name);
146: if( nerrors )
147: cleanup(1);
148: }
149:
150: /*
151: * find out which non-terminals derive the empty string
152: * algorithm is simple
153: * if the non-terminal has a production deriving the empty string
154: * it derives the empty string trivially
155: * otherwise if it consists only of productions which can derive the
156: * empty string, then it derives the empty string as well
157: */
158:
159: ntempty()
160: {
161: register *kp;
162: register struct prod **ppp;
163: register struct sym *sp;
164: int i, changed;
165:
166: for(i=0; i<nnonterm; i++)
167: ntrmptr[i]->s_flags &= ~DERIV;
168: do {
169: changed = 0;
170: for(i=0; i<nnonterm; i++) {
171: sp = ntrmptr[i];
172: if (sp->s_flags & DERIV)
173: continue;
174: for(ppp=sp->s_prods; ppp<&sp->s_prods[sp->s_nprods]; ppp++) {
175: for(kp = PROD_RIGHT (*ppp); *kp!=-1; kp++ )
176: if( *kp<NTBASE ||
177: (ntrmptr[*kp-NTBASE]->s_flags&DERIV)==0 )
178: break;
179: if( *kp==-1 ) {
180: sp->s_flags |= DERIV;
181: changed++;
182: break;
183: }
184: }
185: }
186: } while( changed );
187: }
188:
189: /* some useful local variables */
190: static newgen; /* communication between genstates and install */
191: static char *ntp; /* buffer for use by chklhs */
192:
193: genstates()
194: {
195: extern struct sitem *nititem;
196: register k, sno;
197: int i;
198: struct tgo tgo;
199: struct ntgo ntgo;
200:
201: /* initialize the list of states associated with each nt to empty */
202: if( verbose )
203: fprintf(listout, "\nAutomaton state description:\n\n");
204: for(i=0; i<nnonterm; i++)
205: ntrmptr[i]->s_nstates = 0;
206: ntp = yalloc(nnonterm, sizeof *ntp); /* array used by "install" */
207: nititem->i_nitems = 1;
208: nititem->i_items[0] = PROD_RIGHT (prdptr[0]);
209: closure();
210: install();
211: i = 0;
212: do {
213: newgen = 0; /* newgen is flagged by the install routine */
214: for(; i<nstates; i++) {
215: fwrite(&i, sizeof i, 1, optout); /* sync number */
216: states[i].s_tgo = 0;
217: for(k=0; k<nterm; k++)
218: if( (sno = go2(items[i], k)) >= 0 ) {
219: states[i].s_tgo++;
220: tgo.tg_st = sno;
221: tgo.tg_trm = k;
222: fwrite(&tgo, sizeof tgo, 1, optout);
223: }
224: states[i].s_ntgo = 0;
225: for(k=0; k<nnonterm; k++)
226: if( (sno = go2(items[i], k+NTBASE)) >= 0 ) {
227: states[i].s_ntgo++;
228: ntgo.ng_st = sno;
229: ntgo.ng_nt = k+NTBASE;
230: ntgo.ng_rel = NULL; /* MWC DSC */
231: fwrite(&ntgo, sizeof ntgo, 1, optout);
232: }
233: states[i].s_nred = 0;
234: for(k=0; k<items[i]->i_nitems; k++)
235: if( *(items[i]->i_items[k]) == -1 )
236: states[i].s_nred++;
237: states[i].s_tgos = NULL;
238: states[i].s_ntgos = NULL;
239: states[i].s_reds = NULL; /* MWC DSC */
240: }
241: } while( newgen );
242: free(ntp);
243: }
244:
245: /*
246: * generate the closure of a state (found in global variable `nititem'
247: * Algorithm:
248: * - look at every non terminal's after every '.' item pointer
249: * - add all the productions associated with this non-terminal
250: * to the state (the '.' being at the beginning of the rhs) unless
251: * they are already there. It suffices to test if one of them is
252: * already there, since productions are added to the closure according
253: * according to their lhs
254: * repeat this procedure until no new items are added.
255: *
256: * "It can be shown that (this procedure) computes exactly the sets
257: * of items that are valid for gamma X [Aho and Ullmann 1972]"
258: */
259:
260: closure()
261: {
262: register j, **ipp;
263: register struct prod **ppp;
264: struct sitem *itp;
265: struct sym *sp;
266: int i, changed, nt;
267:
268: itp = nititem;
269: for(i=0; i<nnonterm; i++)
270: ntrmptr[i]->s_flags &= ~CPRES;
271: for(i=0; i<itp->i_nitems; i++)
272: /* kludge: requires p.left & p.rights contiguous */
273: if( (nt = *(itp->i_items[i]-1)) < 0 ) { /* ARE THEY???? */
274: #if 0
275: fprintf (stderr, "CPRES : %d\n", i);
276: #endif
277: ntrmptr[-nt-NTBASE]->s_flags |= CPRES;
278: }
279: do {
280: changed = 0;
281: for(i=0; i<itp->i_nitems; i++) {
282: nt = *(itp->i_items[i]);
283: if( nt>=NTBASE && ((sp = ntrmptr[nt-NTBASE])->s_flags
284: &CPRES)==0 ) {
285: sp->s_flags |= CPRES;
286: changed = 1;
287: ppp = sp->s_prods;
288: ipp = &itp->i_items[itp->i_nitems];
289: itp->i_nitems += j = sp->s_nprods;
290: bounded(itp->i_nitems, maxitem, "items in state");
291: do
292: *ipp++ = PROD_RIGHT (*ppp++);
293: while( --j );
294: }
295: }
296: } while( changed );
297: }
298:
299: /*
300: * add the state in `nititem' to the collection of sets of accessible
301: * items, returning the state pointer
302: * the real work is concerned with finding out whether the set is there
303: * already or not
304: * we sort the items in nititem, compare with every set in "items",
305: * and return the old state pointer if its there already
306: */
307: install()
308: {
309: register n, **ipp1, **ipp2;
310: struct sitem *itp, *itp1;
311: int i;
312:
313: itp = nititem;
314: bubble(itp->i_items, itp->i_nitems);
315: for(i=0; i<nstates; i++) {
316: itp1 = items[i];
317: if( (n = itp->i_nitems) != itp1->i_nitems )
318: continue;
319: ipp1 = itp->i_items;
320: ipp2 = itp1->i_items;
321: do
322: if( *ipp1++ != *ipp2++ )
323: break;
324: while( --n );
325: if( n==0 )
326: break;
327: }
328: if (i == nstates) {
329: bounded (nstates,maxstates,"states");
330: chklhs ();
331:
332: /*
333: * NIGEL: Changed to stop use of flex-arrays.
334: */
335:
336: itp1 = (struct sitem *)
337: yalloc (1, SITEM_TOTAL_SIZE (itp->i_nitems));
338: * itp1 = * itp;
339: SITEM_EXTRA_INIT (itp1);
340:
341: if (SITEM_EXTRA_SIZE (itp->i_nitems) > 0)
342: memcpy (itp1->i_items, itp->i_items,
343: SITEM_EXTRA_SIZE (itp->i_nitems));
344:
345: newgen = 1;
346: items [nstates] = itp1;
347: if (verbose)
348: prstate (nstates, listout);
349: nstates ++;
350: }
351: return i;
352: }
353:
354: go2(itp, tk)
355: struct sitem *itp;
356: int tk;
357: {
358: register **ipp1, **ipp, n;
359:
360: nititem->i_nitems = 0;
361: ipp1 = nititem->i_items;
362: ipp = itp->i_items;
363: n = itp->i_nitems;
364: do {
365: if( **ipp == tk ) {
366: nititem->i_nitems++;
367: *ipp1++ = *ipp+1;
368: }
369: ipp++;
370: } while( --n );
371: if( nititem->i_nitems==0 )
372: return( -1 );
373: else {
374: closure();
375: return( install() );
376: }
377: }
378:
379: chklhs()
380: {
381: register n, **ipp;
382: register char *cp;
383: int nt;
384:
385: n = nnonterm;
386: cp = ntp;
387: do *cp++ = 0; while( --n );
388: ipp = nititem->i_items;
389: n = nititem->i_nitems;
390: cp = ntp;
391: do
392: if( (nt = (*ipp++) [-1]) < 0 )
393: cp[ -nt-NTBASE ] = 1;
394: while( --n );
395: for(n=0; n<nnonterm; n++)
396: if( cp[n] )
397: ntrmptr[n]->s_nstates++;
398: }
399:
400: /*
401: * for each nonterminal generate a list of items
402: * containing items with all of the rhs of a production
403: * whose lhs is the non-terminal after the '.'
404: */
405: genslist()
406: {
407: register struct sym *sp;
408: register i, j;
409: int *ip;
410: int *stp;
411:
412: for(i=j=0; i<nnonterm; i++)
413: j += ntrmptr[i]->s_nstates;
414: stp = (int *)yalloc(j, sizeof *stp);
415: for(i=0; i<nnonterm; i++) {
416: sp = ntrmptr[i];
417: sp->s_states = stp;
418: stp += sp->s_nstates;
419: sp->s_nstates = 0; /* a recharcher dans le boucle suivant */
420: }
421: for(i=0; i<nnonterm; i++) {
422: sp = ntrmptr[i];
423: ip = PROD_RIGHT (sp->s_prods[0]); /* pick an item, any item */
424: for(j=0; j<nstates; j++)
425: if( pitem(ip, items[j]) )
426: sp->s_states[sp->s_nstates++] = j;
427: }
428: }
429:
430: /* binary search for an item in a state */
431:
432: pitem(ip,itp)
433: int *ip;
434: register struct sitem *itp;
435: {
436: register int *el, nb;
437: int ub, lb;
438:
439: lb = 0;
440: ub = itp->i_nitems-1;
441: do {
442: nb = (ub+lb) / 2;
443: if( (el = itp->i_items[nb]) < ip )
444: lb = nb+1;
445: else if( el > ip )
446: ub = nb-1;
447: else
448: return(1);
449: } while( lb<=ub );
450: return(0);
451: }
452:
453: /*
454: * linear insertion sort really.
455: * the decision not to use bubbbbbbbbbbbble sort is thanks to Randall
456: * and to his cs240b notes
457: * (p.s. -- i hate sorting)
458: */
459:
460: bubble(ipp,n)
461: register **ipp;
462: int n;
463: {
464: register **min, **jpp;
465: int m, *t; /* MWC DSC */
466:
467: do {
468: m = n;
469: min = jpp = ipp;
470: do {
471: if( *jpp < *min )
472: min = jpp;
473: jpp++;
474: } while( --m );
475: t = *min;
476: *min = *ipp;
477: *ipp++ = t;
478: } while( --n );
479: }
480:
481: cleanup(err)
482: {
483: unlink(acttmp);
484: unlink(opttmp);
485: stats();
486: exit(err);
487: }
488:
489: stats()
490: {
491: extern nsrconf, nrrconf;
492:
493: if( !pstat && (nsrconf || nrrconf) ) {
494: if( nrrconf ) {
495: fprintf(stderr, "%d R/R conflict", nrrconf);
496: if( nrrconf != 1 )
497: fprintf(stderr, "s");
498: }
499: if( nrrconf && nsrconf )
500: fprintf(stderr, " and ");
501: if( nsrconf ) {
502: fprintf(stderr, "%d S/R conflict", nsrconf);
503: if( nsrconf != 1)
504: fprintf(stderr, "s");
505: }
506: fprintf(stderr, "\n");
507: }
508: if( verbose )
509: stat1(listout);
510: if( pstat )
511: stat1(stdout);
512: }
513:
514:
515: stat1(f)
516: FILE *f;
517: {
518: extern nsrconf, nrrconf, yygodef, yypact, yyredns;
519: extern ndupgos, ndupacts;
520: extern yydefact;
521:
522: fprintf(f, "Statistics:\n");
523: fprintf(f, "%d/%d tokens, %d/%d non terminals\n", nterm, maxterm,
524: nnonterm, maxnterm);
525: fprintf(f, "%d/%d productions, %d/%d states\n", nprod, maxprod,
526: nstates, maxstates);
527: fprintf(f, "%d goto entries; %d saved by goto default\n",
528: yyredns, yygodef);
529: fprintf(f, "%d parsing actions; %d saved by default\n",
530: yypact, yydefact);
531: fprintf(f, "%d duplicated goto entries saved; %d actions\n",
532: ndupgos, ndupacts);
533: if( nsrconf || nrrconf )
534: fprintf(f, "%d R/R conflicts, %d S/R conflicts\n",
535: nrrconf, nsrconf);
536: }
537:
538: char *
539: yalloc(n, s)
540: {
541: register char *cp;
542:
543: if ((cp = calloc(n, s)) == NULL)
544: yyerror (NLNO | FATAL,
545: "storage overflow (requested %d * %d)\n", n, s);
546:
547: return cp;
548: }
549:
550: /*
551: * transform the state representation
552: */
553:
554: sttrans()
555: {
556: register j, k;
557: int i, totgo, tontgo;
558: register struct state *stp;
559: struct tgo *tgp;
560: struct ntgo *ngp;
561:
562: /* a la pubelle !! */
563: for(i=0; i<nstates; i++)
564: free(items[i]);
565: free(items);
566:
567: if( yydebug )
568: fprintf(listout,"Automaton transition graph:\n\n");
569: for(i=totgo=0; i<nstates; i++)
570: totgo += states[i].s_tgo;
571: for(i=tontgo=0; i<nstates; i++)
572: tontgo += states[i].s_ntgo;
573: tgp = (struct tgo *)yalloc(totgo, sizeof *tgp);
574: ngp = (struct ntgo *)yalloc(tontgo, sizeof *ngp);
575: rewopt();
576:
577: for(j=0; j<nstates; j++) {
578: if( yydebug )
579: fprintf(listout, "State %d:\n\n", j);
580: stp = &states[j];
581: if( fread(&i, sizeof i, 1, optout)!=1 || i!=j )
582: yyerror(NLNO|FATAL, "temp file i/o error");
583: fread(tgp, sizeof *tgp, stp->s_tgo, optout);
584: stp->s_tgos = tgp;
585: stp->s_ntgos = ngp;
586: if( yydebug )
587: for(k=0; k<stp->s_tgo; k++)
588: fprintf(listout, "\t%s\t%d\n",
589: ptosym(stp->s_tgos[k].tg_trm),
590: stp->s_tgos[k].tg_st);
591: fread(ngp, sizeof *ngp, stp->s_ntgo, optout);
592: if( yydebug )
593: for(k=0; k<stp->s_ntgo; k++)
594: fprintf(listout, "\t%s\t%d\n",
595: ptosym(stp->s_ntgos[k].ng_nt),
596: stp->s_ntgos[k].ng_st);
597: tgp += stp->s_tgo;
598: ngp += stp->s_ntgo;
599: }
600: }
601:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.