Return to y3.c CVS log

Up to [CSRG BSD Unix] / 41BSD / cmd / yacc

Annotation of 41BSD/cmd/yacc/y3.c, revision 1.1

1.1     ! root        1: # include "dextern"
        !             2: 
        !             3:        /* important local variables */
        !             4: int lastred;  /* the number of the last reduction of a state */
        !             5: int defact[NSTATES];  /* the default actions of states */
        !             6: 
        !             7: output(){ /* print the output for the states */
        !             8: 
        !             9:        int i, k, c;
        !            10:        register struct wset *u, *v;
        !            11: 
        !            12:        fprintf( ftable, "short yyexca[] ={\n" );
        !            13: 
        !            14:        SLOOP(i) { /* output the stuff for state i */
        !            15:                nolook = !(tystate[i]==MUSTLOOKAHEAD);
        !            16:                closure(i);
        !            17:                /* output actions */
        !            18:                nolook = 1;
        !            19:                aryfil( temp1, ntokens+nnonter+1, 0 );
        !            20:                WSLOOP(wsets,u){
        !            21:                        c = *( u->pitem );
        !            22:                        if( c>1 && c<NTBASE && temp1[c]==0 ) {
        !            23:                                WSLOOP(u,v){
        !            24:                                        if( c == *(v->pitem) ) putitem( v->pitem+1, (struct looksets *)0 );
        !            25:                                        }
        !            26:                                temp1[c] = state(c);
        !            27:                                }
        !            28:                        else if( c > NTBASE && temp1[ (c -= NTBASE) + ntokens ] == 0 ){
        !            29:                                temp1[ c+ntokens ] = amem[indgo[i]+c];
        !            30:                                }
        !            31:                        }
        !            32: 
        !            33:                if( i == 1 ) temp1[1] = ACCEPTCODE;
        !            34: 
        !            35:                /* now, we have the shifts; look at the reductions */
        !            36: 
        !            37:                lastred = 0;
        !            38:                WSLOOP(wsets,u){
        !            39:                        c = *( u->pitem );
        !            40:                        if( c<=0 ){ /* reduction */
        !            41:                                lastred = -c;
        !            42:                                TLOOP(k){
        !            43:                                        if( BIT(u->ws.lset,k) ){
        !            44:                                                  if( temp1[k] == 0 ) temp1[k] = c;
        !            45:                                                  else if( temp1[k]<0 ){ /* reduce/reduce conflict */
        !            46:                                                    if( foutput!=NULL )
        !            47:                                                      fprintf( foutput,
        !            48:                                                        "\n%d: reduce/reduce conflict (red'ns %d and %d ) on %s",
        !            49:                                                        i, -temp1[k], lastred, symnam(k) );
        !            50:                                                    if( -temp1[k] > lastred ) temp1[k] = -lastred;
        !            51:                                                    ++zzrrconf;
        !            52:                                                    }
        !            53:                                                  else { /* potential shift/reduce conflict */
        !            54:                                                        precftn( lastred, k, i );
        !            55:                                                        }
        !            56:                                                }
        !            57:                                        }
        !            58:                                }
        !            59:                        }
        !            60:                wract(i);
        !            61:                }
        !            62: 
        !            63:        fprintf( ftable, "\t};\n" );
        !            64: 
        !            65:        wdef( "YYNPROD", nprod );
        !            66: 
        !            67:        }
        !            68: 
        !            69: int pkdebug = 0;
        !            70: apack(p, n ) int *p;{ /* pack state i from temp1 into amem */
        !            71:        int off;
        !            72:        register *pp, *qq, *rr;
        !            73:        int *q, *r;
        !            74: 
        !            75:        /* we don't need to worry about checking because we
        !            76:           we will only look entries known to be there... */
        !            77: 
        !            78:        /* eliminate leading and trailing 0's */
        !            79: 
        !            80:        q = p+n;
        !            81:        for( pp=p,off=0 ; *pp==0 && pp<=q; ++pp,--off ) /* VOID */ ;
        !            82:        if( pp > q ) return(0);  /* no actions */
        !            83:        p = pp;
        !            84: 
        !            85:        /* now, find a place for the elements from p to q, inclusive */
        !            86: 
        !            87:        r = &amem[ACTSIZE-1];
        !            88:        for( rr=amem; rr<=r; ++rr,++off ){  /* try rr */
        !            89:                for( qq=rr,pp=p ; pp<=q ; ++pp,++qq){
        !            90:                        if( *pp != 0 ){
        !            91:                                if( *pp != *qq && *qq != 0 ) goto nextk;
        !            92:                                }
        !            93:                        }
        !            94: 
        !            95:                /* we have found an acceptable k */
        !            96: 
        !            97:                if( pkdebug && foutput!=NULL ) fprintf( foutput, "off = %d, k = %d\n", off, rr-amem );
        !            98: 
        !            99:                for( qq=rr,pp=p; pp<=q; ++pp,++qq ){
        !           100:                        if( *pp ){
        !           101:                                if( qq > r ) error( "action table overflow" );
        !           102:                                if( qq>memp ) memp = qq;
        !           103:                                *qq = *pp;
        !           104:                                }
        !           105:                        }
        !           106:                if( pkdebug && foutput!=NULL ){
        !           107:                        for( pp=amem; pp<= memp; pp+=10 ){
        !           108:                                fprintf( foutput, "\t");
        !           109:                                for( qq=pp; qq<=pp+9; ++qq ) fprintf( foutput, "%d ", *qq );
        !           110:                                fprintf( foutput, "\n");
        !           111:                                }
        !           112:                        }
        !           113:                return( off );
        !           114: 
        !           115:                nextk: ;
        !           116:                }
        !           117:        error("no space in action table" );
        !           118:        /* NOTREACHED */
        !           119:        }
        !           120: 
        !           121: go2out(){ /* output the gotos for the nontermninals */
        !           122:        int i, j, k, best, count, cbest, times;
        !           123: 
        !           124:        fprintf( ftemp, "$\n" );  /* mark begining of gotos */
        !           125: 
        !           126:        for( i=1; i<=nnonter; ++i ) {
        !           127:                go2gen(i);
        !           128: 
        !           129:                /* find the best one to make default */
        !           130: 
        !           131:                best = -1;
        !           132:                times = 0;
        !           133: 
        !           134:                for( j=0; j<=nstate; ++j ){ /* is j the most frequent */
        !           135:                        if( tystate[j] == 0 ) continue;
        !           136:                        if( tystate[j] == best ) continue;
        !           137: 
        !           138:                        /* is tystate[j] the most frequent */
        !           139: 
        !           140:                        count = 0;
        !           141:                        cbest = tystate[j];
        !           142: 
        !           143:                        for( k=j; k<=nstate; ++k ) if( tystate[k]==cbest ) ++count;
        !           144: 
        !           145:                        if( count > times ){
        !           146:                                best = cbest;
        !           147:                                times = count;
        !           148:                                }
        !           149:                        }
        !           150: 
        !           151:                /* best is now the default entry */
        !           152: 
        !           153:                zzgobest += (times-1);
        !           154:                for( j=0; j<=nstate; ++j ){
        !           155:                        if( tystate[j] != 0 && tystate[j]!=best ){
        !           156:                                fprintf( ftemp, "%d,%d,", j, tystate[j] );
        !           157:                                zzgoent += 1;
        !           158:                                }
        !           159:                        }
        !           160: 
        !           161:                /* now, the default */
        !           162: 
        !           163:                zzgoent += 1;
        !           164:                fprintf( ftemp, "%d\n", best );
        !           165: 
        !           166:                }
        !           167: 
        !           168: 
        !           169: 
        !           170:        }
        !           171: 
        !           172: int g2debug = 0;
        !           173: go2gen(c){ /* output the gotos for nonterminal c */
        !           174: 
        !           175:        int i, work, cc;
        !           176:        struct item *p, *q;
        !           177: 
        !           178: 
        !           179:        /* first, find nonterminals with gotos on c */
        !           180: 
        !           181:        aryfil( temp1, nnonter+1, 0 );
        !           182:        temp1[c] = 1;
        !           183: 
        !           184:        work = 1;
        !           185:        while( work ){
        !           186:                work = 0;
        !           187:                PLOOP(0,i){
        !           188:                        if( (cc=prdptr[i][1]-NTBASE) >= 0 ){ /* cc is a nonterminal */
        !           189:                                if( temp1[cc] != 0 ){ /* cc has a goto on c */
        !           190:                                        cc = *prdptr[i]-NTBASE; /* thus, the left side of production i does too */
        !           191:                                        if( temp1[cc] == 0 ){
        !           192:                                                  work = 1;
        !           193:                                                  temp1[cc] = 1;
        !           194:                                                  }
        !           195:                                        }
        !           196:                                }
        !           197:                        }
        !           198:                }
        !           199: 
        !           200:        /* now, we have temp1[c] = 1 if a goto on c in closure of cc */
        !           201: 
        !           202:        if( g2debug && foutput!=NULL ){
        !           203:                fprintf( foutput, "%s: gotos on ", nontrst[c].name );
        !           204:                NTLOOP(i) if( temp1[i] ) fprintf( foutput, "%s ", nontrst[i].name);
        !           205:                fprintf( foutput, "\n");
        !           206:                }
        !           207: 
        !           208:        /* now, go through and put gotos into tystate */
        !           209: 
        !           210:        aryfil( tystate, nstate, 0 );
        !           211:        SLOOP(i){
        !           212:                ITMLOOP(i,p,q){
        !           213:                        if( (cc= *p->pitem) >= NTBASE ){
        !           214:                                if( temp1[cc -= NTBASE] ){ /* goto on c is possible */
        !           215:                                        tystate[i] = amem[indgo[i]+c];
        !           216:                                        break;
        !           217:                                        }
        !           218:                                }
        !           219:                        }
        !           220:                }
        !           221:        }
        !           222: 
        !           223: precftn(r,t,s){ /* decide a shift/reduce conflict by precedence.
        !           224:        /* r is a rule number, t a token number */
        !           225:        /* the conflict is in state s */
        !           226:        /* temp1[t] is changed to reflect the action */
        !           227: 
        !           228:        int lp,lt, action;
        !           229: 
        !           230:        lp = levprd[r];
        !           231:        lt = toklev[t];
        !           232:        if( PLEVEL(lt) == 0 || PLEVEL(lp) == 0 ) {
        !           233:                /* conflict */
        !           234:                if( foutput != NULL ) fprintf( foutput, "\n%d: shift/reduce conflict (shift %d, red'n %d) on %s",
        !           235:                                                s, temp1[t], r, symnam(t) );
        !           236:                ++zzsrconf;
        !           237:                return;
        !           238:                }
        !           239:        if( PLEVEL(lt) == PLEVEL(lp) ) action = ASSOC(lt);
        !           240:        else if( PLEVEL(lt) > PLEVEL(lp) ) action = RASC;  /* shift */
        !           241:        else action = LASC;  /* reduce */
        !           242: 
        !           243:        switch( action ){
        !           244: 
        !           245:        case BASC:  /* error action */
        !           246:                temp1[t] = ERRCODE;
        !           247:                return;
        !           248: 
        !           249:        case LASC:  /* reduce */
        !           250:                temp1[t] = -r;
        !           251:                return;
        !           252: 
        !           253:                }
        !           254:        }
        !           255: 
        !           256: wract(i){ /* output state i */
        !           257:        /* temp1 has the actions, lastred the default */
        !           258:        int p, p0, p1;
        !           259:        int ntimes, tred, count, j;
        !           260:        int flag;
        !           261: 
        !           262:        /* find the best choice for lastred */
        !           263: 
        !           264:        lastred = 0;
        !           265:        ntimes = 0;
        !           266:        TLOOP(j){
        !           267:                if( temp1[j] >= 0 ) continue;
        !           268:                if( temp1[j]+lastred == 0 ) continue;
        !           269:                /* count the number of appearances of temp1[j] */
        !           270:                count = 0;
        !           271:                tred = -temp1[j];
        !           272:                levprd[tred] |= REDFLAG;
        !           273:                TLOOP(p){
        !           274:                        if( temp1[p]+tred == 0 ) ++count;
        !           275:                        }
        !           276:                if( count >ntimes ){
        !           277:                        lastred = tred;
        !           278:                        ntimes = count;
        !           279:                        }
        !           280:                }
        !           281: 
        !           282:        /* for error recovery, arrange that, if there is a shift on the
        !           283:        /* error recovery token, `error', that the default be the error action */
        !           284:        if( temp1[1] > 0 ) lastred = 0;
        !           285: 
        !           286:        /* clear out entries in temp1 which equal lastred */
        !           287:        TLOOP(p) if( temp1[p]+lastred == 0 )temp1[p]=0;
        !           288: 
        !           289:        wrstate(i);
        !           290:        defact[i] = lastred;
        !           291: 
        !           292:        flag = 0;
        !           293:        TLOOP(p0){
        !           294:                if( (p1=temp1[p0])!=0 ) {
        !           295:                        if( p1 < 0 ){
        !           296:                                p1 = -p1;
        !           297:                                goto exc;
        !           298:                                }
        !           299:                        else if( p1 == ACCEPTCODE ) {
        !           300:                                p1 = -1;
        !           301:                                goto exc;
        !           302:                                }
        !           303:                        else if( p1 == ERRCODE ) {
        !           304:                                p1 = 0;
        !           305:                                goto exc;
        !           306:                        exc:
        !           307:                                if( flag++ == 0 ) fprintf( ftable, "-1, %d,\n", i );
        !           308:                                fprintf( ftable, "\t%d, %d,\n", tokset[p0].value, p1 );
        !           309:                                ++zzexcp;
        !           310:                                }
        !           311:                        else {
        !           312:                                fprintf( ftemp, "%d,%d,", tokset[p0].value, p1 );
        !           313:                                ++zzacent;
        !           314:                                }
        !           315:                        }
        !           316:                }
        !           317:        if( flag ) {
        !           318:                defact[i] = -2;
        !           319:                fprintf( ftable, "\t-2, %d,\n", lastred );
        !           320:                }
        !           321:        fprintf( ftemp, "\n" );
        !           322:        return;
        !           323:        }
        !           324: 
        !           325: wrstate(i){ /* writes state i */
        !           326:        register j0,j1;
        !           327:        register struct item *pp, *qq;
        !           328:        register struct wset *u;
        !           329: 
        !           330:        if( foutput == NULL ) return;
        !           331:        fprintf( foutput, "\nstate %d\n",i);
        !           332:        ITMLOOP(i,pp,qq) fprintf( foutput, "\t%s\n", writem(pp->pitem));
        !           333:        if( tystate[i] == MUSTLOOKAHEAD ){
        !           334:                /* print out empty productions in closure */
        !           335:                WSLOOP( wsets+(pstate[i+1]-pstate[i]), u ){
        !           336:                        if( *(u->pitem) < 0 ) fprintf( foutput, "\t%s\n", writem(u->pitem) );
        !           337:                        }
        !           338:                }
        !           339: 
        !           340:        /* check for state equal to another */
        !           341: 
        !           342:        TLOOP(j0) if( (j1=temp1[j0]) != 0 ){
        !           343:                fprintf( foutput, "\n\t%s  ", symnam(j0) );
        !           344:                if( j1>0 ){ /* shift, error, or accept */
        !           345:                        if( j1 == ACCEPTCODE ) fprintf( foutput,  "accept" );
        !           346:                        else if( j1 == ERRCODE ) fprintf( foutput, "error" );
        !           347:                        else fprintf( foutput,  "shift %d", j1 );
        !           348:                        }
        !           349:                else fprintf( foutput, "reduce %d",-j1 );
        !           350:                }
        !           351: 
        !           352:        /* output the final production */
        !           353: 
        !           354:        if( lastred ) fprintf( foutput, "\n\t.  reduce %d\n\n", lastred );
        !           355:        else fprintf( foutput, "\n\t.  error\n\n" );
        !           356: 
        !           357:        /* now, output nonterminal actions */
        !           358: 
        !           359:        j1 = ntokens;
        !           360:        for( j0 = 1; j0 <= nnonter; ++j0 ){
        !           361:                if( temp1[++j1] ) fprintf( foutput, "\t%s  goto %d\n", symnam( j0+NTBASE), temp1[j1] );
        !           362:                }
        !           363: 
        !           364:        }
        !           365: 
        !           366: wdef( s, n ) char *s; { /* output a definition of s to the value n */
        !           367:        fprintf( ftable, "# define %s %d\n", s, n );
        !           368:        }
        !           369: 
        !           370: warray( s, v, n ) char *s; int *v, n; {
        !           371: 
        !           372:        register i;
        !           373: 
        !           374:        fprintf( ftable, "short %s[]={\n", s );
        !           375:        for( i=0; i<n; ){
        !           376:                if( i%10 == 0 ) fprintf( ftable, "\n" );
        !           377:                fprintf( ftable, "%4d", v[i] );
        !           378:                if( ++i == n ) fprintf( ftable, " };\n" );
        !           379:                else fprintf( ftable, "," );
        !           380:                }
        !           381:        }
        !           382: 
        !           383: hideprod(){
        !           384:        /* in order to free up the mem and amem arrays for the optimizer,
        !           385:        /* and still be able to output yyr1, etc., after the sizes of
        !           386:        /* the action array is known, we hide the nonterminals
        !           387:        /* derived by productions in levprd.
        !           388:        */
        !           389: 
        !           390:        register i, j;
        !           391: 
        !           392:        j = 0;
        !           393:        levprd[0] = 0;
        !           394:        PLOOP(1,i){
        !           395:                if( !(levprd[i] & REDFLAG) ){
        !           396:                        ++j;
        !           397:                        if( foutput != NULL ){
        !           398:                                fprintf( foutput, "Rule not reduced:   %s\n", writem( prdptr[i] ) );
        !           399:                                }
        !           400:                        }
        !           401:                levprd[i] = *prdptr[i] - NTBASE;
        !           402:                }
        !           403:        if( j ) fprintf( stdout, "%d rules never reduced\n", j );
        !           404:        }

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