| 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. */ |
| 37 | item_number *itemset; |
| 38 | size_t nitemset; |
| 39 | |
| 40 | static bitset ruleset; |
| 41 | |
| 42 | /* internal data. See comments before set_fderives and set_firsts. */ |
| 43 | static bitsetv fderives = NULL; |
| 44 | static 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 | |
| 55 | static void |
| 56 | print_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 | |
| 72 | static void |
| 73 | print_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 | |
| 92 | static void |
| 93 | print_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 | |
| 123 | static void |
| 124 | set_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 | |
| 158 | static void |
| 159 | set_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 | |
| 182 | void |
| 183 | new_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 | |
| 194 | void |
| 195 | closure (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 | |
| 243 | void |
| 244 | free_closure (void) |
| 245 | { |
| 246 | free (itemset); |
| 247 | bitset_free (ruleset); |
| 248 | bitsetv_free (fderives); |
| 249 | } |