src/conflicts.c

/* Find and resolve or report look-ahead conflicts for bison,

   Copyright (C) 1984, 1989, 1992, 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.  */

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

#include <bitset.h>

#include "LR0.h"
#include "complain.h"
#include "conflicts.h"
#include "files.h"
#include "getargs.h"
#include "gram.h"
#include "lalr.h"
#include "reader.h"
#include "state.h"
#include "symtab.h"

/* -1 stands for not specified. */
int expected_sr_conflicts = -1;
int expected_rr_conflicts = -1;
static char *conflicts;
struct obstack solved_conflicts_obstack;

static bitset shift_set;
static bitset look_ahead_set;

\f

enum conflict_resolution
  {
    shift_resolution,
    reduce_resolution,
    left_resolution,
    right_resolution,
    nonassoc_resolution
  };


/*----------------------------------------------------------------.
| Explain how an SR conflict between TOKEN and RULE was resolved: |
| RESOLUTION.                                                     |
`----------------------------------------------------------------*/

static inline void
log_resolution (rule *r, symbol_number token,
		enum conflict_resolution resolution)
{
  if (report_flag & report_solved_conflicts)
    {
      /* The description of the resolution. */
      switch (resolution)
	{
	case shift_resolution:
	case right_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as shift"),
			  r->number,
			  symbols[token]->tag);
	  break;
	case reduce_resolution:
	case left_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as reduce"),
			  r->number,
			  symbols[token]->tag);
	  break;
	case nonassoc_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  _("\
    Conflict between rule %d and token %s resolved as an error"),
			  r->number,
			  symbols[token]->tag);
	  break;
	}

      /* The reason. */
      switch (resolution)
	{
	case shift_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  " (%s < %s)",
			  r->prec->tag,
			  symbols[token]->tag);
	  break;

	case reduce_resolution:
	  obstack_fgrow2 (&solved_conflicts_obstack,
			  " (%s < %s)",
			  symbols[token]->tag,
			  r->prec->tag);
	  break;

	case left_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%left %s)",
			  symbols[token]->tag);
	  break;

	case right_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%right %s)",
			  symbols[token]->tag);
	  break;
	case nonassoc_resolution:
	  obstack_fgrow1 (&solved_conflicts_obstack,
			  " (%%nonassoc %s)",
			  symbols[token]->tag);
	  break;
	}
      obstack_sgrow (&solved_conflicts_obstack, ".\n");
    }
}


/*------------------------------------------------------------------.
| Turn off the shift recorded for the specified token in the        |
| specified state.  Used when we resolve a shift-reduce conflict in |
| favor of the reduction.                                           |
`------------------------------------------------------------------*/

static void
flush_shift (state *s, int token)
{
  transitions *trans = s->transitions;
  int i;

  bitset_reset (look_ahead_set, token);
  for (i = 0; i < trans->num; i++)
    if (!TRANSITION_IS_DISABLED (trans, i)
	&& TRANSITION_SYMBOL (trans, i) == token)
      TRANSITION_DISABLE (trans, i);
}


/*--------------------------------------------------------------------.
| Turn off the reduce recorded for the specified token for the        |
| specified look-ahead.  Used when we resolve a shift-reduce conflict |
| in favor of the shift.                                              |
`--------------------------------------------------------------------*/

static void
flush_reduce (bitset look_ahead_tokens, int token)
{
  bitset_reset (look_ahead_tokens, token);
}


/*------------------------------------------------------------------.
| Attempt to resolve shift-reduce conflict for one rule by means of |
| precedence declarations.  It has already been checked that the    |
| rule has a precedence.  A conflict is resolved by modifying the   |
| shift or reduce tables so that there is no longer a conflict.     |
|                                                                   |
| RULENO is the number of the look-ahead bitset to consider.      |
|                                                                   |
| ERRORS can be used to store discovered explicit errors.           |
`------------------------------------------------------------------*/

