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