4.3BSD - /usr/src/usr.bin/yacc/y3.c

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

Defined functions

Defined variables