static void
resolve_sr_conflict (state *s, int ruleno, symbol **errors)
{
  symbol_number i;
  reductions *reds = s->reductions;
  /* Find the rule to reduce by to get precedence of reduction.  */
  rule *redrule = reds->rules[ruleno];
  int redprec = redrule->prec->prec;
  bitset look_ahead_tokens = reds->look_ahead_tokens[ruleno];
  int nerrs = 0;

  for (i = 0; i < ntokens; i++)
    if (bitset_test (look_ahead_tokens, i)
	&& bitset_test (look_ahead_set, i)
	&& symbols[i]->prec)
      {
	/* Shift-reduce conflict occurs for token number i
	   and it has a precedence.
	   The precedence of shifting is that of token i.  */
	if (symbols[i]->prec < redprec)
	  {
	    log_resolution (redrule, i, reduce_resolution);
	    flush_shift (s, i);
	  }
	else if (symbols[i]->prec > redprec)
	  {
	    log_resolution (redrule, i, shift_resolution);
	    flush_reduce (look_ahead_tokens, i);
	  }
	else
	  /* Matching precedence levels.
	     For left association, keep only the reduction.
	     For right association, keep only the shift.
	     For nonassociation, keep neither.  */

	  switch (symbols[i]->assoc)
	    {
	    default:
	      abort ();

	    case right_assoc:
	      log_resolution (redrule, i, right_resolution);
	      flush_reduce (look_ahead_tokens, i);
	      break;

	    case left_assoc:
	      log_resolution (redrule, i, left_resolution);
	      flush_shift (s, i);
	      break;

	    case non_assoc:
	      log_resolution (redrule, i, nonassoc_resolution);
	      flush_shift (s, i);
	      flush_reduce (look_ahead_tokens, i);
	      /* Record an explicit error for this token.  */
	      errors[nerrs++] = symbols[i];
	      break;
	    }
      }

  if (nerrs)
    {
      /* Some tokens have been explicitly made errors.  Allocate a
	 permanent errs structure for this state, to record them.  */
      state_errs_set (s, nerrs, errors);
    }

  if (obstack_object_size (&solved_conflicts_obstack))
    {
      obstack_1grow (&solved_conflicts_obstack, '\0');
      s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
    }
}


/*-------------------------------------------------------------------.
| Solve the S/R conflicts of state S using the                       |
| precedence/associativity, and flag it inconsistent if it still has |
| conflicts.  ERRORS can be used as storage to compute the list of   |
| look-ahead tokens on which S raises a syntax error (%nonassoc).    |
`-------------------------------------------------------------------*/

static void
set_conflicts (state *s, symbol **errors)
{
  int i;
  transitions *trans = s->transitions;
  reductions *reds = s->reductions;

  if (s->consistent)
    return;

  bitset_zero (look_ahead_set);

  FOR_EACH_SHIFT (trans, i)
    bitset_set (look_ahead_set, TRANSITION_SYMBOL (trans, i));

  /* Loop over all rules which require look-ahead in this state.  First
     check for shift-reduce conflict, and try to resolve using
     precedence.  */
  for (i = 0; i < reds->num; ++i)
    if (reds->rules[i]->prec && reds->rules[i]->prec->prec
	&& !bitset_disjoint_p (reds->look_ahead_tokens[i], look_ahead_set))
      resolve_sr_conflict (s, i, errors);

  /* Loop over all rules which require look-ahead in this state.  Check
     for conflicts not resolved above.  */
  for (i = 0; i < reds->num; ++i)
    {
      if (!bitset_disjoint_p (reds->look_ahead_tokens[i], look_ahead_set))
	conflicts[s->number] = 1;

      bitset_or (look_ahead_set, look_ahead_set, reds->look_ahead_tokens[i]);
    }
}


/*----------------------------------------------------------------.
| Solve all the S/R conflicts using the precedence/associativity, |
| and flag as inconsistent the states that still have conflicts.  |
`----------------------------------------------------------------*/

