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

   1: # include "dextern"
   2: 
   3: cpres(){ /* conpute an array with the beginnings of  productions yielding given nonterminals
   4: 	The array pres points to these lists */
   5:     int i,j,c;
   6:     pres = yalloc(nnonter+1);
   7:     for(i=0;i<=nnonter;i++){
   8:         c = i+NTBASE;
   9:         pres[i] = mem;
  10:         fatfl = 0;  /* make undefined  symbols  nonfatal */
  11:         for(j=0;j<nprod;j++)
  12:         if (*prdptr[j] == c) *mem++ =  prdptr[j]+1;
  13:         if(pres[i] == mem){
  14:             error("nonterminal %s not defined!", nontrst[i].name);
  15:             }
  16:         }
  17:     pres[i] = mem;
  18:     fatfl = 1;
  19:     if( nerrors ){
  20:         summary();
  21:         cexit(1);
  22:         }
  23:     }
  24: 
  25: int indebug 0;
  26: cpfir() {
  27:   /* compute an array with the first of nonterminals */
  28:   int i, ch, **s, **t, changes, *p;
  29: 
  30:   pfirst = yalloc(nnonter+1);
  31:   for (i=0;i<=nnonter;i++) {
  32:     aryfil( wsets[i].ws, tbitset, 0 );
  33:     t = pres[i+1];
  34:     for( s=pres[i]; s<t; ++s ){ /* initially fill the sets */
  35:       for( p = *s; (ch = *p) > 0 ; ++p ) {
  36:         if( ch < NTBASE ) {
  37:           wsets[i].ws[ch>>4] =| (1 << (ch&017) );
  38:           break;
  39:           }
  40:         else if( !pempty[ch-NTBASE] ) break;
  41:         }
  42:       }
  43:     }
  44: 
  45:   /* now, reflect transitivity */
  46: 
  47:   changes = 1;
  48:   while( changes ){
  49:     changes = 0;
  50:     for( i=0; i<=nnonter; ++i ){
  51:       t = pres[i+1];
  52:       for( s=pres[i]; s<t; ++s ){
  53:         for( p = *s; ( ch = (*p-NTBASE) ) >= 0; ++p ) {
  54:           changes =| union( wsets[i].ws, wsets[i].ws, wsets[ch].ws );
  55:           if( !pempty[ch] ) break;
  56:           }
  57:         }
  58:       }
  59:     }
  60: 
  61:   for( i=0; i<=nnonter; i++ ) pfirst[i] = flset( wsets[i].ws );
  62:   if( !indebug ) return;
  63:   settty();
  64:   for( i=0; i<=nnonter; i++ ){
  65:     printf( "\n%s: ", nontrst[i].name );
  66:     prlook( pfirst[i] );
  67:     printf( " %d\n", pempty[i] );
  68:     }
  69:   }
  70: 
  71: state(c){ /* sorts last state,and sees if it equals earlier ones. returns state number */
  72:     int s,size1,size2;
  73:     _REGISTER i;
  74:     struct item *p1, *p2, *k, *l, *q1, *q2;
  75:     p1 = pstate[nstate];
  76:     p2 = pstate[nstate+1];
  77:     if(p1==p2) return(0); /* null state */
  78:     /* sort the items */
  79:     for(k=p2-1;k>p1;k--) {  /* make k the biggest */
  80:         for(l=k-1;l>=p1;--l)if( l->pitem > k->pitem ){
  81:             s = k->pitem;
  82:             k->pitem = l->pitem;
  83:             l->pitem = s;
  84:             s = k->look;
  85:             k->look = l->look;
  86:             l->look = s;
  87:             }
  88:         }
  89:     size1 = p2 - p1; /* size of state */
  90: 
  91:     for( i= (c>=NTBASE)?ntstates[c-NTBASE]:tstates[c]; i != 0; i = mstates[i] ) {
  92:         /* get ith state */
  93:         q1 = pstate[i];
  94:         q2 = pstate[i+1];
  95:         size2 = q2 - q1;
  96:         if (size1 != size2) continue;
  97:         k=p1;
  98:         for(l=q1;l<q2;l++) {
  99:             if( l->pitem != k->pitem ) break;
 100:             ++k;
 101:             }
 102:         if (l != q2) continue;
 103:         /* found it */
 104:         pstate[nstate+1] = pstate[nstate]; /* delete last state */
 105:         /* fix up lookaheads */
 106:         k=p1;
 107:         for( l=q1; l<q2; ++l ){
 108:             if( union( clset.lset, l->look->lset, k->look->lset ) ) {
 109:                 tystate[i] = 1;
 110:                 /* register the new set */
 111:                 l->look = flset( &clset );
 112:                 }
 113:             ++k;
 114:             }
 115:         return (i);
 116:         }
 117: /* state is new */
 118:     pstate[nstate+2] = p2;
 119:     if(nstate+1 >= stsize) error("too many states");
 120:     if( c >= NTBASE ){
 121:         mstates[ nstate ] = ntstates[ c-NTBASE ];
 122:         ntstates[ c-NTBASE ] = nstate;
 123:         }
 124:     else {
 125:         mstates[ nstate ] = tstates[ c ];
 126:         tstates[ c ] = nstate;
 127:         }
 128:     tystate[nstate]=1;
 129:     return(nstate++);
 130:     }
 131: 
 132: int pidebug 0; /* debugging flag for putitem */
 133: putitem ( ptr, lptr )       int *ptr; struct looksets *lptr;{
 134:     int *jip, k;
 135:     struct item *i, *j;
 136: 
 137:         if( pidebug ) {
 138:           settty();
 139:       printf("putitem(%s), state %d\n", writem(&ptr), nstate );
 140:           }
 141:     /* see if it's there */
 142:     j = pstate[nstate+1];
 143:         for( i=pstate[nstate]; i<j; ++i )
 144:         if(i->pitem == ptr) {
 145:             error("yacc error--duplicate item");
 146:             }
 147:     /* not there */
 148:     j->pitem = ptr;
 149:     j->look = flset( lptr );
 150:     pstate[nstate+1] = ++j;
 151:     jip = j;
 152:     if(jip-mem0 >= memsiz) error("out of state space");
 153:     }
 154: 
 155: cempty(){ /* mark nonterminals which derive the empty string */
 156: 
 157:   int i, *p;
 158: 
 159:   /* set pempty to 0 */
 160:   pempty = yalloc( nnonter );
 161:   aryfil( pempty, nnonter+1, 0 );
 162:   for( i=1; i<nprod; ++i ) /* loop over productions */
 163:     if( prdptr[i][1] <= 0 ) /* i is empty production */
 164:       pempty[ *prdptr[i]-NTBASE ] = 1;
 165: 
 166:   /* now, all explicitly empty nonterminals marked with pempty = 1 */
 167: 
 168:   /* loop as long as we keep finding nontrivial empty nonterminals */
 169: 
 170: again:
 171:   for( i=1; i<nprod; ++i ){
 172:     if( pempty[ *prdptr[i]-NTBASE ]==0 ){ /* not known to be empty */
 173:       for( p=prdptr[i]+1; *p>=NTBASE && pempty[*p-NTBASE]!=0 ; ++p ) ;
 174:       if( *p < 0 ){ /* we have a nontrivially empty nonterminal */
 175:         pempty[*prdptr[i]-NTBASE] = 1;
 176:         goto again; /* got one ... try for another */
 177:         }
 178:       }
 179:     }
 180:   }
 181: 
 182: int gsdebug 0;
 183: stagen(){ /* generate the states */
 184: 
 185:   int i, j, k, c;
 186: 
 187:   /* initialize */
 188: 
 189:   nstate = 0;
 190:   pstate[0] = pstate[1] = mem;
 191:   aryfil( clset.lset, tbitset, 0 );
 192:   putitem( prdptr[0]+1, &clset );
 193:   tystate[0] = 1;
 194:   nstate = 1;
 195:   pstate[2] = pstate[1];
 196: 
 197:   memact = 0;
 198:   aryfil( amem, actsiz, 0 );
 199: 
 200:   /* now, the main state generation loop */
 201: 
 202:   more:
 203:   for( i=0; i<nstate; ++i ){
 204:     if( tystate[i] != 1 ) continue;
 205:     tystate[i] = 0;
 206:     aryfil( temp1, nterms+nnonter+1, 0 );
 207:     /* take state i, close it, and do gotos */
 208:     closure(i);
 209:     for( j=0; j<cwset; ++j ){ /* generate gotos */
 210:       if( wsets[j].flag ) continue;
 211:       wsets[j].flag = 1;
 212:       c = *(wsets[j].pitem);
 213:       if( c <= 1 ) {
 214:         if( pstate[i+1]-pstate[i] <= j ) tystate[i] = (tystate[i]==1)?1:2;
 215:         continue;
 216:         }
 217:       /* do a goto on c */
 218:       for( k=j; k<cwset; ++k ){
 219:         if( c == *(wsets[k].pitem) ){ /* this item contributes to the goto */
 220:           putitem( wsets[k].pitem + 1, wsets[k].ws );
 221:           wsets[k].flag = 1;
 222:           }
 223:         }
 224:       if( c < NTBASE ) temp1[c] = state(c);
 225:       else temp1[c-NTBASE+nterms] = state(c);
 226:       }
 227:     if( gsdebug ){
 228:       settty();
 229:       printf( "%d: ", i );
 230:       for( j=1; j<=nterms; ++j ){
 231:         if( temp1[j] != 0 ) printf( "%s %d, ", symnam(j), temp1[j]);
 232:         }
 233:       for( j=1; j<=nnonter; ++j ){
 234:         if( temp1[j+nterms] ) printf( "%s %d, ", nontrst[j].name, temp1[j+nterms] );
 235:         }
 236:       printf("\n");
 237:       }
 238:     apstate[i] = apack( &temp1[0], nterms );
 239:     indgo[i] = apack( &temp1[nterms+1], nnonter-1 ) - 1;
 240:     goto more; /* we have done one goto; do some more */
 241:     }
 242:   /* no more to do... stop */
 243:   }
 244: 
 245: int cldebug 0; /* debugging flag for closure */
 246: closure(i){ /* generate the closure of state i */
 247: 
 248:   int c, ch, work;
 249:   _REGISTER j, k;
 250:   int *pi;
 251:   int **s, **t;
 252:   struct item *q;
 253:   _REGISTER struct item *p;
 254: 
 255:   ++zzclose;
 256: 
 257:   /* first, copy kernel of state i to wsets */
 258: 
 259:   cwset = 0;
 260:   q = pstate[i+1];
 261:   for( p=pstate[i]; p<q; ++p ){
 262:     wsets[cwset].pitem = p->pitem;
 263:     wsets[cwset].flag = 1;    /* this item must get closed */
 264:     for( k=0; k<tbitset; ++k ) wsets[cwset].ws[k] = p->look->lset[k];
 265:     ++cwset;
 266:     }
 267: 
 268:   /* now, go through the loop, closing each item */
 269: 
 270:   work = 1;
 271:   while( work ){
 272:     work = 0;
 273:     for( j=0; j<cwset; ++j ){
 274: 
 275:       if( wsets[j].flag == 0 ) continue;
 276:       c = *(wsets[j].pitem);  /* dot is before c */
 277: 
 278:       if( c < NTBASE ){
 279:         wsets[j].flag = 0;
 280:         continue;  /* only interesting case is where . is before nonterminal */
 281:         }
 282: 
 283:       /* compute the lookahead */
 284:       aryfil( clset.lset, tbitset, 0 );
 285: 
 286:       /* find items involving c */
 287: 
 288:       for( k=j; k<cwset; ++k ){
 289:         if( wsets[k].flag == 1 && *(pi=wsets[k].pitem) == c ){
 290:           wsets[k].flag = 0;
 291:           if( nolook ) continue;
 292:           while( (ch= *++pi)>0 ){
 293:             if( ch < NTBASE ){ /* terminal symbol */
 294:               clset.lset[ch>>4] =| (1<<(ch&017));
 295:               break;
 296:               }
 297:             /* nonterminal symbol */
 298:             union( clset.lset, clset.lset, pfirst[ch-NTBASE] );
 299:             if( !pempty[ch-NTBASE] ) break;
 300:             }
 301:           if( ch<=0 ) union( clset.lset, clset.lset, wsets[k].ws );
 302:           }
 303:         }
 304: 
 305:       /*  now loop over productions derived from c */
 306: 
 307:       c =- NTBASE; /* c is now nonterminal number */
 308: 
 309:       t = pres[c+1];
 310:       for( s=pres[c]; s<t; ++s ){
 311:         /* put these items into the closure */
 312:         for( k=0; k<cwset; ++k ){ /* is the item there */
 313:           if( wsets[k].pitem == *s ){ /* yes, it is there */
 314:             if( nolook ) goto nexts;
 315:             if( union( wsets[k].ws, wsets[k].ws, clset.lset ) ) wsets[k].flag = work = 1;
 316:             goto nexts;
 317:             }
 318:           }
 319: 
 320:         /*  not there; make a new entry */
 321:         if( cwset+1 >= wssize ) error( "working set overflow" );
 322:         wsets[cwset].pitem = *s;
 323:         wsets[cwset].flag = 1;
 324:         if( nolook ){
 325:           cwset++;
 326:           goto nexts;
 327:           }
 328:         work = 1;
 329:         for( k=0; k<tbitset; ++k ) wsets[cwset].ws[k] = clset.lset[k];
 330:         cwset++;
 331: 
 332:       nexts: ;
 333:         }
 334: 
 335:       }
 336:     }
 337: 
 338:   /* have computed closure; flags are reset; return */
 339: 
 340:   if( cwset > zzcwset ) zzcwset = cwset;
 341:   if( !cldebug ) return;
 342:   settty();
 343:   printf("\nState %d, nolook = %d\n", i, nolook );
 344:   for( j=0; j<cwset; ++j ){
 345:     if( wsets[j].flag ) printf("flag set!\n");
 346:     wsets[j].flag = 0;
 347:     printf("\t%s", writem(&wsets[j].pitem));
 348:     prlook( wsets[j].ws );
 349:     printf( "\n" );
 350:     }
 351: 
 352:   }
 353: 
 354: struct looksets *flset( p )
 355:     struct looksets *p;
 356:     {
 357:     /* decide if the lookahead set pointed to by p is known */
 358:     /* return pointer to a perminent location for the set */
 359: 
 360:     int j, *w;
 361:     _REGISTER *u, *v, i;
 362: 
 363:     for( i=0; i<nlset; ++i ){
 364:         u = p->lset;
 365:         v = lkst[i].lset;
 366:         w = & v[tbitset];
 367:         while( v<w) if( *u++ != *v++ ) goto more;
 368:         /* we have matched */
 369:         return( & lkst[i] );
 370:         more: ;
 371:         }
 372:     /* add a new one */
 373:     if( nlset+1 >= lsetsz )error("too many lookahead sets");
 374:     for( j=0; j<tbitset; ++j ){
 375:         lkst[nlset].lset[j] = p->lset[j];
 376:         }
 377:     return( & lkst[nlset++]);
 378:     }

Defined functions

Defined variables