src/closure.c

   1 /* Closures for Bison
   2
   3    Copyright (C) 1984, 1989, 2000-2002, 2004-2005, 2007, 2009-2015,
   4    2018-2020 Free 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 <http://www.gnu.org/licenses/>.  */
  20
  21 #include <config.h>
  22 #include "system.h"
  23
  24 #include <bitset.h>
  25 #include <bitsetv.h>
  26
  27 #include "closure.h"
  28 #include "derives.h"
  29 #include "getargs.h"
  30 #include "gram.h"
  31 #include "reader.h"
  32 #include "symtab.h"
  33
  34 /* NITEMSET is the size of the array ITEMSET.  */
  35 item_index *itemset;
  36 size_t nitemset;
  37
  38 /* RULESET contains a bit for each rule.  CLOSURE sets the bits for
  39    all rules which could potentially describe the next input to be
  40    read.  */
  41 static bitset ruleset;
  42
  43 /* internal data.  See comments before set_fderives and set_firsts.  */
  44 static bitsetv fderives = NULL;
  45 static bitsetv firsts = NULL;
  46
  47 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */
  48 #define FDERIVES(Var)   fderives[(Var) - ntokens]
  49 #define FIRSTS(Var)   firsts[(Var) - ntokens]
  50 \f
  51
  52 /*-----------------.
  53 | Debugging code.  |
  54 `-----------------*/
  55
  56 static void
  57 closure_print (char const *title, item_index const *array, size_t size)
  58 {
  59   fprintf (stderr, "Closure: %s\n", title);
  60   for (size_t i = 0; i < size; ++i)
  61     {
  62       fprintf (stderr, "  %2d: .", array[i]);
  63       item_number *rp;
  64       for (rp = &ritem[array[i]]; 0 <= *rp; ++rp)
  65         fprintf (stderr, " %s", symbols[*rp]->tag);
  66       fprintf (stderr, "  (rule %d)\n", item_number_as_rule_number (*rp));
  67     }
  68   fputs ("\n\n", stderr);
  69 }
  70
  71
  72 static void
  73 print_firsts (void)
  74 {
  75   fprintf (stderr, "FIRSTS\n");
  76   for (symbol_number i = ntokens; i < nsyms; ++i)
  77     {
  78       fprintf (stderr, "  %s firsts\n", symbols[i]->tag);
  79       bitset_iterator iter;
  80       symbol_number j;
  81       BITSET_FOR_EACH (iter, FIRSTS (i), j, 0)
  82         fprintf (stderr, "    %s\n", symbols[j + ntokens]->tag);
  83     }
  84   fprintf (stderr, "\n\n");
  85 }
  86
  87
  88 static void
  89 print_fderives (void)
  90 {
  91   fprintf (stderr, "FDERIVES\n");
  92   for (symbol_number i = ntokens; i < nsyms; ++i)
  93     {
  94       fprintf (stderr, "  %s derives\n", symbols[i]->tag);
  95       bitset_iterator iter;
  96       rule_number r;
  97       BITSET_FOR_EACH (iter, FDERIVES (i), r, 0)
  98         {
  99           fprintf (stderr, "    %3d ", r);
 100           rule_rhs_print (&rules[r], stderr);
 101           fprintf (stderr, "\n");
 102         }
 103     }
 104   fprintf (stderr, "\n\n");
 105 }
 106 \f
 107 /*-------------------------------------------------------------------.
 108 | Set FIRSTS to be an NNTERMS array of NNTERMS bitsets indicating    |
 109 | which items can represent the beginning of the input corresponding |
 110 | to which other items.                                              |
 111 |                                                                    |
 112 | For example, if some rule expands symbol 5 into the sequence of    |
 113 | symbols 8 3 20, the symbol 8 can be the beginning of the data for  |
 114 | symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST  |
 115 | (5)) is set.                                                       |
 116 `-------------------------------------------------------------------*/
 117
 118 static void
 119 set_firsts (void)
 120 {
 121   firsts = bitsetv_create (nnterms, nnterms, BITSET_FIXED);
 122
 123   for (symbol_number i = ntokens; i < nsyms; ++i)
 124     for (symbol_number j = 0; derives[i - ntokens][j]; ++j)
 125       {
 126         item_number sym = derives[i - ntokens][j]->rhs[0];
 127         if (ISVAR (sym))
 128           bitset_set (FIRSTS (i), sym - ntokens);
 129       }
 130
 131   if (trace_flag & trace_sets)
 132     bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts);
 133   bitsetv_reflexive_transitive_closure (firsts);
 134   if (trace_flag & trace_sets)
 135     bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts);
 136
 137   if (trace_flag & trace_sets)
 138     print_firsts ();
 139 }
 140
 141 /*-------------------------------------------------------------------.
 142 | Set FDERIVES to an NNTERMS by NRULES matrix of bits indicating     |
 143 | which rules can help derive the beginning of the data for each     |
 144 | nonterminal.                                                       |
 145 |                                                                    |
 146 | For example, if symbol 5 can be derived as the sequence of symbols |
 147 | 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then |
 148 | the [5 - NTOKENS, 4] bit in FDERIVES is set.                       |
 149 `-------------------------------------------------------------------*/
 150
 151 static void
 152 set_fderives (void)
 153 {
 154   fderives = bitsetv_create (nnterms, nrules, BITSET_FIXED);
 155
 156   set_firsts ();
 157
 158   for (symbol_number i = ntokens; i < nsyms; ++i)
 159     for (symbol_number j = ntokens; j < nsyms; ++j)
 160       if (bitset_test (FIRSTS (i), j - ntokens))
 161         for (rule_number k = 0; derives[j - ntokens][k]; ++k)
 162           bitset_set (FDERIVES (i), derives[j - ntokens][k]->number);
 163
 164   if (trace_flag & trace_sets)
 165     print_fderives ();
 166
 167   bitsetv_free (firsts);
 168 }
 169
 170 \f
 171
 172 void
 173 closure_new (int n)
 174 {
 175   itemset = xnmalloc (n, sizeof *itemset);
 176
 177   ruleset = bitset_create (nrules, BITSET_FIXED);
 178
 179   set_fderives ();
 180 }
 181
 182
 183
 184 void
 185 closure (item_index const *core, size_t n)
 186 {
 187   if (trace_flag & trace_closure)
 188     closure_print ("input", core, n);
 189
 190   bitset_zero (ruleset);
 191
 192   for (size_t c = 0; c < n; ++c)
 193     if (ISVAR (ritem[core[c]]))
 194       bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]]));
 195
 196   /* core is sorted on item index in ritem, which is sorted on rule number.
 197      Compute itemset with the same sort.  */
 198   nitemset = 0;
 199   size_t c = 0;
 200
 201   /* A bit index over RULESET. */
 202   rule_number ruleno;
 203   bitset_iterator iter;
 204   BITSET_FOR_EACH (iter, ruleset, ruleno, 0)
 205     {
 206       item_index itemno = rules[ruleno].rhs - ritem;
 207       while (c < n && core[c] < itemno)
 208         {
 209           itemset[nitemset] = core[c];
 210           nitemset++;
 211           c++;
 212         }
 213       itemset[nitemset] = itemno;
 214       nitemset++;
 215     };
 216
 217   while (c < n)
 218     {
 219       itemset[nitemset] = core[c];
 220       nitemset++;
 221       c++;
 222     }
 223
 224   if (trace_flag & trace_closure)
 225     closure_print ("output", itemset, nitemset);
 226 }
 227
 228
 229 void
 230 closure_free (void)
 231 {
 232   free (itemset);
 233   bitset_free (ruleset);
 234   bitsetv_free (fderives);
 235 }