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