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. */
39 item_number *itemset;
40 size_t nritemset;
41
42 static bitset ruleset;
43
44 /* internal data. See comments before set_fderives and set_firsts. */
45 static bitsetv fderives = NULL;
46 static 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
57 static void
print_closure(char const * title,item_number * array,size_t size)58 print_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
74 static void
print_firsts(void)75 print_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
94 static void
print_fderives(void)95 print_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
125 static void
set_firsts(void)126 set_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
160 static void
set_fderives(void)161 set_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
184 void
new_closure(unsigned int n)185 new_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
196 void
closure(item_number * core,size_t n)197 closure (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
243 void
free_closure(void)244 free_closure (void)
245 {
246 free (itemset);
247 bitset_free (ruleset);
248 bitsetv_free (fderives);
249 }
250