![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ey3.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 42BSD / ucb / eyacc|
Return to ey3.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ucb / eyacc |
1.1 root 1: static char *sccsid = "@(#)ey3.c 4.2 (Berkeley) 8/30/82";
2: /* (c) 1979 Regents of the University of California */
3: # include "ey.h"
4:
5: cpres(){ /* conpute an array with the beginnings of productions yielding given nonterminals
6: The array pres points to these lists */
7: int i,j,c;
8: pres = (int ***)yalloc(nnonter+1);
9: for(i=0;i<=nnonter;i++){
10: c = i+NTBASE;
11: pres[i] = (int **)mem;
12: fatfl = 0; /* make undefined symbols nonfatal */
13: for(j=0;j<nprod;j++)
14: if (*prdptr[j] == c) *mem++ = (int)(prdptr[j]+1);
15: if(pres[i] == (int **)mem){
16: error("nonterminal %s not defined!", nontrst[i].name);
17: }
18: }
19: pres[i] = (int **)mem;
20: fatfl = 1;
21: if( nerrors ){
22: summary();
23: cexit(1);
24: }
25: }
26:
27: int indebug = 0;
28: cpfir() {
29: /* compute an array with the first of nonterminals */
30: int i, ch, **s, **t, changes, *p;
31:
32: pfirst = (struct looksets **)yalloc(nnonter+1);
33: for (i=0;i<=nnonter;i++) {
34: aryfil( wsets[i].ws, tbitset, 0 );
35: t = pres[i+1];
36: for( s=pres[i]; s<t; ++s ){ /* initially fill the sets */
37: for( p = *s; (ch = *p) > 0 ; ++p ) {
38: if( ch < NTBASE ) {
39: wsets[i].ws[ch>>4] |= (1 << (ch&017) );
40: break;
41: }
42: else if( !pempty[ch-NTBASE] ) break;
43: }
44: }
45: }
46:
47: /* now, reflect transitivity */
48:
49: changes = 1;
50: while( changes ){
51: changes = 0;
52: for( i=0; i<=nnonter; ++i ){
53: t = pres[i+1];
54: for( s=pres[i]; s<t; ++s ){
55: for( p = *s; ( ch = (*p-NTBASE) ) >= 0; ++p ) {
56: changes |= UNION( wsets[i].ws, wsets[i].ws, wsets[ch].ws );
57: if( !pempty[ch] ) break;
58: }
59: }
60: }
61: }
62:
63: for( i=0; i<=nnonter; i++ ) pfirst[i] = flset( wsets[i].ws );
64: if( !indebug ) return;
65: settty();
66: for( i=0; i<=nnonter; i++ ){
67: fprintf( cout , "\n%s: ", nontrst[i].name );
68: prlook( pfirst[i] );
69: fprintf( cout , " %d\n", pempty[i] );
70: }
71: }
72:
73: state(c){ /* sorts last state,and sees if it equals earlier ones. returns state number */
74: int *s,size1,size2;
75: struct looksets *lp;
76: _REGISTER i;
77: struct item *p1, *p2, *k, *l, *q1, *q2;
78: p1 = pstate[nstate];
79: p2 = pstate[nstate+1];
80: if(p1==p2) return(0); /* null state */
81: /* sort the items */
82: for(k=p2-1;k>p1;k--) { /* make k the biggest */
83: for(l=k-1;l>=p1;--l)if( l->pitem > k->pitem ){
84: s = k->pitem;
85: k->pitem = l->pitem;
86: l->pitem = s;
87: lp = k->look;
88: k->look = l->look;
89: l->look = lp;
90: }
91: }
92: size1 = p2 - p1; /* size of state */
93:
94: for( i= (c>=NTBASE)?ntstates[c-NTBASE]:tstates[c]; i != 0; i = mstates[i] ) {
95: /* get ith state */
96: q1 = pstate[i];
97: q2 = pstate[i+1];
98: size2 = q2 - q1;
99: if (size1 != size2) continue;
100: k=p1;
101: for(l=q1;l<q2;l++) {
102: if( l->pitem != k->pitem ) break;
103: ++k;
104: }
105: if (l != q2) continue;
106: /* found it */
107: pstate[nstate+1] = pstate[nstate]; /* delete last state */
108: /* fix up lookaheads */
109: k=p1;
110: for( l=q1; l<q2; ++l ){
111: if( UNION( clset.lset, l->look->lset, k->look->lset ) ) {
112: tystate[i] = 1;
113: /* register the new set */
114: l->look = flset( &clset );
115: }
116: ++k;
117: }
118: return (i);
119: }
120: /* state is new */
121: pstate[nstate+2] = p2;
122: if(nstate+1 >= stsize) error("too many states");
123: if( c >= NTBASE ){
124: mstates[ nstate ] = ntstates[ c-NTBASE ];
125: ntstates[ c-NTBASE ] = nstate;
126: }
127: else {
128: mstates[ nstate ] = tstates[ c ];
129: tstates[ c ] = nstate;
130: }
131: tystate[nstate]=1;
132: return(nstate++);
133: }
134:
135: int pidebug = 0; /* debugging flag for putitem */
136: putitem ( ptr, lptr ) int *ptr; struct looksets *lptr;{
137: int *jip, k;
138: struct item *i, *j;
139:
140: if( pidebug ) {
141: settty();
142: fprintf( cout , "putitem(%s), state %d\n", writem(&ptr), nstate );
143: }
144: /* see if it's there */
145: j = pstate[nstate+1];
146: for( i=pstate[nstate]; i<j; ++i )
147: if(i->pitem == ptr) {
148: error("yacc error--duplicate item");
149: }
150: /* not there */
151: j->pitem = ptr;
152: j->look = flset( lptr );
153: pstate[nstate+1] = ++j;
154: jip = (int *)j;
155: if(jip-mem0 >= memsiz) error("out of state space");
156: }
157:
158: cempty(){ /* mark nonterminals which derive the empty string */
159:
160: int i, *p;
161:
162: /* set pempty to 0 */
163: pempty = (char *)yalloc( nnonter / sizeof(int) + 1 );
164: aryfil( pempty, nnonter+1, 0 );
165: for( i=1; i<nprod; ++i ) /* loop over productions */
166: if( prdptr[i][1] <= 0 ) /* i is empty production */
167: pempty[ *prdptr[i]-NTBASE ] = 1;
168:
169: /* now, all explicitly empty nonterminals marked with pempty = 1 */
170:
171: /* loop as long as we keep finding nontrivial empty nonterminals */
172:
173: again:
174: for( i=1; i<nprod; ++i ){
175: if( pempty[ *prdptr[i]-NTBASE ]==0 ){ /* not known to be empty */
176: for( p=prdptr[i]+1; *p>=NTBASE && pempty[*p-NTBASE]!=0 ; ++p ) ;
177: if( *p < 0 ){ /* we have a nontrivially empty nonterminal */
178: pempty[*prdptr[i]-NTBASE] = 1;
179: goto again; /* got one ... try for another */
180: }
181: }
182: }
183: }
184:
185: int gsdebug = 0;
186: stagen(){ /* generate the states */
187:
188: int i, j, k, c;
189:
190: /* initialize */
191:
192: nstate = 0;
193: pstate[0] = pstate[1] = (struct item *)mem;
194: aryfil( clset.lset, tbitset, 0 );
195: putitem( prdptr[0]+1, &clset );
196: tystate[0] = 1;
197: nstate = 1;
198: pstate[2] = pstate[1];
199:
200: memact = 0;
201: aryfil( amem, actsiz, 0 );
202:
203: /* now, the main state generation loop */
204:
205: more:
206: for( i=0; i<nstate; ++i ){
207: /* if tystate == 2, set to zero */
208: if( tystate[i] != 1 ) continue;
209: tystate[i] = 0;
210: aryfil( temp1, nterms+nnonter+1, 0 );
211: /* take state i, close it, and do gotos */
212: closure(i);
213: for( j=0; j<cwset; ++j ){ /* generate gotos */
214: if( wsets[j].flag ) continue;
215: wsets[j].flag = 1;
216: c = *(wsets[j].pitem);
217: /* if no symbols after the dot (ie empty rule) */
218: if( c <= 1 ) {
219: /* if not in kernel then tystate = 2 unless not done with it */
220: if( pstate[i+1]-pstate[i] <= j ) tystate[i] = (tystate[i]==1)?1:2;
221: continue;
222: }
223: /* do a goto on c */
224: for( k=j; k<cwset; ++k ){
225: if( c == *(wsets[k].pitem) ){ /* this item contributes to the goto */
226: putitem( wsets[k].pitem + 1, wsets[k].ws );
227: wsets[k].flag = 1;
228: }
229: }
230: if( c < NTBASE ) temp1[c] = state(c);
231: else temp1[c-NTBASE+nterms] = state(c);
232: }
233: if( gsdebug ){
234: settty();
235: fprintf( cout , "%d: ", i );
236: for( j=1; j<=nterms; ++j ){
237: if( temp1[j] != 0 ) fprintf( cout , "%s %d, ", symnam(j), temp1[j]);
238: }
239: for( j=1; j<=nnonter; ++j ){
240: if( temp1[j+nterms] ) fprintf( cout , "%s %d, ", nontrst[j].name, temp1[j+nterms] );
241: }
242: fprintf( cout , "\n");
243: }
244: apstate[i] = apack( &temp1[0], nterms );
245: indgo[i] = apack( &temp1[nterms+1], nnonter-1 ) - 1;
246: goto more; /* we have done one goto; do some more */
247: }
248: /* no more to do... stop */
249: }
250:
251: int cldebug = 0; /* debugging flag for closure */
252: closure(i){ /* generate the closure of state i */
253:
254: int c, ch, work;
255: _REGISTER j, k;
256: int *pi;
257: int **s, **t;
258: struct item *q;
259: _REGISTER struct item *p;
260:
261: ++zzclose;
262:
263: /* first, copy kernel of state i to wsets */
264:
265: lambdarule = -1;
266: cwset = 0;
267: q = pstate[i+1];
268: /* for every item in the kernel */
269: for( p=pstate[i]; p<q; ++p ){
270: wsets[cwset].pitem = p->pitem;
271: wsets[cwset].flag = 1; /* this item must get closed */
272: for( k=0; k<tbitset; ++k ) wsets[cwset].ws[k] = p->look->lset[k];
273: ++cwset;
274: }
275:
276: /* now, go through the loop, closing each item */
277:
278: work = 1;
279: while( work ){
280: work = 0;
281: for( j=0; j<cwset; ++j ){
282:
283: /* for every item in state, if terminal after dot, flag = 0 */
284: if( wsets[j].flag == 0 ) continue;
285: /* dot is before c, since pitem of X -> A.B is B */
286: c = *(wsets[j].pitem);
287:
288: if( c < NTBASE ){
289: wsets[j].flag = 0;
290: continue; /* only interesting case is where . is before nonterminal */
291: }
292:
293: /* compute the lookahead */
294: aryfil( clset.lset, tbitset, 0 );
295:
296: /* find items involving c */
297:
298: /* for all the rest of the items in the state */
299: for( k=j; k<cwset; ++k ){
300: if( wsets[k].flag == 1 && *(pi=wsets[k].pitem) == c ){
301: wsets[k].flag = 0;
302: if( nolook ) continue;
303: while( (ch= *++pi)>0 ){
304: if( ch < NTBASE ){ /* terminal symbol */
305: /* put ch in clset */
306: clset.lset[ch>>4] |= (1<<(ch&017));
307: break;
308: }
309: /* nonterminal symbol */
310: /* clset <- clset U first(ch) */
311: UNION( clset.lset, clset.lset, pfirst[ch-NTBASE] );
312: /* if ch cannot derive lambda we are done */
313: if( !pempty[ch-NTBASE] ) break;
314: }
315: /* if end of rule the clset <- clset U (lookahead for LHS) */
316: if( ch<=0 ) UNION( clset.lset, clset.lset, wsets[k].ws );
317: }
318: }
319:
320: /* now loop over productions derived from c */
321:
322: c -= NTBASE; /* c is now nonterminal number */
323:
324: t = pres[c+1];
325: /* for each rule that c derives */
326: for( s=pres[c]; s<t; ++s ){
327: /* put these items into the closure */
328: for( k=0; k<cwset; ++k ){ /* is the item there */
329: if( wsets[k].pitem == *s ){ /* yes, it is there */
330: if( nolook ) goto nexts;
331: /* if something new in ws, set flag = 1 */
332: if( UNION( wsets[k].ws, wsets[k].ws, clset.lset ) )
333: wsets[k].flag = work = 1;
334: goto nexts;
335: }
336: }
337:
338: /* not there; make a new entry */
339: if( cwset+1 >= wssize ) error( "working set overflow" );
340: wsets[cwset].pitem = *s;
341: wsets[cwset].flag = 1;
342: if (**s < 0)
343: lambdarule = cwset;
344: if( nolook ){
345: cwset++;
346: goto nexts;
347: }
348: work = 1;
349: for( k=0; k<tbitset; ++k ) wsets[cwset].ws[k] = clset.lset[k];
350: cwset++;
351:
352: nexts: ;
353: }
354:
355: }
356: }
357:
358: /* have computed closure; flags are reset; return */
359:
360: if( cwset > zzcwset ) zzcwset = cwset;
361: if( !cldebug ) return;
362: settty();
363: fprintf( cout , "\nState %d, nolook = %d\n", i, nolook );
364: for( j=0; j<cwset; ++j ){
365: if( wsets[j].flag ) fprintf( cout , "flag set!\n");
366: wsets[j].flag = 0;
367: fprintf( cout , "\t%s", writem(&wsets[j].pitem));
368: prlook( wsets[j].ws );
369: fprintf( cout , "\n" );
370: }
371:
372: }
373:
374: struct looksets *flset( p )
375: struct looksets *p;
376: {
377: /* decide if the lookahead set pointed to by p is known */
378: /* return pointer to a perminent location for the set */
379:
380: int j, *w;
381: _REGISTER *u, *v, i;
382:
383: for( i=0; i<nlset; ++i ){
384: u = p->lset;
385: v = lkst[i].lset;
386: w = & v[tbitset];
387: while( v<w) if( *u++ != *v++ ) goto more;
388: /* we have matched */
389: return( & lkst[i] );
390: more: ;
391: }
392: /* add a new one */
393: if( nlset+1 >= lsetsz )error("too many lookahead sets");
394: for( j=0; j<tbitset; ++j ){
395: lkst[nlset].lset[j] = p->lset[j];
396: }
397: return( & lkst[nlset++]);
398: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.