Return to y3.c CVS log

Up to [MW Coherent from dump] / coherent / d / bin / yacc

Annotation of coherent/d/bin/yacc/y3.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * LALR-1 parser generator
        !             3:  * generation of lookahead sets
        !             4:  * the algorithm is thanks to Frank D. Remer & Thomas J Pennello,
        !             5:  *  "Efficient computation of LALR(1) lookahead sets",
        !             6:  *   SIGPLAN conference 1979.
        !             7:  */
        !             8: 
        !             9: #include "yacc.h"
        !            10: #include <assert.h>
        !            11: 
        !            12: /* the size of SMAX must be related to the amount of space available
        !            13:    on the runtime stack for recursive calls to traverse.
        !            14:    (on systems which do not dynamically allocate the stack like RSX)
        !            15:    on RSX traverse takes up about 18 bytes per call which means that
        !            16:    with a 1024 byte stack we can probably make 50-55 levels of recursion
        !            17: */
        !            18: #define SMAX 100
        !            19: 
        !            20: #define INFINITY 10000         /* infinity is small for a mathematician */
        !            21: #define INITCODE 1
        !            22: #define COPYCODE 2
        !            23: #define UNIONCODE 3
        !            24: #define EOFCODE 4
        !            25: static struct
        !            26: {
        !            27:        int     s_last;
        !            28:        int     s_vals[SMAX];
        !            29: } stk;                         /* stack for digraph */
        !            30: 
        !            31: static struct trans *transp;   /* temporary vector for traverse */
        !            32: static struct lset *lsetp, *fsetp;
        !            33: static int nttrans;
        !            34: int rread(), rincl();
        !            35: struct lset *getset();
        !            36: 
        !            37: genlook()
        !            38: {
        !            39:        int code = EOFCODE;
        !            40:        rewopt();
        !            41:        cttrans();
        !            42:        transp = (struct trans *)yalloc(nttrans, sizeof *transp);
        !            43:        cdread();
        !            44:        rread(0);
        !            45:        rread(1);
        !            46:        digraph();
        !            47:        free(transp->t_trans->ng_rel);
        !            48:        rincl(0);
        !            49:        rincl(1);
        !            50:        digraph();
        !            51:        free(transp->t_trans->ng_rel);
        !            52:        free(transp);
        !            53:        fwrite(&code, sizeof code, 1, optout);
        !            54:        execute();
        !            55:        lookback();
        !            56: }
        !            57: 
        !            58: cdread()
        !            59: {
        !            60:        register i, j, k;
        !            61:        struct state *stp, *stp1;
        !            62:        struct ntgo *ntp;
        !            63:        struct lset lset;
        !            64:        int code = INITCODE;
        !            65: 
        !            66:        for(i=0; i<nstates; i++) {
        !            67:                stp = &states[i];
        !            68:                for(j=0; j<stp->s_ntgo; j++) {
        !            69:                        zerolset(&lset);
        !            70:                        ntp = &stp->s_ntgos[j];
        !            71:                        stp1 = &states[ntp->ng_st];
        !            72:                        for(k=0; k<stp1->s_tgo; k++) 
        !            73:                                setbit(&lset, stp1->s_tgos[k].tg_trm);
        !            74:                        fwrite(&code, sizeof code, 1, optout);
        !            75:                        fwrite(&ntp, sizeof ntp, 1, optout);
        !            76:                        fwrite(lset.l_bits, sizeof lset.l_bits, 1, optout);
        !            77:                }
        !            78:        }
        !            79: }
        !            80: 
        !            81: 
        !            82: 
        !            83: cttrans()
        !            84: {
        !            85:        /* count number of nonterminal transations in automaton */
        !            86:        register i;
        !            87: 
        !            88:        nttrans = 0;
        !            89:        for(i=0; i<nstates; i++)
        !            90:                nttrans += states[i].s_ntgo;
        !            91: }
        !            92: 
        !            93: digraph()
        !            94: {
        !            95:        register i;
        !            96:        stk.s_last = 0;
        !            97:        zerolev();
        !            98:        for(i=0; i<nttrans; i++)
        !            99:                if( transp[i].t_level==0 )
        !           100:                        traverse(i);
        !           101: }
        !           102: 
        !           103: traverse(x)
        !           104: register int x;
        !           105: {
        !           106:        register i, y;
        !           107:        int k;
        !           108:        struct ntgo *ntp;
        !           109:        int code = UNIONCODE;
        !           110: 
        !           111:        if( stk.s_last>= (SMAX-1) )
        !           112:                yyerror(FATAL|NLNO, "internal stack overflow - SMAX");
        !           113:        stk.s_vals[++stk.s_last] = x;
        !           114:        k = stk.s_last;
        !           115:        transp[x].t_level = k;
        !           116:        ntp = transp[x].t_trans;
        !           117: 
        !           118:        for(i=0; i<ntp->ng_rel->r_count; i++) {
        !           119:                y = ntp->ng_rel->r_list[i];
        !           120:                if( transp[y].t_level==0 )
        !           121:                        traverse(y);
        !           122:                if( transp[y].t_level < transp[x].t_level )
        !           123:                        transp[x].t_level = transp[y].t_level;
        !           124:                fwrite(&code, sizeof code, 1, optout);
        !           125:                fwrite(&ntp, sizeof ntp, 1, optout);
        !           126:                fwrite(&transp[y].t_trans, sizeof ntp, 1, optout);
        !           127:        }
        !           128: 
        !           129:        code = COPYCODE;
        !           130:        if( transp[x].t_level == k ) {
        !           131:                transp[x].t_level = INFINITY;
        !           132:                while( (y = stk.s_vals[stk.s_last--]) != x ) {
        !           133:                        transp[y].t_level = INFINITY;
        !           134:                        fwrite(&code, sizeof code, 1, optout);
        !           135:                        fwrite(&transp[y].t_trans, sizeof ntp, 1, optout);
        !           136:                        fwrite(&ntp, sizeof ntp, 1, optout);
        !           137:                }
        !           138:        }
        !           139: }
        !           140: 
        !           141: /*
        !           142:  * form the set unions of the read sets and the follow sets, following
        !           143:  * the codes left in temp file by digraph
        !           144:  */
        !           145: execute()
        !           146: {
        !           147:        int code;
        !           148:        struct ntgo *ntp1, *ntp2;
        !           149:        register struct lset *csetp;
        !           150: 
        !           151:        rewopt();
        !           152:        csetp = lsetp = (struct lset *)yalloc(nttrans, sizeof *lsetp);
        !           153:        fsetp = NULL;
        !           154:        for(;;) {
        !           155:                if( fread(&code, sizeof code, 1, optout) != 1 )
        !           156:                        yyerror(NLNO|FATAL, "eof on tempfile in execute");
        !           157:                switch( code ) {
        !           158:                case INITCODE:
        !           159:                        fread(&ntp1, sizeof ntp1, 1, optout);
        !           160:                        assert( csetp < &lsetp[nttrans] );
        !           161:                        fread(csetp->l_bits, sizeof csetp->l_bits,  1, optout);
        !           162: /*
        !           163:                        fprintf(listout, "init: "); ptrans(ntp1);
        !           164:                        prlset(csetp); fprintf(listout,"\n");
        !           165: */
        !           166:                        ntp1->ng_lset = csetp++;
        !           167:                        break;
        !           168: 
        !           169:                case UNIONCODE:
        !           170:                        fread(&ntp1, sizeof ntp1, 1, optout);
        !           171:                        fread(&ntp2, sizeof ntp2, 1, optout);
        !           172: /*
        !           173:                        fprintf(listout, "union "); ptrans(ntp1); fprintf(listout," |=");
        !           174:                        ptrans(ntp2);
        !           175: */
        !           176:                        setunion(ntp1->ng_lset, ntp2->ng_lset);
        !           177: /*
        !           178:                        prlset(ntp1->ng_lset); fprintf(listout, "\n");
        !           179: */
        !           180:                        break;
        !           181: 
        !           182:                case COPYCODE:
        !           183:                        fread(&ntp1, sizeof ntp1, 1, optout);
        !           184:                        fread(&ntp2, sizeof ntp2, 1, optout);
        !           185:                        xxx("copy", ntp1, ntp2);
        !           186:                        freeset(ntp1->ng_lset);
        !           187:                        ntp1->ng_lset = getset();
        !           188:                        copylset(ntp1->ng_lset, ntp2->ng_lset);
        !           189:                        break;
        !           190: 
        !           191:                case EOFCODE:
        !           192:                        return;
        !           193:                default:
        !           194:                        yyerror(NLNO|FATAL, "bad temp file; code %o\n", code);
        !           195:                }
        !           196:        }
        !           197: }
        !           198: 
        !           199: lookback()
        !           200: {
        !           201:        register i;
        !           202: 
        !           203:        for(i=0; i<nprod; i++)
        !           204:                reduce(prdptr[i]);
        !           205: 
        !           206: }
        !           207: 
        !           208: reduce(pp)
        !           209: register struct prod *pp;
        !           210: {
        !           211:        register nt, i;
        !           212:        struct sym *sp;
        !           213:        struct redn *rdp;
        !           214:        struct state *stp, *stp1;
        !           215:        int j, sno, sno1;
        !           216:        struct ntgo *ntp;
        !           217: 
        !           218:        nt = -pp->p_left;
        !           219:        sp = ntrmptr[nt-NTBASE];
        !           220:        for(j=0; j<sp->s_nstates; j++) {
        !           221:                stp = &states[sno = sp->s_states[j]];
        !           222:                for(i=0; i<stp->s_ntgo; i++) {
        !           223:                        ntp = &stp->s_ntgos[i];
        !           224:                        if( ntp->ng_nt == nt )
        !           225:                                break;
        !           226:                }
        !           227:                assert(pp->p_prodno==0 || i<stp->s_ntgo);
        !           228:                sno1 = go2star(sno, pp->p_right, pp->p_right+prodl(pp));
        !           229:                stp1 = &states[sno1];
        !           230:                if( stp1->s_reds == (struct redn *)NULL ) {     /* MWC DSC */
        !           231:                        stp1->s_reds = (struct redn *)yalloc(stp1->s_nred, sizeof *stp1->s_reds);
        !           232:                        stp1->s_nred = 0;
        !           233:                }
        !           234:                rdp = stp1->s_reds;
        !           235:                for(i=0; i<stp1->s_nred; i++,rdp++)
        !           236:                        if( rdp->rd_prod==pp )
        !           237:                                break;
        !           238:                if( yydebug ) {
        !           239:                        fprintf(listout, "(%d, pdn %d) ", sno1, pp->p_prodno);
        !           240:                        prlset(ntp->ng_lset);
        !           241:                        fprintf(listout, "\n");
        !           242:                }
        !           243:                if( i==stp1->s_nred ) {
        !           244:                        rdp->rd_prod = pp;
        !           245:                        rdp->rd_lset = getset();
        !           246:                        if( pp->p_prodno!=0 ) {
        !           247:                                copylset(rdp->rd_lset, ntp->ng_lset);
        !           248:                        } else {
        !           249:                                zerolset(rdp->rd_lset);
        !           250:                                setbit(rdp->rd_lset, EOFNO);
        !           251:                        }
        !           252:                        stp1->s_nred++;
        !           253:                } else {
        !           254:                        setunion(rdp->rd_lset, ntp->ng_lset);
        !           255:                }
        !           256:        }
        !           257: }
        !           258: 
        !           259: go2star(sno, ip, fin)
        !           260: register *ip;
        !           261: int *fin;
        !           262: {
        !           263:        register i;
        !           264:        register struct state *stp;
        !           265: 
        !           266:        while( ip!=fin ) {
        !           267:                stp = &states[sno];
        !           268:                if( *ip>=NTBASE ) {
        !           269:                        for(i=0; i<stp->s_ntgo; i++)
        !           270:                                if( stp->s_ntgos[i].ng_nt == *ip )
        !           271:                                        break;
        !           272:                        assert(i<stp->s_ntgo);
        !           273:                        sno = stp->s_ntgos[i].ng_st;
        !           274:                } else {
        !           275:                        for(i=0; i<stp->s_tgo; i++)
        !           276:                                if( stp->s_tgos[i].tg_trm == *ip )
        !           277:                                        break;
        !           278:                        assert(i<stp->s_tgo);
        !           279:                        sno = stp->s_tgos[i].tg_st;
        !           280:                }
        !           281:                ip++;
        !           282:        }
        !           283:        return(sno);
        !           284: }
        !           285: 
        !           286: rread(todo)
        !           287: {
        !           288:        struct state *stp;
        !           289:        register struct sym *sp;
        !           290:        register i, j;
        !           291:        int p;
        !           292:        struct ntgo *ntp;
        !           293: 
        !           294:        if( todo )
        !           295:                zerolev();
        !           296:        else
        !           297:                startcount();
        !           298: 
        !           299:        for(i=0; i<nttrans; i++) {
        !           300:                stp = &states[transp[i].t_trans->ng_st];
        !           301:                for(j=0; j<stp->s_ntgo; j++) {
        !           302:                        ntp = &stp->s_ntgos[j];
        !           303:                        sp = ntrmptr[ntp->ng_nt-NTBASE];
        !           304:                        if( sp->s_flags&DERIV ) {
        !           305:                                p = transp[i].t_level++;
        !           306:                                if( todo ) {
        !           307:                                        transp[i].t_trans->ng_rel->r_list[p] =
        !           308:                                            rsearch(ntp);
        !           309:                                        xxx("reads",transp[i].t_trans,ntp);
        !           310:                                }
        !           311:                                break;
        !           312:                        }
        !           313:                }
        !           314:        }
        !           315:        if( !todo )
        !           316:                endcount();
        !           317: }
        !           318: 
        !           319: rincl(todo)
        !           320: {
        !           321:        register i, j;
        !           322:        int *pb, *pe, k, p, sno, sno1, ind, nt;
        !           323:        struct state *stp;
        !           324:        struct prod *pp;
        !           325:        struct ntgo *ntp;
        !           326:        struct sym *sp;
        !           327: 
        !           328:        if( todo )
        !           329:                zerolev();
        !           330:        else
        !           331:                startcount();
        !           332:        for(i=0; i<nttrans; i++) {
        !           333:                sno = ssearch(transp[i].t_trans);
        !           334:                sp = ntrmptr[transp[i].t_trans->ng_nt-NTBASE];
        !           335:                for(j=0; j<sp->s_nprods; j++) {
        !           336:                        pp = sp->s_prods[j];
        !           337:                        pb = pp->p_right;
        !           338:                        pe = pb + prodl(pp);
        !           339:                        while( pb <= --pe && (nt = *pe) >= NTBASE ) {
        !           340:                                sno1 = go2star(sno, pb, pe);
        !           341:                                stp = &states[sno1];
        !           342:                                for(k=0; k<stp->s_ntgo; k++)
        !           343:                                        if( stp->s_ntgos[k].ng_nt==nt )
        !           344:                                                break;
        !           345:                                assert(k<stp->s_ntgo);
        !           346:                                ind = rsearch(&stp->s_ntgos[k]);
        !           347:                                p = transp[ind].t_level++;
        !           348:                                if( todo ) {
        !           349:                                        ntp = transp[ind].t_trans;
        !           350:                                        xxx("includes", ntp, transp[i].t_trans);
        !           351:                                        ntp->ng_rel->r_list[p] = i;
        !           352:                                }
        !           353:                                if( (ntrmptr[nt-NTBASE]->s_flags&DERIV)==0 )
        !           354:                                        break;
        !           355:                        }
        !           356:                }
        !           357:        }
        !           358:        if( !todo )
        !           359:                endcount();
        !           360: }
        !           361: 
        !           362: endcount()
        !           363: {
        !           364:        register i, k, *relp; /* relp must be integer pointer */
        !           365:        struct ntgo *ntp;
        !           366:        k = 0;
        !           367:        for(i=0; i<nttrans; i++)
        !           368:                                 {
        !           369:                k += transp[i].t_level+1; /* include 1 for count */
        !           370:                }
        !           371:        relp = (int *)yalloc(k, sizeof *relp);
        !           372:        for(i=0; i<nttrans; i++) {
        !           373:                ntp = transp[i].t_trans;
        !           374:                ntp->ng_rel = relp;
        !           375:                ntp->ng_rel->r_count = transp[i].t_level;
        !           376:                relp += transp[i].t_level+1;
        !           377:        }
        !           378: }
        !           379: 
        !           380: startcount()
        !           381: {
        !           382:        register i, j, k;
        !           383:        struct state *stp;
        !           384: 
        !           385:        k = 0;
        !           386:        for(i=0; i<nstates; i++) {
        !           387:                stp = &states[i];
        !           388:                for(j=0; j<stp->s_ntgo; j++) {
        !           389:                        transp[k].t_trans = &stp->s_ntgos[j];
        !           390:                        transp[k].t_level = 0;
        !           391:                        k++;
        !           392:                }
        !           393:        }
        !           394: }
        !           395: 
        !           396: zerolev()
        !           397: {
        !           398:        register i;
        !           399:        for(i=0; i<nttrans; i++)
        !           400:                transp[i].t_level = 0;
        !           401: }
        !           402: 
        !           403: rsearch(ntp)
        !           404: struct ntgo *ntp;
        !           405: {
        !           406:        register lb, nb;
        !           407:        register struct ntgo *el;
        !           408:        int ub;
        !           409: 
        !           410:        lb = 0;
        !           411:        ub = nttrans-1;
        !           412:        do {
        !           413:                nb = (ub+lb)/2;
        !           414:                if( (el = transp[nb].t_trans) < ntp )
        !           415:                        lb = nb+1;
        !           416:                else if( el > ntp )
        !           417:                        ub = nb-1;
        !           418:                else
        !           419:                        return(nb);
        !           420:        } while( lb<=ub );
        !           421:        yyerror(NLNO|FATAL, "oops in rsearch");
        !           422: }
        !           423: 
        !           424: ssearch(ntp)
        !           425: struct ntgo *ntp;
        !           426: {
        !           427:        register lb, nb;
        !           428:        register struct ntgo *el;
        !           429:        int ub;
        !           430: 
        !           431:        lb = 0;
        !           432:        ub = nstates-1;
        !           433: 
        !           434:        do {
        !           435:                nb = (ub+lb) / 2;
        !           436:                el = states[nb].s_ntgos;
        !           437:                if( ntp < el )
        !           438:                        ub = nb-1;
        !           439:                else if( ntp >= &el[states[nb].s_ntgo] )
        !           440:                        lb = nb+1;
        !           441:                else
        !           442:                        return(nb);
        !           443:        } while( lb<=ub );
        !           444:        yyerror(NLNO|FATAL, "oops in ssearch");
        !           445: }
        !           446: 
        !           447: prodl(pp)
        !           448: register struct prod *pp;
        !           449: {
        !           450:        register *ip;
        !           451: 
        !           452:        ip = pp->p_right;
        !           453:        while( *ip++ != -1 );
        !           454:        return( ip-pp->p_right-1 );             /* BONZO OR NO??? */
        !           455: }
        !           456: 
        !           457: struct lset *
        !           458: getset()
        !           459: {
        !           460:        register struct lset *lp;
        !           461:        if( fsetp ) {
        !           462:                lp = fsetp;
        !           463:                fsetp = fsetp->l_next;
        !           464:                return(lp);
        !           465:        }
        !           466:        lp = (struct lset *)yalloc(1, sizeof *lp);
        !           467:        return(lp);
        !           468: }
        !           469: 
        !           470: freeset(lp)
        !           471: struct lset *lp;
        !           472: {
        !           473:        lp->l_next = fsetp;
        !           474:        fsetp = lp;
        !           475: }
        !           476: 
        !           477: frlset()
        !           478: {
        !           479:        register struct state *stp;
        !           480:        register i, j;
        !           481:        struct lset *lp, *lp1;
        !           482: 
        !           483:        free(states[0].s_tgos);
        !           484:        free(states[0].s_ntgos);
        !           485:        for(i=0; i<nstates; i++) {
        !           486:                stp = &states[i];
        !           487:                for(j=0; j<stp->s_nred; j++)
        !           488:                        freeset(stp->s_reds[j].rd_lset);
        !           489:                if( stp->s_reds != (struct redn *)NULL )        /* MWC DSC */
        !           490:                        free(stp->s_reds);
        !           491:                for(j=0; j<stp->s_ntgo; j++)
        !           492:                        freeset(stp->s_ntgos[j].ng_lset);
        !           493:        }
        !           494:        lp = fsetp;
        !           495:        while( lp ) {
        !           496:                lp1 = lp->l_next;
        !           497:                if( lp<&lsetp[0] || lp>=&lsetp[nttrans] )
        !           498:                        free(lp);
        !           499:                lp = lp1;
        !           500:        }
        !           501:        free(lsetp);
        !           502: }
        !           503: 
        !           504: xxx(s, ntp1, ntp2)
        !           505: char *s;
        !           506: struct ntgo *ntp1, *ntp2;
        !           507: {
        !           508:        if( !yydebug )
        !           509:                return;
        !           510:        ptrans(ntp1); fprintf(listout, " %s ", s); ptrans(ntp2); 
        !           511:        fprintf(listout, "\n");
        !           512: }
        !           513: ptrans(ntp)
        !           514: struct ntgo *ntp;
        !           515: {
        !           516:        int sno;
        !           517:        sno = ssearch(ntp);
        !           518:        fprintf(listout, "(%d, %s)", sno, ptosym(ntp->ng_nt));
        !           519: }
        !           520: 
        !           521: prlset(ls)
        !           522: struct lset *ls;
        !           523: {
        !           524:        register i, once;
        !           525:        fprintf(listout, "[");
        !           526:        once = 0;
        !           527:        for(i=first(ls); i>=0; i=next(ls,i)) {
        !           528:                if( once++ ) fprintf(listout, ",");
        !           529:                fprintf(listout, "%s", trmptr[i]->s_name);
        !           530:        }
        !           531:        fprintf(listout, "]");
        !           532: }
        !           533: 
        !           534: 

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