Return to ey3.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / ucb / pascal / eyacc

Annotation of 43BSDTahoe/ucb/pascal/eyacc/ey3.c, revision 1.1

1.1     ! root        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:        }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.