src/lalr.c

/* Compute lookahead criteria for Bison.

   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
   2006, 2007, 2008, 2009 Free Software Foundation, Inc.

   This file is part of Bison, the GNU Compiler Compiler.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */


/* Compute how to make the finite state machine deterministic; find
   which rules need lookahead in each state, and which lookahead
   tokens they accept.  */

#include <config.h>
#include "system.h"

#include <bitset.h>
#include <bitsetv.h>
#include <quotearg.h>

#include "LR0.h"
#include "complain.h"
#include "derives.h"
#include "getargs.h"
#include "gram.h"
#include "lalr.h"
#include "muscle_tab.h"
#include "nullable.h"
#include "reader.h"
#include "relation.h"
#include "symtab.h"

goto_number *goto_map;
goto_number ngotos;
state_number *from_state;
state_number *to_state;
bitsetv goto_follows = NULL;

/* Linked list of goto numbers.  */
typedef struct goto_list
{
  struct goto_list *next;
  goto_number value;
} goto_list;


/* LA is an NLA by NTOKENS matrix of bits.  LA[l, i] is 1 if the rule
   LArule[l] is applicable in the appropriate state when the next
   token is symbol i.  If LA[l, i] and LA[l, j] are both 1 for i != j,
   it is a conflict.  */

static bitsetv LA = NULL;
size_t nLA;


static goto_number **includes;
static goto_list **lookback;


void
set_goto_map (void)
{
  state_number s;
  goto_number *temp_map;

  goto_map = xcalloc (nvars + 1, sizeof *goto_map);
  temp_map = xnmalloc (nvars + 1, sizeof *temp_map);

  ngotos = 0;
  for (s = 0; s < nstates; ++s)
    {
      transitions *sp = states[s]->transitions;
      int i;
      for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
	{
	  ngotos++;

	  /* Abort if (ngotos + 1) would overflow.  */
	  aver (ngotos != GOTO_NUMBER_MAXIMUM);

	  goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	}
    }

  {
    goto_number k = 0;
    int i;
    for (i = ntokens; i < nsyms; i++)
      {
	temp_map[i - ntokens] = k;
	k += goto_map[i - ntokens];
      }

    for (i = ntokens; i < nsyms; i++)
      goto_map[i - ntokens] = temp_map[i - ntokens];

    goto_map[nsyms - ntokens] = ngotos;
    temp_map[nsyms - ntokens] = ngotos;
  }

  from_state = xcalloc (ngotos, sizeof *from_state);
  to_state = xcalloc (ngotos, sizeof *to_state);

  for (s = 0; s < nstates; ++s)
    {
      transitions *sp = states[s]->transitions;
      int i;
      for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
	{
	  goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	  from_state[k] = s;
	  to_state[k] = sp->states[i]->number;
	}
    }

  free (temp_map);
}


goto_number
map_goto (state_number s0, symbol_number sym)
{
  goto_number high;
  goto_number low;
  goto_number middle;
  state_number s;

  low = goto_map[sym - ntokens];
  high = goto_map[sym - ntokens + 1] - 1;

  for (;;)
    {
      aver (low <= high);
      middle = (low + high) / 2;
      s = from_state[middle];
      if (s == s0)
	return middle;
      else if (s < s0)
	low = middle + 1;
      else
	high = middle - 1;
    }
}


static void
initialize_F (void)
{
  goto_number **reads = xnmalloc (ngotos, sizeof *reads);
  goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
  goto_number nedges = 0;

  goto_number i;

  goto_follows = bitsetv_create (ngotos, ntokens, BITSET_FIXED);

  for (i = 0; i < ngotos; i++)
    {
      state_number stateno = to_state[i];
      transitions *sp = states[stateno]->transitions;

      int j;
      FOR_EACH_SHIFT (sp, j)
	bitset_set (goto_follows[i], TRANSITION_SYMBOL (sp, j));

      for (; j < sp->num; j++)
	{
	  symbol_number sym = TRANSITION_SYMBOL (sp, j);
	  if (nullable[sym - ntokens])
	    edge[nedges++] = map_goto (stateno, sym);
	}

      if (nedges == 0)
	reads[i] = NULL;
      else
	{
	  reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
	  memcpy (reads[i], edge, nedges * sizeof edge[0]);
	  reads[i][nedges] = END_NODE;
	  nedges = 0;
	}
    }

  relation_digraph (reads, ngotos, &goto_follows);

  for (i = 0; i < ngotos; i++)
    free (reads[i]);

  free (reads);
  free (edge);
}


