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