src/lalr.c

/* Compute look-ahead criteria for Bison.

   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003
   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 lookahead in each state, and which lookahead
   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 = NULL;
static goto_number ngotos = 0;
state_number *from_state = NULL;
state_number *to_state = NULL;

/* 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;

  CALLOC (goto_map, nvars + 1);
  CALLOC (temp_map, nvars + 1);

  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)
	{
	  if (ngotos >= GOTO_NUMBER_MAXIMUM)
	    abort ();
	  ngotos++;
	  goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	}
    }

  {
    int 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;
  }

  CALLOC (from_state, ngotos);
  CALLOC (to_state, ngotos);

  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)
	{
	  int k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	  from_state[k] = s;
	  to_state[k] = sp->states[i]->number;
	}
    }

  XFREE (temp_map);
}


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

static int
map_goto (state_number s0, symbol_number sym)
{
  int high;
  int low;
  int 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 = CALLOC (reads, ngotos);
  goto_number *edge = CALLOC (edge, ngotos + 1);
  int nedges = 0;

  int 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)
	{
	  CALLOC (reads[i], nedges + 1);
	  memcpy (reads[i], edge, nedges * sizeof (edge[0]));
	  reads[i][nedges] = -1;
	  nedges = 0;
	}
    }

  relation_digraph (reads, ngotos, &F);

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

  XFREE (reads);
  XFREE (edge);
}


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


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

  CALLOC (includes, ngotos);

  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)
	{
	  int j;
	  CALLOC (includes[i], nedges + 1);
	  for (j = 0; j < nedges; j++)
	    includes[i][j] = edge[j];
	  includes[i][nedges] = -1;
	}
    }

  XFREE (edge);
  XFREE (states1);

  relation_transpose (&includes, ngotos);
}


static void
compute_FOLLOWS (void)
{
  int i;

  relation_digraph (includes, ngotos, &F);

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

  XFREE (includes);
}


static void
compute_lookaheads (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]);

  XFREE (lookback);
  bitsetv_free (F);
}


/*-----------------------------------------------------------.
| Count the number of lookaheads required for S (NLOOKAHEADS |
| member).                                                   |
`-----------------------------------------------------------*/

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

  /* 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'.  */
  if (rp->num > 1
      || (rp->num == 1 && sp->num &&
	  !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
    nlookaheads += 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 nlookaheads;
}


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

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

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

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

  /* Initialize the members LOOKAHEADS for each state which reductions
     require lookaheads.  */
  for (i = 0; i < nstates; i++)
    {
      int count = state_lookaheads_count (states[i]);
      if (count)
	{
	  states[i]->reductions->lookaheads = pLA;
	  pLA += count;
	}
    }
}


/*---------------------------------------.
| Output the lookaheads for each state.  |
`---------------------------------------*/

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

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

      fprintf (out, "State %d: %d lookaheads\n",
	       i, nlookaheads);

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

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

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


