2.11BSD#431 - /usr/src/usr.bin/yacc/y3.c

   1: #if !defined(lint) && defined(DOSCCS)
   2: static char sccsid[] = "@(#)y3.c	4.1.1	(2.11BSD)	1995/05/11";
   3: #endif
   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;
  14:     register int c;
  15:     register struct wset *u, *v;
  16: 
  17:     fprintf( ftable, "short yyexca[] ={\n" );
  18: 
  19:     SLOOP(i) { /* output the stuff for state i */
  20:         nolook = !(tystate[i]==MUSTLOOKAHEAD);
  21:         closure(i);
  22:         /* output actions */
  23:         nolook = 1;
  24:         aryfil( temp1, ntokens+nnonter+1, 0 );
  25:         WSLOOP(wsets,u){
  26:             c = *( u->pitem );
  27:             if( c>1 && c<NTBASE && temp1[c]==0 ) {
  28:                 WSLOOP(u,v){
  29:                     if( c == *(v->pitem) ) putitem( v->pitem+1, (struct looksets *)0 );
  30:                     }
  31:                 temp1[c] = state(c);
  32:                 }
  33:             else if( c > NTBASE && temp1[ (c -= NTBASE) + ntokens ] == 0 ){
  34:                 temp1[ c+ntokens ] = amem[indgo[i]+c];
  35:                 }
  36:             }
  37: 
  38:         if( i == 1 ) temp1[1] = ACCEPTCODE;
  39: 
  40:         /* now, we have the shifts; look at the reductions */
  41: 
  42:         lastred = 0;
  43:         WSLOOP(wsets,u){
  44:             c = *( u->pitem );
  45:             if( c<=0 ){ /* reduction */
  46:                 lastred = -c;
  47:                 TLOOP(k){
  48:                     if( BIT(u->ws.lset,k) ){
  49:                           if( temp1[k] == 0 ) temp1[k] = c;
  50:                           else if( temp1[k]<0 ){ /* reduce/reduce conflict */
  51:                             if( foutput!=NULL )
  52:                               fprintf( foutput,
  53:                                 "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
  54:                                 i, -temp1[k], lastred, symnam(k) );
  55:                             if( -temp1[k] > lastred ) temp1[k] = -lastred;
  56:                             ++zzrrconf;
  57:                             }
  58:                           else { /* potential shift/reduce conflict */
  59:                             precftn( lastred, k, i );
  60:                             }
  61:                         }
  62:                     }
  63:                 }
  64:             }
  65:         wract(i);
  66:         }
  67: 
  68:     fprintf( ftable, "\t};\n" );
  69: 
  70:     wdef( "YYNPROD", nprod );
  71: 
  72:     }
  73: 
  74: int pkdebug = 0;
  75: apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
  76:     int off;
  77:     register *pp, *qq, *rr;
  78:     int *q, *r;
  79: 
  80:     /* we don't need to worry about checking because we
  81: 	   we will only look entries known to be there... */
  82: 
  83:     /* eliminate leading and trailing 0's */
  84: 
  85:     q = p+n;
  86:     for( pp=p,off=0 ; *pp==0 && pp<=q; ++pp,--off ) /* VOID */ ;
  87:     if( pp > q ) return(0);  /* no actions */
  88:     p = pp;
  89: 
  90:     /* now, find a place for the elements from p to q, inclusive */
  91: 
  92:     r = &amem[ACTSIZE-1];
  93:     for( rr=amem; rr<=r; ++rr,++off ){  /* try rr */
  94:         for( qq=rr,pp=p ; pp<=q ; ++pp,++qq){
  95:             if( *pp != 0 ){
  96:                 if( *pp != *qq && *qq != 0 ) goto nextk;
  97:                 }
  98:             }
  99: 
 100:         /* we have found an acceptable k */
 101: 
 102:         if( pkdebug && foutput!=NULL ) fprintf( foutput, "off = %d, k = %d\n", off, rr-amem );
 103: 
 104:         for( qq=rr,pp=p; pp<=q; ++pp,++qq ){
 105:             if( *pp ){
 106:                 if( qq > r ) error( "action table overflow" );
 107:                 if( qq>memp ) memp = qq;
 108:                 *qq = *pp;
 109:                 }
 110:             }
 111:         if( pkdebug && foutput!=NULL ){
 112:             for( pp=amem; pp<= memp; pp+=10 ){
 113:                 fprintf( foutput, "\t");
 114:                 for( qq=pp; qq<=pp+9; ++qq ) fprintf( foutput, "%d ", *qq );
 115:                 fprintf( foutput, "\n");
 116:                 }
 117:             }
 118:         return( off );
 119: 
 120:         nextk: ;
 121:         }
 122:     error("no space in action table" );
 123:     /* NOTREACHED */
 124:     }
 125: 
 126: go2out(){ /* output the gotos for the nontermninals */
 127:     register int i, j, k;
 128:     int best, count, cbest, times;
 129: 
 130:     fprintf( ftemp, "$\n" );  /* mark begining of gotos */
 131: 
 132:     for( i=1; i<=nnonter; ++i ) {
 133:         go2gen(i);
 134: 
 135:         /* find the best one to make default */
 136: 
 137:         best = -1;
 138:         times = 0;
 139: 
 140:         for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
 141:             if( tystate[j] == 0 ) continue;
 142:             if( tystate[j] == best ) continue;
 143: 
 144:             /* is tystate[j] the most frequent */
 145: 
 146:             count = 0;
 147:             cbest = tystate[j];
 148: 
 149:             for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
 150: 
 151:             if( count > times ){
 152:                 best = cbest;
 153:                 times = count;
 154:                 }
 155:             }
 156: 
 157:         /* best is now the default entry */
 158: 
 159:         zzgobest += (times-1);
 160:         for( j=0; j<=nstate; ++j ){
 161:             if( tystate[j] != 0 && tystate[j]!=best ){
 162:                 fprintf( ftemp, "%d,%d,", j, tystate[j] );
 163:                 zzgoent += 1;
 164:                 }
 165:             }
 166: 
 167:         /* now, the default */
 168: 
 169:         zzgoent += 1;
 170:         fprintf( ftemp, "%d\n", best );
 171: 
 172:         }
 173: 
 174: 
 175: 
 176:     }
 177: 
 178: int g2debug = 0;
 179: go2gen(c){ /* output the gotos for nonterminal c */
 180: 
 181:     register int i, cc;
 182:     int work;
 183:     struct item *p, *q;
 184: 
 185: 
 186:     /* first, find nonterminals with gotos on c */
 187: 
 188:     aryfil( temp1, nnonter+1, 0 );
 189:     temp1[c] = 1;
 190: 
 191:     work = 1;
 192:     while( work ){
 193:         work = 0;
 194:         PLOOP(0,i){
 195:             if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
 196:                 if( temp1[cc] != 0 ){ /* cc has a goto on c */
 197:                     cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
 198:                     if( temp1[cc] == 0 ){
 199:                           work = 1;
 200:                           temp1[cc] = 1;
 201:                           }
 202:                     }
 203:                 }
 204:             }
 205:         }
 206: 
 207:     /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
 208: 
 209:     if( g2debug && foutput!=NULL ){
 210:         fprintf( foutput, "%s: gotos on ", nontrst[c].name );
 211:         NTLOOP(i) if( temp1[i] ) fprintf( foutput, "%s ", nontrst[i].name);
 212:         fprintf( foutput, "\n");
 213:         }
 214: 
 215:     /* now, go through and put gotos into tystate */
 216: 
 217:     aryfil( tystate, nstate, 0 );
 218:     SLOOP(i){
 219:         ITMLOOP(i,p,q){
 220:             if( (cc= *p->pitem) >= NTBASE ){
 221:                 if( temp1[cc -= NTBASE] ){ /* goto on c is possible */
 222:                     tystate[i] = amem[indgo[i]+c];
 223:                     break;
 224:                     }
 225:                 }
 226:             }
 227:         }
 228:     }
 229: 
 230: precftn(r,t,s) register int t;
 231:     { /* decide a shift/reduce conflict by precedence.
 232: 	/* r is a rule number, t a token number */
 233:     /* the conflict is in state s */
 234:     /* temp1[t] is changed to reflect the action */
 235: 
 236:     int lp,lt, action;
 237: 
 238:     lp = levprd[r];
 239:     lt = toklev[t];
 240:     if( PLEVEL(lt) == 0 || PLEVEL(lp) == 0 ) {
 241:         /* conflict */
 242:         if( foutput != NULL ) fprintf( foutput, "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s",
 243:                         s, temp1[t], r, symnam(t) );
 244:         ++zzsrconf;
 245:         return;
 246:         }
 247:     if( PLEVEL(lt) == PLEVEL(lp) ) action = ASSOC(lt);
 248:     else if( PLEVEL(lt) > PLEVEL(lp) ) action = RASC;  /* shift */
 249:     else action = LASC;  /* reduce */
 250: 
 251:     switch( action ){
 252: 
 253:     case BASC:  /* error action */
 254:         temp1[t] = ERRCODE;
 255:         return;
 256: 
 257:     case LASC:  /* reduce */
 258:         temp1[t] = -r;
 259:         return;
 260: 
 261:         }
 262:     }
 263: 
 264: wract(i) register int i; { /* output state i */
 265:     /* temp1 has the actions, lastred the default */
 266:     int p, p0, p1;
 267:     int ntimes, tred, count;
 268:     register int j;
 269:     int flag;
 270: 
 271:     /* find the best choice for lastred */
 272: 
 273:     lastred = 0;
 274:     ntimes = 0;
 275:     TLOOP(j){
 276:         if( temp1[j] >= 0 ) continue;
 277:         if( temp1[j]+lastred == 0 ) continue;
 278:         /* count the number of appearances of temp1[j] */
 279:         count = 0;
 280:         tred = -temp1[j];
 281:         levprd[tred] |= REDFLAG;
 282:         TLOOP(p){
 283:             if( temp1[p]+tred == 0 ) ++count;
 284:             }
 285:         if( count >ntimes ){
 286:             lastred = tred;
 287:             ntimes = count;
 288:             }
 289:         }
 290: 
 291:     /* for error recovery, arrange that, if there is a shift on the
 292: 	/* error recovery token, `error', that the default be the error action */
 293:     if( temp1[1] > 0 ) lastred = 0;
 294: 
 295:     /* clear out entries in temp1 which equal lastred */
 296:     TLOOP(p) if( temp1[p]+lastred == 0 )temp1[p]=0;
 297: 
 298:     wrstate(i);
 299:     defact[i] = lastred;
 300: 
 301:     flag = 0;
 302:     TLOOP(p0){
 303:         if( (p1=temp1[p0])!=0 ) {
 304:             if( p1 < 0 ){
 305:                 p1 = -p1;
 306:                 goto exc;
 307:                 }
 308:             else if( p1 == ACCEPTCODE ) {
 309:                 p1 = -1;
 310:                 goto exc;
 311:                 }
 312:             else if( p1 == ERRCODE ) {
 313:                 p1 = 0;
 314:                 goto exc;
 315:             exc:
 316:                 if( flag++ == 0 ) fprintf( ftable, "-1, %d,\n", i );
 317:                 fprintf( ftable, "\t%d, %d,\n", tokset[p0].value, p1 );
 318:                 ++zzexcp;
 319:                 }
 320:             else {
 321:                 fprintf( ftemp, "%d,%d,", tokset[p0].value, p1 );
 322:                 ++zzacent;
 323:                 }
 324:             }
 325:         }
 326:     if( flag ) {
 327:         defact[i] = -2;
 328:         fprintf( ftable, "\t-2, %d,\n", lastred );
 329:         }
 330:     fprintf( ftemp, "\n" );
 331:     return;
 332:     }
 333: 
 334: wrstate(i){ /* writes state i */
 335:     register j0,j1;
 336:     register struct item *pp, *qq;
 337:     register struct wset *u;
 338: 
 339:     if( foutput == NULL ) return;
 340:     fprintf( foutput, "\nstate %d\n",i);
 341:     ITMLOOP(i,pp,qq) fprintf( foutput, "\t%s\n", writem(pp->pitem));
 342:     if( tystate[i] == MUSTLOOKAHEAD ){
 343:         /* print out empty productions in closure */
 344:         WSLOOP( wsets+(pstate[i+1]-pstate[i]), u ){
 345:             if( *(u->pitem) < 0 ) fprintf( foutput, "\t%s\n", writem(u->pitem) );
 346:             }
 347:         }
 348: 
 349:     /* check for state equal to another */
 350: 
 351:     TLOOP(j0) if( (j1=temp1[j0]) != 0 ){
 352:         fprintf( foutput, "\n\t%s  ", symnam(j0) );
 353:         if( j1>0 ){ /* shift, error, or accept */
 354:             if( j1 == ACCEPTCODE ) fprintf( foutput,  "accept" );
 355:             else if( j1 == ERRCODE ) fprintf( foutput, "error" );
 356:             else fprintf( foutput,  "shift %d", j1 );
 357:             }
 358:         else fprintf( foutput, "reduce %d",-j1 );
 359:         }
 360: 
 361:     /* output the final production */
 362: 
 363:     if( lastred ) fprintf( foutput, "\n\t.  reduce %d\n\n", lastred );
 364:     else fprintf( foutput, "\n\t.  error\n\n" );
 365: 
 366:     /* now, output nonterminal actions */
 367: 
 368:     j1 = ntokens;
 369:     for( j0 = 1; j0 <= nnonter; ++j0 ){
 370:         if( temp1[++j1] ) fprintf( foutput, "\t%s  goto %d\n", symnam( j0+NTBASE), temp1[j1] );
 371:         }
 372: 
 373:     }
 374: 
 375: wdef( s, n ) char *s; { /* output a definition of s to the value n */
 376:     fprintf( ftable, "# define %s %d\n", s, n );
 377:     }
 378: 
 379: warray( s, v, n ) char *s; int *v, n; {
 380: 
 381:     register i;
 382: 
 383:     fprintf( ftable, "short %s[]={\n", s );
 384:     for( i=0; i<n; ){
 385:         if( i%10 == 0 ) fprintf( ftable, "\n" );
 386:         fprintf( ftable, "%4d", v[i] );
 387:         if( ++i == n ) fprintf( ftable, " };\n" );
 388:         else fprintf( ftable, "," );
 389:         }
 390:     }
 391: 
 392: hideprod(){
 393:     /* in order to free up the mem and amem arrays for the optimizer,
 394: 	/* and still be able to output yyr1, etc., after the sizes of
 395: 	/* the action array is known, we hide the nonterminals
 396: 	/* derived by productions in levprd.
 397: 	*/
 398: 
 399:     register i, j;
 400: 
 401:     j = 0;
 402:     levprd[0] = 0;
 403:     PLOOP(1,i){
 404:         if( !(levprd[i] & REDFLAG) ){
 405:             ++j;
 406:             if( foutput != NULL ){
 407:                 fprintf( foutput, "Rule not reduced:   %s\n", writem( prdptr[i] ) );
 408:                 }
 409:             }
 410:         levprd[i] = *prdptr[i] - NTBASE;
 411:         }
 412:     if( j ) fprintf( stdout, "%d rules never reduced\n", j );
 413:     }

Defined functions

Defined variables