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. */ 36item_number *itemset; 37size_t nitemset; 38 39static bitset ruleset; 40 41/* internal data. See comments before set_fderives and set_firsts. */ 42static bitsetv fderives = NULL; 43static 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 50/*-----------------. 51| Debugging code. | 52`-----------------*/ 53 54static void 55print_closure (char const *title, item_number *array, size_t size) 56{ 57 size_t i; 58 fprintf (stderr, "Closure: %s\n", title); 59 for (i = 0; i < size; ++i) 60 { 61 item_number *rp; 62 fprintf (stderr, " %2d: .", array[i]); 63 for (rp = &ritem[array[i]]; *rp >= 0; ++rp) 64 fprintf (stderr, " %s", symbols[*rp]->tag); 65 fprintf (stderr, " (rule %d)\n", -*rp - 1); 66 } 67 fputs ("\n\n", stderr); 68} 69 70 71static void 72print_firsts (void) 73{ 74 symbol_number i, j; 75 76 fprintf (stderr, "FIRSTS\n"); 77 for (i = ntokens; i < nsyms; i++) 78 { 79 bitset_iterator iter; 80 fprintf (stderr, "\t%s firsts\n", symbols[i]->tag); 81 BITSET_FOR_EACH (iter, FIRSTS (i), j, 0) 82 { 83 fprintf (stderr, "\t\t%s\n", 84 symbols[j + ntokens]->tag); 85 } 86 } 87 fprintf (stderr, "\n\n"); 88} 89 90 91static void 92print_fderives (void) 93{ 94 int i; 95 rule_number r; 96 97 fprintf (stderr, "FDERIVES\n"); 98 for (i = ntokens; i < nsyms; i++) 99 { 100 bitset_iterator iter; 101 fprintf (stderr, "\t%s derives\n", symbols[i]->tag); 102 BITSET_FOR_EACH (iter, FDERIVES (i), r, 0) 103 { 104 fprintf (stderr, "\t\t%3d ", r); 105 rule_rhs_print (&rules[r], stderr); 106 } 107 } 108 fprintf (stderr, "\n\n"); 109} 110 111/*------------------------------------------------------------------. 112| Set FIRSTS to be an NVARS array of NVARS bitsets indicating which | 113| items can represent the beginning of the input corresponding to | 114| which other items. | 115| | 116| For example, if some rule expands symbol 5 into the sequence of | 117| symbols 8 3 20, the symbol 8 can be the beginning of the data for | 118| symbol 5, so the bit [8 - ntokens] in first[5 - ntokens] (= FIRST | 119| (5)) is set. | 120`------------------------------------------------------------------*/ 121 122static void 123set_firsts (void) 124{ 125 symbol_number i, j; 126 127 firsts = bitsetv_create (nvars, nvars, BITSET_FIXED); 128 129 for (i = ntokens; i < nsyms; i++) 130 for (j = 0; derives[i - ntokens][j]; ++j) 131 { 132 item_number sym = derives[i - ntokens][j]->rhs[0]; 133 if (ISVAR (sym)) 134 bitset_set (FIRSTS (i), sym - ntokens); 135 } 136 137 if (trace_flag & trace_sets) 138 bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts); 139 bitsetv_reflexive_transitive_closure (firsts); 140 if (trace_flag & trace_sets) 141 bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts); 142 143 if (trace_flag & trace_sets) 144 print_firsts (); 145} 146 147/*-------------------------------------------------------------------. 148| Set FDERIVES to an NVARS by NRULES matrix of bits indicating which | 149| rules can help derive the beginning of the data for each | 150| nonterminal. | 151| | 152| For example, if symbol 5 can be derived as the sequence of symbols | 153| 8 3 20, and one of the rules for deriving symbol 8 is rule 4, then | 154| the [5 - NTOKENS, 4] bit in FDERIVES is set. | 155`-------------------------------------------------------------------*/ 156 157static void 158set_fderives (void) 159{ 160 symbol_number i, j; 161 rule_number k; 162 163 fderives = bitsetv_create (nvars, nrules, BITSET_FIXED); 164 165 set_firsts (); 166 167 for (i = ntokens; i < nsyms; ++i) 168 for (j = ntokens; j < nsyms; ++j) 169 if (bitset_test (FIRSTS (i), j - ntokens)) 170 for (k = 0; derives[j - ntokens][k]; ++k) 171 bitset_set (FDERIVES (i), derives[j - ntokens][k]->number); 172 173 if (trace_flag & trace_sets) 174 print_fderives (); 175 176 bitsetv_free (firsts); 177} 178 179 180 181void 182new_closure (unsigned int n) 183{ 184 itemset = xnmalloc (n, sizeof *itemset); 185 186 ruleset = bitset_create (nrules, BITSET_FIXED); 187 188 set_fderives (); 189} 190 191 192 193void 194closure (item_number *core, size_t n) 195{ 196 /* Index over CORE. */ 197 size_t c; 198 199 /* A bit index over RULESET. */ 200 rule_number ruleno; 201 202 bitset_iterator iter; 203 204 if (trace_flag & trace_sets) 205 print_closure ("input", core, n); 206 207 bitset_zero (ruleset); 208 209 for (c = 0; c < n; ++c) 210 if (ISVAR (ritem[core[c]])) 211 bitset_or (ruleset, ruleset, FDERIVES (ritem[core[c]])); 212 213 /* core is sorted on item index in ritem, which is sorted on rule number. 214 Compute itemset with the same sort. */ 215 nitemset = 0; 216 c = 0; 217 BITSET_FOR_EACH (iter, ruleset, ruleno, 0) 218 { 219 item_number itemno = rules[ruleno].rhs - ritem; 220 while (c < n && core[c] < itemno) 221 { 222 itemset[nitemset] = core[c]; 223 nitemset++; 224 c++; 225 } 226 itemset[nitemset] = itemno; 227 nitemset++; 228 }; 229 230 while (c < n) 231 { 232 itemset[nitemset] = core[c]; 233 nitemset++; 234 c++; 235 } 236 237 if (trace_flag & trace_sets) 238 print_closure ("output", itemset, nitemset); 239} 240 241 242void 243free_closure (void) 244{ 245 free (itemset); 246 bitset_free (ruleset); 247 bitsetv_free (fderives); 248} 249