void
lalr_free (void)
{
  state_number s;
  for (s = 0; s < nstates; ++s)
    states[s]->reductions->lookaheads = 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
	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 lookahead in each state, and which lookahead
	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 = NULL;
	46	static goto_number ngotos = 0;
	47	state_number *from_state = NULL;
	48	state_number *to_state = NULL;
	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	CALLOC (goto_map, nvars + 1);
	84	CALLOC (temp_map, nvars + 1);
	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	if (ngotos >= GOTO_NUMBER_MAXIMUM)
	94	abort ();
	95	ngotos++;
	96	goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	97	}
	98	}
	99
	100	{
	101	int k = 0;
	102	int i;
	103	for (i = ntokens; i < nsyms; i++)
	104	{
	105	temp_map[i - ntokens] = k;
	106	k += goto_map[i - ntokens];
	107	}
	108
	109	for (i = ntokens; i < nsyms; i++)
	110	goto_map[i - ntokens] = temp_map[i - ntokens];
	111
	112	goto_map[nsyms - ntokens] = ngotos;
	113	temp_map[nsyms - ntokens] = ngotos;
	114	}
	115
	116	CALLOC (from_state, ngotos);
	117	CALLOC (to_state, ngotos);
	118
	119	for (s = 0; s < nstates; ++s)
	120	{
	121	transitions *sp = states[s]->transitions;
	122	int i;
	123	for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
	124	{
	125	int k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
	126	from_state[k] = s;
	127	to_state[k] = sp->states[i]->number;
	128	}
	129	}
	130
	131	XFREE (temp_map);
	132	}
	133
	134
	135
	136	/*----------------------------------------------------------.
	137	\| Map a state/symbol pair into its numeric representation. \|
	138	`----------------------------------------------------------*/
	139
	140	static int
	141	map_goto (state_number s0, symbol_number sym)
	142	{
	143	int high;
	144	int low;
	145	int middle;
	146	state_number s;
	147
	148	low = goto_map[sym - ntokens];
	149	high = goto_map[sym - ntokens + 1] - 1;
	150
	151	for (;;)
	152	{
	153	if (high < low)
	154	abort ();
	155	middle = (low + high) / 2;
	156	s = from_state[middle];
	157	if (s == s0)
	158	return middle;
	159	else if (s < s0)
	160	low = middle + 1;
	161	else
	162	high = middle - 1;
	163	}
	164	}
	165
	166
	167	static void
	168	initialize_F (void)
	169	{
	170	goto_number **reads = CALLOC (reads, ngotos);
	171	goto_number *edge = CALLOC (edge, ngotos + 1);
	172	int nedges = 0;
	173
	174	int i;
	175
	176	F = bitsetv_create (ngotos, ntokens, BITSET_FIXED);
	177
	178	for (i = 0; i < ngotos; i++)
	179	{
	180	state_number stateno = to_state[i];
	181	transitions *sp = states[stateno]->transitions;
	182
	183	int j;
	184	FOR_EACH_SHIFT (sp, j)
	185	bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
	186
	187	for (; j < sp->num; j++)
	188	{
	189	symbol_number sym = TRANSITION_SYMBOL (sp, j);
	190	if (nullable[sym - ntokens])
	191	edge[nedges++] = map_goto (stateno, sym);
	192	}
	193
	194	if (nedges)
	195	{
	196	CALLOC (reads[i], nedges + 1);
	197	memcpy (reads[i], edge, nedges * sizeof (edge[0]));
	198	reads[i][nedges] = -1;
	199	nedges = 0;
	200	}
	201	}
	202
	203	relation_digraph (reads, ngotos, &F);
	204
	205	for (i = 0; i < ngotos; i++)
	206	XFREE (reads[i]);
	207
	208	XFREE (reads);
	209	XFREE (edge);
	210	}
	211
	212
	213	static void
	214	add_lookback_edge (state s, rule r, int gotono)
	215	{
	216	int ri = state_reduction_find (s, r);
	217	goto_list *sp = MALLOC (sp, 1);
	218	sp->next = lookback[(s->reductions->lookaheads - LA) + ri];
	219	sp->value = gotono;
	220	lookback[(s->reductions->lookaheads - LA) + ri] = sp;
	221	}
	222
	223
	224
	225	static void
	226	build_relations (void)
	227	{
	228	goto_number *edge = CALLOC (edge, ngotos + 1);
	229	state_number *states1 = CALLOC (states1, ritem_longest_rhs () + 1);
	230	int i;
	231
	232	CALLOC (includes, ngotos);
	233
	234	for (i = 0; i < ngotos; i++)
	235	{
	236	int nedges = 0;
	237	symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
	238	rule **rulep;
	239
	240	for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)
	241	{
	242	bool done;
	243	int length = 1;
	244	item_number *rp;
	245	state *s = states[from_state[i]];
	246	states1[0] = s->number;
	247
	248	for (rp = (rulep)->rhs; rp >= 0; rp++)
	249	{
	250	s = transitions_to (s->transitions,
	251	item_number_as_symbol_number (*rp));
	252	states1[length++] = s->number;
	253	}
	254
	255	if (!s->consistent)
	256	add_lookback_edge (s, *rulep, i);
	257
	258	length--;
	259	done = false;
	260	while (!done)
	261	{
	262	done = true;
	263	rp--;
	264	/* JF added rp>=ritem && I hope to god its right! */
	265	if (rp >= ritem && ISVAR (*rp))
	266	{
	267	/* Downcasting from item_number to symbol_number. */
	268	edge[nedges++] = map_goto (states1[--length],
	269	item_number_as_symbol_number (*rp));
	270	if (nullable[*rp - ntokens])
	271	done = false;
	272	}
	273	}
	274	}
	275
	276	if (nedges)
	277	{
	278	int j;
	279	CALLOC (includes[i], nedges + 1);
	280	for (j = 0; j < nedges; j++)
	281	includes[i][j] = edge[j];
	282	includes[i][nedges] = -1;
	283	}
	284	}
	285
	286	XFREE (edge);
	287	XFREE (states1);
	288
	289	relation_transpose (&includes, ngotos);
	290	}
	291
	292
	293
	294	static void
	295	compute_FOLLOWS (void)
	296	{
	297	int i;
	298
	299	relation_digraph (includes, ngotos, &F);
	300
	301	for (i = 0; i < ngotos; i++)
	302	XFREE (includes[i]);
	303
	304	XFREE (includes);
	305	}
	306
	307
	308	static void
	309	compute_lookaheads (void)
	310	{
	311	size_t i;
	312	goto_list *sp;
	313
	314	for (i = 0; i < nLA; i++)
	315	for (sp = lookback[i]; sp; sp = sp->next)
	316	bitset_or (LA[i], LA[i], F[sp->value]);
	317
	318	/* Free LOOKBACK. */
	319	for (i = 0; i < nLA; i++)
	320	LIST_FREE (goto_list, lookback[i]);
	321
	322	XFREE (lookback);
	323	bitsetv_free (F);
	324	}
	325
	326
	327	/*-----------------------------------------------------------.
	328	\| Count the number of lookaheads required for S (NLOOKAHEADS \|
	329	\| member). \|
	330	`-----------------------------------------------------------*/
	331
	332	static int
	333	state_lookaheads_count (state *s)
	334	{
	335	int k;
	336	int nlookaheads = 0;
	337	reductions *rp = s->reductions;
	338	transitions *sp = s->transitions;
	339
	340	/* We need a lookahead either to distinguish different
	341	reductions (i.e., there are two or more), or to distinguish a
	342	reduction from a shift. Otherwise, it is straightforward,
	343	and the state is `consistent'. */
	344	if (rp->num > 1
	345	\|\| (rp->num == 1 && sp->num &&
	346	!TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
	347	nlookaheads += rp->num;
	348	else
	349	s->consistent = 1;
	350
	351	for (k = 0; k < sp->num; k++)
	352	if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
	353	{
	354	s->consistent = 0;
	355	break;
	356	}
	357
	358	return nlookaheads;
	359	}
	360
	361
	362	/*----------------------------------------------.
	363	\| Compute LA, NLA, and the lookaheads members. \|
	364	`----------------------------------------------*/
	365
	366	static void
	367	initialize_LA (void)
	368	{
	369	state_number i;
	370	bitsetv pLA;
	371
	372	/* Compute the total number of reductions requiring a lookahead. */
	373	nLA = 0;
	374	for (i = 0; i < nstates; i++)
	375	nLA += state_lookaheads_count (states[i]);
	376	/* Avoid having to special case 0. */
	377	if (!nLA)
	378	nLA = 1;
	379
	380	pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
	381	CALLOC (lookback, nLA);
	382
	383	/* Initialize the members LOOKAHEADS for each state which reductions
	384	require lookaheads. */
	385	for (i = 0; i < nstates; i++)
	386	{
	387	int count = state_lookaheads_count (states[i]);
	388	if (count)
	389	{
	390	states[i]->reductions->lookaheads = pLA;
	391	pLA += count;
	392	}
	393	}
	394	}
	395
	396
	397	/*---------------------------------------.
	398	\| Output the lookaheads for each state. \|
	399	`---------------------------------------*/
	400
	401	static void
	402	lookaheads_print (FILE *out)
	403	{
	404	state_number i;
	405	int j, k;
	406	fprintf (out, "Lookaheads: BEGIN\n");
	407	for (i = 0; i < nstates; ++i)
	408	{
	409	reductions *reds = states[i]->reductions;
	410	bitset_iterator iter;
	411	int nlookaheads = 0;
	412
	413	if (reds->lookaheads)
	414	for (k = 0; k < reds->num; ++k)
	415	if (reds->lookaheads[k])
	416	++nlookaheads;
	417
	418	fprintf (out, "State %d: %d lookaheads\n",
	419	i, nlookaheads);
	420
	421	if (reds->lookaheads)
	422	for (j = 0; j < reds->num; ++j)
	423	BITSET_FOR_EACH (iter, reds->lookaheads[j], k, 0)
	424	{
	425	fprintf (out, " on %d (%s) -> rule %d\n",
	426	k, symbols[k]->tag,
	427	reds->rules[j]->number);
	428	};
	429	}
	430	fprintf (out, "Lookaheads: END\n");
	431	}
	432
	433	void
	434	lalr (void)
	435	{
	436	initialize_LA ();
	437	set_goto_map ();
	438	initialize_F ();
	439	build_relations ();
	440	compute_FOLLOWS ();
	441	compute_lookaheads ();
	442
	443	if (trace_flag & trace_sets)
	444	lookaheads_print (stderr);
	445	}
	446
	447
	448	void
	449	lalr_free (void)
	450	{
	451	state_number s;
	452	for (s = 0; s < nstates; ++s)
	453	states[s]->reductions->lookaheads = NULL;
	454	bitsetv_free (LA);
	455	}