2.11BSD#431 - /usr/ingres/source/yyyacc/yyy3.c

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

Defined functions

Defined variables