![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to y4.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 40BSD / cmd / yacc|
Return to y4.c CVS log | Up to [CSRG BSD Unix] / 40BSD / cmd / yacc |
1.1 root 1: # include "dextern"
2:
3: # define a amem
4: # define mem mem0
5: # define pa indgo
6: # define yypact temp1
7: # define greed tystate
8:
9: int * ggreed = lkst[0].lset;
10: int * pgo = wsets[0].ws.lset;
11: int *yypgo = &nontrst[0].tvalue;
12:
13: int maxspr = 0; /* maximum spread of any entry */
14: int maxoff = 0; /* maximum offset into a array */
15: int *pmem = mem;
16: int *maxa;
17: # define NOMORE -1000
18:
19: int nxdb = 0;
20: int adb = 0;
21:
22: callopt(){
23:
24: register i, *p, j, k, *q;
25:
26: /* read the arrays from tempfile and set parameters */
27:
28: if( (finput=fopen(TEMPNAME,"r")) == NULL ) error( "optimizer cannot open tempfile" );
29:
30: pgo[0] = 0;
31: yypact[0] = 0;
32: nstate = 0;
33: nnonter = 0;
34: for(;;){
35: switch( gtnm() ){
36:
37: case '\n':
38: yypact[++nstate] = (--pmem) - mem;
39: case ',':
40: continue;
41:
42: case '$':
43: break;
44:
45: default:
46: error( "bad tempfile" );
47: }
48: break;
49: }
50:
51: yypact[nstate] = yypgo[0] = (--pmem) - mem;
52:
53: for(;;){
54: switch( gtnm() ){
55:
56: case '\n':
57: yypgo[++nnonter]= pmem-mem;
58: case ',':
59: continue;
60:
61: case EOF:
62: break;
63:
64: default:
65: error( "bad tempfile" );
66: }
67: break;
68: }
69:
70: yypgo[nnonter--] = (--pmem) - mem;
71:
72:
73:
74: for( i=0; i<nstate; ++i ){
75:
76: k = 32000;
77: j = 0;
78: q = mem + yypact[i+1];
79: for( p = mem + yypact[i]; p<q ; p += 2 ){
80: if( *p > j ) j = *p;
81: if( *p < k ) k = *p;
82: }
83: if( k <= j ){ /* nontrivial situation */
84: /* temporarily, kill this for compatibility
85: j -= k; /* j is now the range */
86: if( k > maxoff ) maxoff = k;
87: }
88: greed[i] = (yypact[i+1]-yypact[i]) + 2*j;
89: if( j > maxspr ) maxspr = j;
90: }
91:
92: /* initialize ggreed table */
93:
94: for( i=1; i<=nnonter; ++i ){
95: ggreed[i] = 1;
96: j = 0;
97: /* minimum entry index is always 0 */
98: q = mem + yypgo[i+1] -1;
99: for( p = mem+yypgo[i]; p<q ; p += 2 ) {
100: ggreed[i] += 2;
101: if( *p > j ) j = *p;
102: }
103: ggreed[i] = ggreed[i] + 2*j;
104: if( j > maxoff ) maxoff = j;
105: }
106:
107:
108: /* now, prepare to put the shift actions into the a array */
109:
110: for( i=0; i<ACTSIZE; ++i ) a[i] = 0;
111: maxa = a;
112:
113: for( i=0; i<nstate; ++i ) {
114: if( greed[i]==0 && adb>1 ) fprintf( ftable, "State %d: null\n", i );
115: pa[i] = YYFLAG1;
116: }
117:
118: while( (i = nxti()) != NOMORE ) {
119: if( i >= 0 ) stin(i);
120: else gin(-i);
121:
122: }
123:
124: if( adb>2 ){ /* print a array */
125: for( p=a; p <= maxa; p += 10){
126: fprintf( ftable, "%4d ", p-a );
127: for( i=0; i<10; ++i ) fprintf( ftable, "%4d ", p[i] );
128: fprintf( ftable, "\n" );
129: }
130: }
131: /* write out the output appropriate to the language */
132:
133: aoutput();
134:
135: osummary();
136: ZAPFILE(TEMPNAME);
137: }
138:
139: gin(i){
140:
141: register *p, *r, *s, *q1, *q2;
142:
143: /* enter gotos on nonterminal i into array a */
144:
145: ggreed[i] = 0;
146:
147: q2 = mem+ yypgo[i+1] - 1;
148: q1 = mem + yypgo[i];
149:
150: /* now, find a place for it */
151:
152: for( p=a; p < &a[ACTSIZE]; ++p ){
153: if( *p ) continue;
154: for( r=q1; r<q2; r+=2 ){
155: s = p + *r +1;
156: if( *s ) goto nextgp;
157: if( s > maxa ){
158: if( (maxa=s) > &a[ACTSIZE] ) error( "a array overflow" );
159: }
160: }
161: /* we have found a spot */
162:
163: *p = *q2;
164: if( p > maxa ){
165: if( (maxa=p) > &a[ACTSIZE] ) error( "a array overflow" );
166: }
167: for( r=q1; r<q2; r+=2 ){
168: s = p + *r + 1;
169: *s = r[1];
170: }
171:
172: pgo[i] = p-a;
173: if( adb>1 ) fprintf( ftable, "Nonterminal %d, entry at %d\n" , i, pgo[i] );
174: goto nextgi;
175:
176: nextgp: ;
177: }
178:
179: error( "cannot place goto %d\n", i );
180:
181: nextgi: ;
182: }
183:
184: stin(i){
185: register *r, *s, n, flag, j, *q1, *q2;
186:
187: greed[i] = 0;
188:
189: /* enter state i into the a array */
190:
191: q2 = mem+yypact[i+1];
192: q1 = mem+yypact[i];
193: /* find an acceptable place */
194:
195: for( n= -maxoff; n<ACTSIZE; ++n ){
196:
197: flag = 0;
198: for( r = q1; r < q2; r += 2 ){
199: if( (s = *r + n + a ) < a ) goto nextn;
200: if( *s == 0 ) ++flag;
201: else if( *s != r[1] ) goto nextn;
202: }
203:
204: /* check that the position equals another only if the states are identical */
205:
206: for( j=0; j<nstate; ++j ){
207: if( pa[j] == n ) {
208: if( flag ) goto nextn; /* we have some disagreement */
209: if( yypact[j+1] + yypact[i] == yypact[j] + yypact[i+1] ){
210: /* states are equal */
211: pa[i] = n;
212: if( adb>1 ) fprintf( ftable, "State %d: entry at %d equals state %d\n",
213: i, n, j );
214: return;
215: }
216: goto nextn; /* we have some disagreement */
217: }
218: }
219:
220: for( r = q1; r < q2; r += 2 ){
221: if( (s = *r + n + a ) >= &a[ACTSIZE] ) error( "out of space in optimizer a array" );
222: if( s > maxa ) maxa = s;
223: if( *s != 0 && *s != r[1] ) error( "clobber of a array, pos'n %d, by %d", s-a, r[1] );
224: *s = r[1];
225: }
226: pa[i] = n;
227: if( adb>1 ) fprintf( ftable, "State %d: entry at %d\n", i, pa[i] );
228: return;
229:
230: nextn: ;
231: }
232:
233: error( "Error; failure to place state %d\n", i );
234:
235: }
236:
237: nxti(){ /* finds the next i */
238: register i, max, maxi;
239:
240: max = 0;
241:
242: for( i=1; i<= nnonter; ++i ) if( ggreed[i] >= max ){
243: max = ggreed[i];
244: maxi = -i;
245: }
246:
247: for( i=0; i<nstate; ++i ) if( greed[i] >= max ){
248: max = greed[i];
249: maxi = i;
250: }
251:
252: if( nxdb ) fprintf( ftable, "nxti = %d, max = %d\n", maxi, max );
253: if( max==0 ) return( NOMORE );
254: else return( maxi );
255: }
256:
257: osummary(){
258: /* write summary */
259:
260: register i, *p;
261:
262: if( foutput == NULL ) return;
263: i=0;
264: for( p=maxa; p>=a; --p ) {
265: if( *p == 0 ) ++i;
266: }
267:
268: fprintf( foutput, "Optimizer space used: input %d/%d, output %d/%d\n",
269: pmem-mem+1, MEMSIZE, maxa-a+1, ACTSIZE );
270: fprintf( foutput, "%d table entries, %d zero\n", (maxa-a)+1, i );
271: fprintf( foutput, "maximum spread: %d, maximum offset: %d\n", maxspr, maxoff );
272:
273: }
274:
275: aoutput(){ /* this version is for C */
276:
277:
278: /* write out the optimized parser */
279:
280: fprintf( ftable, "# define YYLAST %d\n", maxa-a+1 );
281:
282: arout( "yyact", a, (maxa-a)+1 );
283: arout( "yypact", pa, nstate );
284: arout( "yypgo", pgo, nnonter+1 );
285:
286: }
287:
288: arout( s, v, n ) char *s; int *v, n; {
289:
290: register i;
291:
292: fprintf( ftable, "short %s[]={\n", s );
293: for( i=0; i<n; ){
294: if( i%10 == 0 ) fprintf( ftable, "\n" );
295: fprintf( ftable, "%4d", v[i] );
296: if( ++i == n ) fprintf( ftable, " };\n" );
297: else fprintf( ftable, "," );
298: }
299: }
300:
301:
302: gtnm(){
303:
304: register s, val, c;
305:
306: /* read and convert an integer from the standard input */
307: /* return the terminating character */
308: /* blanks, tabs, and newlines are ignored */
309:
310: s = 1;
311: val = 0;
312:
313: while( (c=getc(finput)) != EOF ){
314: if( isdigit(c) ){
315: val = val * 10 + c - '0';
316: }
317: else if ( c == '-' ) s = -1;
318: else break;
319: }
320:
321: *pmem++ = s*val;
322: if( pmem > &mem[MEMSIZE] ) error( "out of space" );
323: return( c );
324:
325: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.