Return to nullable.c CVS log

Up to [Apple XNU] / GNUtools / bison

Annotation of GNUtools/bison/nullable.c, revision 1.1.1.1

1.1       root        1: /* Part of the bison parser generator,
                      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: /* set up nullable, a vector saying which nonterminals can expand into the null string.
                     22:    nullable[i - ntokens] is nonzero if symbol i can do so.  */
                     23: 
                     24: #include <stdio.h>
                     25: #include "system.h"
                     26: #include "types.h"
                     27: #include "gram.h"
                     28: #include "new.h"
                     29: 
                     30: 
                     31: char *nullable;
                     32: 
                     33: 
                     34: void
                     35: set_nullable()
                     36: {
                     37:   register short *r;
                     38:   register short *s1;
                     39:   register short *s2;
                     40:   register int ruleno;
                     41:   register int symbol;
                     42:   register shorts *p;
                     43: 
                     44:   short *squeue;
                     45:   short *rcount;
                     46:   shorts **rsets;
                     47:   shorts *relts;
                     48:   char any_tokens;
                     49:   short *r1;
                     50: 
                     51: #ifdef TRACE
                     52:   fprintf(stderr, "Entering set_nullable");
                     53: #endif
                     54: 
                     55:   nullable = NEW2(nvars, char) - ntokens;
                     56: 
                     57:   squeue = NEW2(nvars, short);
                     58:   s1 = s2 = squeue;
                     59: 
                     60:   rcount = NEW2(nrules + 1, short);
                     61:   rsets = NEW2(nvars, shorts *) - ntokens;
                     62:   /* This is said to be more elements than we actually use.
                     63:      Supposedly nitems - nrules is enough.
                     64:      But why take the risk?  */
                     65:   relts = NEW2(nitems + nvars + 1, shorts);
                     66:   p = relts;
                     67: 
                     68:   r = ritem;
                     69:   while (*r)
                     70:     {
                     71:       if (*r < 0)
                     72:        {
                     73:          symbol = rlhs[-(*r++)];
                     74:          if (symbol >= 0 && !nullable[symbol])
                     75:            {
                     76:              nullable[symbol] = 1;
                     77:              *s2++ = symbol;
                     78:            }
                     79:        }
                     80:       else
                     81:        {
                     82:          r1 = r;
                     83:          any_tokens = 0;
                     84:          for (symbol = *r++; symbol > 0; symbol = *r++)
                     85:            {
                     86:              if (ISTOKEN(symbol))
                     87:                any_tokens = 1;
                     88:            }
                     89: 
                     90:          if (!any_tokens)
                     91:            {
                     92:              ruleno = -symbol;
                     93:              r = r1;
                     94:              for (symbol = *r++; symbol > 0; symbol = *r++)
                     95:                {
                     96:                  rcount[ruleno]++;
                     97:                  p->next = rsets[symbol];
                     98:                  p->value = ruleno;
                     99:                  rsets[symbol] = p;
                    100:                  p++;
                    101:                }
                    102:            }
                    103:        }
                    104:     }
                    105: 
                    106:   while (s1 < s2)
                    107:     {
                    108:       p = rsets[*s1++];
                    109:       while (p)
                    110:        {
                    111:          ruleno = p->value;
                    112:          p = p->next;
                    113:          if (--rcount[ruleno] == 0)
                    114:            {
                    115:              symbol = rlhs[ruleno];
                    116:              if (symbol >= 0 && !nullable[symbol])
                    117:                {
                    118:                  nullable[symbol] = 1;
                    119:                  *s2++ = symbol;
                    120:                }
                    121:            }
                    122:        }
                    123:     }
                    124: 
                    125:   FREE(squeue);
                    126:   FREE(rcount);
                    127:   FREE(rsets + ntokens);
                    128:   FREE(relts);
                    129: }
                    130: 
                    131: 
                    132: void
                    133: free_nullable()
                    134: {
                    135:   FREE(nullable + ntokens);
                    136: }

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