1 #ifndef lint 2 static char sccsid[] = "@(#)y3.c 4.1 (Berkeley) 02/11/83"; 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 } 409