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