static void
add_lookback_edge (state *s, rule *r, goto_number gotono)
{
  int ri = state_reduction_find (s, r);
  goto_list *sp = xmalloc (sizeof *sp);
  sp->next = lookback[(s->reductions->lookahead_tokens - LA) + ri];
  sp->value = gotono;
  lookback[(s->reductions->lookahead_tokens - LA) + ri] = sp;
}


static void
build_relations (void)
{
  goto_number *edge = xnmalloc (ngotos + 1, sizeof *edge);
  state_number *states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof *states1);
  goto_number i;

  includes = xnmalloc (ngotos, sizeof *includes);

  for (i = 0; i < ngotos; i++)
    {
      int nedges = 0;
      symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
      rule **rulep;

      for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
	{
	  bool done;
	  int length = 1;
	  item_number const *rp;
	  state *s = states[from_state[i]];
	  states1[0] = s->number;

	  for (rp = (*rulep)->rhs; ! item_number_is_rule_number (*rp); rp++)
	    {
	      s = transitions_to (s->transitions,
				  item_number_as_symbol_number (*rp));
	      states1[length++] = s->number;
	    }

	  if (!s->consistent)
	    add_lookback_edge (s, *rulep, i);

	  length--;
	  done = false;
	  while (!done)
	    {
	      done = true;
	      /* Each rhs ends in a rule number, and there is a
		 sentinel (ritem[-1]=0) before the first rhs, so it is safe to
		 decrement RP here.  */
	      rp--;
	      if (ISVAR (*rp))
		{
		  /* Downcasting from item_number to symbol_number.  */
		  edge[nedges++] = map_goto (states1[--length],
					     item_number_as_symbol_number (*rp));
		  if (nullable[*rp - ntokens])
		    done = false;
		}
	    }
	}

      if (nedges == 0)
	includes[i] = NULL;
      else
	{
	  int j;
	  includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
	  for (j = 0; j < nedges; j++)
	    includes[i][j] = edge[j];
	  includes[i][nedges] = END_NODE;
	}
    }

  free (edge);
  free (states1);

  relation_transpose (&includes, ngotos);
}


static void
compute_FOLLOWS (void)
{
  goto_number i;

  relation_digraph (includes, ngotos, &goto_follows);

  for (i = 0; i < ngotos; i++)
    free (includes[i]);

  free (includes);
}


static void
compute_lookahead_tokens (void)
{
  size_t i;
  goto_list *sp;

  for (i = 0; i < nLA; i++)
    for (sp = lookback[i]; sp; sp = sp->next)
      bitset_or (LA[i], LA[i], goto_follows[sp->value]);

  /* Free LOOKBACK. */
  for (i = 0; i < nLA; i++)
    LIST_FREE (goto_list, lookback[i]);

  free (lookback);
}


/*----------------------------------------------------.
| Count the number of lookahead tokens required for S |
| (N_LOOKAHEAD_TOKENS member).                        |
`----------------------------------------------------*/

