1 /* Generate the nondeterministic finite state machine for Bison. 2 3 Copyright (C) 1984, 1986, 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 9 it 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, 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 Bison; see the file COPYING. If not, write to 20 the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 21 Boston, MA 02110-1301, USA. */ 22 23 24 /* See comments in state.h for the data structures that represent it. 25 The entry point is generate_states. */ 26 27 #include <config.h> 28 #include "system.h" 29 30 #include <bitset.h> 31 #include <quotearg.h> 32 33 #include "LR0.h" 34 #include "closure.h" 35 #include "complain.h" 36 #include "getargs.h" 37 #include "gram.h" 38 #include "gram.h" 39 #include "lalr.h" 40 #include "reader.h" 41 #include "reduce.h" 42 #include "state.h" 43 #include "symtab.h" 44 45 typedef struct state_list 46 { 47 struct state_list *next; 48 state *state; 49 } state_list; 50 51 static state_list *first_state = NULL; 52 static state_list *last_state = NULL; 53 54 55 /*------------------------------------------------------------------. 56 | A state was just discovered from another state. Queue it for | 57 | later examination, in order to find its transitions. Return it. | 58 `------------------------------------------------------------------*/ 59 60 static state * 61 state_list_append (symbol_number sym, size_t core_size, item_number *core) 62 { 63 state_list *node = xmalloc (sizeof *node); 64 state *s = state_new (sym, core_size, core); 65 66 if (trace_flag & trace_automaton) 67 fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n", 68 nstates, sym, symbols[sym]->tag); 69 70 node->next = NULL; 71 node->state = s; 72 73 if (!first_state) 74 first_state = node; 75 if (last_state) 76 last_state->next = node; 77 last_state = node; 78 79 return s; 80 } 81 82 static int nshifts; 83 static symbol_number *shift_symbol; 84 85 static rule **redset; 86 static state **shiftset; 87 88 static item_number **kernel_base; 89 static int *kernel_size; 90 static item_number *kernel_items; 91 92 93 static void 95 allocate_itemsets (void) 96 { 97 symbol_number i; 98 rule_number r; 99 item_number *rhsp; 100 101 /* Count the number of occurrences of all the symbols in RITEMS. 102 Note that useless productions (hence useless nonterminals) are 103 browsed too, hence we need to allocate room for _all_ the 104 symbols. */ 105 size_t count = 0; 106 size_t *symbol_count = xcalloc (nsyms + nuseless_nonterminals, 107 sizeof *symbol_count); 108 109 for (r = 0; r < nrules; ++r) 110 for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp) 111 { 112 count++; 113 symbol_count[*rhsp]++; 114 } 115 116 /* See comments before new_itemsets. All the vectors of items 117 live inside KERNEL_ITEMS. The number of active items after 118 some symbol S cannot be more than the number of times that S 119 appears as an item, which is SYMBOL_COUNT[S]. 120 We allocate that much space for each symbol. */ 121 122 kernel_base = xnmalloc (nsyms, sizeof *kernel_base); 123 kernel_items = xnmalloc (count, sizeof *kernel_items); 124 125 count = 0; 126 for (i = 0; i < nsyms; i++) 127 { 128 kernel_base[i] = kernel_items + count; 129 count += symbol_count[i]; 130 } 131 132 free (symbol_count); 133 kernel_size = xnmalloc (nsyms, sizeof *kernel_size); 134 } 135 136 137 static void 138 allocate_storage (void) 139 { 140 allocate_itemsets (); 141 142 shiftset = xnmalloc (nsyms, sizeof *shiftset); 143 redset = xnmalloc (nrules, sizeof *redset); 144 state_hash_new (); 145 shift_symbol = xnmalloc (nsyms, sizeof *shift_symbol); 146 } 147 148 149 static void 150 free_storage (void) 151 { 152 free (shift_symbol); 153 free (redset); 154 free (shiftset); 155 free (kernel_base); 156 free (kernel_size); 157 free (kernel_items); 158 state_hash_free (); 159 } 160 161 162 163 164 /*---------------------------------------------------------------. 165 | Find which symbols can be shifted in S, and for each one | 166 | record which items would be active after that shift. Uses the | 167 | contents of itemset. | 168 | | 169 | shift_symbol is set to a vector of the symbols that can be | 170 | shifted. For each symbol in the grammar, kernel_base[symbol] | 171 | points to a vector of item numbers activated if that symbol is | 172 | shifted, and kernel_size[symbol] is their numbers. | 173 `---------------------------------------------------------------*/ 174 175 static void 176 new_itemsets (state *s) 177 { 178 size_t i; 179 180 if (trace_flag & trace_automaton) 181 fprintf (stderr, "Entering new_itemsets, state = %d\n", s->number); 182 183 memset (kernel_size, 0, nsyms * sizeof *kernel_size); 184 185 nshifts = 0; 186 187 for (i = 0; i < nritemset; ++i) 188 if (ritem[itemset[i]] >= 0) 189 { 190 symbol_number sym = item_number_as_symbol_number (ritem[itemset[i]]); 191 if (!kernel_size[sym]) 192 { 193 shift_symbol[nshifts] = sym; 194 nshifts++; 195 } 196 197 kernel_base[sym][kernel_size[sym]] = itemset[i] + 1; 198 kernel_size[sym]++; 199 } 200 } 201 202 203 204 /*--------------------------------------------------------------. 205 | Find the state we would get to (from the current state) by | 206 | shifting SYM. Create a new state if no equivalent one exists | 207 | already. Used by append_states. | 208 `--------------------------------------------------------------*/ 209 210 static state * 211 get_state (symbol_number sym, size_t core_size, item_number *core) 212 { 213 state *s; 214 215 if (trace_flag & trace_automaton) 216 fprintf (stderr, "Entering get_state, symbol = %d (%s)\n", 217 sym, symbols[sym]->tag); 218 219 s = state_hash_lookup (core_size, core); 220 if (!s) 221 s = state_list_append (sym, core_size, core); 222 223 if (trace_flag & trace_automaton) 224 fprintf (stderr, "Exiting get_state => %d\n", s->number); 225 226 return s; 227 } 228 229 /*---------------------------------------------------------------. 230 | Use the information computed by new_itemsets to find the state | 231 | numbers reached by each shift transition from S. | 232 | | 233 | SHIFTSET is set up as a vector of those states. | 234 `---------------------------------------------------------------*/ 235 236 static void 237 append_states (state *s) 238 { 239 int i; 240 241 if (trace_flag & trace_automaton) 242 fprintf (stderr, "Entering append_states, state = %d\n", s->number); 243 244 /* First sort shift_symbol into increasing order. */ 245 246 for (i = 1; i < nshifts; i++) 247 { 248 symbol_number sym = shift_symbol[i]; 249 int j; 250 for (j = i; 0 < j && sym < shift_symbol[j - 1]; j--) 251 shift_symbol[j] = shift_symbol[j - 1]; 252 shift_symbol[j] = sym; 253 } 254 255 for (i = 0; i < nshifts; i++) 256 { 257 symbol_number sym = shift_symbol[i]; 258 shiftset[i] = get_state (sym, kernel_size[sym], kernel_base[sym]); 259 } 260 } 261 262 263 /*----------------------------------------------------------------. 264 | Find which rules can be used for reduction transitions from the | 265 | current state and make a reductions structure for the state to | 266 | record their rule numbers. | 267 `----------------------------------------------------------------*/ 268 269 static void 270 save_reductions (state *s) 271 { 272 int count = 0; 273 size_t i; 274 275 /* Find and count the active items that represent ends of rules. */ 276 for (i = 0; i < nritemset; ++i) 277 { 278 item_number item = ritem[itemset[i]]; 279 if (item_number_is_rule_number (item)) 280 { 281 rule_number r = item_number_as_rule_number (item); 282 redset[count++] = &rules[r]; 283 if (r == 0) 284 { 285 /* This is "reduce 0", i.e., accept. */ 286 assert (!final_state); 287 final_state = s; 288 } 289 } 290 } 291 292 /* Make a reductions structure and copy the data into it. */ 293 state_reductions_set (s, count, redset); 294 } 295 296 297 /*---------------. 299 | Build STATES. | 300 `---------------*/ 301 302 static void 303 set_states (void) 304 { 305 states = xcalloc (nstates, sizeof *states); 306 307 while (first_state) 308 { 309 state_list *this = first_state; 310 311 /* Pessimization, but simplification of the code: make sure all 312 the states have valid transitions and reductions members, 313 even if reduced to 0. It is too soon for errs, which are 314 computed later, but set_conflicts. */ 315 state *s = this->state; 316 if (!s->transitions) 317 state_transitions_set (s, 0, 0); 318 if (!s->reductions) 319 state_reductions_set (s, 0, 0); 320 321 states[s->number] = s; 322 323 first_state = this->next; 324 free (this); 325 } 326 first_state = NULL; 327 last_state = NULL; 328 } 329 330 331 /*-------------------------------------------------------------------. 332 | Compute the nondeterministic finite state machine (see state.h for | 333 | details) from the grammar. | 334 `-------------------------------------------------------------------*/ 335 336 void 337 generate_states (void) 338 { 339 item_number initial_core = 0; 340 state_list *list = NULL; 341 allocate_storage (); 342 new_closure (nritems); 343 344 /* Create the initial state. The 0 at the lhs is the index of the 345 item of this initial rule. */ 346 state_list_append (0, 1, &initial_core); 347 348 /* States are queued when they are created; process them all. */ 349 for (list = first_state; list; list = list->next) 350 { 351 state *s = list->state; 352 if (trace_flag & trace_automaton) 353 fprintf (stderr, "Processing state %d (reached by %s)\n", 354 s->number, 355 symbols[s->accessing_symbol]->tag); 356 /* Set up ruleset and itemset for the transitions out of this 357 state. ruleset gets a 1 bit for each rule that could reduce 358 now. itemset gets a vector of all the items that could be 359 accepted next. */ 360 closure (s->items, s->nitems); 361 /* Record the reductions allowed out of this state. */ 362 save_reductions (s); 363 /* Find the itemsets of the states that shifts can reach. */ 364 new_itemsets (s); 365 /* Find or create the core structures for those states. */ 366 append_states (s); 367 368 /* Create the shifts structures for the shifts to those states, 369 now that the state numbers transitioning to are known. */ 370 state_transitions_set (s, nshifts, shiftset); 371 } 372 373 /* discard various storage */ 374 free_closure (); 375 free_storage (); 376 377 /* Set up STATES. */ 378 set_states (); 379 } 380