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