Return to y3.c CVS log

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

Annotation of coherent/b/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: #include "yacc.h"
        !             9: #include <assert.h>
        !            10: 
        !            11: /* the size of SMAX must be related to the amount of space available
        !            12:    on the runtime stack for recursive calls to traverse.
        !            13:    (on systems which do not dynamically allocate the stack like RSX)
        !            14:    on RSX traverse takes up about 18 bytes per call which means that
        !            15:    with a 1024 byte stack we can probably make 50-55 levels of recursion
        !            16: */
        !            17: #define SMAX 300
        !            18: 
        !            19: #define INFINITY 10000         /* infinity is small for a mathematician */
        !            20: #define INITCODE 1
        !            21: #define COPYCODE 2
        !            22: #define UNIONCODE 3
        !            23: #define EOFCODE 4
        !            24: static struct
        !            25: {
        !            26:        int     s_last;
        !            27:        int     s_vals[SMAX];
        !            28: } stk;                         /* stack for digraph */
        !            29: 
        !            30: static struct trans *transp;   /* temporary vector for traverse */
        !            31: static struct lset *lsetp, *fsetp;
        !            32: static int nttrans;
        !            33: int rread(), rincl();
        !            34: struct lset *getset();
        !            35: 
        !            36: genlook()
        !            37: {
        !            38:        int code = EOFCODE;
        !            39:        rewopt();
        !            40:        cttrans();
        !            41:        transp = (struct trans *)yalloc(nttrans, sizeof *transp);
        !            42:        cdread();
        !            43:        rread(0);
        !            44:        rread(1);
        !            45:        digraph();
        !            46:        free(transp->t_trans->ng_rel);
        !            47:        rincl(0);
        !            48:        rincl(1);
        !            49:        digraph();
        !            50:        free(transp->t_trans->ng_rel);
        !            51:        free(transp);
        !            52:        fwrite(&code, sizeof code, 1, optout);
        !            53:        execute();
        !            54:        lookback();
        !            55: }
        !            56: 
        !            57: cdread()
        !            58: {
        !            59:        register i, j, k;
        !            60:        struct state *stp, *stp1;
        !            61:        struct ntgo *ntp;
        !            62:        struct lset lset;
        !            63:        int code = INITCODE;
        !            64: 
        !            65:        for(i=0; i<nstates; i++) {
        !            66:                stp = &states[i];
        !            67:                for(j=0; j<stp->s_ntgo; j++) {
        !            68:                        zerolset(&lset);
        !            69:                        ntp = &stp->s_ntgos[j];
        !            70:                        stp1 = &states[ntp->ng_st];
        !            71:                        for(k=0; k<stp1->s_tgo; k++) 
        !            72:                                setbit(&lset, stp1->s_tgos[k].tg_trm);
        !            73:                        fwrite(&code, sizeof code, 1, optout);
        !            74:                        fwrite(&ntp, sizeof ntp, 1, optout);
        !            75:                        fwrite(lset.l_bits, sizeof lset.l_bits, 1, optout);
        !            76:                }
        !            77:        }
        !            78: }
        !            79: 
        !            80: 
        !            81: 
        !            82: cttrans()
        !            83: {
        !            84:        /* count number of nonterminal transations in automaton */
        !            85:        register i;
        !            86: 
        !            87:        nttrans = 0;
        !            88:        for(i=0; i<nstates; i++)
        !            89:                nttrans += states[i].s_ntgo;
        !            90: }
        !            91: 
        !            92: digraph()
        !            93: {
        !            94:        register i;
        !            95:        stk.s_last = 0;
        !            96:        zerolev();
        !            97:        for(i=0; i<nttrans; i++)
        !            98:                if( transp[i].t_level==0 )
        !            99:                        traverse(i);
        !           100: }
        !           101: 
        !           102: traverse(x)
        !           103: register int x;
        !           104: {
        !           105:        register i, y;
        !           106:        int k;
        !           107:        struct ntgo *ntp;
        !           108:        int code = UNIONCODE;
        !           109: 
        !           110:        if( stk.s_last>= (SMAX-1) )
        !           111:                yyerror(FATAL|NLNO, "internal stack overflow - SMAX");
        !           112:        stk.s_vals[++stk.s_last] = x;
        !           113:        k = stk.s_last;
        !           114:        transp[x].t_level = k;
        !           115:        ntp = transp[x].t_trans;
        !           116: 
        !           117:        for(i=0; i<ntp->ng_rel->r_count; i++) {
        !           118:                y = ntp->ng_rel->r_list[i];
        !           119:                if( transp[y].t_level==0 )
        !           120:                        traverse(y);
        !           121:                if( transp[y].t_level < transp[x].t_level )
        !           122:                        transp[x].t_level = transp[y].t_level;
        !           123:                fwrite(&code, sizeof code, 1, optout);
        !           124:                fwrite(&ntp, sizeof ntp, 1, optout);
        !           125:                fwrite(&transp[y].t_trans, sizeof ntp, 1, optout);
        !           126:        }
        !           127: 
        !           128:        code = COPYCODE;
        !           129:        if( transp[x].t_level == k ) {
        !           130:                transp[x].t_level = INFINITY;
        !           131:                while( (y = stk.s_vals[stk.s_last--]) != x ) {
        !           132:                        transp[y].t_level = INFINITY;
        !           133:                        fwrite(&code, sizeof code, 1, optout);
        !           134:                        fwrite(&transp[y].t_trans, sizeof ntp, 1, optout);
        !           135:                        fwrite(&ntp, sizeof ntp, 1, optout);
        !           136:                }
        !           137:        }
        !           138: }
        !           139: 
        !           140: /*
        !           141:  * form the set unions of the read sets and the follow sets, following
        !           142:  * the codes left in temp file by digraph
        !           143:  */
        !           144: execute()
        !           145: {
        !           146:        int code;
        !           147:        struct ntgo *ntp1, *ntp2;
        !           148:        register struct lset *csetp;
        !           149: 
        !           150:        rewopt();
        !           151:        csetp = lsetp = (struct lset *)yalloc(nttrans, sizeof *lsetp);
        !           152:        fsetp = NULL;
        !           153:        for(;;) {
        !           154:                if( fread(&code, sizeof code, 1, optout) != 1 )
        !           155:                        yyerror(NLNO|FATAL, "eof on tempfile in execute");
        !           156:                switch( code ) {
        !           157:                case INITCODE:
        !           158:                        fread(&ntp1, sizeof ntp1, 1, optout);
        !           159:                        assert( csetp < &lsetp[nttrans] );
        !           160:                        fread(csetp->l_bits, sizeof csetp->l_bits,  1, optout);
        !           161: /*
        !           162:                        fprintf(listout, "init: "); ptrans(ntp1);
        !           163:                        prlset(csetp); fprintf(listout,"\n");
        !           164: */
        !           165:                        ntp1->ng_lset = csetp++;
        !           166:                        break;
        !           167: 
        !           168:                case UNIONCODE:
        !           169:                        fread(&ntp1, sizeof ntp1, 1, optout);
        !           170:                        fread(&ntp2, sizeof ntp2, 1, optout);
        !           171: /*
        !           172:                        fprintf(listout, "union "); ptrans(ntp1); fprintf(listout," |=");
        !           173:                        ptrans(ntp2);
        !           174: */
        !           175:                        setunion(ntp1->ng_lset, ntp2->ng_lset);
        !           176: /*
        !           177:                        prlset(ntp1->ng_lset); fprintf(listout, "\n");
        !           178: */
        !           179:                        break;
        !           180: 
        !           181:                case COPYCODE:
        !           182:                        fread(&ntp1, sizeof ntp1, 1, optout);
        !           183:                        fread(&ntp2, sizeof ntp2, 1, optout);
        !           184:                        xxx("copy", ntp1, ntp2);
        !           185:                        freeset(ntp1->ng_lset);
        !           186:                        ntp1->ng_lset = getset();
        !           187:                        copylset(ntp1->ng_lset, ntp2->ng_lset);
        !           188:                        break;
        !           189: 
        !           190:                case EOFCODE:
        !           191:                        return;
        !           192:                default:
        !           193:                        yyerror(NLNO|FATAL, "bad temp file; code %o\n", code);
        !           194:                }
        !           195:        }
        !           196: }
        !           197: 
        !           198: lookback()
        !           199: {
        !           200:        register i;
        !           201: 
        !           202:        for(i=0; i<nprod; i++)
        !           203:                reduce(prdptr[i]);
        !           204: 
        !           205: }
        !           206: 
        !           207: reduce(pp)
        !           208: register struct prod *pp;
        !           209: {
        !           210:        register nt, i;
        !           211:        struct sym *sp;
        !           212:        struct redn *rdp;
        !           213:        struct state *stp, *stp1;
        !           214:        int j, sno, sno1;
        !           215:        struct ntgo *ntp;
        !           216: 
        !           217:        nt = -pp->p_left;
        !           218:        sp = ntrmptr[nt-NTBASE];
        !           219:        for(j=0; j<sp->s_nstates; j++) {
        !           220:                stp = &states[sno = sp->s_states[j]];
        !           221:                for(i=0; i<stp->s_ntgo; i++) {
        !           222:                        ntp = &stp->s_ntgos[i];
        !           223:                        if( ntp->ng_nt == nt )
        !           224:                                break;
        !           225:                }
        !           226:                assert(pp->p_prodno==0 || i<stp->s_ntgo);
        !           227:                sno1 = go2star(sno, PROD_RIGHT (pp),
        !           228:                                PROD_RIGHT (pp) + 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 = PROD_RIGHT (pp);
        !           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;
        !           365:        struct ntgo *ntp;
        !           366:        char          * alloc;
        !           367: 
        !           368:        k = 0;
        !           369:        for(i = 0 ; i < nttrans ; i ++)
        !           370:                k += REL_TOTAL_SIZE (transp [i].t_level);
        !           371: 
        !           372:        alloc = yalloc (1, k);
        !           373: 
        !           374:        for(i=0; i<nttrans; i++) {
        !           375:                ntp = transp[i].t_trans;
        !           376:                ntp->ng_rel = (struct rel *) alloc;
        !           377:                REL_EXTRA_INIT (ntp->ng_rel);
        !           378:                ntp->ng_rel->r_count = transp[i].t_level;
        !           379: 
        !           380:                alloc += REL_TOTAL_SIZE (transp[i].t_level);
        !           381:        }
        !           382: }
        !           383: 
        !           384: startcount()
        !           385: {
        !           386:        register i, j, k;
        !           387:        struct state *stp;
        !           388: 
        !           389:        k = 0;
        !           390:        for(i=0; i<nstates; i++) {
        !           391:                stp = &states[i];
        !           392:                for(j=0; j<stp->s_ntgo; j++) {
        !           393:                        transp[k].t_trans = &stp->s_ntgos[j];
        !           394:                        transp[k].t_level = 0;
        !           395:                        k++;
        !           396:                }
        !           397:        }
        !           398: }
        !           399: 
        !           400: zerolev()
        !           401: {
        !           402:        register i;
        !           403:        for(i=0; i<nttrans; i++)
        !           404:                transp[i].t_level = 0;
        !           405: }
        !           406: 
        !           407: rsearch(ntp)
        !           408: struct ntgo *ntp;
        !           409: {
        !           410:        register lb, nb;
        !           411:        register struct ntgo *el;
        !           412:        int ub;
        !           413: 
        !           414:        lb = 0;
        !           415:        ub = nttrans-1;
        !           416:        do {
        !           417:                nb = (ub+lb)/2;
        !           418:                if( (el = transp[nb].t_trans) < ntp )
        !           419:                        lb = nb+1;
        !           420:                else if( el > ntp )
        !           421:                        ub = nb-1;
        !           422:                else
        !           423:                        return(nb);
        !           424:        } while( lb<=ub );
        !           425:        yyerror(NLNO|FATAL, "oops in rsearch");
        !           426: }
        !           427: 
        !           428: ssearch(ntp)
        !           429: struct ntgo *ntp;
        !           430: {
        !           431:        register lb, nb;
        !           432:        register struct ntgo *el;
        !           433:        int ub;
        !           434: 
        !           435:        lb = 0;
        !           436:        ub = nstates-1;
        !           437: 
        !           438:        do {
        !           439:                nb = (ub+lb) / 2;
        !           440:                el = states[nb].s_ntgos;
        !           441:                if( ntp < el )
        !           442:                        ub = nb-1;
        !           443:                else if( ntp >= &el[states[nb].s_ntgo] )
        !           444:                        lb = nb+1;
        !           445:                else
        !           446:                        return(nb);
        !           447:        } while( lb<=ub );
        !           448:        yyerror(NLNO|FATAL, "oops in ssearch");
        !           449: }
        !           450: 
        !           451: prodl(pp)
        !           452: register struct prod *pp;
        !           453: {
        !           454:        register *ip;
        !           455: 
        !           456:        ip = PROD_RIGHT (pp);
        !           457:        while (* ip ++ != -1)
        !           458:                /* DO NOTHING */;
        !           459:        return ip - PROD_RIGHT (pp) - 1;                /* BONZO OR NO??? */
        !           460: }
        !           461: 
        !           462: struct lset *
        !           463: getset()
        !           464: {
        !           465:        register struct lset *lp;
        !           466:        if( fsetp ) {
        !           467:                lp = fsetp;
        !           468:                fsetp = fsetp->l_next;
        !           469:                return(lp);
        !           470:        }
        !           471:        lp = (struct lset *)yalloc(1, sizeof *lp);
        !           472:        return(lp);
        !           473: }
        !           474: 
        !           475: freeset(lp)
        !           476: struct lset *lp;
        !           477: {
        !           478:        lp->l_next = fsetp;
        !           479:        fsetp = lp;
        !           480: }
        !           481: 
        !           482: frlset()
        !           483: {
        !           484:        register struct state *stp;
        !           485:        register i, j;
        !           486:        struct lset *lp, *lp1;
        !           487: 
        !           488:        free(states[0].s_tgos);
        !           489:        free(states[0].s_ntgos);
        !           490:        for(i=0; i<nstates; i++) {
        !           491:                stp = &states[i];
        !           492:                for(j=0; j<stp->s_nred; j++)
        !           493:                        freeset(stp->s_reds[j].rd_lset);
        !           494:                if( stp->s_reds != (struct redn *)NULL )        /* MWC DSC */
        !           495:                        free(stp->s_reds);
        !           496:                for(j=0; j<stp->s_ntgo; j++)
        !           497:                        freeset(stp->s_ntgos[j].ng_lset);
        !           498:        }
        !           499:        lp = fsetp;
        !           500:        while( lp ) {
        !           501:                lp1 = lp->l_next;
        !           502:                if( lp<&lsetp[0] || lp>=&lsetp[nttrans] )
        !           503:                        free(lp);
        !           504:                lp = lp1;
        !           505:        }
        !           506:        free(lsetp);
        !           507: }
        !           508: 
        !           509: xxx(s, ntp1, ntp2)
        !           510: char *s;
        !           511: struct ntgo *ntp1, *ntp2;
        !           512: {
        !           513:        if( !yydebug )
        !           514:                return;
        !           515:        ptrans(ntp1); fprintf(listout, " %s ", s); ptrans(ntp2); 
        !           516:        fprintf(listout, "\n");
        !           517: }
        !           518: ptrans(ntp)
        !           519: struct ntgo *ntp;
        !           520: {
        !           521:        int sno;
        !           522:        sno = ssearch(ntp);
        !           523:        fprintf(listout, "(%d, %s)", sno, ptosym(ntp->ng_nt));
        !           524: }
        !           525: 
        !           526: prlset(ls)
        !           527: struct lset *ls;
        !           528: {
        !           529:        register i, once;
        !           530:        fprintf(listout, "[");
        !           531:        once = 0;
        !           532:        for(i=first(ls); i>=0; i=next(ls,i)) {
        !           533:                if( once++ ) fprintf(listout, ",");
        !           534:                fprintf(listout, "%s", trmptr[i]->s_name);
        !           535:        }
        !           536:        fprintf(listout, "]");
        !           537: }
        !           538: 
        !           539: 

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