void
conflicts_solve (void)
{
  state_number i;
  /* List of look-ahead tokens on which we explicitly raise a syntax error.  */
  symbol **errors = xnmalloc (ntokens + 1, sizeof *errors);

  conflicts = xcalloc (nstates, sizeof *conflicts);
  shift_set = bitset_create (ntokens, BITSET_FIXED);
  look_ahead_set = bitset_create (ntokens, BITSET_FIXED);
  obstack_init (&solved_conflicts_obstack);

  for (i = 0; i < nstates; i++)
    {
      set_conflicts (states[i], errors);

      /* For uniformity of the code, make sure all the states have a valid
	 `errs' member.  */
      if (!states[i]->errs)
	states[i]->errs = errs_new (0, 0);
    }

  free (errors);
}


/*---------------------------------------------.
| Count the number of shift/reduce conflicts.  |
`---------------------------------------------*/

static int
count_sr_conflicts (state *s)
{
  int i;
  int src_count = 0;
  transitions *trans = s->transitions;
  reductions *reds = s->reductions;

  if (!trans)
    return 0;

  bitset_zero (look_ahead_set);
  bitset_zero (shift_set);

  FOR_EACH_SHIFT (trans, i)
    bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));

  for (i = 0; i < reds->num; ++i)
    bitset_or (look_ahead_set, look_ahead_set, reds->look_ahead_tokens[i]);

  bitset_and (look_ahead_set, look_ahead_set, shift_set);

  src_count = bitset_count (look_ahead_set);

  return src_count;
}


/*----------------------------------------------------------------.
| Count the number of reduce/reduce conflicts.  If ONE_PER_TOKEN, |
| count one conflict for each token that has any reduce/reduce    |
| conflicts.  Otherwise, count one conflict for each pair of      |
| conflicting reductions.                                         |
+`----------------------------------------------------------------*/

static int
count_rr_conflicts (state *s, bool one_per_token)
{
  int i;
  reductions *reds = s->reductions;
  int rrc_count = 0;

  for (i = 0; i < ntokens; i++)
    {
      int count = 0;
      int j;
      for (j = 0; j < reds->num; ++j)
	if (bitset_test (reds->look_ahead_tokens[j], i))
	  count++;

      if (count >= 2)
	rrc_count += one_per_token ? 1 : count-1;
    }

  return rrc_count;
}


/*--------------------------------------------------------.
| Report the number of conflicts, using the Yacc format.  |
`--------------------------------------------------------*/

static void
conflict_report (FILE *out, int src_num, int rrc_num)
{
  if (src_num && rrc_num)
    fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
	     src_num, rrc_num);
  else if (src_num)
    fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
  else if (rrc_num)
    fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
}


/*-----------------------------------------------------------.
| Output the detailed description of states with conflicts.  |
`-----------------------------------------------------------*/

void
conflicts_output (FILE *out)
{
  bool printed_sth = false;
  state_number i;
  for (i = 0; i < nstates; i++)
    {
      state *s = states[i];
      if (conflicts[i])
	{
	  fprintf (out, _("State %d "), i);
	  conflict_report (out, count_sr_conflicts (s),
			   count_rr_conflicts (s, true));
	  printed_sth = true;
	}
    }
  if (printed_sth)
    fputs ("\n\n", out);
}

/*--------------------------------------------------------.
| Total the number of S/R and R/R conflicts.  Unlike the  |
| code in conflicts_output, however, count EACH pair of   |
| reductions for the same state and look-ahead as one     |
| conflict.						  |
`--------------------------------------------------------*/

int
conflicts_total_count (void)
{
  state_number i;
  int count;

  /* Conflicts by state.  */
  count = 0;
  for (i = 0; i < nstates; i++)
    if (conflicts[i])
      {
	count += count_sr_conflicts (states[i]);
	count += count_rr_conflicts (states[i], false);
      }
  return count;
}


/*------------------------------------------.
| Reporting the total number of conflicts.  |
`------------------------------------------*/

