![[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 / d / bin / yacc|
Return to y1.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin / yacc |
1.1 root 1: /*
2: * LALR-1 parser generator
3: *
4: * the comments previously here have been suppressed since they were
5: * boring
6: */
7: #include "yacc.h"
8:
9: main(argc,argv)
10: char *argv[];
11: {
12: options(argc,argv);
13: getfiles();
14: readrules();
15: ntprod();
16: ntderive();
17: listgram();
18: if( nerrors )
19: cleanup(1);
20: ntempty();
21: if( nerrors )
22: cleanup(1);
23: genstates();
24: genslist();
25: sttrans();
26: genlook();
27: go2out();
28: paout();
29: callopt();
30: cleanup(0);
31: }
32:
33: getfiles()
34: {
35: if( gramy==NULL )
36: usage();
37: if( strcmp(gramy,"-")==0 )
38: defin = stdin;
39: else
40: if( (defin = fopen(gramy,"r")) == NULL )
41: yyerror(!FATAL, "cannot open grammar file %s", gramy);
42: mktemp(acttmp);
43: mktemp(opttmp);
44: if( (actout = fopen(acttmp,"w")) == NULL )
45: yyerror(!FATAL, "cannot create action temp file %s", acttmp);
46: if( (tabout = fopen(ytabc,"w")) == NULL )
47: yyerror(!FATAL, "cannot create output file %s", ytabc);
48: if( (fhdr = fopen(ytabh, "w")) == NULL )
49: yyerror(!FATAL, "cannot create %s", ytabh);
50: if( verbose )
51: if( (listout = fopen(youtput,"w")) == NULL )
52: yyerror(NLNO, "cannot open listing file %s", youtput);
53: if ((optout = fopen(opttmp, "wb")) == NULL
54: || (optout = freopen(opttmp, "rwb", optout)) == NULL)
55: yyerror(NLNO, "open error temp %s", opttmp);
56: if( nerrors )
57: cleanup(2);
58: }
59:
60: rewopt()
61: {
62: fseek(optout, 0L, 0);
63: }
64:
65: /*
66: * for each non-terminal, generate a list of productions which the
67: * the non terminal derives
68: */
69: ntprod()
70: {
71: register i;
72: register struct sym *sp;
73:
74: /* first run down the production table, counting references to
75: all the non terminals. */
76: for(i=0; i<nnonterm; i++)
77: ntrmptr[i]->s_nprods = 0;
78: for(i=0; i<nprod; i++)
79: ntrmptr[-prdptr[i]->p_left-NTBASE]->s_nprods++;
80: for(i=0; i<nnonterm; i++)
81: if( ntrmptr[i]->s_nprods==0 )
82: yyerror(NLNO|!FATAL, "non terminal %s not defined",
83: ntrmptr[i]->s_name);
84: if( nerrors )
85: cleanup(1);
86: /* now allocate list pointers for each non-terminal */
87: for(i=0; i<nnonterm; i++) {
88: sp = ntrmptr[i];
89: sp->s_prods = (struct prod **)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=pp->p_right; *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 = (*ppp)->p_right; *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] = prdptr[0]->p_right;
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 = states[i].s_ntgos =
238: states[i].s_reds = NULL; /* MWC DSC */
239: }
240: } while( newgen );
241: free(ntp);
242: }
243:
244: /*
245: * generate the closure of a state (found in global variable `nititem'
246: * Algorithm:
247: * - look at every non terminal's after every '.' item pointer
248: * - add all the productions associated with this non-terminal
249: * to the state (the '.' being at the beginning of the rhs) unless
250: * they are already there. It suffices to test if one of them is
251: * already there, since productions are added to the closure according
252: * according to their lhs
253: * repeat this procedure until no new items are added.
254: *
255: * "It can be shown that (this procedure) computes exactly the sets
256: * of items that are valid for gamma X [Aho and Ullmann 1972]"
257: */
258:
259: closure()
260: {
261: register j, **ipp;
262: register struct prod **ppp;
263: struct sitem *itp;
264: struct sym *sp;
265: int i, changed, nt;
266:
267: itp = nititem;
268: for(i=0; i<nnonterm; i++)
269: ntrmptr[i]->s_flags &= ~CPRES;
270: for(i=0; i<itp->i_nitems; i++)
271: /* kludge: requires p.left & p.rights contigouuous */
272: if( (nt = *(itp->i_items[i]-1)) < 0 ) /* ARE THEY???? */
273: ntrmptr[-nt-NTBASE]->s_flags |= CPRES;
274: do {
275: changed = 0;
276: for(i=0; i<itp->i_nitems; i++) {
277: nt = *(itp->i_items[i]);
278: if( nt>=NTBASE && ((sp = ntrmptr[nt-NTBASE])->s_flags
279: &CPRES)==0 ) {
280: sp->s_flags |= CPRES;
281: changed = 1;
282: ppp = sp->s_prods;
283: ipp = &itp->i_items[itp->i_nitems];
284: itp->i_nitems += j = sp->s_nprods;
285: bounded(itp->i_nitems, MAXITEM, "items in state");
286: do
287: *ipp++ = (*ppp++)->p_right;
288: while( --j );
289: }
290: }
291: } while( changed );
292: }
293:
294: /*
295: * add the state in `nititem' to the collection of sets of accessible
296: * items, returning the state pointer
297: * the real work is concerned with finding out whether the set is there
298: * already or not
299: * we sort the items in nititem, compare with every set in "items",
300: * and return the old state pointer if its there already
301: */
302: install()
303: {
304: register n, **ipp1, **ipp2;
305: struct sitem *itp, *itp1;
306: int i;
307:
308: itp = nititem;
309: bubble(itp->i_items, itp->i_nitems);
310: for(i=0; i<nstates; i++) {
311: itp1 = items[i];
312: if( (n = itp->i_nitems) != itp1->i_nitems )
313: continue;
314: ipp1 = itp->i_items;
315: ipp2 = itp1->i_items;
316: do
317: if( *ipp1++ != *ipp2++ )
318: break;
319: while( --n );
320: if( n==0 )
321: break;
322: }
323: if( i==nstates ) {
324: bounded(nstates,maxstates,"states");
325: chklhs();
326: itp1 = (struct sitem *)yalloc(1, sizeof *itp1 + itp->i_nitems *
327: sizeof itp->i_items[0]);
328: copyb(itp, itp1, sizeof *itp1 + itp->i_nitems *
329: sizeof itp->i_items[0]);
330: newgen = 1;
331: items[nstates] = itp1;
332: if( verbose )
333: prstate(nstates, listout);
334: nstates++;
335: }
336: return( i );
337: }
338:
339: go2(itp, tk)
340: struct sitem *itp;
341: int tk;
342: {
343: register **ipp1, **ipp, n;
344:
345: nititem->i_nitems = 0;
346: ipp1 = nititem->i_items;
347: ipp = itp->i_items;
348: n = itp->i_nitems;
349: do {
350: if( **ipp == tk ) {
351: nititem->i_nitems++;
352: *ipp1++ = *ipp+1;
353: }
354: ipp++;
355: } while( --n );
356: if( nititem->i_nitems==0 )
357: return( -1 );
358: else {
359: closure();
360: return( install() );
361: }
362: }
363:
364: chklhs()
365: {
366: register n, **ipp;
367: register char *cp;
368: int nt;
369:
370: n = nnonterm;
371: cp = ntp;
372: do *cp++ = 0; while( --n );
373: ipp = nititem->i_items;
374: n = nititem->i_nitems;
375: cp = ntp;
376: do
377: if( (nt = (*ipp++) [-1]) < 0 )
378: cp[ -nt-NTBASE ] = 1;
379: while( --n );
380: for(n=0; n<nnonterm; n++)
381: if( cp[n] )
382: ntrmptr[n]->s_nstates++;
383: }
384:
385: /*
386: * for each nonterminal generate a list of items
387: * containing items with all of the rhs of a production
388: * whose lhs is the non-terminal after the '.'
389: */
390: genslist()
391: {
392: register struct sym *sp;
393: register i, j;
394: int *ip;
395: int *stp;
396:
397: for(i=j=0; i<nnonterm; i++)
398: j += ntrmptr[i]->s_nstates;
399: stp = (int *)yalloc(j, sizeof *stp);
400: for(i=0; i<nnonterm; i++) {
401: sp = ntrmptr[i];
402: sp->s_states = stp;
403: stp += sp->s_nstates;
404: sp->s_nstates = 0; /* a recharcher dans le boucle suivant */
405: }
406: for(i=0; i<nnonterm; i++) {
407: sp = ntrmptr[i];
408: ip = sp->s_prods[0]->p_right; /* pick an item, any item */
409: for(j=0; j<nstates; j++)
410: if( pitem(ip, items[j]) )
411: sp->s_states[sp->s_nstates++] = j;
412: }
413: }
414:
415: /* binary search for an item in a state */
416:
417: pitem(ip,itp)
418: int *ip;
419: register struct sitem *itp;
420: {
421: register int *el, nb;
422: int ub, lb;
423:
424: lb = 0;
425: ub = itp->i_nitems-1;
426: do {
427: nb = (ub+lb) / 2;
428: if( (el = itp->i_items[nb]) < ip )
429: lb = nb+1;
430: else if( el > ip )
431: ub = nb-1;
432: else
433: return(1);
434: } while( lb<=ub );
435: return(0);
436: }
437:
438: /*
439: * linear insertion sort really.
440: * the decision not to use bubbbbbbbbbbbble sort is thanks to Randall
441: * and to his cs240b notes
442: * (p.s. -- i hate sorting)
443: */
444:
445: bubble(ipp,n)
446: register **ipp;
447: int n;
448: {
449: register **min, **jpp;
450: int m, *t; /* MWC DSC */
451:
452: do {
453: m = n;
454: min = jpp = ipp;
455: do {
456: if( *jpp < *min )
457: min = jpp;
458: jpp++;
459: } while( --m );
460: t = *min;
461: *min = *ipp;
462: *ipp++ = t;
463: } while( --n );
464: }
465:
466: copyb(sp,dp,n)
467: register char *sp, *dp;
468: register n;
469: {
470: do
471: *dp++ = *sp++;
472: while( --n );
473: }
474:
475: cleanup(err)
476: {
477: unlink(acttmp);
478: unlink(opttmp);
479: stats();
480: exit(err);
481: }
482:
483: stats()
484: {
485: extern nsrconf, nrrconf;
486:
487: if( !pstat && (nsrconf || nrrconf) ) {
488: if( nrrconf ) {
489: fprintf(stderr, "%d R/R conflict", nrrconf);
490: if( nrrconf != 1 )
491: fprintf(stderr, "s");
492: }
493: if( nrrconf && nsrconf )
494: fprintf(stderr, " and ");
495: if( nsrconf ) {
496: fprintf(stderr, "%d S/R conflict", nsrconf);
497: if( nsrconf != 1)
498: fprintf(stderr, "s");
499: }
500: fprintf(stderr, "\n");
501: }
502: if( verbose )
503: stat1(listout);
504: if( pstat )
505: stat1(stdout);
506: }
507:
508:
509: stat1(f)
510: FILE *f;
511: {
512: extern nsrconf, nrrconf, yygodef, yypact, yyredns;
513: extern ndupgos, ndupacts;
514: extern yydefact;
515:
516: fprintf(f, "Statistics:\n");
517: fprintf(f, "%d/%d tokens, %d/%d non terminals\n", nterm, maxterm,
518: nnonterm, maxnterm);
519: fprintf(f, "%d/%d productions, %d/%d states\n", nprod, maxprod,
520: nstates, maxstates);
521: fprintf(f, "%d goto entries; %d saved by goto default\n",
522: yyredns, yygodef);
523: fprintf(f, "%d parsing actions; %d saved by default\n",
524: yypact, yydefact);
525: fprintf(f, "%d duplicated goto entries saved; %d actions\n",
526: ndupgos, ndupacts);
527: if( nsrconf || nrrconf )
528: fprintf(f, "%d R/R conflicts, %d S/R conflicts\n",
529: nrrconf, nsrconf);
530: }
531:
532: char *
533: yalloc(n, s)
534: {
535: register char *cp;
536:
537: if( cp = calloc(n, s) )
538: return(cp);
539: yyerror(NLNO|FATAL, "storage overflow (requested %d)\n", n*s);
540: }
541:
542: /*
543: * transform the state representation
544: */
545:
546: sttrans()
547: {
548: register j, k;
549: int i, totgo, tontgo;
550: register struct state *stp;
551: struct tgo *tgp;
552: struct ntgo *ngp;
553:
554: /* a la pubelle !! */
555: for(i=0; i<nstates; i++)
556: free(items[i]);
557: free(items);
558:
559: if( yydebug )
560: fprintf(listout,"Automaton transition graph:\n\n");
561: for(i=totgo=0; i<nstates; i++)
562: totgo += states[i].s_tgo;
563: for(i=tontgo=0; i<nstates; i++)
564: tontgo += states[i].s_ntgo;
565: tgp = (struct tgo *)yalloc(totgo, sizeof *tgp);
566: ngp = (struct ntgo *)yalloc(tontgo, sizeof *ngp);
567: rewopt();
568:
569: for(j=0; j<nstates; j++) {
570: if( yydebug )
571: fprintf(listout, "State %d:\n\n", j);
572: stp = &states[j];
573: if( fread(&i, sizeof i, 1, optout)!=1 || i!=j )
574: yyerror(NLNO|FATAL, "temp file i/o error");
575: fread(tgp, sizeof *tgp, stp->s_tgo, optout);
576: stp->s_tgos = tgp;
577: stp->s_ntgos = ngp;
578: if( yydebug )
579: for(k=0; k<stp->s_tgo; k++)
580: fprintf(listout, "\t%s\t%d\n",
581: ptosym(stp->s_tgos[k].tg_trm),
582: stp->s_tgos[k].tg_st);
583: fread(ngp, sizeof *ngp, stp->s_ntgo, optout);
584: if( yydebug )
585: for(k=0; k<stp->s_ntgo; k++)
586: fprintf(listout, "\t%s\t%d\n",
587: ptosym(stp->s_ntgos[k].ng_nt),
588: stp->s_ntgos[k].ng_st);
589: tgp += stp->s_tgo;
590: ngp += stp->s_ntgo;
591: }
592: }
593:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.