src/nullable.c

   1 /* Calculate which nonterminals can expand into the null string for Bison.
   2
   3    Copyright (C) 1984, 1989, 2000-2006, 2009-2015, 2018-2021 Free
   4    Software Foundation, Inc.
   5
   6    This file is part of Bison, the GNU Compiler Compiler.
   7
   8    This program is free software: you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation, either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  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 <config.h>
  27 #include "system.h"
  28
  29 #include "getargs.h"
  30 #include "gram.h"
  31 #include "nullable.h"
  32 #include "reduce.h"
  33 #include "symtab.h"
  34
  35 /* Linked list of rules.  */
  36 typedef struct rule_list
  37 {
  38   struct rule_list *next;
  39   const rule *value;
  40 } rule_list;
  41
  42 bool *nullable = NULL;
  43
  44 static void
  45 nullable_print (FILE *out)
  46 {
  47   fputs ("NULLABLE\n", out);
  48   for (int i = ntokens; i < nsyms; i++)
  49     fprintf (out, "  %s: %s\n", symbols[i]->tag,
  50              nullable[i - ntokens] ? "yes" : "no");
  51   fputs ("\n\n", out);
  52 }
  53
  54 void
  55 nullable_compute (void)
  56 {
  57   nullable = xcalloc (nnterms, sizeof *nullable);
  58
  59   size_t *rcount = xcalloc (nrules, sizeof *rcount);
  60   /* RITEM contains all the rules, including useless productions.
  61      Hence we must allocate room for useless nonterminals too.  */
  62   rule_list **rsets = xcalloc (nnterms, sizeof *rsets);
  63   /* This is said to be more elements than we actually use.
  64      Supposedly NRITEMS - NRULES is enough.  But why take the risk?  */
  65   rule_list *relts = xnmalloc (nritems + nnterms + 1, sizeof *relts);
  66
  67   symbol_number *squeue = xnmalloc (nnterms, sizeof *squeue);
  68   symbol_number *s2 = squeue;
  69   {
  70     rule_list *p = relts;
  71     for (rule_number ruleno = 0; ruleno < nrules; ++ruleno)
  72       if (rules[ruleno].useful)
  73         {
  74           const rule *r = &rules[ruleno];
  75           if (r->rhs[0] >= 0)
  76             {
  77               /* This rule has a non empty RHS. */
  78               bool any_tokens = false;
  79               for (item_number *rp = r->rhs; *rp >= 0; ++rp)
  80                 if (ISTOKEN (*rp))
  81                   any_tokens = true;
  82
  83               /* This rule has only nonterminals: schedule it for the second
  84                  pass.  */
  85               if (!any_tokens)
  86                 for (item_number *rp = r->rhs; *rp >= 0; ++rp)
  87                   {
  88                     rcount[ruleno]++;
  89                     p->next = rsets[*rp - ntokens];
  90                     p->value = r;
  91                     rsets[*rp - ntokens] = p;
  92                     p++;
  93                   }
  94             }
  95           else
  96             {
  97               /* This rule has an empty RHS. */
  98               if (r->useful
  99                   && ! nullable[r->lhs->number - ntokens])
 100                 {
 101                   nullable[r->lhs->number - ntokens] = true;
 102                   *s2++ = r->lhs->number;
 103                 }
 104             }
 105         }
 106   }
 107
 108   symbol_number *s1 = squeue;
 109   while (s1 < s2)
 110     for (rule_list *p = rsets[*s1++ - ntokens]; p; p = p->next)
 111       {
 112         const rule *r = p->value;
 113         if (--rcount[r->number] == 0)
 114           if (r->useful && ! nullable[r->lhs->number - ntokens])
 115             {
 116               nullable[r->lhs->number - ntokens] = true;
 117               *s2++ = r->lhs->number;
 118             }
 119       }
 120
 121   free (squeue);
 122   free (rcount);
 123   free (rsets);
 124   free (relts);
 125
 126   if (trace_flag & trace_sets)
 127     nullable_print (stderr);
 128 }
 129
 130
 131 void
 132 nullable_free (void)
 133 {
 134   free (nullable);
 135 }