Return to closure.c CVS log

Up to [Apple XNU] / GNUtools / bison

Annotation of GNUtools/bison/closure.c, revision 1.1

1.1     ! root        1: /* Subroutines for bison
        !             2:    Copyright (C) 1984, 1989 Free Software Foundation, Inc.
        !             3: 
        !             4: This file is part of Bison, the GNU Compiler Compiler.
        !             5: 
        !             6: Bison is free software; you can redistribute it and/or modify
        !             7: it under the terms of the GNU General Public License as published by
        !             8: the Free Software Foundation; either version 2, or (at your option)
        !             9: any later version.
        !            10: 
        !            11: Bison is distributed in the hope that it will be useful,
        !            12: but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            14: GNU General Public License for more details.
        !            15: 
        !            16: You should have received a copy of the GNU General Public License
        !            17: along with Bison; see the file COPYING.  If not, write to
        !            18: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
        !            19: 
        !            20: 
        !            21: /* subroutines of file LR0.c.
        !            22: 
        !            23: Entry points:
        !            24: 
        !            25:   closure (items, n)
        !            26: 
        !            27: Given a vector of item numbers items, of length n,
        !            28: set up ruleset and itemset to indicate what rules could be run
        !            29: and which items could be accepted when those items are the active ones.
        !            30: 
        !            31: ruleset contains a bit for each rule.  closure sets the bits
        !            32: for all rules which could potentially describe the next input to be read.
        !            33: 
        !            34: itemset is a vector of item numbers; itemsetend points to just beyond the end
        !            35:  of the part of it that is significant.
        !            36: closure places there the indices of all items which represent units of
        !            37: input that could arrive next.
        !            38: 
        !            39:   initialize_closure (n)
        !            40: 
        !            41: Allocates the itemset and ruleset vectors,
        !            42: and precomputes useful data so that closure can be called.
        !            43: n is the number of elements to allocate for itemset.
        !            44: 
        !            45:   finalize_closure ()
        !            46: 
        !            47: Frees itemset, ruleset and internal data.
        !            48: 
        !            49: */
        !            50: 
        !            51: #include <stdio.h>
        !            52: #include "system.h"
        !            53: #include "machine.h"
        !            54: #include "new.h"
        !            55: #include "gram.h"
        !            56: 
        !            57: 
        !            58: extern short **derives;
        !            59: extern char **tags;
        !            60: 
        !            61: void set_fderives();
        !            62: void set_firsts();
        !            63: 
        !            64: extern void RTC();
        !            65: 
        !            66: short *itemset;
        !            67: short *itemsetend;
        !            68: static unsigned *ruleset;
        !            69: 
        !            70: /* internal data.  See comments before set_fderives and set_firsts.  */
        !            71: static unsigned *fderives;
        !            72: static unsigned *firsts;
        !            73: 
        !            74: /* number of words required to hold a bit for each rule */
        !            75: static int rulesetsize;
        !            76: 
        !            77: /* number of words required to hold a bit for each variable */
        !            78: static int varsetsize;
        !            79: 
        !            80: 
        !            81: void
        !            82: initialize_closure(n)
        !            83: int n;
        !            84: {
        !            85:   itemset = NEW2(n, short);
        !            86: 
        !            87:   rulesetsize = WORDSIZE(nrules + 1);
        !            88:   ruleset = NEW2(rulesetsize, unsigned);
        !            89: 
        !            90:   set_fderives();
        !            91: }
        !            92: 
        !            93: 
        !            94: 
        !            95: /* set fderives to an nvars by nrules matrix of bits
        !            96:    indicating which rules can help derive the beginning of the data
        !            97:    for each nonterminal.  For example, if symbol 5 can be derived as
        !            98:    the sequence of symbols 8 3 20, and one of the rules for deriving
        !            99:    symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set.  */
        !           100: void
        !           101: set_fderives()
        !           102: {
        !           103:   register unsigned *rrow;
        !           104:   register unsigned *vrow;
        !           105:   register int j;
        !           106:   register unsigned cword;
        !           107:   register short *rp;
        !           108:   register int b;
        !           109: 
        !           110:   int ruleno;
        !           111:   int i;
        !           112: 
        !           113:   fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
        !           114: 
        !           115:   set_firsts();
        !           116: 
        !           117:   rrow = fderives + ntokens * rulesetsize;
        !           118: 
        !           119:   for (i = ntokens; i < nsyms; i++)
        !           120:     {
        !           121:       vrow = firsts + ((i - ntokens) * varsetsize);
        !           122:       cword = *vrow++;
        !           123:       b = 0;
        !           124:       for (j = ntokens; j < nsyms; j++)
        !           125:        {
        !           126:          if (cword & (1 << b))
        !           127:            {
        !           128:              rp = derives[j];
        !           129:              while ((ruleno = *rp++) > 0)
        !           130:                {
        !           131:                  SETBIT(rrow, ruleno);
        !           132:                }
        !           133:            }
        !           134: 
        !           135:          b++;
        !           136:          if (b >= BITS_PER_WORD && j + 1 < nsyms)
        !           137:            {
        !           138:              cword = *vrow++;
        !           139:              b = 0;
        !           140:            }
        !           141:        }
        !           142: 
        !           143:       rrow += rulesetsize;
        !           144:     }
        !           145: 
        !           146: #ifdef DEBUG
        !           147:   print_fderives();
        !           148: #endif
        !           149: 
        !           150:   FREE(firsts);
        !           151: }
        !           152: 
        !           153: 
        !           154: 
        !           155: /* set firsts to be an nvars by nvars bit matrix indicating which items
        !           156:    can represent the beginning of the input corresponding to which other items.
        !           157:    For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20,
        !           158:    the symbol 8 can be the beginning of the data for symbol 5,
        !           159:    so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */
        !           160: void
        !           161: set_firsts()
        !           162: {
        !           163:   register unsigned *row;
        !           164: /*   register int done; JF unused */
        !           165:   register int symbol;
        !           166:   register short *sp;
        !           167:   register int rowsize;
        !           168: 
        !           169:   int i;
        !           170: 
        !           171:   varsetsize = rowsize = WORDSIZE(nvars);
        !           172: 
        !           173:   firsts = NEW2(nvars * rowsize, unsigned);
        !           174: 
        !           175:   row = firsts;
        !           176:   for (i = ntokens; i < nsyms; i++)
        !           177:     {
        !           178:       sp = derives[i];
        !           179:       while (*sp >= 0)
        !           180:        {
        !           181:          symbol = ritem[rrhs[*sp++]];
        !           182:          if (ISVAR(symbol))
        !           183:            {
        !           184:              symbol -= ntokens;
        !           185:              SETBIT(row, symbol);
        !           186:            }
        !           187:        }
        !           188: 
        !           189:       row += rowsize;
        !           190:     }
        !           191: 
        !           192:   RTC(firsts, nvars);
        !           193: 
        !           194: #ifdef DEBUG
        !           195:   print_firsts();
        !           196: #endif
        !           197: }
        !           198: 
        !           199: 
        !           200: void
        !           201: closure(core, n)
        !           202: short *core;
        !           203: int n;
        !           204: {
        !           205:   register int ruleno;
        !           206:   register unsigned word;
        !           207:   register short *csp;
        !           208:   register unsigned *dsp;
        !           209:   register unsigned *rsp;
        !           210: 
        !           211:   short *csend;
        !           212:   unsigned *rsend;
        !           213:   int symbol;
        !           214:   int itemno;
        !           215: 
        !           216:   rsp = ruleset;
        !           217:   rsend = ruleset + rulesetsize;
        !           218:   csend = core + n;
        !           219: 
        !           220:   if (n == 0)
        !           221:     {
        !           222:       dsp = fderives + start_symbol * rulesetsize;
        !           223:       while (rsp < rsend)
        !           224:        *rsp++ = *dsp++;
        !           225:     }
        !           226:   else
        !           227:     {
        !           228:       while (rsp < rsend)
        !           229:        *rsp++ = 0;
        !           230: 
        !           231:       csp = core;
        !           232:       while (csp < csend)
        !           233:        {
        !           234:          symbol = ritem[*csp++];
        !           235:          if (ISVAR(symbol))
        !           236:            {
        !           237:              dsp = fderives + symbol * rulesetsize;
        !           238:              rsp = ruleset;
        !           239:              while (rsp < rsend)
        !           240:                *rsp++ |= *dsp++;
        !           241:            }
        !           242:        }
        !           243:     }
        !           244: 
        !           245:   ruleno = 0;
        !           246:   itemsetend = itemset;
        !           247:   csp = core;
        !           248:   rsp = ruleset;
        !           249:   while (rsp < rsend)
        !           250:     {
        !           251:       word = *rsp++;
        !           252:       if (word == 0)
        !           253:        {
        !           254:          ruleno += BITS_PER_WORD;
        !           255:        }
        !           256:       else
        !           257:        {
        !           258:          register int b;
        !           259: 
        !           260:          for (b = 0; b < BITS_PER_WORD; b++)
        !           261:            {
        !           262:              if (word & (1 << b))
        !           263:                {
        !           264:                  itemno = rrhs[ruleno];
        !           265:                  while (csp < csend && *csp < itemno)
        !           266:                    *itemsetend++ = *csp++;
        !           267:                  *itemsetend++ = itemno;
        !           268:                }
        !           269: 
        !           270:              ruleno++;
        !           271:            }
        !           272:        }
        !           273:     }
        !           274: 
        !           275:   while (csp < csend)
        !           276:     *itemsetend++ = *csp++;
        !           277: 
        !           278: #ifdef DEBUG
        !           279:   print_closure(n);
        !           280: #endif
        !           281: }
        !           282: 
        !           283: 
        !           284: void
        !           285: finalize_closure()
        !           286: {
        !           287:   FREE(itemset);
        !           288:   FREE(ruleset);
        !           289:   FREE(fderives + ntokens * rulesetsize);
        !           290: }
        !           291: 
        !           292: 
        !           293: 
        !           294: #ifdef DEBUG
        !           295: 
        !           296: print_closure(n)
        !           297: int n;
        !           298: {
        !           299:   register short *isp;
        !           300: 
        !           301:   printf("\n\nn = %d\n\n", n);
        !           302:   for (isp = itemset; isp < itemsetend; isp++)
        !           303:     printf("   %d\n", *isp);
        !           304: }
        !           305: 
        !           306: 
        !           307: 
        !           308: print_firsts()
        !           309: {
        !           310:   register int i;
        !           311:   register int j;
        !           312:   register unsigned *rowp;
        !           313: 
        !           314:   printf("\n\n\nFIRSTS\n\n");
        !           315: 
        !           316:   for (i = ntokens; i < nsyms; i++)
        !           317:     {
        !           318:       printf("\n\n%s firsts\n\n", tags[i]);
        !           319: 
        !           320:       rowp = firsts + ((i - ntokens) * varsetsize);
        !           321: 
        !           322:       for (j = 0; j < nvars; j++)
        !           323:        if (BITISSET (rowp, j))
        !           324:          printf("   %s\n", tags[j + ntokens]);
        !           325:     }
        !           326: }
        !           327: 
        !           328: 
        !           329: 
        !           330: print_fderives()
        !           331: {
        !           332:   register int i;
        !           333:   register int j;
        !           334:   register unsigned *rp;
        !           335: 
        !           336:   printf("\n\n\nFDERIVES\n");
        !           337: 
        !           338:   for (i = ntokens; i < nsyms; i++)
        !           339:     {
        !           340:       printf("\n\n%s derives\n\n", tags[i]);
        !           341:       rp = fderives + i * rulesetsize;
        !           342: 
        !           343:       for (j = 0; j <= nrules; j++)
        !           344:        if (BITISSET (rp, j))
        !           345:          printf("   %d\n", j);
        !           346:     }
        !           347: 
        !           348:   fflush(stdout);
        !           349: }
        !           350: 
        !           351: #endif

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