void
conflicts_print (void)
{
  /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
     not set, and then we want 0 SR, or else it is specified, in which
     case we want equality.  */
  bool src_ok;
  bool rrc_ok;

  int src_total = 0;
  int rrc_total = 0;
  int src_expected;
  int rrc_expected;

  /* Conflicts by state.  */
  {
    state_number i;

    for (i = 0; i < nstates; i++)
      if (conflicts[i])
	{
	  src_total += count_sr_conflicts (states[i]);
	  rrc_total += count_rr_conflicts (states[i], true);
	}
  }

  if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
    {
      warn (_("%%expect-rr applies only to GLR parsers"));
      expected_rr_conflicts = -1;
    }

  src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
  rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
  src_ok = src_total == src_expected;
  rrc_ok = rrc_total == rrc_expected;

  /* If there are as many RR conflicts and SR conflicts as
     expected, then there is nothing to report.  */
  if (rrc_ok & src_ok)
    return;

  /* Report the total number of conflicts on STDERR.  */
  if (src_total | rrc_total)
    {
      if (! yacc_flag)
	fprintf (stderr, "%s: ", current_file);
      conflict_report (stderr, src_total, rrc_total);
    }

  if (expected_sr_conflicts != -1 || expected_rr_conflicts != -1)
    {
      if (! src_ok)
	complain (ngettext ("expected %d shift/reduce conflict",
			    "expected %d shift/reduce conflicts",
			    src_expected),
		  src_expected);
      if (! rrc_ok)
	complain (ngettext ("expected %d reduce/reduce conflict",
			    "expected %d reduce/reduce conflicts",
			    rrc_expected),
		  rrc_expected);
    }
}


