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