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