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

#### Defined functions

cempty defined in line 166; used 1 times

- in /usr/src/ucb/PORT/pascal/eyacc/ey1.c line 85

closure defined in line 260; used 2 times

- in line 220
- in /usr/src/ucb/PORT/pascal/eyacc/ey4.c line 22

cpfir defined in line 36; used 1 times

- in /usr/src/ucb/PORT/pascal/eyacc/ey1.c line 86

cpres defined in line 13; used 1 times

- in /usr/src/ucb/PORT/pascal/eyacc/ey1.c line 84

flset defined in line 382; used 4 times

- in line 71, 122, 160
- in /usr/src/ucb/PORT/pascal/eyacc/ey.h line 141

putitem defined in line 144; used 2 times

- in line 203, 234

stagen defined in line 194; used 1 times

- in /usr/src/ucb/PORT/pascal/eyacc/ey1.c line 87

state defined in line 81; used 2 times

- in line 238-239(2)

#### Defined variables

cldebug defined in line 259; used 1 times

- in line 369

gsdebug defined in line 193; used 1 times

- in line 241

indebug defined in line 35; used 1 times

- in line 72

pidebug defined in line 143; used 1 times

- in line 148

sccsid defined in line 8; never used

Last modified: 1985-04-30 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 1890 |