![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to y3.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 3BSD / cmd / yacc|
Return to y3.c CVS log | Up to [CSRG BSD Unix] / 3BSD / cmd / yacc |
1.1 root 1: # include "dextern"
2:
3: /* important local variables */
4: int lastred; /* the number of the last reduction of a state */
5: int defact[NSTATES]; /* the default actions of states */
6:
7: output(){ /* print the output for the states */
8:
9: int i, k, c;
10: register struct wset *u, *v;
11:
12: fprintf( ftable, "short yyexca[] ={\n" );
13:
14: SLOOP(i) { /* output the stuff for state i */
15: nolook = !(tystate[i]==MUSTLOOKAHEAD);
16: closure(i);
17: /* output actions */
18: nolook = 1;
19: aryfil( temp1, ntokens+nnonter+1, 0 );
20: WSLOOP(wsets,u){
21: c = *( u->pitem );
22: if( c>1 && c<NTBASE && temp1[c]==0 ) {
23: WSLOOP(u,v){
24: if( c == *(v->pitem) ) putitem( v->pitem+1, (struct looksets *)0 );
25: }
26: temp1[c] = state(c);
27: }
28: else if( c > NTBASE && temp1[ (c -= NTBASE) + ntokens ] == 0 ){
29: temp1[ c+ntokens ] = amem[indgo[i]+c];
30: }
31: }
32:
33: if( i == 1 ) temp1[1] = ACCEPTCODE;
34:
35: /* now, we have the shifts; look at the reductions */
36:
37: lastred = 0;
38: WSLOOP(wsets,u){
39: c = *( u->pitem );
40: if( c<=0 ){ /* reduction */
41: lastred = -c;
42: TLOOP(k){
43: if( BIT(u->ws.lset,k) ){
44: if( temp1[k] == 0 ) temp1[k] = c;
45: else if( temp1[k]<0 ){ /* reduce/reduce conflict */
46: if( foutput!=NULL )
47: fprintf( foutput,
48: "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
49: i, -temp1[k], lastred, symnam(k) );
50: if( -temp1[k] > lastred ) temp1[k] = -lastred;
51: ++zzrrconf;
52: }
53: else { /* potential shift/reduce conflict */
54: precftn( lastred, k, i );
55: }
56: }
57: }
58: }
59: }
60: wract(i);
61: }
62:
63: fprintf( ftable, "\t};\n" );
64:
65: wdef( "YYNPROD", nprod );
66:
67: }
68:
69: int pkdebug = 0;
70: apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
71: int off;
72: register *pp, *qq, *rr;
73: int *q, *r;
74:
75: /* we don't need to worry about checking because we
76: we will only look entries known to be there... */
77:
78: /* eliminate leading and trailing 0's */
79:
80: q = p+n;
81: for( pp=p,off=0 ; *pp==0 && pp<=q; ++pp,--off ) /* VOID */ ;
82: if( pp > q ) return(0); /* no actions */
83: p = pp;
84:
85: /* now, find a place for the elements from p to q, inclusive */
86:
87: r = &amem[ACTSIZE-1];
88: for( rr=amem; rr<=r; ++rr,++off ){ /* try rr */
89: for( qq=rr,pp=p ; pp<=q ; ++pp,++qq){
90: if( *pp != 0 ){
91: if( *pp != *qq && *qq != 0 ) goto nextk;
92: }
93: }
94:
95: /* we have found an acceptable k */
96:
97: if( pkdebug && foutput!=NULL ) fprintf( foutput, "off = %d, k = %d\n", off, rr-amem );
98:
99: for( qq=rr,pp=p; pp<=q; ++pp,++qq ){
100: if( *pp ){
101: if( qq > r ) error( "action table overflow" );
102: if( qq>memp ) memp = qq;
103: *qq = *pp;
104: }
105: }
106: if( pkdebug && foutput!=NULL ){
107: for( pp=amem; pp<= memp; pp+=10 ){
108: fprintf( foutput, "\t");
109: for( qq=pp; qq<=pp+9; ++qq ) fprintf( foutput, "%d ", *qq );
110: fprintf( foutput, "\n");
111: }
112: }
113: return( off );
114:
115: nextk: ;
116: }
117: error("no space in action table" );
118: /* NOTREACHED */
119: }
120:
121: go2out(){ /* output the gotos for the nontermninals */
122: int i, j, k, best, count, cbest, times;
123:
124: fprintf( ftemp, "$\n" ); /* mark begining of gotos */
125:
126: for( i=1; i<=nnonter; ++i ) {
127: go2gen(i);
128:
129: /* find the best one to make default */
130:
131: best = -1;
132: times = 0;
133:
134: for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
135: if( tystate[j] == 0 ) continue;
136: if( tystate[j] == best ) continue;
137:
138: /* is tystate[j] the most frequent */
139:
140: count = 0;
141: cbest = tystate[j];
142:
143: for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
144:
145: if( count > times ){
146: best = cbest;
147: times = count;
148: }
149: }
150:
151: /* best is now the default entry */
152:
153: zzgobest += (times-1);
154: for( j=0; j<=nstate; ++j ){
155: if( tystate[j] != 0 && tystate[j]!=best ){
156: fprintf( ftemp, "%d,%d,", j, tystate[j] );
157: zzgoent += 1;
158: }
159: }
160:
161: /* now, the default */
162:
163: zzgoent += 1;
164: fprintf( ftemp, "%d\n", best );
165:
166: }
167:
168:
169:
170: }
171:
172: int g2debug = 0;
173: go2gen(c){ /* output the gotos for nonterminal c */
174:
175: int i, work, cc;
176: struct item *p, *q;
177:
178:
179: /* first, find nonterminals with gotos on c */
180:
181: aryfil( temp1, nnonter+1, 0 );
182: temp1[c] = 1;
183:
184: work = 1;
185: while( work ){
186: work = 0;
187: PLOOP(0,i){
188: if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
189: if( temp1[cc] != 0 ){ /* cc has a goto on c */
190: cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
191: if( temp1[cc] == 0 ){
192: work = 1;
193: temp1[cc] = 1;
194: }
195: }
196: }
197: }
198: }
199:
200: /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
201:
202: if( g2debug && foutput!=NULL ){
203: fprintf( foutput, "%s: gotos on ", nontrst[c].name );
204: NTLOOP(i) if( temp1[i] ) fprintf( foutput, "%s ", nontrst[i].name);
205: fprintf( foutput, "\n");
206: }
207:
208: /* now, go through and put gotos into tystate */
209:
210: aryfil( tystate, nstate, 0 );
211: SLOOP(i){
212: ITMLOOP(i,p,q){
213: if( (cc= *p->pitem) >= NTBASE ){
214: if( temp1[cc -= NTBASE] ){ /* goto on c is possible */
215: tystate[i] = amem[indgo[i]+c];
216: break;
217: }
218: }
219: }
220: }
221: }
222:
223: precftn(r,t,s){ /* decide a shift/reduce conflict by precedence.
224: /* r is a rule number, t a token number */
225: /* the conflict is in state s */
226: /* temp1[t] is changed to reflect the action */
227:
228: int lp,lt, action;
229:
230: lp = levprd[r];
231: lt = toklev[t];
232: if( PLEVEL(lt) == 0 || PLEVEL(lp) == 0 ) {
233: /* conflict */
234: if( foutput != NULL ) fprintf( foutput, "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s",
235: s, temp1[t], r, symnam(t) );
236: ++zzsrconf;
237: return;
238: }
239: if( PLEVEL(lt) == PLEVEL(lp) ) action = ASSOC(lt);
240: else if( PLEVEL(lt) > PLEVEL(lp) ) action = RASC; /* shift */
241: else action = LASC; /* reduce */
242:
243: switch( action ){
244:
245: case BASC: /* error action */
246: temp1[t] = ERRCODE;
247: return;
248:
249: case LASC: /* reduce */
250: temp1[t] = -r;
251: return;
252:
253: }
254: }
255:
256: wract(i){ /* output state i */
257: /* temp1 has the actions, lastred the default */
258: int p, p0, p1;
259: int ntimes, tred, count, j;
260: int flag;
261:
262: /* find the best choice for lastred */
263:
264: lastred = 0;
265: ntimes = 0;
266: TLOOP(j){
267: if( temp1[j] >= 0 ) continue;
268: if( temp1[j]+lastred == 0 ) continue;
269: /* count the number of appearances of temp1[j] */
270: count = 0;
271: tred = -temp1[j];
272: levprd[tred] |= REDFLAG;
273: TLOOP(p){
274: if( temp1[p]+tred == 0 ) ++count;
275: }
276: if( count >ntimes ){
277: lastred = tred;
278: ntimes = count;
279: }
280: }
281:
282: /* for error recovery, arrange that, if there is a shift on the
283: /* error recovery token, `error', that the default be the error action */
284: if( temp1[1] > 0 ) lastred = 0;
285:
286: /* clear out entries in temp1 which equal lastred */
287: TLOOP(p) if( temp1[p]+lastred == 0 )temp1[p]=0;
288:
289: wrstate(i);
290: defact[i] = lastred;
291:
292: flag = 0;
293: TLOOP(p0){
294: if( (p1=temp1[p0])!=0 ) {
295: if( p1 < 0 ){
296: p1 = -p1;
297: goto exc;
298: }
299: else if( p1 == ACCEPTCODE ) {
300: p1 = -1;
301: goto exc;
302: }
303: else if( p1 == ERRCODE ) {
304: p1 = 0;
305: goto exc;
306: exc:
307: if( flag++ == 0 ) fprintf( ftable, "-1, %d,\n", i );
308: fprintf( ftable, "\t%d, %d,\n", tokset[p0].value, p1 );
309: ++zzexcp;
310: }
311: else {
312: fprintf( ftemp, "%d,%d,", tokset[p0].value, p1 );
313: ++zzacent;
314: }
315: }
316: }
317: if( flag ) {
318: defact[i] = -2;
319: fprintf( ftable, "\t-2, %d,\n", lastred );
320: }
321: fprintf( ftemp, "\n" );
322: return;
323: }
324:
325: wrstate(i){ /* writes state i */
326: register j0,j1;
327: register struct item *pp, *qq;
328: register struct wset *u;
329:
330: if( foutput == NULL ) return;
331: fprintf( foutput, "\nstate %d\n",i);
332: ITMLOOP(i,pp,qq) fprintf( foutput, "\t%s\n", writem(pp->pitem));
333: if( tystate[i] == MUSTLOOKAHEAD ){
334: /* print out empty productions in closure */
335: WSLOOP( wsets+(pstate[i+1]-pstate[i]), u ){
336: if( *(u->pitem) < 0 ) fprintf( foutput, "\t%s\n", writem(u->pitem) );
337: }
338: }
339:
340: /* check for state equal to another */
341:
342: TLOOP(j0) if( (j1=temp1[j0]) != 0 ){
343: fprintf( foutput, "\n\t%s ", symnam(j0) );
344: if( j1>0 ){ /* shift, error, or accept */
345: if( j1 == ACCEPTCODE ) fprintf( foutput, "accept" );
346: else if( j1 == ERRCODE ) fprintf( foutput, "error" );
347: else fprintf( foutput, "shift %d", j1 );
348: }
349: else fprintf( foutput, "reduce %d",-j1 );
350: }
351:
352: /* output the final production */
353:
354: if( lastred ) fprintf( foutput, "\n\t. reduce %d\n\n", lastred );
355: else fprintf( foutput, "\n\t. error\n\n" );
356:
357: /* now, output nonterminal actions */
358:
359: j1 = ntokens;
360: for( j0 = 1; j0 <= nnonter; ++j0 ){
361: if( temp1[++j1] ) fprintf( foutput, "\t%s goto %d\n", symnam( j0+NTBASE), temp1[j1] );
362: }
363:
364: }
365:
366: wdef( s, n ) char *s; { /* output a definition of s to the value n */
367: fprintf( ftable, "# define %s %d\n", s, n );
368: }
369:
370: warray( s, v, n ) char *s; int *v, n; {
371:
372: register i;
373:
374: fprintf( ftable, "short %s[]={\n", s );
375: for( i=0; i<n; ){
376: if( i%10 == 0 ) fprintf( ftable, "\n" );
377: fprintf( ftable, "%4d", v[i] );
378: if( ++i == n ) fprintf( ftable, " };\n" );
379: else fprintf( ftable, "," );
380: }
381: }
382:
383: hideprod(){
384: /* in order to free up the mem and amem arrays for the optimizer,
385: /* and still be able to output yyr1, etc., after the sizes of
386: /* the action array is known, we hide the nonterminals
387: /* derived by productions in levprd.
388: */
389:
390: register i, j;
391:
392: j = 0;
393: levprd[0] = 0;
394: PLOOP(1,i){
395: if( !(levprd[i] & REDFLAG) ){
396: ++j;
397: if( foutput != NULL ){
398: fprintf( foutput, "Rule not reduced: %s\n", writem( prdptr[i] ) );
399: }
400: }
401: levprd[i] = *prdptr[i] - NTBASE;
402: }
403: if( j ) fprintf( stdout, "%d rules never reduced\n", j );
404: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.