src/lalr.c

/* Compute look-ahead criteria for Bison.

   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004
   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., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, 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 "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.  */
	  if (ngotos == GOTO_NUMBER_MAXIMUM)
	    abort ();

	  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 (;;)
    {
      if (high < low)
	abort ();
      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 *rp;
	  state *s = states[from_state[i]];
	  states1[0] = s->number;

	  for (rp = (*rulep)->rhs; *rp >= 0; 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;
	      rp--;
	      /* JF added rp>=ritem &&   I hope to god its right! */
	      if (rp >= ritem && 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
	4	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., 59 Temple Place - Suite 330,
	21	Boston, MA 02111-1307, 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 "system.h"
	29
	30	#include <bitset.h>
	31	#include <bitsetv.h>
	32	#include <quotearg.h>
	33
	34	#include "LR0.h"
	35	#include "complain.h"
	36	#include "derives.h"
	37	#include "getargs.h"
	38	#include "gram.h"
	39	#include "lalr.h"
	40	#include "nullable.h"
	41	#include "reader.h"
	42	#include "relation.h"
	43	#include "symtab.h"
	44
	45	goto_number *goto_map;
	46	static goto_number ngotos;
	47	state_number *from_state;
	48	state_number *to_state;
	49
	50	/* Linked list of goto numbers. */
	51	typedef struct goto_list
	52	{
	53	struct goto_list *next;
	54	goto_number value;
	55	} goto_list;
	56
	57
	58	/* LA is a LR by NTOKENS matrix of bits. LA[l, i] is 1 if the rule
	59	LArule[l] is applicable in the appropriate state when the next
	60	token is symbol i. If LA[l, i] and LA[l, j] are both 1 for i != j,
	61	it is a conflict. */
	62
	63	static bitsetv LA = NULL;
	64	size_t nLA;
	65
	66
	67	/* And for the famous F variable, which name is so descriptive that a
	68	comment is hardly needed. <grin>. */
	69	static bitsetv F = NULL;
	70
	71	static goto_number **includes;
	72	static goto_list **lookback;
	73
	74
	75
	76
	77	static void
	78	set_goto_map (void)
	79	{
	80	state_number s;
	81	goto_number *temp_map;
	82
	83	goto_map = xcalloc (nvars + 1, sizeof *goto_map);
	84	temp_map = xnmalloc (nvars + 1, sizeof *temp_map);
	85
	86	ngotos = 0;
	87	for (s = 0; s < nstates; ++s)
	88	{
	89	transitions *sp = states[s]->transitions;
	90	int i;
	91	for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
	92	{
	93	ngotos++;
	94
	95	/* Abort if (ngotos + 1) would overflow. */
	96	if (ngotos == GOTO_NUMBER_MAXIMUM)
	97	abort ();
	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	if (high < low)
	157	abort ();
	158	middle = (low + high) / 2;
	159	s = from_state[middle];
	160	if (s == s0)
	161	return middle;
	162	else if (s < s0)
	163	low = middle + 1;
	164	else
	165	high = middle - 1;
	166	}
	167	}
	168
	169
	170	static void
	171	initialize_F (void)
	172	{
	173	goto_number *reads = xnmalloc (ngotos, sizeof reads);
	174	goto_number edge = xnmalloc (ngotos + 1, sizeof edge);
	175	goto_number nedges = 0;
	176
	177	goto_number i;
	178
	179	F = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
	180
	181	for (i = 0; i < ngotos; i++)
	182	{
	183	state_number stateno = to_state[i];
	184	transitions *sp = states[stateno]->transitions;
	185
	186	int j;
	187	FOR_EACH_SHIFT (sp, j)
	188	bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
	189
	190	for (; j < sp->num; j++)
	191	{
	192	symbol_number sym = TRANSITION_SYMBOL (sp, j);
	193	if (nullable[sym - ntokens])
	194	edge[nedges++] = map_goto (stateno, sym);
	195	}
	196
	197	if (nedges == 0)
	198	reads[i] = NULL;
	199	else
	200	{
	201	reads[i] = xnmalloc (nedges + 1, sizeof reads[i][0]);
	202	memcpy (reads[i], edge, nedges * sizeof edge[0]);
	203	reads[i][nedges] = END_NODE;
	204	nedges = 0;
	205	}
	206	}
	207
	208	relation_digraph (reads, ngotos, &F);
	209
	210	for (i = 0; i < ngotos; i++)
	211	free (reads[i]);
	212
	213	free (reads);
	214	free (edge);
	215	}
	216
	217
	218	static void
	219	add_lookback_edge (state s, rule r, goto_number gotono)
	220	{
	221	int ri = state_reduction_find (s, r);
	222	goto_list sp = xmalloc (sizeof sp);
	223	sp->next = lookback[(s->reductions->look_ahead_tokens - LA) + ri];
	224	sp->value = gotono;
	225	lookback[(s->reductions->look_ahead_tokens - LA) + ri] = sp;
	226	}
	227
	228
	229
	230	static void
	231	build_relations (void)
	232	{
	233	goto_number edge = xnmalloc (ngotos + 1, sizeof edge);
	234	state_number states1 = xnmalloc (ritem_longest_rhs () + 1, sizeof states1);
	235	goto_number i;
	236
	237	includes = xnmalloc (ngotos, sizeof *includes);
	238
	239	for (i = 0; i < ngotos; i++)
	240	{
	241	int nedges = 0;
	242	symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
	243	rule **rulep;
	244
	245	for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
	246	{
	247	bool done;
	248	int length = 1;
	249	item_number *rp;
	250	state *s = states[from_state[i]];
	251	states1[0] = s->number;
	252
	253	for (rp = (rulep)->rhs; rp >= 0; rp++)
	254	{
	255	s = transitions_to (s->transitions,
	256	item_number_as_symbol_number (*rp));
	257	states1[length++] = s->number;
	258	}
	259
	260	if (!s->consistent)
	261	add_lookback_edge (s, *rulep, i);
	262
	263	length--;
	264	done = false;
	265	while (!done)
	266	{
	267	done = true;
	268	rp--;
	269	/* JF added rp>=ritem && I hope to god its right! */
	270	if (rp >= ritem && ISVAR (*rp))
	271	{
	272	/* Downcasting from item_number to symbol_number. */
	273	edge[nedges++] = map_goto (states1[--length],
	274	item_number_as_symbol_number (*rp));
	275	if (nullable[*rp - ntokens])
	276	done = false;
	277	}
	278	}
	279	}
	280
	281	if (nedges == 0)
	282	includes[i] = NULL;
	283	else
	284	{
	285	int j;
	286	includes[i] = xnmalloc (nedges + 1, sizeof includes[i][0]);
	287	for (j = 0; j < nedges; j++)
	288	includes[i][j] = edge[j];
	289	includes[i][nedges] = END_NODE;
	290	}
	291	}
	292
	293	free (edge);
	294	free (states1);
	295
	296	relation_transpose (&includes, ngotos);
	297	}
	298
	299
	300
	301	static void
	302	compute_FOLLOWS (void)
	303	{
	304	goto_number i;
	305
	306	relation_digraph (includes, ngotos, &F);
	307
	308	for (i = 0; i < ngotos; i++)
	309	free (includes[i]);
	310
	311	free (includes);
	312	}
	313
	314
	315	static void
	316	compute_look_ahead_tokens (void)
	317	{
	318	size_t i;
	319	goto_list *sp;
	320
	321	for (i = 0; i < nLA; i++)
	322	for (sp = lookback[i]; sp; sp = sp->next)
	323	bitset_or (LA[i], LA[i], F[sp->value]);
	324
	325	/* Free LOOKBACK. */
	326	for (i = 0; i < nLA; i++)
	327	LIST_FREE (goto_list, lookback[i]);
	328
	329	free (lookback);
	330	bitsetv_free (F);
	331	}
	332
	333
	334	/*-----------------------------------------------------.
	335	\| Count the number of look-ahead tokens required for S \|
	336	\| (N_LOOK_AHEAD_TOKENS member). \|
	337	`-----------------------------------------------------*/
	338
	339	static int
	340	state_look_ahead_tokens_count (state *s)
	341	{
	342	int k;
	343	int n_look_ahead_tokens = 0;
	344	reductions *rp = s->reductions;
	345	transitions *sp = s->transitions;
	346
	347	/* We need a look-ahead either to distinguish different
	348	reductions (i.e., there are two or more), or to distinguish a
	349	reduction from a shift. Otherwise, it is straightforward,
	350	and the state is `consistent'. */
	351	if (rp->num > 1
	352	\|\| (rp->num == 1 && sp->num &&
	353	!TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
	354	n_look_ahead_tokens += rp->num;
	355	else
	356	s->consistent = 1;
	357
	358	for (k = 0; k < sp->num; k++)
	359	if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
	360	{
	361	s->consistent = 0;
	362	break;
	363	}
	364
	365	return n_look_ahead_tokens;
	366	}
	367
	368
	369	/*-----------------------------------------------------.
	370	\| Compute LA, NLA, and the look_ahead_tokens members. \|
	371	`-----------------------------------------------------*/
	372
	373	static void
	374	initialize_LA (void)
	375	{
	376	state_number i;
	377	bitsetv pLA;
	378
	379	/* Compute the total number of reductions requiring a look-ahead. */
	380	nLA = 0;
	381	for (i = 0; i < nstates; i++)
	382	nLA += state_look_ahead_tokens_count (states[i]);
	383	/* Avoid having to special case 0. */
	384	if (!nLA)
	385	nLA = 1;
	386
	387	pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
	388	lookback = xcalloc (nLA, sizeof *lookback);
	389
	390	/* Initialize the members LOOK_AHEAD_TOKENS for each state whose reductions
	391	require look-ahead tokens. */
	392	for (i = 0; i < nstates; i++)
	393	{
	394	int count = state_look_ahead_tokens_count (states[i]);
	395	if (count)
	396	{
	397	states[i]->reductions->look_ahead_tokens = pLA;
	398	pLA += count;
	399	}
	400	}
	401	}
	402
	403
	404	/*----------------------------------------------.
	405	\| Output the look-ahead tokens for each state. \|
	406	`----------------------------------------------*/
	407
	408	static void
	409	look_ahead_tokens_print (FILE *out)
	410	{
	411	state_number i;
	412	int j, k;
	413	fprintf (out, "Look-ahead tokens: BEGIN\n");
	414	for (i = 0; i < nstates; ++i)
	415	{
	416	reductions *reds = states[i]->reductions;
	417	bitset_iterator iter;
	418	int n_look_ahead_tokens = 0;
	419
	420	if (reds->look_ahead_tokens)
	421	for (k = 0; k < reds->num; ++k)
	422	if (reds->look_ahead_tokens[k])
	423	++n_look_ahead_tokens;
	424
	425	fprintf (out, "State %d: %d look-ahead tokens\n",
	426	i, n_look_ahead_tokens);
	427
	428	if (reds->look_ahead_tokens)
	429	for (j = 0; j < reds->num; ++j)
	430	BITSET_FOR_EACH (iter, reds->look_ahead_tokens[j], k, 0)
	431	{
	432	fprintf (out, " on %d (%s) -> rule %d\n",
	433	k, symbols[k]->tag,
	434	reds->rules[j]->number);
	435	};
	436	}
	437	fprintf (out, "Look-ahead tokens: END\n");
	438	}
	439
	440	void
	441	lalr (void)
	442	{
	443	initialize_LA ();
	444	set_goto_map ();
	445	initialize_F ();
	446	build_relations ();
	447	compute_FOLLOWS ();
	448	compute_look_ahead_tokens ();
	449
	450	if (trace_flag & trace_sets)
	451	look_ahead_tokens_print (stderr);
	452	}
	453
	454
	455	void
	456	lalr_free (void)
	457	{
	458	state_number s;
	459	for (s = 0; s < nstates; ++s)
	460	states[s]->reductions->look_ahead_tokens = NULL;
	461	bitsetv_free (LA);
	462	}