UNIX 6th Ed. - /usr/source/yacc/source/y4.c

   1: # include "dextern"
   2: 
   3: output(){ /* print the output for the states */
   4: 
   5:   int i, j, k, c;
   6: 
   7:   settab();
   8:   arrset("yyact");
   9: 
  10:   for( i=0; i<nstate; ++i ){ /* output the stuff for state i */
  11:     nolook = (tystate[i]==0);
  12:     closure(i);
  13:     /* output actions */
  14:     aryfil( temp1, nterms+1, 0 );
  15:     for( j=0; j<cwset; ++j ){ /* look at the items */
  16:       c = *( wsets[j].pitem );
  17:       if( c>0 && c<NTBASE && temp1[c]==0 ) temp1[c] = go2(i,c);
  18:       }
  19: 
  20:     if( i == 1 ) temp1[1] = ACCEPTCODE;
  21: 
  22:     /* now, we have the shifts; look at the reductions */
  23: 
  24:     lastred = 0;
  25:     for( j=0; j<cwset; ++j ){
  26:       c = *( wsets[j].pitem );
  27:       if( c<=0 ){ /* reduction */
  28:         lastred = -c;
  29:         for( k=1; k<=nterms; ++k ){
  30:           if( ((wsets[j].ws[k>>4])&(1<<(k&017))) != 0 ) {
  31:             if( temp1[k] == 0 ) temp1[k] = c;
  32:             else if( temp1[k]<0 ){ /* reduce/reduce conflict */
  33:               settty();
  34:               printf("\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
  35:                 i, -temp1[k], lastred, symnam(k) );
  36:               if( -temp1[k] > lastred ) temp1[k] = -lastred;
  37:               ++zzrrconf;
  38:               settab();
  39:               }
  40:             else { /* potential shift/reduce conflict */
  41:               switch( precftn( lastred, k ) ) {
  42: 
  43:             case 0: /* precedence does not apply */
  44: 
  45:                 settty();
  46:                 printf("\n%d: shift/reduce conflict (shift %d, red'n %d) on %s", i,
  47:             temp1[k], lastred, symnam(k) );
  48:                 ++zzsrconf;
  49:                 settab();
  50:                 break;
  51: 
  52:             case 1: /*  reduce */
  53: 
  54:                 temp1[k] = -lastred;
  55:                 break;
  56: 
  57:             case 2: /* error, binary operator */
  58: 
  59:                 temp1[k] = ERRCODE;
  60:                 break;
  61: 
  62:             case 3: /* shift ... leave the entry alone */
  63: 
  64:                 break;
  65:                 }
  66:               }
  67:             }
  68:           }
  69:         }
  70:       }
  71:     wract(i);
  72:     }
  73: 
  74:   settab();
  75:   arrdone();
  76: 
  77:   /* now, output the pointers to the action array */
  78:   /* also output the info about reductions */
  79:   prred();
  80:   }
  81: 
  82: prred(){ /* print the information about the actions and the reductions */
  83:   int index, i;
  84: 
  85:   arrset("yypact");
  86:   index = 1;    /* position in the output table */
  87: 
  88:   for( i=0; i<nstate; ++i ){
  89:     if( tystate[i]>0 ){  /* the state is real */
  90:       temp1[i] = index;
  91:       arrval( index );
  92:       index =+ tystate[i];
  93:       }
  94:     else {
  95:       arrval( temp1[-tystate[i]] );
  96:       }
  97:     }
  98: 
  99:   arrdone();
 100: 
 101:   arrset("yyr1");
 102:   for( i=1; i<nprod; ++i ) arrval( *prdptr[i] - NTBASE );
 103:   arrdone();
 104: 
 105:   arrset("yyr2");
 106:   for( i=1; i<nprod; ++i ) arrval( ( prdptr[i+1]-prdptr[i]-2 ) );
 107:   arrdone();
 108: 
 109:   }
 110: 
 111: go2(i,c){ /* do a goto on the closure state, not worrying about lookaheads */
 112:   if( c<NTBASE ) return( amem[ apstate[i]+c ] );
 113:   else return( amem[ apstate[i] + c - NTBASE + nterms ] );
 114:   }
 115: 
 116: int pkdebug 0;
 117: apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
 118:   _REGISTER k, l, off;
 119:   int j;
 120: 
 121:   /* find the spot */
 122: 
 123:   j = n;
 124:   for( off = 0; off <= j && p[off] == 0; ++off ) ;
 125:   if( off > j ){ /* no actions */
 126:     return(0);
 127:     }
 128:   j =- off;
 129:   for( k=0; k<actsiz; ++k ){
 130:     for( l=0; l<=j; ++l ){
 131:       if( p[off+l] != 0 ){
 132:         if( p[off+l] != amem[k+l] && amem[k+l] != 0 ) goto nextk;
 133:         }
 134:       }
 135:     if( pkdebug ){ settty(); printf("off = %d, k = %d\n", off, k ); }
 136:     /* we have found an acceptable k */
 137:     for( l=0; l<=j; ++l ){
 138:       if( p[off+l] ){
 139:         if( k+l >= actsiz ) error("action table overflow");
 140:         if( k+l >= memact ) memact = k+l;
 141:         amem[k+l] = p[off+l];
 142:         }
 143:       }
 144:     if( pkdebug ){
 145:       for( k=0; k<memact; k=+10){
 146:         printf("\t");
 147:         for( l=0; l<=9; ++l ) printf("%d ", amem[k+l] );
 148:         printf("\n");
 149:         }
 150:       }
 151:     return(k-off);
 152: 
 153:     nextk: ;
 154:     }
 155:   error("no space in action table");
 156:   }
 157: 
 158: go2out(){ /* output the gotos for the nontermninals */
 159:   int i, j, k, best, offset, count, cbest, times;
 160: 
 161:   settab();
 162:   arrset("yygo");
 163:   offset = 1;
 164: 
 165:   for( i=1; i<=nnonter; ++i ) {
 166:     go2gen(i);
 167: 
 168:     /* find the best one to make default */
 169: 
 170:     temp2[i] = offset;
 171: 
 172:     best = -1;
 173:     times = 0;
 174: 
 175:     for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
 176:       if( tystate[j] == 0 ) continue;
 177:       if( tystate[j] == best ) continue;
 178: 
 179:       /* is tystate[j] the most frequent */
 180: 
 181:       count = 0;
 182:       cbest = tystate[j];
 183: 
 184:       for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
 185: 
 186:       if( count > times ){
 187:         best = cbest;
 188:         times = count;
 189:         }
 190:       }
 191: 
 192:     /* best is now the default entry */
 193: 
 194:     zzgobest =+ (times-1)*2;
 195:     settab();
 196:     for( j=0; j<=nstate; ++j ){
 197:       if( tystate[j] != 0 && tystate[j]!=best ){
 198:         arrval( j );
 199:         arrval( tystate[j] );
 200:         offset =+ 2;
 201:         zzgoent =+ 2;
 202:         }
 203:       }
 204: 
 205:     /* now, the default */
 206: 
 207:     zzgoent =+ 2;
 208:     arrval( -1 );
 209:     arrval( best );
 210:     offset =+ 2;
 211: 
 212:     }
 213: 
 214:   arrdone();
 215: 
 216:   arrset("yypgo");
 217:   for( i=1; i<=nnonter; ++i ) arrval( temp2[i] );
 218:   arrdone();
 219: 
 220:   }
 221: 
 222: int g2debug 0;
 223: go2gen(c){ /* output the gotos for nonterminal c */
 224: 
 225:   int i, work, cc;
 226:   struct item *p, *q;
 227: 
 228:   /* first, find nonterminals with gotos on c */
 229: 
 230:   aryfil( temp1, nnonter+1, 0 );
 231:   temp1[c] = 1;
 232: 
 233:   work = 1;
 234:   while( work ){
 235:     work = 0;
 236:     for( i=0; i<nprod; ++i ){
 237:       if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
 238:         if( temp1[cc] != 0 ){ /* cc has a goto on c */
 239:           cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
 240:           if( temp1[cc] == 0 ){
 241:             work = 1;
 242:             temp1[cc] = 1;
 243:             }
 244:           }
 245:         }
 246:       }
 247:     }
 248: 
 249:   /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
 250: 
 251:   if( g2debug ){
 252:     settty();
 253:     printf("%s: gotos on ", nontrst[c].name );
 254:     for( i=0; i<=nnonter; ++i ) if( temp1[i]) printf("%s ", nontrst[i].name);
 255:     printf("\n");
 256:     }
 257: 
 258:   /* now, go through and put gotos into tystate */
 259: 
 260:   aryfil( tystate, nstate, 0 );
 261:   settty();
 262:   printf("\nnonterminal %s\n", nontrst[c].name );
 263:   for( i=0; i<nstate; ++i ){
 264:     q = pstate[i+1];
 265:     for( p=pstate[i]; p<q; ++p ){
 266:       if( (cc= *p->pitem) >= NTBASE ){
 267:         if( temp1[cc =- NTBASE] ){ /* goto on c is possible */
 268:           tystate[i] = amem[indgo[i]+c];
 269:           break;
 270:           }
 271:         }
 272:       }
 273:     if( tystate[i] ) printf("\t%d\t%d\n", i, tystate[i]);
 274:     }
 275:   }
 276: 
 277: precftn(r,t){ /* decide a shift/reduce conflict by precedence.
 278: 			Returns 0 if action is 'do nothing',1 if action is reduce,
 279: 			2 if the action is 'error,binary operator'
 280: 			and 3 if the action is 'reduce'. */
 281: 
 282:     int lp,lt;
 283:     lp = levprd[r];
 284:     lt = trmlev[t];
 285:     if ((lt==0)||((lp&03)==0))return(0);
 286:     if((lt>>3) == (lp>>3)){
 287:         return(lt&03);
 288:         }
 289:     if((lt>>3) > (lp>>3)) return(3);
 290:     return(1);
 291:     }
 292: 
 293: int cdebug 0; /* debug for common states */
 294: wract(i){ /* output state i */
 295:   /* temp1 has the actions, lastred the default */
 296:   int p, p0, p1, size;
 297:   int ntimes, tred, count, j;
 298:   struct item *q0, *q1;
 299: 
 300:   /* find the best choice for lastred */
 301: 
 302:   lastred = 0;
 303:   ntimes = 0;
 304:   for( j=1; j<=nterms; ++j ){
 305:     if( temp1[j] >= 0 ) continue;
 306:     if( temp1[j]+lastred == 0 ) continue;
 307:     /* count the number of appearances of temp1[j] */
 308:     count = 0;
 309:     tred = -temp1[j];
 310:     for( p=1; p<=nterms; ++p ){
 311:       if( temp1[p]+tred == 0 ) ++count;
 312:       }
 313:     if( count >ntimes ){
 314:       lastred = tred;
 315:       ntimes = count;
 316:       }
 317:     }
 318: 
 319:     /* clear out entries in temp1 which equal lastred */
 320:     for( p=1; p<= nterms; ++p ) if( temp1[p]+lastred == 0 )temp1[p]=0;
 321: 
 322:     /* write out the state */
 323: 
 324:     /* first, check for equality with another state */
 325:     /* see if there is a nonterminal with all dots before it. */
 326: 
 327:     p0 = 0;
 328:     q1 = pstate[i+1];
 329:     for( q0=pstate[i]; q0<q1; ++q0 ){
 330:       if( (p1= *(q0->pitem) ) < NTBASE ) goto standard;
 331:       if( p0 == 0 ) p0 = p1;
 332:       else if( p0 != p1 ) goto standard;
 333:       }
 334: 
 335:     /* now, all items have dots before p0 */
 336:     if( cdebug ){
 337:       settty();
 338:       printf("state %d, pre-nonterminal %s\n",i,nontrst[p0-NTBASE].name);
 339:       }
 340: 
 341:     for( j=0; j<i; ++j ){
 342:       if( apstate[i] != apstate[j] ) continue;
 343: 
 344:       /* equal positions -- check items */
 345: 
 346:       if( cdebug )printf("states %d and %d have equal positions\n",i,j);
 347:       q1 = pstate[j+1];
 348:       for( q0=pstate[j]; q0<q1; ++q0 ){
 349:         if( *(q0->pitem) != p0 ) goto nextj;
 350:         }
 351: 
 352:       /* we have a match with state j ! */
 353: 
 354:       tystate[i] = -j;
 355:       zzacsave =+ tystate[j];
 356:       zznsave++;
 357:       wrstate(i);
 358:       return;
 359: 
 360:     nextj:  ;
 361:       }
 362: 
 363: 
 364:   standard:
 365:     tystate[i] = 2;
 366:     wrstate(i);
 367: 
 368:     size = 0;
 369:     for( p0=1; p0<=nterms; ++p0 )
 370:       if( (p1=temp1[p0])!=0 ) {
 371:         arrval( TESTACT+trmset[p0].value );
 372:         if( p1 < 0 ) arrval( REDUCACT - p1 );
 373:         else if( p1 == ACCEPTCODE ) arrval( ACCEPTACT );
 374:         else if( p1 == ERRCODE ) arrval( ERRACT );
 375:         else arrval( SHIFTACT + p1 );
 376:         size =+ 2;
 377:         }
 378:     if( lastred ) arrval( REDUCACT + lastred );
 379:     else arrval( ERRACT );
 380:     tystate[i] = size+1; /* store entry size in tystate */
 381:     zzacent =+ (size+1);
 382:     return;
 383:   }
 384: 
 385: wrstate(i){ /* writes state i */
 386:     int j0,j1,s;
 387:         struct item *pp, *qq;
 388:     settty();
 389:     printf("\nstate %d\n",i);
 390:     qq = pstate[i+1];
 391:     for( pp=pstate[i]; pp<qq; ++pp) printf("\t%s\n", writem(pp));
 392: 
 393:         /* check for state equal to another */
 394: 
 395:         if( tystate[i] <= 0 ){
 396:           printf("\n\tsame as %d\n\n", -tystate[i] );
 397:           return;
 398:           }
 399: 
 400:     for( j0=1; j0<=nterms; ++j0 ) if( (j1=temp1[j0]) != 0 ){
 401:     printf("\n\t%s  ", symnam(j0) );
 402:              if( j1>0 ){ /* shift, error, or accept */
 403:                if( j1 == ACCEPTCODE ) printf( "accept" );
 404:                else if( j1 == ERRCODE ) printf( "error" );
 405:                else printf( "shift %d", j1 );
 406:                }
 407:            else printf("reduce %d",-j1 );
 408:        }
 409: 
 410:     /* output the final production */
 411: 
 412:     if( lastred ) printf("\n\t.  reduce %d\n\n", lastred );
 413:     else printf("\n\t.  error\n\n" );
 414: 
 415: ret:
 416:     settab();
 417:     }

Defined functions

Defined variables