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 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 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 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; 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 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; 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 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 */ 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 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