1/* Generate the LR(0) parser states for Bison. 2 3 Copyright (C) 1984, 1986, 1989, 2000-2002, 2004-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 22/* See comments in state.h for the data structures that represent it. 23 The entry point is generate_states. */ 24 25#include <config.h> 26#include "system.h" 27 28#include <bitset.h> 29 30#include "LR0.h" 31#include "closure.h" 32#include "complain.h" 33#include "getargs.h" 34#include "gram.h" 35#include "gram.h" 36#include "lalr.h" 37#include "reader.h" 38#include "reduce.h" 39#include "state.h" 40#include "symtab.h" 41 42typedef struct state_list 43{ 44 struct state_list *next; 45 state *state; 46} state_list; 47 48static state_list *first_state = NULL; 49static state_list *last_state = NULL; 50 51 52/*------------------------------------------------------------------. 53| A state was just discovered from another state. Queue it for | 54| later examination, in order to find its transitions. Return it. | 55`------------------------------------------------------------------*/ 56 57static state * 58state_list_append (symbol_number sym, size_t core_size, item_number *core) 59{ 60 state_list *node = xmalloc (sizeof *node); 61 state *s = state_new (sym, core_size, core); 62 63 if (trace_flag & trace_automaton) 64 fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n", 65 nstates, sym, symbols[sym]->tag); 66 67 node->next = NULL; 68 node->state = s; 69 70 if (!first_state) 71 first_state = node; 72 if (last_state) 73 last_state->next = node; 74 last_state = node; 75 76 return s; 77} 78 79static int nshifts; 80static symbol_number *shift_symbol; 81 82static rule **redset; 83static state **shiftset; 84 85static item_number **kernel_base; 86static int *kernel_size; 87static item_number *kernel_items; 88 89 90static void 91allocate_itemsets (void) 92{ 93 symbol_number i; 94 rule_number r; 95 item_number *rhsp; 96 97 /* Count the number of occurrences of all the symbols in RITEMS. 98 Note that useless productions (hence useless nonterminals) are 99 browsed too, hence we need to allocate room for _all_ the 100 symbols. */ 101 size_t count = 0; 102 size_t *symbol_count = xcalloc (nsyms + nuseless_nonterminals, 103 sizeof *symbol_count); 104 105 for (r = 0; r < nrules; ++r) 106 for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp) 107 { 108 count++; 109 symbol_count[*rhsp]++; 110 } 111 112 /* See comments before new_itemsets. All the vectors of items 113 live inside KERNEL_ITEMS. The number of active items after 114 some symbol S cannot be more than the number of times that S 115 appears as an item, which is SYMBOL_COUNT[S]. 116 We allocate that much space for each symbol. */ 117 118 kernel_base = xnmalloc (nsyms, sizeof *kernel_base); 119 kernel_items = xnmalloc (count, sizeof *kernel_items); 120 121 count = 0; 122 for (i = 0; i < nsyms; i++) 123 { 124 kernel_base[i] = kernel_items + count; 125 count += symbol_count[i]; 126 } 127 128 free (symbol_count); 129 kernel_size = xnmalloc (nsyms, sizeof *kernel_size); 130} 131 132 133static void 134allocate_storage (void) 135{ 136 allocate_itemsets (); 137 138 shiftset = xnmalloc (nsyms, sizeof *shiftset); 139 redset = xnmalloc (nrules, sizeof *redset); 140 state_hash_new (); 141 shift_symbol = xnmalloc (nsyms, sizeof *shift_symbol); 142} 143 144 145static void 146free_storage (void) 147{ 148 free (shift_symbol); 149 free (redset); 150 free (shiftset); 151 free (kernel_base); 152 free (kernel_size); 153 free (kernel_items); 154 state_hash_free (); 155} 156 157 158 159 160/*---------------------------------------------------------------. 161| Find which symbols can be shifted in S, and for each one | 162| record which items would be active after that shift. Uses the | 163| contents of itemset. | 164| | 165| shift_symbol is set to a vector of the symbols that can be | 166| shifted. For each symbol in the grammar, kernel_base[symbol] | 167| points to a vector of item numbers activated if that symbol is | 168| shifted, and kernel_size[symbol] is their numbers. | 169| | 170| itemset is sorted on item index in ritem, which is sorted on | 171| rule number. Compute each kernel_base[symbol] with the same | 172| sort. | 173`---------------------------------------------------------------*/ 174 175static void 176new_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 < nitemset; ++i) 188 if (item_number_is_symbol_number (ritem[itemset[i]])) 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 210static state * 211get_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 236static void 237append_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 269static void 270save_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 < nitemset; ++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 aver (!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/*---------------. 298| Build STATES. | 299`---------------*/ 300 301static void 302set_states (void) 303{ 304 states = xcalloc (nstates, sizeof *states); 305 306 while (first_state) 307 { 308 state_list *this = first_state; 309 310 /* Pessimization, but simplification of the code: make sure all 311 the states have valid transitions and reductions members, 312 even if reduced to 0. It is too soon for errs, which are 313 computed later, but set_conflicts. */ 314 state *s = this->state; 315 if (!s->transitions) 316 state_transitions_set (s, 0, 0); 317 if (!s->reductions) 318 state_reductions_set (s, 0, 0); 319 320 states[s->number] = s; 321 322 first_state = this->next; 323 free (this); 324 } 325 first_state = NULL; 326 last_state = NULL; 327} 328 329 330/*-------------------------------------------------------------------. 331| Compute the LR(0) parser states (see state.h for details) from the | 332| grammar. | 333`-------------------------------------------------------------------*/ 334 335void 336generate_states (void) 337{ 338 item_number initial_core = 0; 339 state_list *list = NULL; 340 allocate_storage (); 341 new_closure (nritems); 342 343 /* Create the initial state. The 0 at the lhs is the index of the 344 item of this initial rule. */ 345 state_list_append (0, 1, &initial_core); 346 347 /* States are queued when they are created; process them all. */ 348 for (list = first_state; list; list = list->next) 349 { 350 state *s = list->state; 351 if (trace_flag & trace_automaton) 352 fprintf (stderr, "Processing state %d (reached by %s)\n", 353 s->number, 354 symbols[s->accessing_symbol]->tag); 355 /* Set up itemset for the transitions out of this state. itemset gets a 356 vector of all the items that could be accepted next. */ 357 closure (s->items, s->nitems); 358 /* Record the reductions allowed out of this state. */ 359 save_reductions (s); 360 /* Find the itemsets of the states that shifts can reach. */ 361 new_itemsets (s); 362 /* Find or create the core structures for those states. */ 363 append_states (s); 364 365 /* Create the shifts structures for the shifts to those states, 366 now that the state numbers transitioning to are known. */ 367 state_transitions_set (s, nshifts, shiftset); 368 } 369 370 /* discard various storage */ 371 free_closure (); 372 free_storage (); 373 374 /* Set up STATES. */ 375 set_states (); 376} 377