]>
Commit | Line | Data |
---|---|---|
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 | 36 | item_number *itemset; |
b09f4f48 | 37 | size_t nitemset; |
fb908786 | 38 | |
dfdb1797 | 39 | static bitset ruleset; |
d0fb370f RS |
40 | |
41 | /* internal data. See comments before set_fderives and set_firsts. */ | |
914feea9 AD |
42 | static bitsetv fderives = NULL; |
43 | static 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 | 54 | static void |
510c8497 | 55 | print_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 | ||
71 | static void | |
72 | print_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 |
88 | static void |
89 | print_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 | |
120 | static void | |
121 | set_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 | 155 | static void |
d2729d44 | 156 | set_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 | 179 | void |
da2a7671 | 180 | new_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 | 191 | void |
510c8497 | 192 | closure (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 | ||
240 | void | |
2fa6973e | 241 | free_closure (void) |
d0fb370f | 242 | { |
afbb696d | 243 | free (itemset); |
dfdb1797 | 244 | bitset_free (ruleset); |
914feea9 | 245 | bitsetv_free (fderives); |
d0fb370f | 246 | } |