Return to lr0.c CVS log

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

Annotation of 43BSDReno/pgrm/yacc/lr0.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[] = "@(#)lr0.c      5.2 (Berkeley) 6/1/90";
        !            25: #endif /* not lint */
        !            26: 
        !            27: #include "defs.h"
        !            28: 
        !            29: extern short *itemset;
        !            30: extern short *itemsetend;
        !            31: extern unsigned *ruleset;
        !            32: 
        !            33: int nstates;
        !            34: core *first_state;
        !            35: shifts *first_shift;
        !            36: reductions *first_reduction;
        !            37: 
        !            38: int get_state();
        !            39: core *new_state();
        !            40: 
        !            41: static core *this_state;
        !            42: static core *last_state;
        !            43: static shifts *last_shift;
        !            44: static reductions *last_reduction;
        !            45: 
        !            46: static int nshifts;
        !            47: static short *shift_symbol;
        !            48: 
        !            49: static short *redset;
        !            50: static short *shiftset;
        !            51: 
        !            52: static short **kernel_base;
        !            53: static short **kernel_end;
        !            54: static short *kernel_items;
        !            55: 
        !            56: static core **state_table;
        !            57: 
        !            58: 
        !            59: allocate_itemsets()
        !            60: {
        !            61:   register short *itemp;
        !            62:   register short *item_end;
        !            63:   register int symbol;
        !            64:   register int i;
        !            65:   register int count;
        !            66:   register int max;
        !            67:   register short *symbol_count;
        !            68: 
        !            69:   count = 0;
        !            70:   symbol_count = NEW2(nsyms, short);
        !            71: 
        !            72:   item_end = ritem + nitems;
        !            73:   for (itemp = ritem; itemp < item_end; itemp++)
        !            74:     {
        !            75:       symbol = *itemp;
        !            76:       if (symbol >= 0)
        !            77:        {
        !            78:          count++;
        !            79:          symbol_count[symbol]++;
        !            80:        }
        !            81:     }
        !            82: 
        !            83:   kernel_base = NEW2(nsyms, short *);
        !            84:   kernel_items = NEW2(count, short);
        !            85: 
        !            86:   count = 0;
        !            87:   max = 0;
        !            88:   for (i = 0; i < nsyms; i++)
        !            89:     {
        !            90:       kernel_base[i] = kernel_items + count;
        !            91:       count += symbol_count[i];
        !            92:       if (max < symbol_count[i])
        !            93:        max = symbol_count[i];
        !            94:     }
        !            95: 
        !            96:   shift_symbol = symbol_count;
        !            97:   kernel_end = NEW2(nsyms, short *);
        !            98: }
        !            99: 
        !           100: 
        !           101: 
        !           102: allocate_storage()
        !           103: {
        !           104:   allocate_itemsets();
        !           105: 
        !           106:   shiftset = NEW2(nsyms, short);
        !           107:   redset = NEW2(nrules + 1, short);
        !           108:   state_table = NEW2(nitems, core *);
        !           109: }
        !           110: 
        !           111: 
        !           112: 
        !           113: append_states()
        !           114: {
        !           115:   register int i;
        !           116:   register int j;
        !           117:   register int symbol;
        !           118: 
        !           119: #ifdef TRACE
        !           120:   fprintf(stderr, "Entering append_states\n");
        !           121: #endif
        !           122: 
        !           123:   for (i = 1; i < nshifts; i++)
        !           124:     {
        !           125:       symbol = shift_symbol[i];
        !           126:       j = i;
        !           127:       while (j > 0 && shift_symbol[j - 1] > symbol)
        !           128:        {
        !           129:          shift_symbol[j] = shift_symbol[j - 1];
        !           130:          j--;
        !           131:        }
        !           132:       shift_symbol[j] = symbol;
        !           133:     }
        !           134: 
        !           135:   for (i = 0; i < nshifts; i++)
        !           136:     {
        !           137:       symbol = shift_symbol[i];
        !           138:       shiftset[i] = get_state(symbol);
        !           139:     }
        !           140: }
        !           141: 
        !           142: 
        !           143: free_storage()
        !           144: {
        !           145:   FREE(shift_symbol);
        !           146:   FREE(redset);
        !           147:   FREE(shiftset);
        !           148:   FREE(kernel_base);
        !           149:   FREE(kernel_end);
        !           150:   FREE(kernel_items);
        !           151:   FREE(state_table);
        !           152: }
        !           153: 
        !           154: 
        !           155: 
        !           156: generate_states()
        !           157: {
        !           158:   allocate_storage();
        !           159:   itemset = NEW2(nitems, short);
        !           160:   ruleset = NEW2(WORDSIZE(nrules), unsigned);
        !           161:   set_first_derives();
        !           162:   initialize_states();
        !           163: 
        !           164:   while (this_state)
        !           165:     {
        !           166:       closure(this_state->items, this_state->nitems);
        !           167:       save_reductions();
        !           168:       new_itemsets();
        !           169:       append_states();
        !           170: 
        !           171:       if (nshifts > 0)
        !           172:         save_shifts();
        !           173: 
        !           174:       this_state = this_state->next;
        !           175:     }
        !           176: 
        !           177:   finalize_closure();
        !           178:   free_storage();
        !           179: }
        !           180: 
        !           181: 
        !           182: 
        !           183: int
        !           184: get_state(symbol)
        !           185: int symbol;
        !           186: {
        !           187:   register int key;
        !           188:   register short *isp1;
        !           189:   register short *isp2;
        !           190:   register short *iend;
        !           191:   register core *sp;
        !           192:   register int found;
        !           193: 
        !           194:   int n;
        !           195: 
        !           196: #ifdef TRACE
        !           197:   fprintf(stderr, "Entering get_state, symbol = %d\n", symbol);
        !           198: #endif
        !           199: 
        !           200:   isp1 = kernel_base[symbol];
        !           201:   iend = kernel_end[symbol];
        !           202:   n = iend - isp1;
        !           203: 
        !           204:   key = *isp1;
        !           205:   assert(0 <= key && key < nitems);
        !           206:   sp = state_table[key];
        !           207:   if (sp)
        !           208:     {
        !           209:       found = 0;
        !           210:       while (!found)
        !           211:        {
        !           212:          if (sp->nitems == n)
        !           213:            {
        !           214:              found = 1;
        !           215:              isp1 = kernel_base[symbol];
        !           216:              isp2 = sp->items;
        !           217: 
        !           218:              while (found && isp1 < iend)
        !           219:                {
        !           220:                  if (*isp1++ != *isp2++)
        !           221:                    found = 0;
        !           222:                }
        !           223:            }
        !           224: 
        !           225:          if (!found)
        !           226:            {
        !           227:              if (sp->link)
        !           228:                {
        !           229:                  sp = sp->link;
        !           230:                }
        !           231:              else
        !           232:                {
        !           233:                  sp = sp->link = new_state(symbol);
        !           234:                  found = 1;
        !           235:                }
        !           236:            }
        !           237:        }
        !           238:     }
        !           239:   else
        !           240:     {
        !           241:       state_table[key] = sp = new_state(symbol);
        !           242:     }
        !           243: 
        !           244:   return (sp->number);
        !           245: }
        !           246: 
        !           247: 
        !           248: 
        !           249: initialize_states()
        !           250: {
        !           251:     register int i;
        !           252:     register short *start_derives;
        !           253:     register core *p;
        !           254: 
        !           255:     start_derives = derives[start_symbol];
        !           256:     for (i = 0; start_derives[i] >= 0; ++i)
        !           257:        continue;
        !           258: 
        !           259:     p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
        !           260:     if (p == 0) no_space();
        !           261: 
        !           262:     p->next = 0;
        !           263:     p->link = 0;
        !           264:     p->number = 0;
        !           265:     p->accessing_symbol = 0;
        !           266:     p->nitems = i;
        !           267: 
        !           268:     for (i = 0;  start_derives[i] >= 0; ++i)
        !           269:        p->items[i] = rrhs[start_derives[i]];
        !           270: 
        !           271:     first_state = last_state = this_state = p;
        !           272:     nstates = 1;
        !           273: }
        !           274: 
        !           275: 
        !           276: new_itemsets()
        !           277: {
        !           278:   register int i;
        !           279:   register int shiftcount;
        !           280:   register short *isp;
        !           281:   register short *ksp;
        !           282:   register int symbol;
        !           283: 
        !           284:   for (i = 0; i < nsyms; i++)
        !           285:     kernel_end[i] = 0;
        !           286: 
        !           287:   shiftcount = 0;
        !           288:   isp = itemset;
        !           289:   while (isp < itemsetend)
        !           290:     {
        !           291:       i = *isp++;
        !           292:       symbol = ritem[i];
        !           293:       if (symbol > 0)
        !           294:        {
        !           295:           ksp = kernel_end[symbol];
        !           296: 
        !           297:           if (!ksp)
        !           298:            {
        !           299:              shift_symbol[shiftcount++] = symbol;
        !           300:              ksp = kernel_base[symbol];
        !           301:            }
        !           302: 
        !           303:           *ksp++ = i + 1;
        !           304:           kernel_end[symbol] = ksp;
        !           305:        }
        !           306:     }
        !           307: 
        !           308:   nshifts = shiftcount;
        !           309: }
        !           310: 
        !           311: 
        !           312: 
        !           313: core *
        !           314: new_state(symbol)
        !           315: int symbol;
        !           316: {
        !           317:   register int n;
        !           318:   register core *p;
        !           319:   register short *isp1;
        !           320:   register short *isp2;
        !           321:   register short *iend;
        !           322: 
        !           323: #ifdef TRACE
        !           324:   fprintf(stderr, "Entering new_state, symbol = %d\n", symbol);
        !           325: #endif
        !           326: 
        !           327:   if (nstates >= MAXSHORT)
        !           328:     fatal("too many states");
        !           329: 
        !           330:   isp1 = kernel_base[symbol];
        !           331:   iend = kernel_end[symbol];
        !           332:   n = iend - isp1;
        !           333: 
        !           334:   p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
        !           335:   p->accessing_symbol = symbol;
        !           336:   p->number = nstates;
        !           337:   p->nitems = n;
        !           338: 
        !           339:   isp2 = p->items;
        !           340:   while (isp1 < iend)
        !           341:     *isp2++ = *isp1++;
        !           342: 
        !           343:   last_state->next = p;
        !           344:   last_state = p;
        !           345: 
        !           346:   nstates++;
        !           347: 
        !           348:   return (p);
        !           349: }
        !           350: 
        !           351: 
        !           352: /* show_cores is used for debugging */
        !           353: 
        !           354: show_cores()
        !           355: {
        !           356:     core *p;
        !           357:     int i, j, k, n;
        !           358:     int itemno;
        !           359: 
        !           360:     k = 0;
        !           361:     for (p = first_state; p; ++k, p = p->next)
        !           362:     {
        !           363:        if (k) printf("\n");
        !           364:        printf("state %d, number = %d, accessing symbol = %s\n",
        !           365:                k, p->number, symbol_name[p->accessing_symbol]);
        !           366:        n = p->nitems;
        !           367:        for (i = 0; i < n; ++i)
        !           368:        {
        !           369:            itemno = p->items[i];
        !           370:            printf("%4d  ", itemno);
        !           371:            j = itemno;
        !           372:            while (ritem[j] >= 0) ++j;
        !           373:            printf("%s :", symbol_name[rlhs[-ritem[j]]]);
        !           374:            j = rrhs[-ritem[j]];
        !           375:            while (j < itemno)
        !           376:                printf(" %s", symbol_name[ritem[j++]]);
        !           377:            printf(" .");
        !           378:            while (ritem[j] >= 0)
        !           379:                printf(" %s", symbol_name[ritem[j++]]);
        !           380:            printf("\n");
        !           381:            fflush(stdout);
        !           382:        }
        !           383:     }
        !           384: }
        !           385: 
        !           386: 
        !           387: /* show_ritems is used for debugging */
        !           388: 
        !           389: show_ritems()
        !           390: {
        !           391:     int i;
        !           392: 
        !           393:     for (i = 0; i < nitems; ++i)
        !           394:        printf("ritem[%d] = %d\n", i, ritem[i]);
        !           395: }
        !           396: 
        !           397: 
        !           398: /* show_rrhs is used for debugging */
        !           399: show_rrhs()
        !           400: {
        !           401:     int i;
        !           402: 
        !           403:     for (i = 0; i < nrules; ++i)
        !           404:        printf("rrhs[%d] = %d\n", i, rrhs[i]);
        !           405: }
        !           406: 
        !           407: 
        !           408: /* show_shifts is used for debugging */
        !           409: 
        !           410: show_shifts()
        !           411: {
        !           412:     shifts *p;
        !           413:     int i, j, k;
        !           414: 
        !           415:     k = 0;
        !           416:     for (p = first_shift; p; ++k, p = p->next)
        !           417:     {
        !           418:        if (k) printf("\n");
        !           419:        printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
        !           420:                p->nshifts);
        !           421:        j = p->nshifts;
        !           422:        for (i = 0; i < j; ++i)
        !           423:            printf("\t%d\n", p->shift[i]);
        !           424:     }
        !           425: }
        !           426: 
        !           427: 
        !           428: save_shifts()
        !           429: {
        !           430:   register shifts *p;
        !           431:   register short *sp1;
        !           432:   register short *sp2;
        !           433:   register short *send;
        !           434: 
        !           435:   p = (shifts *) allocate((unsigned) (sizeof(shifts) +
        !           436:                        (nshifts - 1) * sizeof(short)));
        !           437: 
        !           438:   p->number = this_state->number;
        !           439:   p->nshifts = nshifts;
        !           440: 
        !           441:   sp1 = shiftset;
        !           442:   sp2 = p->shift;
        !           443:   send = shiftset + nshifts;
        !           444: 
        !           445:   while (sp1 < send)
        !           446:     *sp2++ = *sp1++;
        !           447: 
        !           448:   if (last_shift)
        !           449:     {
        !           450:       last_shift->next = p;
        !           451:       last_shift = p;
        !           452:     }
        !           453:   else
        !           454:     {
        !           455:       first_shift = p;
        !           456:       last_shift = p;
        !           457:     }
        !           458: }
        !           459: 
        !           460: 
        !           461: 
        !           462: save_reductions()
        !           463: {
        !           464:   register short *isp;
        !           465:   register short *rp1;
        !           466:   register short *rp2;
        !           467:   register int item;
        !           468:   register int count;
        !           469:   register reductions *p;
        !           470: 
        !           471:   short *rend;
        !           472: 
        !           473:   count = 0;
        !           474:   for (isp = itemset; isp < itemsetend; isp++)
        !           475:     {
        !           476:       item = ritem[*isp];
        !           477:       if (item < 0)
        !           478:        {
        !           479:          redset[count++] = -item;
        !           480:        }
        !           481:     }
        !           482: 
        !           483:   if (count)
        !           484:     {
        !           485:       p = (reductions *) allocate((unsigned) (sizeof(reductions) +
        !           486:                                        (count - 1) * sizeof(short)));
        !           487: 
        !           488:       p->number = this_state->number;
        !           489:       p->nreds = count;
        !           490: 
        !           491:       rp1 = redset;
        !           492:       rp2 = p->rules;
        !           493:       rend = rp1 + count;
        !           494: 
        !           495:       while (rp1 < rend)
        !           496:        *rp2++ = *rp1++;
        !           497: 
        !           498:       if (last_reduction)
        !           499:        {
        !           500:          last_reduction->next = p;
        !           501:          last_reduction = p;
        !           502:        }
        !           503:       else
        !           504:        {
        !           505:          first_reduction = p;
        !           506:          last_reduction = p;
        !           507:        }
        !           508:     }
        !           509: }
        !           510: 
        !           511: 
        !           512: set_derives()
        !           513: {
        !           514:   register int i, k;
        !           515:   register int lhs;
        !           516:   register short *rules;
        !           517: 
        !           518:   derives = NEW2(nsyms, short *);
        !           519:   rules = NEW2(nvars + nrules, short);
        !           520: 
        !           521:   k = 0;
        !           522:   for (lhs = start_symbol; lhs < nsyms; lhs++)
        !           523:     {
        !           524:       derives[lhs] = rules + k;
        !           525:       for (i = 0; i < nrules; i++)
        !           526:        {
        !           527:          if (rlhs[i] == lhs)
        !           528:            {
        !           529:              rules[k] = i;
        !           530:              k++;
        !           531:            }
        !           532:        }
        !           533:       rules[k] = -1;
        !           534:       k++;
        !           535:     }
        !           536: 
        !           537: #ifdef DEBUG
        !           538:   print_derives();
        !           539: #endif
        !           540: }
        !           541: 
        !           542: free_derives()
        !           543: {
        !           544:   FREE(derives[start_symbol]);
        !           545:   FREE(derives);
        !           546: }
        !           547: 
        !           548: #ifdef DEBUG
        !           549: print_derives()
        !           550: {
        !           551:   register int i;
        !           552:   register short *sp;
        !           553: 
        !           554:   printf("\nDERIVES\n\n");
        !           555: 
        !           556:   for (i = start_symbol; i < nsyms; i++)
        !           557:     {
        !           558:       printf("%s derives ", symbol_name[i]);
        !           559:       for (sp = derives[i]; *sp >= 0; sp++)
        !           560:        {
        !           561:          printf("  %d", *sp);
        !           562:        }
        !           563:       putchar('\n');
        !           564:     }
        !           565: 
        !           566:   putchar('\n');
        !           567: }
        !           568: #endif
        !           569: 
        !           570: 
        !           571: set_nullable()
        !           572: {
        !           573:     register int i, j;
        !           574:     register int empty;
        !           575:     int done;
        !           576: 
        !           577:     nullable = MALLOC(nsyms);
        !           578:     if (nullable == 0) no_space();
        !           579: 
        !           580:     for (i = 0; i < nsyms; ++i)
        !           581:        nullable[i] = 0;
        !           582: 
        !           583:     done = 0;
        !           584:     while (!done)
        !           585:     {
        !           586:        done = 1;
        !           587:        for (i = 1; i < nitems; i++)
        !           588:        {
        !           589:            empty = 1;
        !           590:            while ((j = ritem[i]) >= 0)
        !           591:            {
        !           592:                if (!nullable[j])
        !           593:                    empty = 0;
        !           594:                ++i;
        !           595:            }
        !           596:            if (empty)
        !           597:            {
        !           598:                j = rlhs[-j];
        !           599:                if (!nullable[j])
        !           600:                {
        !           601:                    nullable[j] = 1;
        !           602:                    done = 0;
        !           603:                }
        !           604:            }
        !           605:        }
        !           606:     }
        !           607: 
        !           608: #ifdef DEBUG
        !           609:     for (i = 0; i < nsyms; i++)
        !           610:     {
        !           611:        if (nullable[i])
        !           612:            printf("%s is nullable\n", symbol_name[i]);
        !           613:        else
        !           614:            printf("%s is not nullable\n", symbol_name[i]);
        !           615:     }
        !           616: #endif
        !           617: }
        !           618: 
        !           619: 
        !           620: free_nullable()
        !           621: {
        !           622:   FREE(nullable);
        !           623: }
        !           624: 
        !           625: 
        !           626: lr0()
        !           627: {
        !           628:     set_derives();
        !           629:     set_nullable();
        !           630:     generate_states();
        !           631: }

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