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