4.3BSD - /usr/src/ucb/pascal/eyacc/ey4.c

   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) 4/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:     }

Defined functions

Defined variables