src/lalr.c

/* Compute look-ahead criteria for Bison.

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

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

   Bison 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 2, or (at your option)
   any later version.

   Bison 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 Bison; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
   Boston, MA 02110-1301, USA.  */


/* Compute how to make the finite state machine deterministic; find
   which rules need look-ahead in each state, and which look-ahead
   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 "nullable.h"
#include "reader.h"
#include "relation.h"
#include "symtab.h"

goto_number *goto_map;
static goto_number ngotos;
state_number *from_state;
state_number *to_state;

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


/* LA is a LR 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;


/* And for the famous F variable, which name is so descriptive that a
   comment is hardly needed.  <grin>.  */
static bitsetv F = NULL;

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


static 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.  */
	  assert (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);
}


/*----------------------------------------------------------.
| Map a state/symbol pair into its numeric representation.  |
`----------------------------------------------------------*/

static 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 (;;)
    {
      assert (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;

  F = 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 (F[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, &F);

  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->look_ahead_tokens - LA) + ri];
  sp->value = gotono;
  lookback[(s->reductions->look_ahead_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 an item number, and there is a
		 sentinel 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, &F);

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

  free (includes);
}


static void
compute_look_ahead_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], F[sp->value]);

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

  free (lookback);
  bitsetv_free (F);
}


/*-----------------------------------------------------.
| Count the number of look-ahead tokens required for S |
| (N_LOOK_AHEAD_TOKENS member).                        |
`-----------------------------------------------------*/

