src/nullable.c

   1 /* Part of the bison parser generator,
   2    Copyright (C) 1984, 1989, 2000, 2001, 2002 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
  23    the null string.  NULLABLE[I - NTOKENS] is nonzero if symbol I can
  24    do so.  */
  25
  26 #include "system.h"
  27
  28 #include "getargs.h"
  29 #include "gram.h"
  30 #include "nullable.h"
  31 #include "reduce.h"
  32 #include "symtab.h"
  33
  34 /* Linked list of rules.  */
  35 typedef struct rule_list
  36 {
  37   struct rule_list *next;
  38   rule *value;
  39 } rule_list;
  40
  41 bool *nullable = NULL;
  42
  43 static void
  44 nullable_print (FILE *out)
  45 {
  46   int i;
  47   fputs ("NULLABLE\n", out);
  48   for (i = ntokens; i < nsyms; i++)
  49     fprintf (out, "\t%s: %s\n", symbols[i]->tag, nullable[i] ? "yes" : "no");
  50   fputs ("\n\n", out);
  51 }
  52
  53 void
  54 nullable_compute (void)
  55 {
  56   rule_number ruleno;
  57   symbol_number *s1;
  58   symbol_number *s2;
  59   rule_list *p;
  60
  61   symbol_number *squeue = XCALLOC (symbol_number, nvars);
  62   short *rcount = XCALLOC (short, nrules);
  63   /* RITEM contains all the rules, including useless productions.
  64      Hence we must allocate room for useless nonterminals too.  */
  65   rule_list **rsets = XCALLOC (rule_list *, nvars) - ntokens;
  66   /* This is said to be more elements than we actually use.
  67      Supposedly NRITEMS - NRULES is enough.  But why take the risk?  */
  68   rule_list *relts = XCALLOC (rule_list, nritems + nvars + 1);
  69
  70   nullable = XCALLOC (bool, nvars) - ntokens;
  71
  72   s1 = s2 = squeue;
  73   p = relts;
  74
  75   for (ruleno = 0; ruleno < nrules; ++ruleno)
  76     if (rules[ruleno].useful)
  77       {
  78         rule *rules_ruleno = &rules[ruleno];
  79         if (rules_ruleno->rhs[0] >= 0)
  80           {
  81             /* This rule has a non empty RHS. */
  82             item_number *r = NULL;
  83             int any_tokens = 0;
  84             for (r = rules_ruleno->rhs; *r >= 0; ++r)
  85               if (ISTOKEN (*r))
  86                 any_tokens = 1;
  87
  88             /* This rule has only nonterminals: schedule it for the second
  89                pass.  */
  90             if (!any_tokens)
  91               for (r = rules_ruleno->rhs; *r >= 0; ++r)
  92                 {
  93                   rcount[ruleno]++;
  94                   p->next = rsets[*r];
  95                   p->value = rules_ruleno;
  96                   rsets[*r] = p;
  97                   p++;
  98                 }
  99           }
 100         else
 101           {
 102             /* This rule has an empty RHS. */
 103             if (item_number_as_rule_number (rules_ruleno->rhs[0]) != ruleno)
 104               abort ();
 105             if (rules_ruleno->useful && !nullable[rules_ruleno->lhs->number])
 106               {
 107                 nullable[rules_ruleno->lhs->number] = 1;
 108                 *s2++ = rules_ruleno->lhs->number;
 109               }
 110           }
 111       }
 112
 113   while (s1 < s2)
 114     for (p = rsets[*s1++]; p; p = p->next)
 115       {
 116         rule *r = p->value;
 117         if (--rcount[r->number] == 0)
 118           if (r->useful && !nullable[r->lhs->number])
 119             {
 120               nullable[r->lhs->number] = 1;
 121               *s2++ = r->lhs->number;
 122             }
 123       }
 124
 125   XFREE (squeue);
 126   XFREE (rcount);
 127   XFREE (rsets + ntokens);
 128   XFREE (relts);
 129
 130   if (trace_flag & trace_sets)
 131     nullable_print (stderr);
 132 }
 133
 134
 135 void
 136 nullable_free (void)
 137 {
 138   XFREE (nullable + ntokens);
 139 }