Return to mkpar.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / pgrm / yacc

Annotation of 43BSDReno/pgrm/yacc/mkpar.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1989 The Regents of the University of California.
        !             3:  * All rights reserved.
        !             4:  *
        !             5:  * This code is derived from software contributed to Berkeley by
        !             6:  * Robert Paul Corbett.
        !             7:  *
        !             8:  * Redistribution and use in source and binary forms are permitted provided
        !             9:  * that: (1) source distributions retain this entire copyright notice and
        !            10:  * comment, and (2) distributions including binaries display the following
        !            11:  * acknowledgement:  ``This product includes software developed by the
        !            12:  * University of California, Berkeley and its contributors'' in the
        !            13:  * documentation or other materials provided with the distribution and in
        !            14:  * all advertising materials mentioning features or use of this software.
        !            15:  * Neither the name of the University nor the names of its contributors may
        !            16:  * be used to endorse or promote products derived from this software without
        !            17:  * specific prior written permission.
        !            18:  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
        !            19:  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
        !            20:  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            21:  */
        !            22: 
        !            23: #ifndef lint
        !            24: static char sccsid[] = "@(#)mkpar.c    5.2 (Berkeley) 6/1/90";
        !            25: #endif /* not lint */
        !            26: 
        !            27: #include "defs.h"
        !            28: 
        !            29: action **parser;
        !            30: int SRtotal;
        !            31: int RRtotal;
        !            32: short *SRconflicts;
        !            33: short *RRconflicts;
        !            34: short *defred;
        !            35: short *rules_used;
        !            36: short nunused;
        !            37: short final_state;
        !            38: 
        !            39: static int SRcount;
        !            40: static int RRcount;
        !            41: 
        !            42: extern action *parse_actions();
        !            43: extern action *get_shifts();
        !            44: extern action *add_reductions();
        !            45: extern action *add_reduce();
        !            46: 
        !            47: 
        !            48: make_parser()
        !            49: {
        !            50:     register int i;
        !            51: 
        !            52:     parser = NEW2(nstates, action *);
        !            53:     for (i = 0; i < nstates; i++)
        !            54:        parser[i] = parse_actions(i);
        !            55: 
        !            56:     find_final_state();
        !            57:     remove_conflicts();
        !            58:     unused_rules();
        !            59:     if (SRtotal + RRtotal > 0) total_conflicts();
        !            60:     defreds();
        !            61: }
        !            62: 
        !            63: 
        !            64: action *
        !            65: parse_actions(stateno)
        !            66: register int stateno;
        !            67: {
        !            68:     register action *actions;
        !            69: 
        !            70:     actions = get_shifts(stateno);
        !            71:     actions = add_reductions(stateno, actions);
        !            72:     return (actions);
        !            73: }
        !            74: 
        !            75: 
        !            76: action *
        !            77: get_shifts(stateno)
        !            78: int stateno;
        !            79: {
        !            80:     register action *actions, *temp;
        !            81:     register shifts *sp;
        !            82:     register short *to_state;
        !            83:     register int i, k;
        !            84:     register int symbol;
        !            85: 
        !            86:     actions = 0;
        !            87:     sp = shift_table[stateno];
        !            88:     if (sp)
        !            89:     {
        !            90:        to_state = sp->shift;
        !            91:        for (i = sp->nshifts - 1; i >= 0; i--)
        !            92:        {
        !            93:            k = to_state[i];
        !            94:            symbol = accessing_symbol[k];
        !            95:            if (ISTOKEN(symbol))
        !            96:            {
        !            97:                temp = NEW(action);
        !            98:                temp->next = actions;
        !            99:                temp->symbol = symbol;
        !           100:                temp->number = k;
        !           101:                temp->prec = symbol_prec[symbol];
        !           102:                temp->action_code = SHIFT;
        !           103:                temp->assoc = symbol_assoc[symbol];
        !           104:                actions = temp;
        !           105:            }
        !           106:        }
        !           107:     }
        !           108:     return (actions);
        !           109: }
        !           110: 
        !           111: action *
        !           112: add_reductions(stateno, actions)
        !           113: int stateno;
        !           114: register action *actions;
        !           115: {
        !           116:     register int i, j, m, n;
        !           117:     register int ruleno, tokensetsize;
        !           118:     register unsigned *rowp;
        !           119: 
        !           120:     tokensetsize = WORDSIZE(ntokens);
        !           121:     m = lookaheads[stateno];
        !           122:     n = lookaheads[stateno + 1];
        !           123:     for (i = m; i < n; i++)
        !           124:     {
        !           125:        ruleno = LAruleno[i];
        !           126:        rowp = LA + i * tokensetsize;
        !           127:        for (j = ntokens - 1; j >= 0; j--)
        !           128:        {
        !           129:            if (BIT(rowp, j))
        !           130:                actions = add_reduce(actions, ruleno, j);
        !           131:        }
        !           132:     }
        !           133:     return (actions);
        !           134: }
        !           135: 
        !           136: 
        !           137: action *
        !           138: add_reduce(actions, ruleno, symbol)
        !           139: register action *actions;
        !           140: register int ruleno, symbol;
        !           141: {
        !           142:     register action *temp, *prev, *next;
        !           143: 
        !           144:     prev = 0;
        !           145:     for (next = actions; next && next->symbol < symbol; next = next->next)
        !           146:        prev = next;
        !           147: 
        !           148:     while (next && next->symbol == symbol && next->action_code == SHIFT)
        !           149:     {
        !           150:        prev = next;
        !           151:        next = next->next;
        !           152:     }
        !           153: 
        !           154:     while (next && next->symbol == symbol &&
        !           155:            next->action_code == REDUCE && next->number < ruleno)
        !           156:     {
        !           157:        prev = next;
        !           158:        next = next->next;
        !           159:     }
        !           160: 
        !           161:     temp = NEW(action);
        !           162:     temp->next = next;
        !           163:     temp->symbol = symbol;
        !           164:     temp->number = ruleno;
        !           165:     temp->prec = rprec[ruleno];
        !           166:     temp->action_code = REDUCE;
        !           167:     temp->assoc = rassoc[ruleno];
        !           168: 
        !           169:     if (prev)
        !           170:        prev->next = temp;
        !           171:     else
        !           172:        actions = temp;
        !           173: 
        !           174:     return (actions);
        !           175: }
        !           176: 
        !           177: 
        !           178: find_final_state()
        !           179: {
        !           180:     register int goal, i;
        !           181:     register short *to_state;
        !           182:     register shifts *p;
        !           183: 
        !           184:     p = shift_table[0];
        !           185:     to_state = p->shift;
        !           186:     goal = ritem[1];
        !           187:     for (i = p->nshifts - 1; i >= 0; --i)
        !           188:     {
        !           189:        final_state = to_state[i];
        !           190:        if (accessing_symbol[final_state] == goal) break;
        !           191:     }
        !           192: }
        !           193: 
        !           194: 
        !           195: unused_rules()
        !           196: {
        !           197:     register int i;
        !           198:     register action *p;
        !           199: 
        !           200:     rules_used = (short *) MALLOC(nrules*sizeof(short));
        !           201:     if (rules_used == 0) no_space();
        !           202: 
        !           203:     for (i = 0; i < nrules; ++i)
        !           204:        rules_used[i] = 0;
        !           205: 
        !           206:     for (i = 0; i < nstates; ++i)
        !           207:     {
        !           208:        for (p = parser[i]; p; p = p->next)
        !           209:        {
        !           210:            if (p->action_code == REDUCE && p->suppressed == 0)
        !           211:                rules_used[p->number] = 1;
        !           212:        }
        !           213:     }
        !           214: 
        !           215:     nunused = 0;
        !           216:     for (i = 3; i < nrules; ++i)
        !           217:        if (!rules_used[i]) ++nunused;
        !           218: 
        !           219:     if (nunused)
        !           220:        if (nunused == 1)
        !           221:            fprintf(stderr, "%s: 1 rule never reduced\n", myname);
        !           222:        else
        !           223:            fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
        !           224: }
        !           225: 
        !           226: 
        !           227: remove_conflicts()
        !           228: {
        !           229:     register int i;
        !           230:     register int symbol;
        !           231:     register action *p, *q;
        !           232: 
        !           233:     SRtotal = 0;
        !           234:     RRtotal = 0;
        !           235:     SRconflicts = NEW2(nstates, short);
        !           236:     RRconflicts = NEW2(nstates, short);
        !           237:     for (i = 0; i < nstates; i++)
        !           238:     {
        !           239:        SRcount = 0;
        !           240:        RRcount = 0;
        !           241:        for (p = parser[i]; p; p = q->next)
        !           242:        {
        !           243:            symbol = p->symbol;
        !           244:            q = p;
        !           245:            while (q->next && q->next->symbol == symbol)
        !           246:                q = q->next;
        !           247:            if (i == final_state && symbol == 0)
        !           248:                end_conflicts(p, q);
        !           249:            else if (p != q)
        !           250:                resolve_conflicts(p, q);
        !           251:        }
        !           252:        SRtotal += SRcount;
        !           253:        RRtotal += RRcount;
        !           254:        SRconflicts[i] = SRcount;
        !           255:        RRconflicts[i] = RRcount;
        !           256:     }
        !           257: }
        !           258: 
        !           259: 
        !           260: end_conflicts(p, q)
        !           261: register action *p, *q;
        !           262: {
        !           263:     for (;;)
        !           264:     {
        !           265:        SRcount++;
        !           266:        p->suppressed = 1;
        !           267:        if (p == q) break;
        !           268:        p = p->next;
        !           269:     }
        !           270: }
        !           271: 
        !           272: 
        !           273: resolve_conflicts(first, last)
        !           274: register action *first, *last;
        !           275: {
        !           276:     register action *p;
        !           277:     register int count;
        !           278: 
        !           279:     count = 1;
        !           280:     for (p = first; p != last; p = p->next)
        !           281:        ++count;
        !           282:     assert(count > 1);
        !           283: 
        !           284:     if (first->action_code == SHIFT && count == 2 &&
        !           285:            first->prec > 0 && last->prec > 0)
        !           286:     {
        !           287:        if (first->prec == last->prec)
        !           288:        {
        !           289:            if (first->assoc == LEFT)
        !           290:                first->suppressed = 2;
        !           291:            else if (first->assoc == RIGHT)
        !           292:                last->suppressed = 2;
        !           293:            else
        !           294:            {
        !           295:                first->suppressed = 2;
        !           296:                last->suppressed = 2;
        !           297:                first->action_code = ERROR;
        !           298:                last->action_code = ERROR;
        !           299:            }
        !           300:        }
        !           301:        else if (first->prec < last->prec)
        !           302:            first->suppressed = 2;
        !           303:        else
        !           304:            last->suppressed = 2;
        !           305:     }
        !           306:     else
        !           307:     {
        !           308:        if (first->action_code == SHIFT)
        !           309:            SRcount += (count - 1);
        !           310:         else
        !           311:            RRcount += (count - 1);
        !           312:        for (p = first; p != last; p = p->next, p->suppressed = 1)
        !           313:            continue;
        !           314:     }
        !           315: }
        !           316: 
        !           317: 
        !           318: total_conflicts()
        !           319: {
        !           320:     fprintf(stderr, "%s: ", myname);
        !           321:     if (SRtotal == 1)
        !           322:        fprintf(stderr, "1 shift/reduce conflict");
        !           323:     else if (SRtotal > 1)
        !           324:        fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
        !           325: 
        !           326:     if (SRtotal && RRtotal)
        !           327:        fprintf(stderr, ", ");
        !           328: 
        !           329:     if (RRtotal == 1)
        !           330:        fprintf(stderr, "1 reduce/reduce conflict");
        !           331:     else if (RRtotal > 1)
        !           332:        fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
        !           333: 
        !           334:     fprintf(stderr, ".\n");
        !           335: }
        !           336: 
        !           337: 
        !           338: int
        !           339: sole_reduction(stateno)
        !           340: int stateno;
        !           341: {
        !           342:     register int count, ruleno;
        !           343:     register action *p;
        !           344: 
        !           345:     count = 0;
        !           346:     ruleno = 0; 
        !           347:     for (p = parser[stateno]; p; p = p->next)
        !           348:     {
        !           349:        if (p->action_code == SHIFT && p->suppressed == 0)
        !           350:            return (0);
        !           351:        else if (p->action_code == REDUCE && p->suppressed == 0)
        !           352:        {
        !           353:            if (ruleno > 0 && p->number != ruleno)
        !           354:                return (0);
        !           355:            if (p->symbol != 1)
        !           356:                ++count;
        !           357:            ruleno = p->number;
        !           358:        }
        !           359:     }
        !           360: 
        !           361:     if (count == 0)
        !           362:        return (0);
        !           363:     return (ruleno);
        !           364: }
        !           365: 
        !           366: 
        !           367: defreds()
        !           368: {
        !           369:     register int i;
        !           370: 
        !           371:     defred = NEW2(nstates, short);
        !           372:     for (i = 0; i < nstates; i++)
        !           373:        defred[i] = sole_reduction(i);
        !           374: }
        !           375:  
        !           376: free_action_row(p)
        !           377: register action *p;
        !           378: {
        !           379:   register action *q;
        !           380: 
        !           381:   while (p)
        !           382:     {
        !           383:       q = p->next;
        !           384:       FREE(p);
        !           385:       p = q;
        !           386:     }
        !           387: }
        !           388: 
        !           389: free_parser()
        !           390: {
        !           391:   register int i;
        !           392: 
        !           393:   for (i = 0; i < nstates; i++)
        !           394:     free_action_row(parser[i]);
        !           395: 
        !           396:   FREE(parser);
        !           397: }

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