1 /*-
2 * Copyright (c) 1979, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * %sccs.include.proprietary.c%
6 */
7
8 #ifndef lint
9 static char sccsid[] = "@(#)ey4.c 8.1 (Berkeley) 06/06/93";
10 #endif /* not lint */
11
12 # include "ey.h"
13
output()14 output(){ /* print the output for the states */
15
16 int i, j, k, c;
17
18 settab();
19 arrset("yyact");
20
21 for( i=0; i<nstate; ++i ){ /* output the stuff for state i */
22 nolook = (tystate[i]==0);
23 closure(i);
24 /* output actions */
25 aryfil( temp1, nterms+1, 0 );
26 for( j=0; j<cwset; ++j ){ /* look at the items */
27 c = *( wsets[j].pitem );
28 if( c>0 && c<NTBASE && temp1[c]==0 ) temp1[c] = go2(i,c);
29 }
30
31 if( i == 1 ) temp1[1] = ACCEPTCODE;
32
33 /* now, we have the shifts; look at the reductions */
34
35 lastred = 0;
36 for( j=0; j<cwset; ++j ){
37 c = *( wsets[j].pitem );
38 if( c<=0 ){ /* reduction */
39 lastred = -c;
40 for( k=1; k<=nterms; ++k ){
41 if( ((wsets[j].ws[k>>4])&(1<<(k&017))) != 0 ) {
42 if( temp1[k] == 0 ) temp1[k] = c;
43 else if( temp1[k]<0 ){ /* reduce/reduce conflict */
44 settty();
45 fprintf( cout , "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
46 i, -temp1[k], lastred, symnam(k) );
47 if( -temp1[k] > lastred ) temp1[k] = -lastred;
48 ++zzrrconf;
49 settab();
50 }
51 else { /* potential shift/reduce conflict */
52 switch( precftn( lastred, k ) ) {
53
54 case 0: /* precedence does not apply */
55
56 settty();
57 fprintf( cout , "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s", i,
58 temp1[k], lastred, symnam(k) );
59 ++zzsrconf;
60 settab();
61 /* resolve in favor of shifting, so remove from reduce set */
62 wsets[j].ws[k>>4] &=~ (1<<(k&017));
63 break;
64
65 case 1: /* reduce */
66
67 temp1[k] = -lastred;
68 break;
69
70 case 2: /* error, binary operator */
71
72 temp1[k] = ERRCODE;
73 break;
74
75 case 3: /* shift ... leave the entry alone */
76
77 break;
78 }
79 }
80 }
81 }
82 }
83 }
84 wract(i);
85 }
86
87 settab();
88 arrdone();
89
90 /* now, output the pointers to the action array */
91 /* also output the info about reductions */
92 prred();
93 }
94
prred()95 prred(){ /* print the information about the actions and the reductions */
96 int index, i;
97
98 arrset("yypact");
99 index = 1; /* position in the output table */
100
101 for( i=0; i<nstate; ++i ){
102 if( tystate[i]>0 ){ /* the state is real */
103 temp1[i] = index;
104 arrval( index );
105 index += tystate[i];
106 }
107 else {
108 arrval( temp1[-tystate[i]] );
109 }
110 }
111
112 arrdone();
113
114 arrset("yyr1");
115 for( i=1; i<nprod; ++i ) arrval( *prdptr[i] - NTBASE );
116 arrdone();
117
118 arrset("yyr2");
119 for( i=1; i<nprod; ++i ) arrval( ( prdptr[i+1]-prdptr[i]-2 ) );
120 arrdone();
121
122 }
123
go2(i,c)124 go2(i,c){ /* do a goto on the closure state, not worrying about lookaheads */
125 if( c<NTBASE ) return( amem[ apstate[i]+c ] );
126 else return( amem[ apstate[i] + c - NTBASE + nterms ] );
127 }
128
129 int pkdebug = 0;
apack(p,n)130 apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
131 _REGISTER k, l, off;
132 int j;
133
134 /* find the spot */
135
136 j = n;
137 for( off = 0; off <= j && p[off] == 0; ++off ) ;
138 if( off > j ){ /* no actions */
139 return(0);
140 }
141 j -= off;
142 for( k=0; k<actsiz; ++k ){
143 for( l=0; l<=j; ++l ){
144 if( p[off+l] != 0 ){
145 if( p[off+l] != amem[k+l] && amem[k+l] != 0 ) goto nextk;
146 }
147 }
148 if( pkdebug ){ settty(); fprintf( cout , "off = %d, k = %d\n", off, k ); }
149 /* we have found an acceptable k */
150 for( l=0; l<=j; ++l ){
151 if( p[off+l] ){
152 if( k+l >= actsiz ) error("action table overflow");
153 if( k+l >= memact ) memact = k+l;
154 amem[k+l] = p[off+l];
155 }
156 }
157 if( pkdebug ){
158 for( k=0; k<memact; k+=10){
159 fprintf( cout , "\t");
160 for( l=0; l<=9; ++l ) fprintf( cout , "%d ", amem[k+l] );
161 fprintf( cout , "\n");
162 }
163 }
164 return(k-off);
165
166 nextk: ;
167 }
168 error("no space in action table");
169 }
170
go2out()171 go2out(){ /* output the gotos for the nontermninals */
172 int i, j, k, best, offset, count, cbest, times;
173
174 settab();
175 arrset("yygo");
176 offset = 1;
177
178 for( i=1; i<=nnonter; ++i ) {
179 go2gen(i);
180
181 /* find the best one to make default */
182
183 temp2[i] = offset;
184
185 best = -1;
186 times = 0;
187
188 for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
189 if( tystate[j] == 0 ) continue;
190 if( tystate[j] == best ) continue;
191
192 /* is tystate[j] the most frequent */
193
194 count = 0;
195 cbest = tystate[j];
196
197 for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
198
199 if( count > times ){
200 best = cbest;
201 times = count;
202 }
203 }
204
205 /* best is now the default entry */
206
207 zzgobest += (times-1)*2;
208 settab();
209 for( j=0; j<=nstate; ++j ){
210 if( tystate[j] != 0 && tystate[j]!=best ){
211 arrval( j );
212 arrval( tystate[j] );
213 offset += 2;
214 zzgoent += 2;
215 }
216 }
217
218 /* now, the default */
219
220 zzgoent += 2;
221 arrval( -1 );
222 arrval( best );
223 offset += 2;
224
225 }
226
227 arrdone();
228
229 arrset("yypgo");
230 for( i=1; i<=nnonter; ++i ) arrval( temp2[i] );
231 arrdone();
232
233 }
234
235 int g2debug = 0;
go2gen(c)236 go2gen(c){ /* output the gotos for nonterminal c */
237
238 int i, work, cc;
239 struct item *p, *q;
240
241 /* first, find nonterminals with gotos on c */
242
243 aryfil( temp1, nnonter+1, 0 );
244 temp1[c] = 1;
245
246 work = 1;
247 while( work ){
248 work = 0;
249 for( i=0; i<nprod; ++i ){
250 if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
251 if( temp1[cc] != 0 ){ /* cc has a goto on c */
252 cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
253 if( temp1[cc] == 0 ){
254 work = 1;
255 temp1[cc] = 1;
256 }
257 }
258 }
259 }
260 }
261
262 /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
263
264 if( g2debug ){
265 settty();
266 fprintf( cout , "%s: gotos on ", nontrst[c].name );
267 for( i=0; i<=nnonter; ++i ) if( temp1[i]) fprintf( cout , "%s ", nontrst[i].name);
268 fprintf( cout , "\n");
269 }
270
271 /* now, go through and put gotos into tystate */
272
273 aryfil( tystate, nstate, 0 );
274 settty();
275 fprintf( cout , "\nnonterminal %s\n", nontrst[c].name );
276 for( i=0; i<nstate; ++i ){
277 q = pstate[i+1];
278 for( p=pstate[i]; p<q; ++p ){
279 if( (cc= *p->pitem) >= NTBASE ){
280 if( temp1[cc -= NTBASE] ){ /* goto on c is possible */
281 tystate[i] = amem[indgo[i]+c];
282 break;
283 }
284 }
285 }
286 if( tystate[i] ) fprintf( cout , "\t%d\t%d\n", i, tystate[i]);
287 }
288 }
289
precftn(r,t)290 precftn(r,t){ /* decide a shift/reduce conflict by precedence.
291 Returns 0 if action is 'do nothing',1 if action is reduce,
292 2 if the action is 'error,binary operator'
293 and 3 if the action is 'reduce'. */
294
295 int lp,lt;
296 lp = levprd[r];
297 lt = trmlev[t];
298 if ((lt==0)||((lp&03)==0))return(0);
299 if((lt>>3) == (lp>>3)){
300 return(lt&03);
301 }
302 if((lt>>3) > (lp>>3)) return(3);
303 return(1);
304 }
305
306 int cdebug = 0; /* debug for common states */
wract(i)307 wract(i){ /* output state i */
308 /* temp1 has the actions, lastred the default */
309 int p, p0, p1, size;
310 int ntimes, tred, count, j, k;
311 struct item *q0, *q1;
312
313 /* find the best choice for lastred */
314
315 lastred = 0;
316 ntimes = 0;
317 stateflags[i] = 0;
318 /***** UCB MOD - full state spec if shift on error *****/
319 if (temp1[2] > 0)
320 stateflags[i] |= NEEDSREDUCE;
321 else for( j=1; j<=nterms; ++j ){
322 /* find the entry on which the greatest number of reductions are done */
323 if( temp1[j] >= 0 ) continue;
324 if( temp1[j]+lastred == 0 ) continue;
325 /* count the number of appearances of temp1[j] */
326 count = 0;
327 tred = -temp1[j];
328 for( p=1; p<=nterms; ++p ){
329 if( temp1[p]+tred == 0 ) ++count;
330 }
331 if( count >ntimes ){
332 lastred = tred;
333 ntimes = count;
334 }
335 }
336
337 /* clear out entries in temp1 which equal lastred */
338 /* ie, make the most frequent reduction into the default reduction */
339 for( p=1; p<= nterms; ++p ) if( temp1[p]+lastred == 0 )temp1[p]=0;
340
341 /* write out the state */
342
343 /* first, check for equality with another state */
344 /* see if there is a nonterminal with all dots before it, */
345 /* and no reductions in the state */
346 /* this is done by checking if all items are the same non-terminal */
347 p0 = 0;
348 q1 = pstate[i+1];
349 for( q0=pstate[i]; q0<q1; ++q0 ){
350 if( (p1= *(q0->pitem) ) < NTBASE ) goto standard;
351 if( p0 == 0 ) p0 = p1;
352 else if( p0 != p1 ) goto standard;
353 }
354 stateflags[i] |= SINGLE_NT | pempty[p0 - NTBASE];
355
356 /* now, all items have dots before p0 */
357 if( cdebug ){
358 settty();
359 fprintf( cout , "state %d, pre-nonterminal %s\n",i,nontrst[p0-NTBASE].name);
360 }
361
362 for( j=0; j<i; ++j ){
363 /*
364 * check that the states have the same shift lookaheads.
365 */
366 if( apstate[i] != apstate[j] )
367 continue;
368 if (cdebug)
369 fprintf(cout, "states %d and %d have same shift lookaheads\n",i,j);
370
371 /*
372 * Check that state has one item, and that the item matches.
373 */
374 if ((stateflags[j] & SINGLE_NT) == 0 || *(pstate[j]->pitem) != p0)
375 continue;
376
377 /*
378 * Check that enumeration and reduce lookaheads are the same.
379 */
380 if ((stateflags[i]&(GENLAMBDA|NEEDSREDUCE)) == (GENLAMBDA|NEEDSREDUCE)) {
381 /*
382 * p0 derives lambda.
383 * state[i] needs full reduce lookahead
384 * state[j] has full reduce lookahead
385 */
386 if ((stateflags[j] & NEEDSREDUCE) == 0)
387 error("state %d does not need full reduce", j);
388 if (lambdarule < 0)
389 error("missing lambda rule definition in state %d", i);
390 if (lookstate[j] == 0)
391 error("state %d lookahead was not saved", j);
392 /* must check lookaheads */
393 for (k = 0; k < tbitset; ++k)
394 if (lastate[lookstate[j]].lset[k] != wsets[lambdarule].ws[k])
395 /* cannot merge states */ goto nextj;
396 }
397
398 /* we have a match with state j ! */
399
400 if( cdebug ){
401 settty();
402 fprintf( cout , "state %d matches state %d\n", i, j);
403 }
404 tystate[i] = -j;
405 zzacsave += tystate[j];
406 zznsave++;
407 wrstate(i);
408 /* merged, so no need for future consideration */
409 stateflags[i] = 0;
410 return;
411
412 nextj: ;
413 }
414
415
416 standard:
417 tystate[i] = 2;
418 wrstate(i);
419 if ((stateflags[i] & (SINGLE_NT|NEEDSREDUCE|GENLAMBDA)) ==
420 (SINGLE_NT|NEEDSREDUCE|GENLAMBDA)) {
421 if (savedlook + 1 >= maxlastate) {
422 settty();
423 fprintf(cout,
424 "Warning: _maxlastate too small (%d), state packing impared\n",
425 maxlastate);
426 /* cannot consider future merger with this state */
427 stateflags[i] = 0;
428 } else {
429 if( cdebug ){
430 settty();
431 fprintf( cout , "save lookahead for state %d\n", i);
432 }
433 lookstate[i] = savedlook;
434 for (k = 0; k < tbitset; ++k)
435 lastate[savedlook].lset[k] = wsets[lambdarule].ws[k];
436 savedlook++;
437 }
438 }
439
440 size = 0;
441 for( p0=1; p0<=nterms; ++p0 )
442 if( (p1=temp1[p0])!=0 ) {
443 /***** UCB MOD - test actions are negative of symbol to be tested
444 this speeds up the parser as it is easy to check for
445 *****/
446 arrval( -trmset[p0].value );
447 if( p1 < 0 ) arrval( REDUCACT - p1 );
448 else if( p1 == ACCEPTCODE ) arrval( ACCEPTACT );
449 else if( p1 == ERRCODE ) arrval( ERRACT );
450 else arrval( SHIFTACT + p1 );
451 size += 2;
452 }
453 if( lastred ) arrval( REDUCACT + lastred );
454 else arrval( ERRACT );
455 tystate[i] = size+1; /* store entry size in tystate */
456 zzacent += (size+1);
457 return;
458 }
459
wrstate(i)460 wrstate(i){ /* writes state i */
461 int j0,j1,s;
462 struct item *pp, *qq;
463 settty();
464 fprintf( cout , "\nstate %d\n",i);
465 qq = pstate[i+1];
466 for( pp=pstate[i]; pp<qq; ++pp) fprintf( cout , "\t%s\n", writem(pp));
467
468 /* check for state equal to another */
469
470 if( tystate[i] <= 0 ){
471 fprintf( cout , "\n\tsame as %d\n\n", -tystate[i] );
472 return;
473 }
474
475 for( j0=1; j0<=nterms; ++j0 ) if( (j1=temp1[j0]) != 0 ){
476 fprintf( cout , "\n\t%s ", symnam(j0) );
477 if( j1>0 ){ /* shift, error, or accept */
478 if( j1 == ACCEPTCODE ) fprintf( cout , "accept" );
479 else if( j1 == ERRCODE ) fprintf( cout , "error" );
480 else fprintf( cout , "shift %d", j1 );
481 }
482 else fprintf( cout , "reduce %d",-j1 );
483 }
484
485 /* output the final production */
486
487 if( lastred ) fprintf( cout , "\n\t. reduce %d\n\n", lastred );
488 else fprintf( cout , "\n\t. error\n\n" );
489
490 ret:
491 settab();
492 }
493