]> git.saurik.com Git - bison.git/blame - src/closure.c
build: fix VPATH issue
[bison.git] / src / closure.c
CommitLineData
c7bd07f7
PE
1/* Closures for Bison
2
34136e65 3 Copyright (C) 1984, 1989, 2000-2002, 2004-2005, 2007, 2009-2012 Free
575619af 4 Software Foundation, Inc.
d0fb370f 5
8dc26b76 6 This file is part of Bison, the GNU Compiler Compiler.
d0fb370f 7
f16b0819
PE
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.
d0fb370f 12
f16b0819
PE
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.
d0fb370f 17
8dc26b76 18 You should have received a copy of the GNU General Public License
f16b0819 19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
d0fb370f 20
2cec9080 21#include <config.h>
d0fb370f 22#include "system.h"
c7bd07f7
PE
23
24#include <bitset.h>
25#include <bitsetv-print.h>
26#include <bitsetv.h>
c7bd07f7
PE
27
28#include "closure.h"
29#include "derives.h"
9bfe901c 30#include "getargs.h"
d0fb370f 31#include "gram.h"
2c5f66ed 32#include "reader.h"
c7bd07f7 33#include "symtab.h"
d0fb370f 34
b2872512 35/* NITEMSET is the size of the array ITEMSET. */
c7bd07f7 36item_number *itemset;
b09f4f48 37size_t nitemset;
fb908786 38
dfdb1797 39static bitset ruleset;
d0fb370f
RS
40
41/* internal data. See comments before set_fderives and set_firsts. */
914feea9
AD
42static bitsetv fderives = NULL;
43static bitsetv firsts = NULL;
d0fb370f 44
03ec521c 45/* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var. */
7086e707 46#define FDERIVES(Var) fderives[(Var) - ntokens]
a99ec53e 47#define FIRSTS(Var) firsts[(Var) - ntokens]
2fa6973e 48\f
d0fb370f 49
2fa6973e
AD
50/*-----------------.
51| Debugging code. |
52`-----------------*/
d0fb370f 53
2fa6973e 54static void
510c8497 55print_closure (char const *title, item_number const *array, size_t size)
2fa6973e 56{
23cbcc6c 57 size_t i;
427c0dda 58 fprintf (stderr, "Closure: %s\n", title);
23cbcc6c
AD
59 for (i = 0; i < size; ++i)
60 {
c7bd07f7 61 item_number *rp;
23cbcc6c 62 fprintf (stderr, " %2d: .", array[i]);
75142d45 63 for (rp = &ritem[array[i]]; *rp >= 0; ++rp)
e9690142 64 fprintf (stderr, " %s", symbols[*rp]->tag);
427c0dda 65 fprintf (stderr, " (rule %d)\n", -*rp - 1);
23cbcc6c
AD
66 }
67 fputs ("\n\n", stderr);
2fa6973e
AD
68}
69
70
71static void
72print_firsts (void)
d0fb370f 73{
c7bd07f7 74 symbol_number i, j;
2fa6973e 75
2f4f028d 76 fprintf (stderr, "FIRSTS\n");
2fa6973e
AD
77 for (i = ntokens; i < nsyms; i++)
78 {
613f5e1a 79 bitset_iterator iter;
5cd907c4 80 fprintf (stderr, " %s firsts\n", symbols[i]->tag);
613f5e1a 81 BITSET_FOR_EACH (iter, FIRSTS (i), j, 0)
5cd907c4 82 fprintf (stderr, " %s\n", symbols[j + ntokens]->tag);
2fa6973e 83 }
2f4f028d 84 fprintf (stderr, "\n\n");
d0fb370f
RS
85}
86
87
2fa6973e
AD
88static void
89print_fderives (void)
90{
9222837b 91 int i;
c7bd07f7 92 rule_number r;
2fa6973e 93
2f4f028d 94 fprintf (stderr, "FDERIVES\n");
2fa6973e
AD
95 for (i = ntokens; i < nsyms; i++)
96 {
613f5e1a 97 bitset_iterator iter;
5cd907c4 98 fprintf (stderr, " %s derives\n", symbols[i]->tag);
613f5e1a 99 BITSET_FOR_EACH (iter, FDERIVES (i), r, 0)
e9690142 100 {
5cd907c4 101 fprintf (stderr, " %3d ", r);
e9690142 102 rule_rhs_print (&rules[r], stderr);
3e153163 103 fprintf (stderr, "\n");
e9690142 104 }
2fa6973e 105 }
2f4f028d 106 fprintf (stderr, "\n\n");
2fa6973e 107}
2fa6973e 108\f
d8a0245c
AD
109/*------------------------------------------------------------------.
110| Set FIRSTS to be an NVARS array of NVARS bitsets indicating which |
111| items can represent the beginning of the input corresponding to |
112| which other items. |
113| |
114| For example, if some rule expands symbol 5 into the sequence of |
115| symbols 8 3 20, the symbol 8 can be the beginning of the data for |
116| symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST |
117| (5)) is set. |
118`------------------------------------------------------------------*/
2fa6973e
AD
119
120static void
121set_firsts (void)
122{
c7bd07f7 123 symbol_number i, j;
2fa6973e 124
914feea9
AD
125 firsts = bitsetv_create (nvars, nvars, BITSET_FIXED);
126
2fa6973e 127 for (i = ntokens; i < nsyms; i++)
bb7c2bc6 128 for (j = 0; derives[i - ntokens][j]; ++j)
914feea9 129 {
e9690142
JD
130 item_number sym = derives[i - ntokens][j]->rhs[0];
131 if (ISVAR (sym))
132 bitset_set (FIRSTS (i), sym - ntokens);
914feea9 133 }
2fa6973e 134
273a74fa 135 if (trace_flag & trace_sets)
427c0dda 136 bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts);
65ccf9fc 137 bitsetv_reflexive_transitive_closure (firsts);
273a74fa 138 if (trace_flag & trace_sets)
427c0dda 139 bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts);
2fa6973e 140
273a74fa 141 if (trace_flag & trace_sets)
9bfe901c 142 print_firsts ();
2fa6973e
AD
143}
144
145/*-------------------------------------------------------------------.
146| Set FDERIVES to an NVARS by NRULES matrix of bits indicating which |
147| rules can help derive the beginning of the data for each |
148| nonterminal. |
149| |
150| For example, if symbol 5 can be derived as the sequence of symbols |
151| 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then |
152| the [5 - NTOKENS, 4] bit in FDERIVES is set. |
153`-------------------------------------------------------------------*/
d0fb370f 154
4a120d45 155static void
d2729d44 156set_fderives (void)
d0fb370f 157{
c7bd07f7
PE
158 symbol_number i, j;
159 rule_number k;
d0fb370f 160
4b3d3a8e 161 fderives = bitsetv_create (nvars, nrules, BITSET_FIXED);
d0fb370f 162
2fa6973e 163 set_firsts ();
d0fb370f 164
1cbcf2e7
AD
165 for (i = ntokens; i < nsyms; ++i)
166 for (j = ntokens; j < nsyms; ++j)
d8a0245c 167 if (bitset_test (FIRSTS (i), j - ntokens))
e9690142
JD
168 for (k = 0; derives[j - ntokens][k]; ++k)
169 bitset_set (FDERIVES (i), derives[j - ntokens][k]->number);
d0fb370f 170
273a74fa 171 if (trace_flag & trace_sets)
9bfe901c 172 print_fderives ();
d0fb370f 173
914feea9 174 bitsetv_free (firsts);
d0fb370f 175}
1565b720 176
2fa6973e 177\f
d0fb370f 178
2fa6973e 179void
da2a7671 180new_closure (unsigned int n)
d0fb370f 181{
da2a7671 182 itemset = xnmalloc (n, sizeof *itemset);
d0fb370f 183
4b3d3a8e 184 ruleset = bitset_create (nrules, BITSET_FIXED);
d0fb370f 185
2fa6973e 186 set_fderives ();
d0fb370f
RS
187}
188
189
2fa6973e 190
d0fb370f 191void
510c8497 192closure (item_number const *core, size_t n)
d0fb370f 193{
576890b7 194 /* Index over CORE. */
f6fbd3da 195 size_t c;
576890b7 196
d2b04478 197 /* A bit index over RULESET. */
c7bd07f7 198 rule_number ruleno;
d0fb370f 199
613f5e1a
AD
200 bitset_iterator iter;
201
273a74fa 202 if (trace_flag & trace_sets)
427c0dda 203 print_closure ("input", core, n);
c87d4863 204
643a5994 205 bitset_zero (ruleset);
d0fb370f 206
643a5994
AD
207 for (c = 0; c < n; ++c)
208 if (ISVAR (ritem[core[c]]))
209 bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]]));
d0fb370f 210
6ce2d93a 211 /* core is sorted on item index in ritem, which is sorted on rule number.
71b61d4d 212 Compute itemset with the same sort. */
b09f4f48 213 nitemset = 0;
576890b7 214 c = 0;
613f5e1a
AD
215 BITSET_FOR_EACH (iter, ruleset, ruleno, 0)
216 {
c7bd07f7 217 item_number itemno = rules[ruleno].rhs - ritem;
613f5e1a 218 while (c < n && core[c] < itemno)
e9690142
JD
219 {
220 itemset[nitemset] = core[c];
221 nitemset++;
222 c++;
223 }
b09f4f48
JD
224 itemset[nitemset] = itemno;
225 nitemset++;
613f5e1a 226 };
d0fb370f 227
576890b7
AD
228 while (c < n)
229 {
b09f4f48
JD
230 itemset[nitemset] = core[c];
231 nitemset++;
576890b7
AD
232 c++;
233 }
d0fb370f 234
273a74fa 235 if (trace_flag & trace_sets)
b09f4f48 236 print_closure ("output", itemset, nitemset);
d0fb370f
RS
237}
238
239
240void
2fa6973e 241free_closure (void)
d0fb370f 242{
afbb696d 243 free (itemset);
dfdb1797 244 bitset_free (ruleset);
914feea9 245 bitsetv_free (fderives);
d0fb370f 246}