void
conflicts_free (void)
{
  free (conflicts);
  bitset_free (shift_set);
  bitset_free (look_ahead_set);
  obstack_free (&solved_conflicts_obstack, NULL);
}
Commit	Line	Data
	1	/* Find and resolve or report look-ahead conflicts for bison,
	2
	3	Copyright (C) 1984, 1989, 1992, 2000, 2001, 2002, 2003, 2004, 2005, 2006
	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 it
	9	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, but
	14	WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	16	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 the Free
	20	Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
	21	02110-1301, USA. */
	22
	23	#include <config.h>
	24	#include "system.h"
	25
	26	#include <bitset.h>
	27
	28	#include "LR0.h"
	29	#include "complain.h"
	30	#include "conflicts.h"
	31	#include "files.h"
	32	#include "getargs.h"
	33	#include "gram.h"
	34	#include "lalr.h"
	35	#include "reader.h"
	36	#include "state.h"
	37	#include "symtab.h"
	38
	39	/* -1 stands for not specified. */
	40	int expected_sr_conflicts = -1;
	41	int expected_rr_conflicts = -1;
	42	static char *conflicts;
	43	struct obstack solved_conflicts_obstack;
	44
	45	static bitset shift_set;
	46	static bitset look_ahead_set;
	47
	48	\f
	49
	50	enum conflict_resolution
	51	{
	52	shift_resolution,
	53	reduce_resolution,
	54	left_resolution,
	55	right_resolution,
	56	nonassoc_resolution
	57	};
	58
	59
	60	/*----------------------------------------------------------------.
	61	\| Explain how an SR conflict between TOKEN and RULE was resolved: \|
	62	\| RESOLUTION. \|
	63	`----------------------------------------------------------------*/
	64
	65	static inline void
	66	log_resolution (rule *r, symbol_number token,
	67	enum conflict_resolution resolution)
	68	{
	69	if (report_flag & report_solved_conflicts)
	70	{
	71	/* The description of the resolution. */
	72	switch (resolution)
	73	{
	74	case shift_resolution:
	75	case right_resolution:
	76	obstack_fgrow2 (&solved_conflicts_obstack,
	77	_("\
	78	Conflict between rule %d and token %s resolved as shift"),
	79	r->number,
	80	symbols[token]->tag);
	81	break;
	82	case reduce_resolution:
	83	case left_resolution:
	84	obstack_fgrow2 (&solved_conflicts_obstack,
	85	_("\
	86	Conflict between rule %d and token %s resolved as reduce"),
	87	r->number,
	88	symbols[token]->tag);
	89	break;
	90	case nonassoc_resolution:
	91	obstack_fgrow2 (&solved_conflicts_obstack,
	92	_("\
	93	Conflict between rule %d and token %s resolved as an error"),
	94	r->number,
	95	symbols[token]->tag);
	96	break;
	97	}
	98
	99	/* The reason. */
	100	switch (resolution)
	101	{
	102	case shift_resolution:
	103	obstack_fgrow2 (&solved_conflicts_obstack,
	104	" (%s < %s)",
	105	r->prec->tag,
	106	symbols[token]->tag);
	107	break;
	108
	109	case reduce_resolution:
	110	obstack_fgrow2 (&solved_conflicts_obstack,
	111	" (%s < %s)",
	112	symbols[token]->tag,
	113	r->prec->tag);
	114	break;
	115
	116	case left_resolution:
	117	obstack_fgrow1 (&solved_conflicts_obstack,
	118	" (%%left %s)",
	119	symbols[token]->tag);
	120	break;
	121
	122	case right_resolution:
	123	obstack_fgrow1 (&solved_conflicts_obstack,
	124	" (%%right %s)",
	125	symbols[token]->tag);
	126	break;
	127	case nonassoc_resolution:
	128	obstack_fgrow1 (&solved_conflicts_obstack,
	129	" (%%nonassoc %s)",
	130	symbols[token]->tag);
	131	break;
	132	}
	133	obstack_sgrow (&solved_conflicts_obstack, ".\n");
	134	}
	135	}
	136
	137
	138	/*------------------------------------------------------------------.
	139	\| Turn off the shift recorded for the specified token in the \|
	140	\| specified state. Used when we resolve a shift-reduce conflict in \|
	141	\| favor of the reduction. \|
	142	`------------------------------------------------------------------*/
	143
	144	static void
	145	flush_shift (state *s, int token)
	146	{
	147	transitions *trans = s->transitions;
	148	int i;
	149
	150	bitset_reset (look_ahead_set, token);
	151	for (i = 0; i < trans->num; i++)
	152	if (!TRANSITION_IS_DISABLED (trans, i)
	153	&& TRANSITION_SYMBOL (trans, i) == token)
	154	TRANSITION_DISABLE (trans, i);
	155	}
	156
	157
	158	/*--------------------------------------------------------------------.
	159	\| Turn off the reduce recorded for the specified token for the \|
	160	\| specified look-ahead. Used when we resolve a shift-reduce conflict \|
	161	\| in favor of the shift. \|
	162	`--------------------------------------------------------------------*/
	163
	164	static void
	165	flush_reduce (bitset look_ahead_tokens, int token)
	166	{
	167	bitset_reset (look_ahead_tokens, token);
	168	}
	169
	170
	171	/*------------------------------------------------------------------.
	172	\| Attempt to resolve shift-reduce conflict for one rule by means of \|
	173	\| precedence declarations. It has already been checked that the \|
	174	\| rule has a precedence. A conflict is resolved by modifying the \|
	175	\| shift or reduce tables so that there is no longer a conflict. \|
	176	\| \|
	177	\| RULENO is the number of the look-ahead bitset to consider. \|
	178	\| \|
	179	\| ERRORS can be used to store discovered explicit errors. \|
	180	`------------------------------------------------------------------*/
	181
	182	static void
	183	resolve_sr_conflict (state s, int ruleno, symbol *errors)
	184	{
	185	symbol_number i;
	186	reductions *reds = s->reductions;
	187	/* Find the rule to reduce by to get precedence of reduction. */
	188	rule *redrule = reds->rules[ruleno];
	189	int redprec = redrule->prec->prec;
	190	bitset look_ahead_tokens = reds->look_ahead_tokens[ruleno];
	191	int nerrs = 0;
	192
	193	for (i = 0; i < ntokens; i++)
	194	if (bitset_test (look_ahead_tokens, i)
	195	&& bitset_test (look_ahead_set, i)
	196	&& symbols[i]->prec)
	197	{
	198	/* Shift-reduce conflict occurs for token number i
	199	and it has a precedence.
	200	The precedence of shifting is that of token i. */
	201	if (symbols[i]->prec < redprec)
	202	{
	203	log_resolution (redrule, i, reduce_resolution);
	204	flush_shift (s, i);
	205	}
	206	else if (symbols[i]->prec > redprec)
	207	{
	208	log_resolution (redrule, i, shift_resolution);
	209	flush_reduce (look_ahead_tokens, i);
	210	}
	211	else
	212	/* Matching precedence levels.
	213	For left association, keep only the reduction.
	214	For right association, keep only the shift.
	215	For nonassociation, keep neither. */
	216
	217	switch (symbols[i]->assoc)
	218	{
	219	default:
	220	abort ();
	221
	222	case right_assoc:
	223	log_resolution (redrule, i, right_resolution);
	224	flush_reduce (look_ahead_tokens, i);
	225	break;
	226
	227	case left_assoc:
	228	log_resolution (redrule, i, left_resolution);
	229	flush_shift (s, i);
	230	break;
	231
	232	case non_assoc:
	233	log_resolution (redrule, i, nonassoc_resolution);
	234	flush_shift (s, i);
	235	flush_reduce (look_ahead_tokens, i);
	236	/* Record an explicit error for this token. */
	237	errors[nerrs++] = symbols[i];
	238	break;
	239	}
	240	}
	241
	242	if (nerrs)
	243	{
	244	/* Some tokens have been explicitly made errors. Allocate a
	245	permanent errs structure for this state, to record them. */
	246	state_errs_set (s, nerrs, errors);
	247	}
	248
	249	if (obstack_object_size (&solved_conflicts_obstack))
	250	{
	251	obstack_1grow (&solved_conflicts_obstack, '\0');
	252	s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
	253	}
	254	}
	255
	256
	257	/*-------------------------------------------------------------------.
	258	\| Solve the S/R conflicts of state S using the \|
	259	\| precedence/associativity, and flag it inconsistent if it still has \|
	260	\| conflicts. ERRORS can be used as storage to compute the list of \|
	261	\| look-ahead tokens on which S raises a syntax error (%nonassoc). \|
	262	`-------------------------------------------------------------------*/
	263
	264	static void
	265	set_conflicts (state s, symbol *errors)
	266	{
	267	int i;
	268	transitions *trans = s->transitions;
	269	reductions *reds = s->reductions;
	270
	271	if (s->consistent)
	272	return;
	273
	274	bitset_zero (look_ahead_set);
	275
	276	FOR_EACH_SHIFT (trans, i)
	277	bitset_set (look_ahead_set, TRANSITION_SYMBOL (trans, i));
	278
	279	/* Loop over all rules which require look-ahead in this state. First
	280	check for shift-reduce conflict, and try to resolve using
	281	precedence. */
	282	for (i = 0; i < reds->num; ++i)
	283	if (reds->rules[i]->prec && reds->rules[i]->prec->prec
	284	&& !bitset_disjoint_p (reds->look_ahead_tokens[i], look_ahead_set))
	285	resolve_sr_conflict (s, i, errors);
	286
	287	/* Loop over all rules which require look-ahead in this state. Check
	288	for conflicts not resolved above. */
	289	for (i = 0; i < reds->num; ++i)
	290	{
	291	if (!bitset_disjoint_p (reds->look_ahead_tokens[i], look_ahead_set))
	292	conflicts[s->number] = 1;
	293
	294	bitset_or (look_ahead_set, look_ahead_set, reds->look_ahead_tokens[i]);
	295	}
	296	}
	297
	298
	299	/*----------------------------------------------------------------.
	300	\| Solve all the S/R conflicts using the precedence/associativity, \|
	301	\| and flag as inconsistent the states that still have conflicts. \|
	302	`----------------------------------------------------------------*/
	303
	304	void
	305	conflicts_solve (void)
	306	{
	307	state_number i;
	308	/* List of look-ahead tokens on which we explicitly raise a syntax error. */
	309	symbol *errors = xnmalloc (ntokens + 1, sizeof errors);
	310
	311	conflicts = xcalloc (nstates, sizeof *conflicts);
	312	shift_set = bitset_create (ntokens, BITSET_FIXED);
	313	look_ahead_set = bitset_create (ntokens, BITSET_FIXED);
	314	obstack_init (&solved_conflicts_obstack);
	315
	316	for (i = 0; i < nstates; i++)
	317	{
	318	set_conflicts (states[i], errors);
	319
	320	/* For uniformity of the code, make sure all the states have a valid
	321	`errs' member. */
	322	if (!states[i]->errs)
	323	states[i]->errs = errs_new (0, 0);
	324	}
	325
	326	free (errors);
	327	}
	328
	329
	330	/*---------------------------------------------.
	331	\| Count the number of shift/reduce conflicts. \|
	332	`---------------------------------------------*/
	333
	334	static int
	335	count_sr_conflicts (state *s)
	336	{
	337	int i;
	338	int src_count = 0;
	339	transitions *trans = s->transitions;
	340	reductions *reds = s->reductions;
	341
	342	if (!trans)
	343	return 0;
	344
	345	bitset_zero (look_ahead_set);
	346	bitset_zero (shift_set);
	347
	348	FOR_EACH_SHIFT (trans, i)
	349	bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
	350
	351	for (i = 0; i < reds->num; ++i)
	352	bitset_or (look_ahead_set, look_ahead_set, reds->look_ahead_tokens[i]);
	353
	354	bitset_and (look_ahead_set, look_ahead_set, shift_set);
	355
	356	src_count = bitset_count (look_ahead_set);
	357
	358	return src_count;
	359	}
	360
	361
	362	/*----------------------------------------------------------------.
	363	\| Count the number of reduce/reduce conflicts. If ONE_PER_TOKEN, \|
	364	\| count one conflict for each token that has any reduce/reduce \|
	365	\| conflicts. Otherwise, count one conflict for each pair of \|
	366	\| conflicting reductions. \|
	367	+`----------------------------------------------------------------*/
	368
	369	static int
	370	count_rr_conflicts (state *s, bool one_per_token)
	371	{
	372	int i;
	373	reductions *reds = s->reductions;
	374	int rrc_count = 0;
	375
	376	for (i = 0; i < ntokens; i++)
	377	{
	378	int count = 0;
	379	int j;
	380	for (j = 0; j < reds->num; ++j)
	381	if (bitset_test (reds->look_ahead_tokens[j], i))
	382	count++;
	383
	384	if (count >= 2)
	385	rrc_count += one_per_token ? 1 : count-1;
	386	}
	387
	388	return rrc_count;
	389	}
	390
	391
	392	/*--------------------------------------------------------.
	393	\| Report the number of conflicts, using the Yacc format. \|
	394	`--------------------------------------------------------*/
	395
	396	static void
	397	conflict_report (FILE *out, int src_num, int rrc_num)
	398	{
	399	if (src_num && rrc_num)
	400	fprintf (out, _("conflicts: %d shift/reduce, %d reduce/reduce\n"),
	401	src_num, rrc_num);
	402	else if (src_num)
	403	fprintf (out, _("conflicts: %d shift/reduce\n"), src_num);
	404	else if (rrc_num)
	405	fprintf (out, _("conflicts: %d reduce/reduce\n"), rrc_num);
	406	}
	407
	408
	409	/*-----------------------------------------------------------.
	410	\| Output the detailed description of states with conflicts. \|
	411	`-----------------------------------------------------------*/
	412
	413	void
	414	conflicts_output (FILE *out)
	415	{
	416	bool printed_sth = false;
	417	state_number i;
	418	for (i = 0; i < nstates; i++)
	419	{
	420	state *s = states[i];
	421	if (conflicts[i])
	422	{
	423	fprintf (out, _("State %d "), i);
	424	conflict_report (out, count_sr_conflicts (s),
	425	count_rr_conflicts (s, true));
	426	printed_sth = true;
	427	}
	428	}
	429	if (printed_sth)
	430	fputs ("\n\n", out);
	431	}
	432
	433	/*--------------------------------------------------------.
	434	\| Total the number of S/R and R/R conflicts. Unlike the \|
	435	\| code in conflicts_output, however, count EACH pair of \|
	436	\| reductions for the same state and look-ahead as one \|
	437	\| conflict. \|
	438	`--------------------------------------------------------*/
	439
	440	int
	441	conflicts_total_count (void)
	442	{
	443	state_number i;
	444	int count;
	445
	446	/* Conflicts by state. */
	447	count = 0;
	448	for (i = 0; i < nstates; i++)
	449	if (conflicts[i])
	450	{
	451	count += count_sr_conflicts (states[i]);
	452	count += count_rr_conflicts (states[i], false);
	453	}
	454	return count;
	455	}
	456
	457
	458	/*------------------------------------------.
	459	\| Reporting the total number of conflicts. \|
	460	`------------------------------------------*/
	461
	462	void
	463	conflicts_print (void)
	464	{
	465	/* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is
	466	not set, and then we want 0 SR, or else it is specified, in which
	467	case we want equality. */
	468	bool src_ok;
	469	bool rrc_ok;
	470
	471	int src_total = 0;
	472	int rrc_total = 0;
	473	int src_expected;
	474	int rrc_expected;
	475
	476	/* Conflicts by state. */
	477	{
	478	state_number i;
	479
	480	for (i = 0; i < nstates; i++)
	481	if (conflicts[i])
	482	{
	483	src_total += count_sr_conflicts (states[i]);
	484	rrc_total += count_rr_conflicts (states[i], true);
	485	}
	486	}
	487
	488	if (! glr_parser && rrc_total > 0 && expected_rr_conflicts != -1)
	489	{
	490	warn (_("%%expect-rr applies only to GLR parsers"));
	491	expected_rr_conflicts = -1;
	492	}
	493
	494	src_expected = expected_sr_conflicts == -1 ? 0 : expected_sr_conflicts;
	495	rrc_expected = expected_rr_conflicts == -1 ? 0 : expected_rr_conflicts;
	496	src_ok = src_total == src_expected;
	497	rrc_ok = rrc_total == rrc_expected;
	498
	499	/* If there are as many RR conflicts and SR conflicts as
	500	expected, then there is nothing to report. */
	501	if (rrc_ok & src_ok)
	502	return;
	503
	504	/* Report the total number of conflicts on STDERR. */
	505	if (src_total \| rrc_total)
	506	{
	507	if (! yacc_flag)
	508	fprintf (stderr, "%s: ", current_file);
	509	conflict_report (stderr, src_total, rrc_total);
	510	}
	511
	512	if (expected_sr_conflicts != -1 \|\| expected_rr_conflicts != -1)
	513	{
	514	if (! src_ok)
	515	complain (ngettext ("expected %d shift/reduce conflict",
	516	"expected %d shift/reduce conflicts",
	517	src_expected),
	518	src_expected);
	519	if (! rrc_ok)
	520	complain (ngettext ("expected %d reduce/reduce conflict",
	521	"expected %d reduce/reduce conflicts",
	522	rrc_expected),
	523	rrc_expected);
	524	}
	525	}
	526
	527
	528	void
	529	conflicts_free (void)
	530	{
	531	free (conflicts);
	532	bitset_free (shift_set);
	533	bitset_free (look_ahead_set);
	534	obstack_free (&solved_conflicts_obstack, NULL);
	535	}