1/* Closures for Bison
2
3   Copyright (C) 1984, 1989, 2000, 2001, 2002, 2004, 2005 Free
4   Software Foundation, Inc.
5
6   This file is part of Bison, the GNU Compiler Compiler.
7
8   Bison is free software; you can redistribute it and/or modify it
9   under the terms of the GNU General Public License as published by
10   the Free Software Foundation; either version 2, or (at your option)
11   any later version.
12
13   Bison is distributed in the hope that it will be useful, but
14   WITHOUT ANY WARRANTY; without even the implied warranty of
15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16   General Public License for more details.
17
18   You should have received a copy of the GNU General Public License
19   along with Bison; see the file COPYING.  If not, write to the Free
20   Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21   02110-1301, USA.  */
22
23#include <config.h>
24#include "system.h"
25
26#include <bitset.h>
27#include <bitsetv-print.h>
28#include <bitsetv.h>
29#include <quotearg.h>
30
31#include "closure.h"
32#include "derives.h"
33#include "getargs.h"
34#include "gram.h"
35#include "reader.h"
36#include "symtab.h"
37
38/* NITEMSET is the size of the array ITEMSET.  */
39item_number *itemset;
40size_t nritemset;
41
42static bitset ruleset;
43
44/* internal data.  See comments before set_fderives and set_firsts.  */
45static bitsetv fderives = NULL;
46static bitsetv firsts = NULL;
47
48/* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var.  */
49#define FDERIVES(Var)   fderives[(Var) - ntokens]
50#define   FIRSTS(Var)   firsts[(Var) - ntokens]
51
52
53/*-----------------.
54| Debugging code.  |
55`-----------------*/
56
57static void
58print_closure (char const *title, item_number *array, size_t size)
59{
60  size_t i;
61  fprintf (stderr, "Closure: %s\n", title);
62  for (i = 0; i < size; ++i)
63    {
64      item_number *rp;
65      fprintf (stderr, "  %2d: .", array[i]);
66      for (rp = &ritem[array[i]]; *rp >= 0; ++rp)
67	fprintf (stderr, " %s", symbols[*rp]->tag);
68      fprintf (stderr, "  (rule %d)\n", -*rp - 1);
69    }
70  fputs ("\n\n", stderr);
71}
72
73
74static void
75print_firsts (void)
76{
77  symbol_number i, j;
78
79  fprintf (stderr, "FIRSTS\n");
80  for (i = ntokens; i < nsyms; i++)
81    {
82      bitset_iterator iter;
83      fprintf (stderr, "\t%s firsts\n", symbols[i]->tag);
84      BITSET_FOR_EACH (iter, FIRSTS (i), j, 0)
85	{
86	  fprintf (stderr, "\t\t%s\n",
87		   symbols[j + ntokens]->tag);
88	}
89    }
90  fprintf (stderr, "\n\n");
91}
92
93
94static void
95print_fderives (void)
96{
97  int i;
98  rule_number r;
99
100  fprintf (stderr, "FDERIVES\n");
101  for (i = ntokens; i < nsyms; i++)
102    {
103      bitset_iterator iter;
104      fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
105      BITSET_FOR_EACH (iter, FDERIVES (i), r, 0)
106	{
107	  fprintf (stderr, "\t\t%3d ", r);
108	  rule_rhs_print (&rules[r], stderr);
109	}
110    }
111  fprintf (stderr, "\n\n");
112}
113
114/*------------------------------------------------------------------.
115| Set FIRSTS to be an NVARS array of NVARS bitsets indicating which |
116| items can represent the beginning of the input corresponding to   |
117| which other items.                                                |
118|                                                                   |
119| For example, if some rule expands symbol 5 into the sequence of   |
120| symbols 8 3 20, the symbol 8 can be the beginning of the data for |
121| symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST |
122| (5)) is set.                                                      |
123`------------------------------------------------------------------*/
124
125static void
126set_firsts (void)
127{
128  symbol_number i, j;
129
130  firsts = bitsetv_create (nvars, nvars, BITSET_FIXED);
131
132  for (i = ntokens; i < nsyms; i++)
133    for (j = 0; derives[i - ntokens][j]; ++j)
134      {
135	item_number sym = derives[i - ntokens][j]->rhs[0];
136	if (ISVAR (sym))
137	  bitset_set (FIRSTS (i), sym - ntokens);
138      }
139
140  if (trace_flag & trace_sets)
141    bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts);
142  bitsetv_reflexive_transitive_closure (firsts);
143  if (trace_flag & trace_sets)
144    bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts);
145
146  if (trace_flag & trace_sets)
147    print_firsts ();
148}
149
150/*-------------------------------------------------------------------.
151| Set FDERIVES to an NVARS by NRULES matrix of bits indicating which |
152| rules can help derive the beginning of the data for each           |
153| nonterminal.                                                       |
154|                                                                    |
155| For example, if symbol 5 can be derived as the sequence of symbols |
156| 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then |
157| the [5 - NTOKENS, 4] bit in FDERIVES is set.                       |
158`-------------------------------------------------------------------*/
159
160static void
161set_fderives (void)
162{
163  symbol_number i, j;
164  rule_number k;
165
166  fderives = bitsetv_create (nvars, nrules, BITSET_FIXED);
167
168  set_firsts ();
169
170  for (i = ntokens; i < nsyms; ++i)
171    for (j = ntokens; j < nsyms; ++j)
172      if (bitset_test (FIRSTS (i), j - ntokens))
173	for (k = 0; derives[j - ntokens][k]; ++k)
174	  bitset_set (FDERIVES (i), derives[j - ntokens][k]->number);
175
176  if (trace_flag & trace_sets)
177    print_fderives ();
178
179  bitsetv_free (firsts);
180}
181
182
183
184void
185new_closure (unsigned int n)
186{
187  itemset = xnmalloc (n, sizeof *itemset);
188
189  ruleset = bitset_create (nrules, BITSET_FIXED);
190
191  set_fderives ();
192}
193
194
195
196void
197closure (item_number *core, size_t n)
198{
199  /* Index over CORE. */
200  size_t c;
201
202  /* A bit index over RULESET. */
203  rule_number ruleno;
204
205  bitset_iterator iter;
206
207  if (trace_flag & trace_sets)
208    print_closure ("input", core, n);
209
210  bitset_zero (ruleset);
211
212  for (c = 0; c < n; ++c)
213    if (ISVAR (ritem[core[c]]))
214      bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]]));
215
216  nritemset = 0;
217  c = 0;
218  BITSET_FOR_EACH (iter, ruleset, ruleno, 0)
219    {
220      item_number itemno = rules[ruleno].rhs - ritem;
221      while (c < n && core[c] < itemno)
222	{
223	  itemset[nritemset] = core[c];
224	  nritemset++;
225	  c++;
226	}
227      itemset[nritemset] = itemno;
228      nritemset++;
229    };
230
231  while (c < n)
232    {
233      itemset[nritemset] = core[c];
234      nritemset++;
235      c++;
236    }
237
238  if (trace_flag & trace_sets)
239    print_closure ("output", itemset, nritemset);
240}
241
242
243void
244free_closure (void)
245{
246  free (itemset);
247  bitset_free (ruleset);
248  bitsetv_free (fderives);
249}
250