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