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