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