Return to y3.c CVS log

Up to [Research Unix] / researchv10no / cmd / picasso

Annotation of researchv10no/cmd/picasso/y3.c, revision 1.1

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

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