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