Commit | Line | Data |
---|---|---|
39d276e4 RH |
1 | #ifndef lint |
2 | static char sccsid[] = "@(#)y4.c 4.1 (Berkeley) %G%"; | |
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 | } |