OLD | NEW |
(Empty) | |
| 1 /* Generate the nondeterministic finite state machine for Bison. |
| 2 |
| 3 Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2004, 2005, 2006, 2007 |
| 4 Free 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 #include <quotearg.h> |
| 30 |
| 31 #include "LR0.h" |
| 32 #include "closure.h" |
| 33 #include "complain.h" |
| 34 #include "getargs.h" |
| 35 #include "gram.h" |
| 36 #include "gram.h" |
| 37 #include "lalr.h" |
| 38 #include "reader.h" |
| 39 #include "reduce.h" |
| 40 #include "state.h" |
| 41 #include "symtab.h" |
| 42 |
| 43 typedef struct state_list |
| 44 { |
| 45 struct state_list *next; |
| 46 state *state; |
| 47 } state_list; |
| 48 |
| 49 static state_list *first_state = NULL; |
| 50 static state_list *last_state = NULL; |
| 51 |
| 52 |
| 53 /*------------------------------------------------------------------. |
| 54 | A state was just discovered from another state. Queue it for | |
| 55 | later examination, in order to find its transitions. Return it. | |
| 56 `------------------------------------------------------------------*/ |
| 57 |
| 58 static state * |
| 59 state_list_append (symbol_number sym, size_t core_size, item_number *core) |
| 60 { |
| 61 state_list *node = xmalloc (sizeof *node); |
| 62 state *s = state_new (sym, core_size, core); |
| 63 |
| 64 if (trace_flag & trace_automaton) |
| 65 fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n", |
| 66 nstates, sym, symbols[sym]->tag); |
| 67 |
| 68 node->next = NULL; |
| 69 node->state = s; |
| 70 |
| 71 if (!first_state) |
| 72 first_state = node; |
| 73 if (last_state) |
| 74 last_state->next = node; |
| 75 last_state = node; |
| 76 |
| 77 return s; |
| 78 } |
| 79 |
| 80 static int nshifts; |
| 81 static symbol_number *shift_symbol; |
| 82 |
| 83 static rule **redset; |
| 84 static state **shiftset; |
| 85 |
| 86 static item_number **kernel_base; |
| 87 static int *kernel_size; |
| 88 static item_number *kernel_items; |
| 89 |
| 90 |
| 91 static void |
| 92 allocate_itemsets (void) |
| 93 { |
| 94 symbol_number i; |
| 95 rule_number r; |
| 96 item_number *rhsp; |
| 97 |
| 98 /* Count the number of occurrences of all the symbols in RITEMS. |
| 99 Note that useless productions (hence useless nonterminals) are |
| 100 browsed too, hence we need to allocate room for _all_ the |
| 101 symbols. */ |
| 102 size_t count = 0; |
| 103 size_t *symbol_count = xcalloc (nsyms + nuseless_nonterminals, |
| 104 sizeof *symbol_count); |
| 105 |
| 106 for (r = 0; r < nrules; ++r) |
| 107 for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp) |
| 108 { |
| 109 count++; |
| 110 symbol_count[*rhsp]++; |
| 111 } |
| 112 |
| 113 /* See comments before new_itemsets. All the vectors of items |
| 114 live inside KERNEL_ITEMS. The number of active items after |
| 115 some symbol S cannot be more than the number of times that S |
| 116 appears as an item, which is SYMBOL_COUNT[S]. |
| 117 We allocate that much space for each symbol. */ |
| 118 |
| 119 kernel_base = xnmalloc (nsyms, sizeof *kernel_base); |
| 120 kernel_items = xnmalloc (count, sizeof *kernel_items); |
| 121 |
| 122 count = 0; |
| 123 for (i = 0; i < nsyms; i++) |
| 124 { |
| 125 kernel_base[i] = kernel_items + count; |
| 126 count += symbol_count[i]; |
| 127 } |
| 128 |
| 129 free (symbol_count); |
| 130 kernel_size = xnmalloc (nsyms, sizeof *kernel_size); |
| 131 } |
| 132 |
| 133 |
| 134 static void |
| 135 allocate_storage (void) |
| 136 { |
| 137 allocate_itemsets (); |
| 138 |
| 139 shiftset = xnmalloc (nsyms, sizeof *shiftset); |
| 140 redset = xnmalloc (nrules, sizeof *redset); |
| 141 state_hash_new (); |
| 142 shift_symbol = xnmalloc (nsyms, sizeof *shift_symbol); |
| 143 } |
| 144 |
| 145 |
| 146 static void |
| 147 free_storage (void) |
| 148 { |
| 149 free (shift_symbol); |
| 150 free (redset); |
| 151 free (shiftset); |
| 152 free (kernel_base); |
| 153 free (kernel_size); |
| 154 free (kernel_items); |
| 155 state_hash_free (); |
| 156 } |
| 157 |
| 158 |
| 159 |
| 160 |
| 161 /*---------------------------------------------------------------. |
| 162 | Find which symbols can be shifted in S, and for each one | |
| 163 | record which items would be active after that shift. Uses the | |
| 164 | contents of itemset. | |
| 165 | | |
| 166 | shift_symbol is set to a vector of the symbols that can be | |
| 167 | shifted. For each symbol in the grammar, kernel_base[symbol] | |
| 168 | points to a vector of item numbers activated if that symbol is | |
| 169 | shifted, and kernel_size[symbol] is their numbers. | |
| 170 | | |
| 171 | itemset is sorted on item index in ritem, which is sorted on | |
| 172 | rule number. Compute each kernel_base[symbol] with the same | |
| 173 | sort. | |
| 174 `---------------------------------------------------------------*/ |
| 175 |
| 176 static void |
| 177 new_itemsets (state *s) |
| 178 { |
| 179 size_t i; |
| 180 |
| 181 if (trace_flag & trace_automaton) |
| 182 fprintf (stderr, "Entering new_itemsets, state = %d\n", s->number); |
| 183 |
| 184 memset (kernel_size, 0, nsyms * sizeof *kernel_size); |
| 185 |
| 186 nshifts = 0; |
| 187 |
| 188 for (i = 0; i < nitemset; ++i) |
| 189 if (item_number_is_symbol_number (ritem[itemset[i]])) |
| 190 { |
| 191 symbol_number sym = item_number_as_symbol_number (ritem[itemset[i]]); |
| 192 if (!kernel_size[sym]) |
| 193 { |
| 194 shift_symbol[nshifts] = sym; |
| 195 nshifts++; |
| 196 } |
| 197 |
| 198 kernel_base[sym][kernel_size[sym]] = itemset[i] + 1; |
| 199 kernel_size[sym]++; |
| 200 } |
| 201 } |
| 202 |
| 203 |
| 204 |
| 205 /*--------------------------------------------------------------. |
| 206 | Find the state we would get to (from the current state) by | |
| 207 | shifting SYM. Create a new state if no equivalent one exists | |
| 208 | already. Used by append_states. | |
| 209 `--------------------------------------------------------------*/ |
| 210 |
| 211 static state * |
| 212 get_state (symbol_number sym, size_t core_size, item_number *core) |
| 213 { |
| 214 state *s; |
| 215 |
| 216 if (trace_flag & trace_automaton) |
| 217 fprintf (stderr, "Entering get_state, symbol = %d (%s)\n", |
| 218 sym, symbols[sym]->tag); |
| 219 |
| 220 s = state_hash_lookup (core_size, core); |
| 221 if (!s) |
| 222 s = state_list_append (sym, core_size, core); |
| 223 |
| 224 if (trace_flag & trace_automaton) |
| 225 fprintf (stderr, "Exiting get_state => %d\n", s->number); |
| 226 |
| 227 return s; |
| 228 } |
| 229 |
| 230 /*---------------------------------------------------------------. |
| 231 | Use the information computed by new_itemsets to find the state | |
| 232 | numbers reached by each shift transition from S. | |
| 233 | | |
| 234 | SHIFTSET is set up as a vector of those states. | |
| 235 `---------------------------------------------------------------*/ |
| 236 |
| 237 static void |
| 238 append_states (state *s) |
| 239 { |
| 240 int i; |
| 241 |
| 242 if (trace_flag & trace_automaton) |
| 243 fprintf (stderr, "Entering append_states, state = %d\n", s->number); |
| 244 |
| 245 /* First sort shift_symbol into increasing order. */ |
| 246 |
| 247 for (i = 1; i < nshifts; i++) |
| 248 { |
| 249 symbol_number sym = shift_symbol[i]; |
| 250 int j; |
| 251 for (j = i; 0 < j && sym < shift_symbol[j - 1]; j--) |
| 252 shift_symbol[j] = shift_symbol[j - 1]; |
| 253 shift_symbol[j] = sym; |
| 254 } |
| 255 |
| 256 for (i = 0; i < nshifts; i++) |
| 257 { |
| 258 symbol_number sym = shift_symbol[i]; |
| 259 shiftset[i] = get_state (sym, kernel_size[sym], kernel_base[sym]); |
| 260 } |
| 261 } |
| 262 |
| 263 |
| 264 /*----------------------------------------------------------------. |
| 265 | Find which rules can be used for reduction transitions from the | |
| 266 | current state and make a reductions structure for the state to | |
| 267 | record their rule numbers. | |
| 268 `----------------------------------------------------------------*/ |
| 269 |
| 270 static void |
| 271 save_reductions (state *s) |
| 272 { |
| 273 int count = 0; |
| 274 size_t i; |
| 275 |
| 276 /* Find and count the active items that represent ends of rules. */ |
| 277 for (i = 0; i < nitemset; ++i) |
| 278 { |
| 279 item_number item = ritem[itemset[i]]; |
| 280 if (item_number_is_rule_number (item)) |
| 281 { |
| 282 rule_number r = item_number_as_rule_number (item); |
| 283 redset[count++] = &rules[r]; |
| 284 if (r == 0) |
| 285 { |
| 286 /* This is "reduce 0", i.e., accept. */ |
| 287 aver (!final_state); |
| 288 final_state = s; |
| 289 } |
| 290 } |
| 291 } |
| 292 |
| 293 /* Make a reductions structure and copy the data into it. */ |
| 294 state_reductions_set (s, count, redset); |
| 295 } |
| 296 |
| 297 |
| 298 /*---------------. |
| 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 itemset for the transitions out of this state. itemset gets a |
| 357 vector of all the items that could be 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 } |
OLD | NEW |