static int
state_lookahead_tokens_count (state *s, bool default_reduction_only_for_accept)
{
  int n_lookahead_tokens = 0;
  reductions *rp = s->reductions;
  transitions *sp = s->transitions;

  /* Transitions are only disabled during conflict resolution, and that
     hasn't happened yet, so there should be no need to check that
     transition 0 hasn't been disabled before checking if it is a shift.
     However, this check was performed at one time, so we leave it as an
     aver.  */
  aver (sp->num == 0 || !TRANSITION_IS_DISABLED (sp, 0));

  /* We need a lookahead either to distinguish different reductions
     (i.e., there are two or more), or to distinguish a reduction from a
     shift.  Otherwise, it is straightforward, and the state is
     `consistent'.  However, treat only the accepting state as
     consistent (because there is never a lookahead token that makes
     sense there, and so no lookahead token should be read) if the user
     has otherwise disabled default reductions.  */
  if (rp->num > 1
      || (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0))
      || (rp->num == 1 && rp->rules[0]->number != 0
          && default_reduction_only_for_accept))
    n_lookahead_tokens += rp->num;
  else
    s->consistent = 1;

  return n_lookahead_tokens;
}


/*----------------------------------------------------.
| Compute LA, NLA, and the lookahead_tokens members.  |
`----------------------------------------------------*/

void
initialize_LA (void)
{
  state_number i;
  bitsetv pLA;
  bool default_reduction_only_for_accept;
  {
    char *default_reductions =
      muscle_percent_define_get ("lr.default-reductions");
    default_reduction_only_for_accept =
      0 == strcmp (default_reductions, "accepting");
    free (default_reductions);
  }

  /* Compute the total number of reductions requiring a lookahead.  */
  nLA = 0;
  for (i = 0; i < nstates; i++)
    nLA +=
      state_lookahead_tokens_count (states[i],
                                    default_reduction_only_for_accept);
  /* Avoid having to special case 0.  */
  if (!nLA)
    nLA = 1;

  pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);

  /* Initialize the members LOOKAHEAD_TOKENS for each state whose reductions
     require lookahead tokens.  */
  for (i = 0; i < nstates; i++)
    {
      int count =
        state_lookahead_tokens_count (states[i],
                                      default_reduction_only_for_accept);
      if (count)
	{
	  states[i]->reductions->lookahead_tokens = pLA;
	  pLA += count;
	}
    }
}


/*---------------------------------------------.
| Output the lookahead tokens for each state.  |
`---------------------------------------------*/

static void
lookahead_tokens_print (FILE *out)
{
  state_number i;
  int j, k;
  fprintf (out, "Lookahead tokens: BEGIN\n");
  for (i = 0; i < nstates; ++i)
    {
      reductions *reds = states[i]->reductions;
      bitset_iterator iter;
      int n_lookahead_tokens = 0;

      if (reds->lookahead_tokens)
	for (k = 0; k < reds->num; ++k)
	  if (reds->lookahead_tokens[k])
	    ++n_lookahead_tokens;

      fprintf (out, "State %d: %d lookahead tokens\n",
	       i, n_lookahead_tokens);

      if (reds->lookahead_tokens)
	for (j = 0; j < reds->num; ++j)
	  BITSET_FOR_EACH (iter, reds->lookahead_tokens[j], k, 0)
	  {
	    fprintf (out, "   on %d (%s) -> rule %d\n",
		     k, symbols[k]->tag,
		     reds->rules[j]->number);
	  };
    }
  fprintf (out, "Lookahead tokens: END\n");
}

void
lalr (void)
{
  initialize_LA ();
  set_goto_map ();
  initialize_F ();
  lookback = xcalloc (nLA, sizeof *lookback);
  build_relations ();
  compute_FOLLOWS ();
  compute_lookahead_tokens ();

  if (trace_flag & trace_sets)
    lookahead_tokens_print (stderr);
}


void
lalr_update_state_numbers (state_number old_to_new[], state_number nstates_old)
{
  goto_number ngotos_reachable = 0;
  symbol_number nonterminal = 0;
  aver (nsyms == nvars + ntokens);
  {
    goto_number i;
    for (i = 0; i < ngotos; ++i)
      {
        while (i == goto_map[nonterminal])
          goto_map[nonterminal++] = ngotos_reachable;
        /* If old_to_new[from_state[i]] = nstates_old, remove this goto
           entry.  */
        if (old_to_new[from_state[i]] != nstates_old)
          {
            /* from_state[i] is not removed, so it and thus to_state[i] are
               reachable, so to_state[i] != nstates_old.  */
            aver (old_to_new[to_state[i]] != nstates_old);
            from_state[ngotos_reachable] = old_to_new[from_state[i]];
            to_state[ngotos_reachable] = old_to_new[to_state[i]];
            ++ngotos_reachable;
          }
      }
  }
  while (nonterminal <= nvars)
    {
      aver (ngotos == goto_map[nonterminal]);
      goto_map[nonterminal++] = ngotos_reachable;
    }
  ngotos = ngotos_reachable;
}


