Return to y3.c CVS log

Up to [CSRG BSD Unix] / 43BSD / usr.bin / yacc

Annotation of 43BSD/usr.bin/yacc/y3.c, revision 1.1

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

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