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

##### Functions

    cempty            X
    closure           X
    cpfir             X
    cpres             X
    flset             X
    putitem           X
    stagen            X
    state             X

##### Variables

    cldebug           X
    gsdebug           X
    indebug           X
    pidebug           X

       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

cempty defined in line 159; used 1 times

- in /usr/ingres/source/yyyacc/yyy1.c line 41

closure defined in line 250; used 2 times

- in line 212
- in /usr/ingres/source/yyyacc/y4.c line 15

cpfir defined in line 29; used 1 times

- in /usr/ingres/source/yyyacc/yyy1.c line 42

cpres defined in line 6; used 1 times

- in /usr/ingres/source/yyyacc/yyy1.c line 40

flset defined in line 358; used 4 times

- in line 64, 114, 139, 153

putitem defined in line 136; used 2 times

- in line 196, 224

stagen defined in line 187; used 1 times

- in /usr/ingres/source/yyyacc/yyy1.c line 43

state defined in line 74; used 2 times

- in line 228-229(2)

#### Defined variables

cldebug defined in line 249; used 1 times

- in line 345

gsdebug defined in line 186; used 1 times

- in line 231

indebug defined in line 28; used 1 times

- in line 65

pidebug defined in line 135; used 1 times

- in line 141

Last modified: 1995-02-18 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1915 |