void
lalr_free (void)
{
  state_number s;
  for (s = 0; s < nstates; ++s)
    states[s]->reductions->lookahead_tokens = NULL;
  bitsetv_free (LA);
}
Commit	Line	Data
	1	/* Compute lookahead criteria for Bison.
	2
	3	Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
	4	2006, 2007, 2008, 2009 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	/* Compute how to make the finite state machine deterministic; find
	23	which rules need lookahead in each state, and which lookahead
	24	tokens they accept. */
	25
	26	#include <config.h>
	27	#include "system.h"
	28
	29	#include <bitset.h>
	30	#include <bitsetv.h>
	31	#include <quotearg.h>
	32
	33	#include "LR0.h"
	34	#include "complain.h"
	35	#include "derives.h"
	36	#include "getargs.h"
	37	#include "gram.h"
	38	#include "lalr.h"
	39	#include "muscle_tab.h"
	40	#include "nullable.h"
	41	#include "reader.h"
	42	#include "relation.h"
	43	#include "symtab.h"
	44
	45	goto_number *goto_map;
	46	goto_number ngotos;
	47	state_number *from_state;
	48	state_number *to_state;
	49	bitsetv goto_follows = NULL;
	50
	51	/* Linked list of goto numbers. */
	52	typedef struct goto_list
	53	{
	54	struct goto_list *next;
	55	goto_number value;
	56	} goto_list;
	57
	58
	59	/* LA is an NLA by NTOKENS matrix of bits. LA[l, i] is 1 if the rule
	60	LArule[l] is applicable in the appropriate state when the next
	61	token is symbol i. If LA[l, i] and LA[l, j] are both 1 for i != j,
	62	it is a conflict. */
	63
	64	static bitsetv LA = NULL;
	65	size_t nLA;
	66
	67
	68	static goto_number **includes;
	69	static goto_list **lookback;
	70
	71
	72
	73
	74	void
	75	set_goto_map (void)
	76	{
	77	state_number s;
	78	goto_number *temp_map;
	79
	80	goto_map = xcalloc (nvars + 1, sizeof *goto_map);
	81	temp_map = xnmalloc (nvars + 1, sizeof *temp_map);
	82
	83	ngotos = 0;
	84	for (s = 0; s < nstates; ++s)
	85	{
	86	transitions *sp = states[s]->transitions;
	87	int i;
	88	for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
	89	{
	90	ngotos++;
	91
	92	/* Abort if (ngotos + 1) would overflow. */
	93	aver (ngotos != GOTO_NUMBER_MAXIMUM);
	94
	95	goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	96	}
	97	}
	98
	99	{
	100	goto_number k = 0;
	101	int i;
	102	for (i = ntokens; i < nsyms; i++)
	103	{
	104	temp_map[i - ntokens] = k;
	105	k += goto_map[i - ntokens];
	106	}
	107
	108	for (i = ntokens; i < nsyms; i++)
	109	goto_map[i - ntokens] = temp_map[i - ntokens];
	110
	111	goto_map[nsyms - ntokens] = ngotos;
	112	temp_map[nsyms - ntokens] = ngotos;
	113	}
	114
	115	from_state = xcalloc (ngotos, sizeof *from_state);
	116	to_state = xcalloc (ngotos, sizeof *to_state);
	117
	118	for (s = 0; s < nstates; ++s)
	119	{
	120	transitions *sp = states[s]->transitions;
	121	int i;
	122	for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
	123	{
	124	goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	125	from_state[k] = s;
	126	to_state[k] = sp->states[i]->number;
	127	}
	128	}
	129
	130	free (temp_map);
	131	}
	132
	133
	134	goto_number
	135	map_goto (state_number s0, symbol_number sym)
	136	{
	137	goto_number high;
	138	goto_number low;
	139	goto_number middle;
	140	state_number s;
	141
	142	low = goto_map[sym - ntokens];
	143	high = goto_map[sym - ntokens + 1] - 1;
	144
	145	for (;;)
	146	{
	147	aver (low <= high);
	148	middle = (low + high) / 2;
	149	s = from_state[middle];
	150	if (s == s0)
	151	return middle;
	152	else if (s < s0)
	153	low = middle + 1;
	154	else
	155	high = middle - 1;
	156	}
	157	}
	158
	159
	160	static void
	161	initialize_F (void)
	162	{
	163	goto_number *reads = xnmalloc (ngotos, sizeof reads);
	164	goto_number edge = xnmalloc (ngotos + 1, sizeof edge);
	165	goto_number nedges = 0;
	166
	167	goto_number i;
	168
	169	goto_follows = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
	170
	171	for (i = 0; i < ngotos; i++)
	172	{
	173	state_number stateno = to_state[i];
	174	transitions *sp = states[stateno]->transitions;
	175
	176	int j;
	177	FOR_EACH_SHIFT (sp, j)
	178	bitset_set (goto_follows[i], TRANSITION_SYMBOL (sp, j));
	179
	180	for (; j < sp->num; j++)
	181	{
	182	symbol_number sym = TRANSITION_SYMBOL (sp, j);
	183	if (nullable[sym - ntokens])
	184	edge[nedges++] = map_goto (stateno, sym);
	185	}
	186
	187	if (nedges == 0)
	188	reads[i] = NULL;
	189	else
	190	{
	191	reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
	192	memcpy (reads[i], edge, nedges * sizeof edge[0]);
	193	reads[i][nedges] = END_NODE;
	194	nedges = 0;
	195	}
	196	}
	197
	198	relation_digraph (reads, ngotos, &goto_follows);
	199
	200	for (i = 0; i < ngotos; i++)
	201	free (reads[i]);
	202
	203	free (reads);
	204	free (edge);
	205	}
	206
	207
	208	static void
	209	add_lookback_edge (state s, rule r, goto_number gotono)
	210	{
	211	int ri = state_reduction_find (s, r);
	212	goto_list sp = xmalloc (sizeof sp);
	213	sp->next = lookback[(s->reductions->lookahead_tokens - LA) + ri];
	214	sp->value = gotono;
	215	lookback[(s->reductions->lookahead_tokens - LA) + ri] = sp;
	216	}
	217
	218
	219
	220	static void
	221	build_relations (void)
	222	{
	223	goto_number edge = xnmalloc (ngotos + 1, sizeof edge);
	224	state_number states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof states1);
	225	goto_number i;
	226
	227	includes = xnmalloc (ngotos, sizeof *includes);
	228
	229	for (i = 0; i < ngotos; i++)
	230	{
	231	int nedges = 0;
	232	symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
	233	rule **rulep;
	234
	235	for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
	236	{
	237	bool done;
	238	int length = 1;
	239	item_number const *rp;
	240	state *s = states[from_state[i]];
	241	states1[0] = s->number;
	242
	243	for (rp = (rulep)->rhs; ! item_number_is_rule_number (rp); rp++)
	244	{
	245	s = transitions_to (s->transitions,
	246	item_number_as_symbol_number (*rp));
	247	states1[length++] = s->number;
	248	}
	249
	250	if (!s->consistent)
	251	add_lookback_edge (s, *rulep, i);
	252
	253	length--;
	254	done = false;
	255	while (!done)
	256	{
	257	done = true;
	258	/* Each rhs ends in a rule number, and there is a
	259	sentinel (ritem[-1]=0) before the first rhs, so it is safe to
	260	decrement RP here. */
	261	rp--;
	262	if (ISVAR (*rp))
	263	{
	264	/* Downcasting from item_number to symbol_number. */
	265	edge[nedges++] = map_goto (states1[--length],
	266	item_number_as_symbol_number (*rp));
	267	if (nullable[*rp - ntokens])
	268	done = false;
	269	}
	270	}
	271	}
	272
	273	if (nedges == 0)
	274	includes[i] = NULL;
	275	else
	276	{
	277	int j;
	278	includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
	279	for (j = 0; j < nedges; j++)
	280	includes[i][j] = edge[j];
	281	includes[i][nedges] = END_NODE;
	282	}
	283	}
	284
	285	free (edge);
	286	free (states1);
	287
	288	relation_transpose (&includes, ngotos);
	289	}
	290
	291
	292
	293	static void
	294	compute_FOLLOWS (void)
	295	{
	296	goto_number i;
	297
	298	relation_digraph (includes, ngotos, &goto_follows);
	299
	300	for (i = 0; i < ngotos; i++)
	301	free (includes[i]);
	302
	303	free (includes);
	304	}
	305
	306
	307	static void
	308	compute_lookahead_tokens (void)
	309	{
	310	size_t i;
	311	goto_list *sp;
	312
	313	for (i = 0; i < nLA; i++)
	314	for (sp = lookback[i]; sp; sp = sp->next)
	315	bitset_or (LA[i], LA[i], goto_follows[sp->value]);
	316
	317	/* Free LOOKBACK. */
	318	for (i = 0; i < nLA; i++)
	319	LIST_FREE (goto_list, lookback[i]);
	320
	321	free (lookback);
	322	}
	323
	324
	325	/*----------------------------------------------------.
	326	\| Count the number of lookahead tokens required for S \|
	327	\| (N_LOOKAHEAD_TOKENS member). \|
	328	`----------------------------------------------------*/
	329
	330	static int
	331	state_lookahead_tokens_count (state *s, bool default_reduction_only_for_accept)
	332	{
	333	int n_lookahead_tokens = 0;
	334	reductions *rp = s->reductions;
	335	transitions *sp = s->transitions;
	336
	337	/* Transitions are only disabled during conflict resolution, and that
	338	hasn't happened yet, so there should be no need to check that
	339	transition 0 hasn't been disabled before checking if it is a shift.
	340	However, this check was performed at one time, so we leave it as an
	341	aver. */
	342	aver (sp->num == 0 \|\| !TRANSITION_IS_DISABLED (sp, 0));
	343
	344	/* We need a lookahead either to distinguish different reductions
	345	(i.e., there are two or more), or to distinguish a reduction from a
	346	shift. Otherwise, it is straightforward, and the state is
	347	`consistent'. However, treat only the accepting state as
	348	consistent (because there is never a lookahead token that makes
	349	sense there, and so no lookahead token should be read) if the user
	350	has otherwise disabled default reductions. */
	351	if (rp->num > 1
	352	\|\| (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0))
	353	\|\| (rp->num == 1 && rp->rules[0]->number != 0
	354	&& default_reduction_only_for_accept))
	355	n_lookahead_tokens += rp->num;
	356	else
	357	s->consistent = 1;
	358
	359	return n_lookahead_tokens;
	360	}
	361
	362
	363	/*----------------------------------------------------.
	364	\| Compute LA, NLA, and the lookahead_tokens members. \|
	365	`----------------------------------------------------*/
	366
	367	void
	368	initialize_LA (void)
	369	{
	370	state_number i;
	371	bitsetv pLA;
	372	bool default_reduction_only_for_accept;
	373	{
	374	char *default_reductions =
	375	muscle_percent_define_get ("lr.default-reductions");
	376	default_reduction_only_for_accept =
	377	0 == strcmp (default_reductions, "accepting");
	378	free (default_reductions);
	379	}
	380
	381	/* Compute the total number of reductions requiring a lookahead. */
	382	nLA = 0;
	383	for (i = 0; i < nstates; i++)
	384	nLA +=
	385	state_lookahead_tokens_count (states[i],
	386	default_reduction_only_for_accept);
	387	/* Avoid having to special case 0. */
	388	if (!nLA)
	389	nLA = 1;
	390
	391	pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
	392
	393	/* Initialize the members LOOKAHEAD_TOKENS for each state whose reductions
	394	require lookahead tokens. */
	395	for (i = 0; i < nstates; i++)
	396	{
	397	int count =
	398	state_lookahead_tokens_count (states[i],
	399	default_reduction_only_for_accept);
	400	if (count)
	401	{
	402	states[i]->reductions->lookahead_tokens = pLA;
	403	pLA += count;
	404	}
	405	}
	406	}
	407
	408
	409	/*---------------------------------------------.
	410	\| Output the lookahead tokens for each state. \|
	411	`---------------------------------------------*/
	412
	413	static void
	414	lookahead_tokens_print (FILE *out)
	415	{
	416	state_number i;
	417	int j, k;
	418	fprintf (out, "Lookahead tokens: BEGIN\n");
	419	for (i = 0; i < nstates; ++i)
	420	{
	421	reductions *reds = states[i]->reductions;
	422	bitset_iterator iter;
	423	int n_lookahead_tokens = 0;
	424
	425	if (reds->lookahead_tokens)
	426	for (k = 0; k < reds->num; ++k)
	427	if (reds->lookahead_tokens[k])
	428	++n_lookahead_tokens;
	429
	430	fprintf (out, "State %d: %d lookahead tokens\n",
	431	i, n_lookahead_tokens);
	432
	433	if (reds->lookahead_tokens)
	434	for (j = 0; j < reds->num; ++j)
	435	BITSET_FOR_EACH (iter, reds->lookahead_tokens[j], k, 0)
	436	{
	437	fprintf (out, " on %d (%s) -> rule %d\n",
	438	k, symbols[k]->tag,
	439	reds->rules[j]->number);
	440	};
	441	}
	442	fprintf (out, "Lookahead tokens: END\n");
	443	}
	444
	445	void
	446	lalr (void)
	447	{
	448	initialize_LA ();
	449	set_goto_map ();
	450	initialize_F ();
	451	lookback = xcalloc (nLA, sizeof *lookback);
	452	build_relations ();
	453	compute_FOLLOWS ();
	454	compute_lookahead_tokens ();
	455
	456	if (trace_flag & trace_sets)
	457	lookahead_tokens_print (stderr);
	458	}
	459
	460
	461	void
	462	lalr_update_state_numbers (state_number old_to_new[], state_number nstates_old)
	463	{
	464	goto_number ngotos_reachable = 0;
	465	symbol_number nonterminal = 0;
	466	aver (nsyms == nvars + ntokens);
	467	{
	468	goto_number i;
	469	for (i = 0; i < ngotos; ++i)
	470	{
	471	while (i == goto_map[nonterminal])
	472	goto_map[nonterminal++] = ngotos_reachable;
	473	/* If old_to_new[from_state[i]] = nstates_old, remove this goto
	474	entry. */
	475	if (old_to_new[from_state[i]] != nstates_old)
	476	{
	477	/* from_state[i] is not removed, so it and thus to_state[i] are
	478	reachable, so to_state[i] != nstates_old. */
	479	aver (old_to_new[to_state[i]] != nstates_old);
	480	from_state[ngotos_reachable] = old_to_new[from_state[i]];
	481	to_state[ngotos_reachable] = old_to_new[to_state[i]];
	482	++ngotos_reachable;
	483	}
	484	}
	485	}
	486	while (nonterminal <= nvars)
	487	{
	488	aver (ngotos == goto_map[nonterminal]);
	489	goto_map[nonterminal++] = ngotos_reachable;
	490	}
	491	ngotos = ngotos_reachable;
	492	}
	493
	494
	495	void
	496	lalr_free (void)
	497	{
	498	state_number s;
	499	for (s = 0; s < nstates; ++s)
	500	states[s]->reductions->lookahead_tokens = NULL;
	501	bitsetv_free (LA);
	502	}