1/* Closures for Bison
2
3 Copyright (C) 1984, 1989, 2000-2002, 2004-2005, 2007, 2009-2015,
4 2018-2019 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. */
35item_number *itemset;
36size_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. */
41static bitset ruleset;
42
43/* internal data. See comments before set_fderives and set_firsts. */
44static bitsetv fderives = NULL;
45static 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
51
52/*-----------------.
53| Debugging code. |
54`-----------------*/
55
56static void
57closure_print (char const *title, item_number 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]]; *rp >= 0; ++rp)
65 fprintf (stderr, " %s", symbols[*rp]->tag);
66 fprintf (stderr, " (rule %d)\n", -*rp - 1);
67 }
68 fputs ("\n\n", stderr);
69}
70
71
72static void
73print_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
88static void
89print_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
107/*------------------------------------------------------------------.
108| Set FIRSTS to be an NVARS array of NVARS bitsets indicating which |
109| items can represent the beginning of the input corresponding to |
110| 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
118static void
119set_firsts (void)
120{
121 firsts = bitsetv_create (nvars, nvars, 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 NVARS by NRULES matrix of bits indicating which |
143| 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
151static void
152set_fderives (void)
153{
154 fderives = bitsetv_create (nvars, 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
171
172void
173closure_new (unsigned n)
174{
175 itemset = xnmalloc (n, sizeof *itemset);
176
177 ruleset = bitset_create (nrules, BITSET_FIXED);
178
179 set_fderives ();
180}
181
182
183
184void
185closure (item_number 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_number 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
229void
230closure_free (void)
231{
232 free (itemset);
233 bitset_free (ruleset);
234 bitsetv_free (fderives);
235}
236