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. */ |
35 | item_number *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_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 | |
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 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 | |
118 | static void |
119 | set_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 | |
151 | static void |
152 | set_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 | |
172 | void |
173 | closure_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 | |
184 | void |
185 | closure (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 | |
229 | void |
230 | closure_free (void) |
231 | { |
232 | free (itemset); |
233 | bitset_free (ruleset); |
234 | bitsetv_free (fderives); |
235 | } |
236 | |