1 /* Closures for Bison 2 3 Copyright (C) 1984, 1989, 2000, 2001, 2002, 2004, 2005 Free 4 Software Foundation, Inc. 5 6 This file is part of Bison, the GNU Compiler Compiler. 7 8 Bison is free software; you can redistribute it and/or modify it 9 under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 2, or (at your option) 11 any later version. 12 13 Bison is distributed in the hope that it will be useful, but 14 WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with Bison; see the file COPYING. If not, write to the Free 20 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 21 02110-1301, USA. */ 22 23 #include <config.h> 24 #include "system.h" 25 26 #include <bitset.h> 27 #include <bitsetv-print.h> 28 #include <bitsetv.h> 29 #include <quotearg.h> 30 31 #include "closure.h" 32 #include "derives.h" 33 #include "getargs.h" 34 #include "gram.h" 35 #include "reader.h" 36 #include "symtab.h" 37 38 /* NITEMSET is the size of the array ITEMSET. */ 39 item_number *itemset; 40 size_t nritemset; 41 42 static bitset ruleset; 43 44 /* internal data. See comments before set_fderives and set_firsts. */ 45 static bitsetv fderives = NULL; 46 static bitsetv firsts = NULL; 47 48 /* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var. */ 49 #define FDERIVES(Var) fderives[(Var) - ntokens] 50 #define FIRSTS(Var) firsts[(Var) - ntokens] 51 52 54 /*-----------------. 55 | Debugging code. | 56 `-----------------*/ 57 58 static void 59 print_closure (char const *title, item_number *array, size_t size) 60 { 61 size_t i; 62 fprintf (stderr, "Closure: %s\n", title); 63 for (i = 0; i < size; ++i) 64 { 65 item_number *rp; 66 fprintf (stderr, " %2d: .", array[i]); 67 for (rp = &ritem[array[i]]; *rp >= 0; ++rp) 68 fprintf (stderr, " %s", symbols[*rp]->tag); 69 fprintf (stderr, " (rule %d)\n", -*rp - 1); 70 } 71 fputs ("\n\n", stderr); 72 } 73 74 75 static void 76 print_firsts (void) 77 { 78 symbol_number i, j; 79 80 fprintf (stderr, "FIRSTS\n"); 81 for (i = ntokens; i < nsyms; i++) 82 { 83 bitset_iterator iter; 84 fprintf (stderr, "\t%s firsts\n", symbols[i]->tag); 85 BITSET_FOR_EACH (iter, FIRSTS (i), j, 0) 86 { 87 fprintf (stderr, "\t\t%s\n", 88 symbols[j + ntokens]->tag); 89 } 90 } 91 fprintf (stderr, "\n\n"); 92 } 93 94 95 static void 96 print_fderives (void) 97 { 98 int i; 99 rule_number r; 100 101 fprintf (stderr, "FDERIVES\n"); 102 for (i = ntokens; i < nsyms; i++) 103 { 104 bitset_iterator iter; 105 fprintf (stderr, "\t%s derives\n", symbols[i]->tag); 106 BITSET_FOR_EACH (iter, FDERIVES (i), r, 0) 107 { 108 fprintf (stderr, "\t\t%3d ", r); 109 rule_rhs_print (&rules[r], stderr); 110 } 111 } 112 fprintf (stderr, "\n\n"); 113 } 114 115 /*------------------------------------------------------------------. 117 | Set FIRSTS to be an NVARS array of NVARS bitsets indicating which | 118 | items can represent the beginning of the input corresponding to | 119 | which other items. | 120 | | 121 | For example, if some rule expands symbol 5 into the sequence of | 122 | symbols 8 3 20, the symbol 8 can be the beginning of the data for | 123 | symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST | 124 | (5)) is set. | 125 `------------------------------------------------------------------*/ 126 127 static void 128 set_firsts (void) 129 { 130 symbol_number i, j; 131 132 firsts = bitsetv_create (nvars, nvars, BITSET_FIXED); 133 134 for (i = ntokens; i < nsyms; i++) 135 for (j = 0; derives[i - ntokens][j]; ++j) 136 { 137 item_number sym = derives[i - ntokens][j]->rhs[0]; 138 if (ISVAR (sym)) 139 bitset_set (FIRSTS (i), sym - ntokens); 140 } 141 142 if (trace_flag & trace_sets) 143 bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts); 144 bitsetv_reflexive_transitive_closure (firsts); 145 if (trace_flag & trace_sets) 146 bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts); 147 148 if (trace_flag & trace_sets) 149 print_firsts (); 150 } 151 152 /*-------------------------------------------------------------------. 153 | Set FDERIVES to an NVARS by NRULES matrix of bits indicating which | 154 | rules can help derive the beginning of the data for each | 155 | nonterminal. | 156 | | 157 | For example, if symbol 5 can be derived as the sequence of symbols | 158 | 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then | 159 | the [5 - NTOKENS, 4] bit in FDERIVES is set. | 160 `-------------------------------------------------------------------*/ 161 162 static void 163 set_fderives (void) 164 { 165 symbol_number i, j; 166 rule_number k; 167 168 fderives = bitsetv_create (nvars, nrules, BITSET_FIXED); 169 170 set_firsts (); 171 172 for (i = ntokens; i < nsyms; ++i) 173 for (j = ntokens; j < nsyms; ++j) 174 if (bitset_test (FIRSTS (i), j - ntokens)) 175 for (k = 0; derives[j - ntokens][k]; ++k) 176 bitset_set (FDERIVES (i), derives[j - ntokens][k]->number); 177 178 if (trace_flag & trace_sets) 179 print_fderives (); 180 181 bitsetv_free (firsts); 182 } 183 184 185 187 void 188 new_closure (unsigned int n) 189 { 190 itemset = xnmalloc (n, sizeof *itemset); 191 192 ruleset = bitset_create (nrules, BITSET_FIXED); 193 194 set_fderives (); 195 } 196 197 198 199 void 200 closure (item_number *core, size_t n) 201 { 202 /* Index over CORE. */ 203 size_t c; 204 205 /* A bit index over RULESET. */ 206 rule_number ruleno; 207 208 bitset_iterator iter; 209 210 if (trace_flag & trace_sets) 211 print_closure ("input", core, n); 212 213 bitset_zero (ruleset); 214 215 for (c = 0; c < n; ++c) 216 if (ISVAR (ritem[core[c]])) 217 bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]])); 218 219 nritemset = 0; 220 c = 0; 221 BITSET_FOR_EACH (iter, ruleset, ruleno, 0) 222 { 223 item_number itemno = rules[ruleno].rhs - ritem; 224 while (c < n && core[c] < itemno) 225 { 226 itemset[nritemset] = core[c]; 227 nritemset++; 228 c++; 229 } 230 itemset[nritemset] = itemno; 231 nritemset++; 232 }; 233 234 while (c < n) 235 { 236 itemset[nritemset] = core[c]; 237 nritemset++; 238 c++; 239 } 240 241 if (trace_flag & trace_sets) 242 print_closure ("output", itemset, nritemset); 243 } 244 245 246 void 247 free_closure (void) 248 { 249 free (itemset); 250 bitset_free (ruleset); 251 bitsetv_free (fderives); 252 } 253
