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