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