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