OLD | NEW |
(Empty) | |
| 1 /* Closures for Bison |
| 2 |
| 3 Copyright (C) 1984, 1989, 2000, 2001, 2002, 2004, 2005, 2007 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 |
| 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 |
| 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 |
| 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 } |
OLD | NEW |