1 /* Closures for Bison
2
3 Copyright (C) 1984, 1989, 2000-2002, 2004-2005, 2007, 2009-2015,
4 2018-2021 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 <https://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
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
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
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 }