1 /* Closures for Bison 2 3 Copyright (C) 1984, 1989, 2000-2002, 2004-2005, 2007, 2009-2012 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 28 #include "closure.h" 29 #include "derives.h" 30 #include "getargs.h" 31 #include "gram.h" 32 #include "reader.h" 33 #include "symtab.h" 34 35 /* NITEMSET is the size of the array ITEMSET. */ 36 item_number *itemset; 37 size_t nitemset; 38 39 static bitset ruleset; 40 41 /* internal data. See comments before set_fderives and set_firsts. */ 42 static bitsetv fderives = NULL; 43 static bitsetv firsts = NULL; 44 45 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var. */ 46 #define FDERIVES(Var) fderives[(Var) - ntokens] 47 #define FIRSTS(Var) firsts[(Var) - ntokens] 48 49 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 /*------------------------------------------------------------------. 114 | Set FIRSTS to be an NVARS array of NVARS bitsets indicating which | 115 | items can represent the beginning of the input corresponding to | 116 | which other items. | 117 | | 118 | For example, if some rule expands symbol 5 into the sequence of | 119 | symbols 8 3 20, the symbol 8 can be the beginning of the data for | 120 | symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST | 121 | (5)) is set. | 122 `------------------------------------------------------------------*/ 123 124 static void 125 set_firsts (void) 126 { 127 symbol_number i, j; 128 129 firsts = bitsetv_create (nvars, nvars, BITSET_FIXED); 130 131 for (i = ntokens; i < nsyms; i++) 132 for (j = 0; derives[i - ntokens][j]; ++j) 133 { 134 item_number sym = derives[i - ntokens][j]->rhs[0]; 135 if (ISVAR (sym)) 136 bitset_set (FIRSTS (i), sym - ntokens); 137 } 138 139 if (trace_flag & trace_sets) 140 bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts); 141 bitsetv_reflexive_transitive_closure (firsts); 142 if (trace_flag & trace_sets) 143 bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts); 144 145 if (trace_flag & trace_sets) 146 print_firsts (); 147 } 148 149 /*-------------------------------------------------------------------. 150 | Set FDERIVES to an NVARS by NRULES matrix of bits indicating which | 151 | rules can help derive the beginning of the data for each | 152 | nonterminal. | 153 | | 154 | For example, if symbol 5 can be derived as the sequence of symbols | 155 | 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then | 156 | the [5 - NTOKENS, 4] bit in FDERIVES is set. | 157 `-------------------------------------------------------------------*/ 158 159 static void 160 set_fderives (void) 161 { 162 symbol_number i, j; 163 rule_number k; 164 165 fderives = bitsetv_create (nvars, nrules, BITSET_FIXED); 166 167 set_firsts (); 168 169 for (i = ntokens; i < nsyms; ++i) 170 for (j = ntokens; j < nsyms; ++j) 171 if (bitset_test (FIRSTS (i), j - ntokens)) 172 for (k = 0; derives[j - ntokens][k]; ++k) 173 bitset_set (FDERIVES (i), derives[j - ntokens][k]->number); 174 175 if (trace_flag & trace_sets) 176 print_fderives (); 177 178 bitsetv_free (firsts); 179 } 180 181 182 184 void 185 new_closure (unsigned int n) 186 { 187 itemset = xnmalloc (n, sizeof *itemset); 188 189 ruleset = bitset_create (nrules, BITSET_FIXED); 190 191 set_fderives (); 192 } 193 194 195 196 void 197 closure (item_number *core, size_t n) 198 { 199 /* Index over CORE. */ 200 size_t c; 201 202 /* A bit index over RULESET. */ 203 rule_number ruleno; 204 205 bitset_iterator iter; 206 207 if (trace_flag & trace_sets) 208 print_closure ("input", core, n); 209 210 bitset_zero (ruleset); 211 212 for (c = 0; c < n; ++c) 213 if (ISVAR (ritem[core[c]])) 214 bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]])); 215 216 /* core is sorted on item index in ritem, which is sorted on rule number. 217 Compute itemset with the same sort. */ 218 nitemset = 0; 219 c = 0; 220 BITSET_FOR_EACH (iter, ruleset, ruleno, 0) 221 { 222 item_number itemno = rules[ruleno].rhs - ritem; 223 while (c < n && core[c] < itemno) 224 { 225 itemset[nitemset] = core[c]; 226 nitemset++; 227 c++; 228 } 229 itemset[nitemset] = itemno; 230 nitemset++; 231 }; 232 233 while (c < n) 234 { 235 itemset[nitemset] = core[c]; 236 nitemset++; 237 c++; 238 } 239 240 if (trace_flag & trace_sets) 241 print_closure ("output", itemset, nitemset); 242 } 243 244 245 void 246 free_closure (void) 247 { 248 free (itemset); 249 bitset_free (ruleset); 250 bitsetv_free (fderives); 251 } 252
