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