src/nullable.c

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