![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to ey4.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 ey4.c CVS log | Up to [CSRG BSD Unix] / 42BSD / ucb / eyacc |
1.1 root 1: static char *sccsid = "@(#)ey4.c 4.2 (Berkeley) 8/30/82";
2: /* (c) 1979 Regents of the University of California */
3: # include "ey.h"
4:
5: output(){ /* print the output for the states */
6:
7: int i, j, k, c;
8:
9: settab();
10: arrset("yyact");
11:
12: for( i=0; i<nstate; ++i ){ /* output the stuff for state i */
13: nolook = (tystate[i]==0);
14: closure(i);
15: /* output actions */
16: aryfil( temp1, nterms+1, 0 );
17: for( j=0; j<cwset; ++j ){ /* look at the items */
18: c = *( wsets[j].pitem );
19: if( c>0 && c<NTBASE && temp1[c]==0 ) temp1[c] = go2(i,c);
20: }
21:
22: if( i == 1 ) temp1[1] = ACCEPTCODE;
23:
24: /* now, we have the shifts; look at the reductions */
25:
26: lastred = 0;
27: for( j=0; j<cwset; ++j ){
28: c = *( wsets[j].pitem );
29: if( c<=0 ){ /* reduction */
30: lastred = -c;
31: for( k=1; k<=nterms; ++k ){
32: if( ((wsets[j].ws[k>>4])&(1<<(k&017))) != 0 ) {
33: if( temp1[k] == 0 ) temp1[k] = c;
34: else if( temp1[k]<0 ){ /* reduce/reduce conflict */
35: settty();
36: fprintf( cout , "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
37: i, -temp1[k], lastred, symnam(k) );
38: if( -temp1[k] > lastred ) temp1[k] = -lastred;
39: ++zzrrconf;
40: settab();
41: }
42: else { /* potential shift/reduce conflict */
43: switch( precftn( lastred, k ) ) {
44:
45: case 0: /* precedence does not apply */
46:
47: settty();
48: fprintf( cout , "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s", i,
49: temp1[k], lastred, symnam(k) );
50: ++zzsrconf;
51: settab();
52: /* resolve in favor of shifting, so remove from reduce set */
53: wsets[j].ws[k>>4] &=~ (1<<(k&017));
54: break;
55:
56: case 1: /* reduce */
57:
58: temp1[k] = -lastred;
59: break;
60:
61: case 2: /* error, binary operator */
62:
63: temp1[k] = ERRCODE;
64: break;
65:
66: case 3: /* shift ... leave the entry alone */
67:
68: break;
69: }
70: }
71: }
72: }
73: }
74: }
75: wract(i);
76: }
77:
78: settab();
79: arrdone();
80:
81: /* now, output the pointers to the action array */
82: /* also output the info about reductions */
83: prred();
84: }
85:
86: prred(){ /* print the information about the actions and the reductions */
87: int index, i;
88:
89: arrset("yypact");
90: index = 1; /* position in the output table */
91:
92: for( i=0; i<nstate; ++i ){
93: if( tystate[i]>0 ){ /* the state is real */
94: temp1[i] = index;
95: arrval( index );
96: index += tystate[i];
97: }
98: else {
99: arrval( temp1[-tystate[i]] );
100: }
101: }
102:
103: arrdone();
104:
105: arrset("yyr1");
106: for( i=1; i<nprod; ++i ) arrval( *prdptr[i] - NTBASE );
107: arrdone();
108:
109: arrset("yyr2");
110: for( i=1; i<nprod; ++i ) arrval( ( prdptr[i+1]-prdptr[i]-2 ) );
111: arrdone();
112:
113: }
114:
115: go2(i,c){ /* do a goto on the closure state, not worrying about lookaheads */
116: if( c<NTBASE ) return( amem[ apstate[i]+c ] );
117: else return( amem[ apstate[i] + c - NTBASE + nterms ] );
118: }
119:
120: int pkdebug = 0;
121: apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
122: _REGISTER k, l, off;
123: int j;
124:
125: /* find the spot */
126:
127: j = n;
128: for( off = 0; off <= j && p[off] == 0; ++off ) ;
129: if( off > j ){ /* no actions */
130: return(0);
131: }
132: j -= off;
133: for( k=0; k<actsiz; ++k ){
134: for( l=0; l<=j; ++l ){
135: if( p[off+l] != 0 ){
136: if( p[off+l] != amem[k+l] && amem[k+l] != 0 ) goto nextk;
137: }
138: }
139: if( pkdebug ){ settty(); fprintf( cout , "off = %d, k = %d\n", off, k ); }
140: /* we have found an acceptable k */
141: for( l=0; l<=j; ++l ){
142: if( p[off+l] ){
143: if( k+l >= actsiz ) error("action table overflow");
144: if( k+l >= memact ) memact = k+l;
145: amem[k+l] = p[off+l];
146: }
147: }
148: if( pkdebug ){
149: for( k=0; k<memact; k+=10){
150: fprintf( cout , "\t");
151: for( l=0; l<=9; ++l ) fprintf( cout , "%d ", amem[k+l] );
152: fprintf( cout , "\n");
153: }
154: }
155: return(k-off);
156:
157: nextk: ;
158: }
159: error("no space in action table");
160: }
161:
162: go2out(){ /* output the gotos for the nontermninals */
163: int i, j, k, best, offset, count, cbest, times;
164:
165: settab();
166: arrset("yygo");
167: offset = 1;
168:
169: for( i=1; i<=nnonter; ++i ) {
170: go2gen(i);
171:
172: /* find the best one to make default */
173:
174: temp2[i] = offset;
175:
176: best = -1;
177: times = 0;
178:
179: for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
180: if( tystate[j] == 0 ) continue;
181: if( tystate[j] == best ) continue;
182:
183: /* is tystate[j] the most frequent */
184:
185: count = 0;
186: cbest = tystate[j];
187:
188: for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
189:
190: if( count > times ){
191: best = cbest;
192: times = count;
193: }
194: }
195:
196: /* best is now the default entry */
197:
198: zzgobest += (times-1)*2;
199: settab();
200: for( j=0; j<=nstate; ++j ){
201: if( tystate[j] != 0 && tystate[j]!=best ){
202: arrval( j );
203: arrval( tystate[j] );
204: offset += 2;
205: zzgoent += 2;
206: }
207: }
208:
209: /* now, the default */
210:
211: zzgoent += 2;
212: arrval( -1 );
213: arrval( best );
214: offset += 2;
215:
216: }
217:
218: arrdone();
219:
220: arrset("yypgo");
221: for( i=1; i<=nnonter; ++i ) arrval( temp2[i] );
222: arrdone();
223:
224: }
225:
226: int g2debug = 0;
227: go2gen(c){ /* output the gotos for nonterminal c */
228:
229: int i, work, cc;
230: struct item *p, *q;
231:
232: /* first, find nonterminals with gotos on c */
233:
234: aryfil( temp1, nnonter+1, 0 );
235: temp1[c] = 1;
236:
237: work = 1;
238: while( work ){
239: work = 0;
240: for( i=0; i<nprod; ++i ){
241: if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
242: if( temp1[cc] != 0 ){ /* cc has a goto on c */
243: cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
244: if( temp1[cc] == 0 ){
245: work = 1;
246: temp1[cc] = 1;
247: }
248: }
249: }
250: }
251: }
252:
253: /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
254:
255: if( g2debug ){
256: settty();
257: fprintf( cout , "%s: gotos on ", nontrst[c].name );
258: for( i=0; i<=nnonter; ++i ) if( temp1[i]) fprintf( cout , "%s ", nontrst[i].name);
259: fprintf( cout , "\n");
260: }
261:
262: /* now, go through and put gotos into tystate */
263:
264: aryfil( tystate, nstate, 0 );
265: settty();
266: fprintf( cout , "\nnonterminal %s\n", nontrst[c].name );
267: for( i=0; i<nstate; ++i ){
268: q = pstate[i+1];
269: for( p=pstate[i]; p<q; ++p ){
270: if( (cc= *p->pitem) >= NTBASE ){
271: if( temp1[cc -= NTBASE] ){ /* goto on c is possible */
272: tystate[i] = amem[indgo[i]+c];
273: break;
274: }
275: }
276: }
277: if( tystate[i] ) fprintf( cout , "\t%d\t%d\n", i, tystate[i]);
278: }
279: }
280:
281: precftn(r,t){ /* decide a shift/reduce conflict by precedence.
282: Returns 0 if action is 'do nothing',1 if action is reduce,
283: 2 if the action is 'error,binary operator'
284: and 3 if the action is 'reduce'. */
285:
286: int lp,lt;
287: lp = levprd[r];
288: lt = trmlev[t];
289: if ((lt==0)||((lp&03)==0))return(0);
290: if((lt>>3) == (lp>>3)){
291: return(lt&03);
292: }
293: if((lt>>3) > (lp>>3)) return(3);
294: return(1);
295: }
296:
297: int cdebug = 0; /* debug for common states */
298: wract(i){ /* output state i */
299: /* temp1 has the actions, lastred the default */
300: int p, p0, p1, size;
301: int ntimes, tred, count, j, k;
302: struct item *q0, *q1;
303:
304: /* find the best choice for lastred */
305:
306: lastred = 0;
307: ntimes = 0;
308: stateflags[i] = 0;
309: /***** UCB MOD - full state spec if shift on error *****/
310: if (temp1[2] > 0)
311: stateflags[i] |= NEEDSREDUCE;
312: else for( j=1; j<=nterms; ++j ){
313: /* find the entry on which the greatest number of reductions are done */
314: if( temp1[j] >= 0 ) continue;
315: if( temp1[j]+lastred == 0 ) continue;
316: /* count the number of appearances of temp1[j] */
317: count = 0;
318: tred = -temp1[j];
319: for( p=1; p<=nterms; ++p ){
320: if( temp1[p]+tred == 0 ) ++count;
321: }
322: if( count >ntimes ){
323: lastred = tred;
324: ntimes = count;
325: }
326: }
327:
328: /* clear out entries in temp1 which equal lastred */
329: /* ie, make the most frequent reduction into the default reduction */
330: for( p=1; p<= nterms; ++p ) if( temp1[p]+lastred == 0 )temp1[p]=0;
331:
332: /* write out the state */
333:
334: /* first, check for equality with another state */
335: /* see if there is a nonterminal with all dots before it, */
336: /* and no reductions in the state */
337: /* this is done by checking if all items are the same non-terminal */
338: p0 = 0;
339: q1 = pstate[i+1];
340: for( q0=pstate[i]; q0<q1; ++q0 ){
341: if( (p1= *(q0->pitem) ) < NTBASE ) goto standard;
342: if( p0 == 0 ) p0 = p1;
343: else if( p0 != p1 ) goto standard;
344: }
345: stateflags[i] |= SINGLE_NT | pempty[p0 - NTBASE];
346:
347: /* now, all items have dots before p0 */
348: if( cdebug ){
349: settty();
350: fprintf( cout , "state %d, pre-nonterminal %s\n",i,nontrst[p0-NTBASE].name);
351: }
352:
353: for( j=0; j<i; ++j ){
354: /*
355: * check that the states have the same shift lookaheads.
356: */
357: if( apstate[i] != apstate[j] )
358: continue;
359: if (cdebug)
360: fprintf(cout, "states %d and %d have same shift lookaheads\n",i,j);
361:
362: /*
363: * Check that state has one item, and that the item matches.
364: */
365: if ((stateflags[j] & SINGLE_NT) == 0 || *(pstate[j]->pitem) != p0)
366: continue;
367:
368: /*
369: * Check that enumeration and reduce lookaheads are the same.
370: */
371: if ((stateflags[i]&(GENLAMBDA|NEEDSREDUCE)) == (GENLAMBDA|NEEDSREDUCE)) {
372: /*
373: * p0 derives lambda.
374: * state[i] needs full reduce lookahead
375: * state[j] has full reduce lookahead
376: */
377: if ((stateflags[j] & NEEDSREDUCE) == 0)
378: error("state %d does not need full reduce", j);
379: if (lambdarule < 0)
380: error("missing lambda rule definition in state %d", i);
381: if (lookstate[j] == 0)
382: error("state %d lookahead was not saved", j);
383: /* must check lookaheads */
384: for (k = 0; k < tbitset; ++k)
385: if (lastate[lookstate[j]].lset[k] != wsets[lambdarule].ws[k])
386: /* cannot merge states */ goto nextj;
387: }
388:
389: /* we have a match with state j ! */
390:
391: if( cdebug ){
392: settty();
393: fprintf( cout , "state %d matches state %d\n", i, j);
394: }
395: tystate[i] = -j;
396: zzacsave += tystate[j];
397: zznsave++;
398: wrstate(i);
399: /* merged, so no need for future consideration */
400: stateflags[i] = 0;
401: return;
402:
403: nextj: ;
404: }
405:
406:
407: standard:
408: tystate[i] = 2;
409: wrstate(i);
410: if ((stateflags[i] & (SINGLE_NT|NEEDSREDUCE|GENLAMBDA)) ==
411: (SINGLE_NT|NEEDSREDUCE|GENLAMBDA)) {
412: if (savedlook + 1 >= maxlastate) {
413: settty();
414: fprintf(cout,
415: "Warning: _maxlastate too small (%d), state packing impared\n",
416: maxlastate);
417: /* cannot consider future merger with this state */
418: stateflags[i] = 0;
419: } else {
420: if( cdebug ){
421: settty();
422: fprintf( cout , "save lookahead for state %d\n", i);
423: }
424: lookstate[i] = savedlook;
425: for (k = 0; k < tbitset; ++k)
426: lastate[savedlook].lset[k] = wsets[lambdarule].ws[k];
427: savedlook++;
428: }
429: }
430:
431: size = 0;
432: for( p0=1; p0<=nterms; ++p0 )
433: if( (p1=temp1[p0])!=0 ) {
434: /***** UCB MOD - test actions are negative of symbol to be tested
435: this speeds up the parser as it is easy to check for
436: *****/
437: arrval( -trmset[p0].value );
438: if( p1 < 0 ) arrval( REDUCACT - p1 );
439: else if( p1 == ACCEPTCODE ) arrval( ACCEPTACT );
440: else if( p1 == ERRCODE ) arrval( ERRACT );
441: else arrval( SHIFTACT + p1 );
442: size += 2;
443: }
444: if( lastred ) arrval( REDUCACT + lastred );
445: else arrval( ERRACT );
446: tystate[i] = size+1; /* store entry size in tystate */
447: zzacent += (size+1);
448: return;
449: }
450:
451: wrstate(i){ /* writes state i */
452: int j0,j1,s;
453: struct item *pp, *qq;
454: settty();
455: fprintf( cout , "\nstate %d\n",i);
456: qq = pstate[i+1];
457: for( pp=pstate[i]; pp<qq; ++pp) fprintf( cout , "\t%s\n", writem(pp));
458:
459: /* check for state equal to another */
460:
461: if( tystate[i] <= 0 ){
462: fprintf( cout , "\n\tsame as %d\n\n", -tystate[i] );
463: return;
464: }
465:
466: for( j0=1; j0<=nterms; ++j0 ) if( (j1=temp1[j0]) != 0 ){
467: fprintf( cout , "\n\t%s ", symnam(j0) );
468: if( j1>0 ){ /* shift, error, or accept */
469: if( j1 == ACCEPTCODE ) fprintf( cout , "accept" );
470: else if( j1 == ERRCODE ) fprintf( cout , "error" );
471: else fprintf( cout , "shift %d", j1 );
472: }
473: else fprintf( cout , "reduce %d",-j1 );
474: }
475:
476: /* output the final production */
477:
478: if( lastred ) fprintf( cout , "\n\t. reduce %d\n\n", lastred );
479: else fprintf( cout , "\n\t. error\n\n" );
480:
481: ret:
482: settab();
483: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.