static int
state_look_ahead_tokens_count (state *s)
{
  int k;
  int n_look_ahead_tokens = 0;
  reductions *rp = s->reductions;
  transitions *sp = s->transitions;

  /* We need a look-ahead 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'.  */
  if (rp->num > 1
      || (rp->num == 1 && sp->num &&
	  !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
    n_look_ahead_tokens += rp->num;
  else
    s->consistent = 1;

  for (k = 0; k < sp->num; k++)
    if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
      {
	s->consistent = 0;
	break;
      }

  return n_look_ahead_tokens;
}


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

static void
initialize_LA (void)
{
  state_number i;
  bitsetv pLA;

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

  pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
  lookback = xcalloc (nLA, sizeof *lookback);

  /* Initialize the members LOOK_AHEAD_TOKENS for each state whose reductions
     require look-ahead tokens.  */
  for (i = 0; i < nstates; i++)
    {
      int count = state_look_ahead_tokens_count (states[i]);
      if (count)
	{
	  states[i]->reductions->look_ahead_tokens = pLA;
	  pLA += count;
	}
    }
}


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

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

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

      fprintf (out, "State %d: %d look-ahead tokens\n",
	       i, n_look_ahead_tokens);

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

void
lalr (void)
{
  initialize_LA ();
  set_goto_map ();
  initialize_F ();
  build_relations ();
  compute_FOLLOWS ();
  compute_look_ahead_tokens ();

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


void
lalr_free (void)
{
  state_number s;
  for (s = 0; s < nstates; ++s)
    states[s]->reductions->look_ahead_tokens = NULL;
  bitsetv_free (LA);
}
Commit	Line	Data
	1	/* Compute look-ahead criteria for Bison.
	2
	3	Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004, 2005,
	4	2006 Free 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	/* Compute how to make the finite state machine deterministic; find
	25	which rules need look-ahead in each state, and which look-ahead
	26	tokens they accept. */
	27
	28	#include <config.h>
	29	#include "system.h"
	30
	31	#include <bitset.h>
	32	#include <bitsetv.h>
	33	#include <quotearg.h>
	34
	35	#include "LR0.h"
	36	#include "complain.h"
	37	#include "derives.h"
	38	#include "getargs.h"
	39	#include "gram.h"
	40	#include "lalr.h"
	41	#include "nullable.h"
	42	#include "reader.h"
	43	#include "relation.h"
	44	#include "symtab.h"
	45
	46	goto_number *goto_map;
	47	static goto_number ngotos;
	48	state_number *from_state;
	49	state_number *to_state;
	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 a LR 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	/* And for the famous F variable, which name is so descriptive that a
	69	comment is hardly needed. <grin>. */
	70	static bitsetv F = NULL;
	71
	72	static goto_number **includes;
	73	static goto_list **lookback;
	74
	75
	76
	77
	78	static void
	79	set_goto_map (void)
	80	{
	81	state_number s;
	82	goto_number *temp_map;
	83
	84	goto_map = xcalloc (nvars + 1, sizeof *goto_map);
	85	temp_map = xnmalloc (nvars + 1, sizeof *temp_map);
	86
	87	ngotos = 0;
	88	for (s = 0; s < nstates; ++s)
	89	{
	90	transitions *sp = states[s]->transitions;
	91	int i;
	92	for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
	93	{
	94	ngotos++;
	95
	96	/* Abort if (ngotos + 1) would overflow. */
	97	assert (ngotos != GOTO_NUMBER_MAXIMUM);
	98
	99	goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	100	}
	101	}
	102
	103	{
	104	goto_number k = 0;
	105	int i;
	106	for (i = ntokens; i < nsyms; i++)
	107	{
	108	temp_map[i - ntokens] = k;
	109	k += goto_map[i - ntokens];
	110	}
	111
	112	for (i = ntokens; i < nsyms; i++)
	113	goto_map[i - ntokens] = temp_map[i - ntokens];
	114
	115	goto_map[nsyms - ntokens] = ngotos;
	116	temp_map[nsyms - ntokens] = ngotos;
	117	}
	118
	119	from_state = xcalloc (ngotos, sizeof *from_state);
	120	to_state = xcalloc (ngotos, sizeof *to_state);
	121
	122	for (s = 0; s < nstates; ++s)
	123	{
	124	transitions *sp = states[s]->transitions;
	125	int i;
	126	for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
	127	{
	128	goto_number k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	129	from_state[k] = s;
	130	to_state[k] = sp->states[i]->number;
	131	}
	132	}
	133
	134	free (temp_map);
	135	}
	136
	137
	138
	139	/*----------------------------------------------------------.
	140	\| Map a state/symbol pair into its numeric representation. \|
	141	`----------------------------------------------------------*/
	142
	143	static goto_number
	144	map_goto (state_number s0, symbol_number sym)
	145	{
	146	goto_number high;
	147	goto_number low;
	148	goto_number middle;
	149	state_number s;
	150
	151	low = goto_map[sym - ntokens];
	152	high = goto_map[sym - ntokens + 1] - 1;
	153
	154	for (;;)
	155	{
	156	assert (low <= high);
	157	middle = (low + high) / 2;
	158	s = from_state[middle];
	159	if (s == s0)
	160	return middle;
	161	else if (s < s0)
	162	low = middle + 1;
	163	else
	164	high = middle - 1;
	165	}
	166	}
	167
	168
	169	static void
	170	initialize_F (void)
	171	{
	172	goto_number *reads = xnmalloc (ngotos, sizeof reads);
	173	goto_number edge = xnmalloc (ngotos + 1, sizeof edge);
	174	goto_number nedges = 0;
	175
	176	goto_number i;
	177
	178	F = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
	179
	180	for (i = 0; i < ngotos; i++)
	181	{
	182	state_number stateno = to_state[i];
	183	transitions *sp = states[stateno]->transitions;
	184
	185	int j;
	186	FOR_EACH_SHIFT (sp, j)
	187	bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
	188
	189	for (; j < sp->num; j++)
	190	{
	191	symbol_number sym = TRANSITION_SYMBOL (sp, j);
	192	if (nullable[sym - ntokens])
	193	edge[nedges++] = map_goto (stateno, sym);
	194	}
	195
	196	if (nedges == 0)
	197	reads[i] = NULL;
	198	else
	199	{
	200	reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
	201	memcpy (reads[i], edge, nedges * sizeof edge[0]);
	202	reads[i][nedges] = END_NODE;
	203	nedges = 0;
	204	}
	205	}
	206
	207	relation_digraph (reads, ngotos, &F);
	208
	209	for (i = 0; i < ngotos; i++)
	210	free (reads[i]);
	211
	212	free (reads);
	213	free (edge);
	214	}
	215
	216
	217	static void
	218	add_lookback_edge (state s, rule r, goto_number gotono)
	219	{
	220	int ri = state_reduction_find (s, r);
	221	goto_list sp = xmalloc (sizeof sp);
	222	sp->next = lookback[(s->reductions->look_ahead_tokens - LA) + ri];
	223	sp->value = gotono;
	224	lookback[(s->reductions->look_ahead_tokens - LA) + ri] = sp;
	225	}
	226
	227
	228
	229	static void
	230	build_relations (void)
	231	{
	232	goto_number edge = xnmalloc (ngotos + 1, sizeof edge);
	233	state_number states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof states1);
	234	goto_number i;
	235
	236	includes = xnmalloc (ngotos, sizeof *includes);
	237
	238	for (i = 0; i < ngotos; i++)
	239	{
	240	int nedges = 0;
	241	symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
	242	rule **rulep;
	243
	244	for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
	245	{
	246	bool done;
	247	int length = 1;
	248	item_number const *rp;
	249	state *s = states[from_state[i]];
	250	states1[0] = s->number;
	251
	252	for (rp = (rulep)->rhs; ! item_number_is_rule_number (rp); rp++)
	253	{
	254	s = transitions_to (s->transitions,
	255	item_number_as_symbol_number (*rp));
	256	states1[length++] = s->number;
	257	}
	258
	259	if (!s->consistent)
	260	add_lookback_edge (s, *rulep, i);
	261
	262	length--;
	263	done = false;
	264	while (!done)
	265	{
	266	done = true;
	267	/* Each rhs ends in an item number, and there is a
	268	sentinel before the first rhs, so it is safe to
	269	decrement RP here. */
	270	rp--;
	271	if (ISVAR (*rp))
	272	{
	273	/* Downcasting from item_number to symbol_number. */
	274	edge[nedges++] = map_goto (states1[--length],
	275	item_number_as_symbol_number (*rp));
	276	if (nullable[*rp - ntokens])
	277	done = false;
	278	}
	279	}
	280	}
	281
	282	if (nedges == 0)
	283	includes[i] = NULL;
	284	else
	285	{
	286	int j;
	287	includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
	288	for (j = 0; j < nedges; j++)
	289	includes[i][j] = edge[j];
	290	includes[i][nedges] = END_NODE;
	291	}
	292	}
	293
	294	free (edge);
	295	free (states1);
	296
	297	relation_transpose (&includes, ngotos);
	298	}
	299
	300
	301
	302	static void
	303	compute_FOLLOWS (void)
	304	{
	305	goto_number i;
	306
	307	relation_digraph (includes, ngotos, &F);
	308
	309	for (i = 0; i < ngotos; i++)
	310	free (includes[i]);
	311
	312	free (includes);
	313	}
	314
	315
	316	static void
	317	compute_look_ahead_tokens (void)
	318	{
	319	size_t i;
	320	goto_list *sp;
	321
	322	for (i = 0; i < nLA; i++)
	323	for (sp = lookback[i]; sp; sp = sp->next)
	324	bitset_or (LA[i], LA[i], F[sp->value]);
	325
	326	/* Free LOOKBACK. */
	327	for (i = 0; i < nLA; i++)
	328	LIST_FREE (goto_list, lookback[i]);
	329
	330	free (lookback);
	331	bitsetv_free (F);
	332	}
	333
	334
	335	/*-----------------------------------------------------.
	336	\| Count the number of look-ahead tokens required for S \|
	337	\| (N_LOOK_AHEAD_TOKENS member). \|
	338	`-----------------------------------------------------*/
	339
	340	static int
	341	state_look_ahead_tokens_count (state *s)
	342	{
	343	int k;
	344	int n_look_ahead_tokens = 0;
	345	reductions *rp = s->reductions;
	346	transitions *sp = s->transitions;
	347
	348	/* We need a look-ahead either to distinguish different
	349	reductions (i.e., there are two or more), or to distinguish a
	350	reduction from a shift. Otherwise, it is straightforward,
	351	and the state is `consistent'. */
	352	if (rp->num > 1
	353	\|\| (rp->num == 1 && sp->num &&
	354	!TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
	355	n_look_ahead_tokens += rp->num;
	356	else
	357	s->consistent = 1;
	358
	359	for (k = 0; k < sp->num; k++)
	360	if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
	361	{
	362	s->consistent = 0;
	363	break;
	364	}
	365
	366	return n_look_ahead_tokens;
	367	}
	368
	369
	370	/*-----------------------------------------------------.
	371	\| Compute LA, NLA, and the look_ahead_tokens members. \|
	372	`-----------------------------------------------------*/
	373
	374	static void
	375	initialize_LA (void)
	376	{
	377	state_number i;
	378	bitsetv pLA;
	379
	380	/* Compute the total number of reductions requiring a look-ahead. */
	381	nLA = 0;
	382	for (i = 0; i < nstates; i++)
	383	nLA += state_look_ahead_tokens_count (states[i]);
	384	/* Avoid having to special case 0. */
	385	if (!nLA)
	386	nLA = 1;
	387
	388	pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
	389	lookback = xcalloc (nLA, sizeof *lookback);
	390
	391	/* Initialize the members LOOK_AHEAD_TOKENS for each state whose reductions
	392	require look-ahead tokens. */
	393	for (i = 0; i < nstates; i++)
	394	{
	395	int count = state_look_ahead_tokens_count (states[i]);
	396	if (count)
	397	{
	398	states[i]->reductions->look_ahead_tokens = pLA;
	399	pLA += count;
	400	}
	401	}
	402	}
	403
	404
	405	/*----------------------------------------------.
	406	\| Output the look-ahead tokens for each state. \|
	407	`----------------------------------------------*/
	408
	409	static void
	410	look_ahead_tokens_print (FILE *out)
	411	{
	412	state_number i;
	413	int j, k;
	414	fprintf (out, "Look-ahead tokens: BEGIN\n");
	415	for (i = 0; i < nstates; ++i)
	416	{
	417	reductions *reds = states[i]->reductions;
	418	bitset_iterator iter;
	419	int n_look_ahead_tokens = 0;
	420
	421	if (reds->look_ahead_tokens)
	422	for (k = 0; k < reds->num; ++k)
	423	if (reds->look_ahead_tokens[k])
	424	++n_look_ahead_tokens;
	425
	426	fprintf (out, "State %d: %d look-ahead tokens\n",
	427	i, n_look_ahead_tokens);
	428
	429	if (reds->look_ahead_tokens)
	430	for (j = 0; j < reds->num; ++j)
	431	BITSET_FOR_EACH (iter, reds->look_ahead_tokens[j], k, 0)
	432	{
	433	fprintf (out, " on %d (%s) -> rule %d\n",
	434	k, symbols[k]->tag,
	435	reds->rules[j]->number);
	436	};
	437	}
	438	fprintf (out, "Look-ahead tokens: END\n");
	439	}
	440
	441	void
	442	lalr (void)
	443	{
	444	initialize_LA ();
	445	set_goto_map ();
	446	initialize_F ();
	447	build_relations ();
	448	compute_FOLLOWS ();
	449	compute_look_ahead_tokens ();
	450
	451	if (trace_flag & trace_sets)
	452	look_ahead_tokens_print (stderr);
	453	}
	454
	455
	456	void
	457	lalr_free (void)
	458	{
	459	state_number s;
	460	for (s = 0; s < nstates; ++s)
	461	states[s]->reductions->look_ahead_tokens = NULL;
	462	bitsetv_free (LA);
	463	}