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