[bison.git] / src / conflicts.c

/* Find and resolve or report look-ahead conflicts for bison,
   Copyright (C) 1984, 1989, 1992 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.  */

#include <stdio.h>
#include "system.h"
#include "machine.h"
#include "alloc.h"
#include "files.h"
#include "gram.h"
#include "state.h"


extern char **tags;
extern int tokensetsize;
extern char *consistent;
extern short *accessing_symbol;
extern shifts **shift_table;
extern unsigned *LA;
extern short *LAruleno;
extern short *lookaheads;
extern int verboseflag;
extern int fixed_outfiles;

extern void initialize_conflicts PARAMS((void));
extern void conflict_log PARAMS((void));
extern void verbose_conflict_log PARAMS((void));
extern void print_reductions PARAMS((int));
extern void finalize_conflicts PARAMS((void));

static void set_conflicts PARAMS((int));
static void resolve_sr_conflict PARAMS((int, int));
static void flush_shift PARAMS((int, int));
static void log_resolution PARAMS((int, int, int, char *));
static void total_conflicts PARAMS((void));
static void count_sr_conflicts PARAMS((int));
static void count_rr_conflicts PARAMS((int));

char any_conflicts;
errs **err_table;
int expected_conflicts;
static char *conflicts;


static unsigned *shiftset;
static unsigned *lookaheadset;
static int src_total;
static int rrc_total;
static int src_count;
static int rrc_count;


void
initialize_conflicts (void)
{
  register int i;
/*  register errs *sp; JF unused */

  conflicts = NEW2(nstates, char);
  shiftset = NEW2(tokensetsize, unsigned);
  lookaheadset = NEW2(tokensetsize, unsigned);

  err_table = NEW2(nstates, errs *);

  any_conflicts = 0;

  for (i = 0; i < nstates; i++)
    set_conflicts(i);
}


static void
set_conflicts (int state)
{
  register int i;
  register int k;
  register shifts *shiftp;
  register unsigned *fp2;
  register unsigned *fp3;
  register unsigned *fp4;
  register unsigned *fp1;
  register int symbol;

  if (consistent[state]) return;

  for (i = 0; i < tokensetsize; i++)
    lookaheadset[i] = 0;

  shiftp = shift_table[state];
  if (shiftp)
    {
      k = shiftp->nshifts;
      for (i = 0; i < k; i++)
	{
	  symbol = accessing_symbol[shiftp->shifts[i]];
	  if (ISVAR(symbol)) break;
	  SETBIT(lookaheadset, symbol);
	}
    }

  k = lookaheads[state + 1];
  fp4 = lookaheadset + tokensetsize;

  /* loop over all rules which require lookahead in this state */
  /* first check for shift-reduce conflict, and try to resolve using precedence  */

  for (i = lookaheads[state]; i < k; i++)
    if (rprec[LAruleno[i]])
      {
	fp1 = LA + i * tokensetsize;
	fp2 = fp1;
	fp3 = lookaheadset;
  
	while (fp3 < fp4)
	  {
	    if (*fp2++ & *fp3++)
	      {
		resolve_sr_conflict(state, i);
		break;
	      }
	  }
      }

  /* loop over all rules which require lookahead in this state */
  /* Check for conflicts not resolved above.  */

  for (i = lookaheads[state]; i < k; i++)
    {
      fp1 = LA + i * tokensetsize;
      fp2 = fp1;
      fp3 = lookaheadset;

      while (fp3 < fp4)
	{
	  if (*fp2++ & *fp3++)
	    {
	      conflicts[state] = 1;
	      any_conflicts = 1;
	    }
	}

      fp2 = fp1;
      fp3 = lookaheadset;

      while (fp3 < fp4)
	*fp3++ |= *fp2++;
    }
}


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

static void
resolve_sr_conflict (int state, int lookaheadnum)
{
  register int i;
  register int mask;
  register unsigned *fp1;
  register unsigned *fp2;
  register int redprec;
  errs *errp = (errs *) xmalloc (sizeof(errs) + ntokens * sizeof(short));
  short *errtokens = errp->errs;

  /* find the rule to reduce by to get precedence of reduction  */
  redprec = rprec[LAruleno[lookaheadnum]];

  mask = 1;
  fp1 = LA + lookaheadnum * tokensetsize;
  fp2 = lookaheadset;
  for (i = 0; i < ntokens; i++)
    {
      if ((mask & *fp2 & *fp1) && sprec[i])
	/* Shift-reduce conflict occurs for token number i
	   and it has a precedence.
	   The precedence of shifting is that of token i.  */
	{
	  if (sprec[i] < redprec)
	    {
	      if (verboseflag) log_resolution(state, lookaheadnum, i, _("reduce"));
	      *fp2 &= ~mask;  /* flush the shift for this token */
	      flush_shift(state, i);
	    }
	  else if (sprec[i] > redprec)
	    {
	      if (verboseflag) log_resolution(state, lookaheadnum, i, _("shift"));
	      *fp1 &= ~mask;  /* flush the reduce for this token */
	    }
	  else
	    {
	      /* Matching precedence levels.
		 For left association, keep only the reduction.
		 For right association, keep only the shift.
		 For nonassociation, keep neither.  */

	      switch (sassoc[i])
		{

		case RIGHT_ASSOC:
	          if (verboseflag) log_resolution(state, lookaheadnum, i, _("shift"));
		  break;

		case LEFT_ASSOC:
	          if (verboseflag) log_resolution(state, lookaheadnum, i, _("reduce"));
		  break;

		case NON_ASSOC:
	          if (verboseflag) log_resolution(state, lookaheadnum, i, _("an error"));
		  break;
		}

	      if (sassoc[i] != RIGHT_ASSOC)
		{
		  *fp2 &= ~mask;  /* flush the shift for this token */
		  flush_shift(state, i);
		}
	      if (sassoc[i] != LEFT_ASSOC)
	        {
		  *fp1 &= ~mask;  /* flush the reduce for this token */
		}
	      if (sassoc[i] == NON_ASSOC)
		{
		  /* Record an explicit error for this token.  */
		  *errtokens++ = i;
		}
	    }
	}

      mask <<= 1;
      if (mask == 0)
	{
	  mask = 1;
	  fp2++;  fp1++;
	}
    }
  errp->nerrs = errtokens - errp->errs;
  if (errp->nerrs)
    {
      /* Some tokens have been explicitly made errors.  Allocate
	 a permanent errs structure for this state, to record them.  */
      i = (char *) errtokens - (char *) errp;
      err_table[state] = (errs *) xmalloc ((unsigned int)i);
      bcopy (errp, err_table[state], i);
    }
  else
    err_table[state] = 0;
  free(errp);
}


/* 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 (int state, int token)
{
  register shifts *shiftp;
  register int k, i;
/*  register unsigned symbol; JF unused */

  shiftp = shift_table[state];

  if (shiftp)
    {
      k = shiftp->nshifts;
      for (i = 0; i < k; i++)
	{
	  if (shiftp->shifts[i] && token == accessing_symbol[shiftp->shifts[i]])
	    (shiftp->shifts[i]) = 0;
	}
    }
}


static void
log_resolution (int state, int LAno, int token, char *resolution)
{
  fprintf(foutput,
	  _("Conflict in state %d between rule %d and token %s resolved as %s.\n"),
	  state, LAruleno[LAno], tags[token], resolution);
}


void
conflict_log (void)
{
  register int i;

  src_total = 0;
  rrc_total = 0;

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

  total_conflicts();
}
  

void
verbose_conflict_log (void)
{
  register int i;

  src_total = 0;
  rrc_total = 0;

  for (i = 0; i < nstates; i++)
    {
      if (conflicts[i])
	{
	  count_sr_conflicts(i);
	  count_rr_conflicts(i);
	  src_total += src_count;
	  rrc_total += rrc_count;

	  fprintf(foutput, _("State %d contains"), i);

	  if (src_count == 1)
	    fprintf(foutput, _(" 1 shift/reduce conflict"));
	  else if (src_count > 1)
	    fprintf(foutput, _(" %d shift/reduce conflicts"), src_count);

	  if (src_count > 0 && rrc_count > 0)
	    fprintf(foutput, _(" and"));

	  if (rrc_count == 1)
	    fprintf(foutput, _(" 1 reduce/reduce conflict"));
	  else if (rrc_count > 1)
	    fprintf(foutput, _(" %d reduce/reduce conflicts"), rrc_count);

	  putc('.', foutput);
	  putc('\n', foutput);
	}
    }

  total_conflicts();
}


static void
total_conflicts (void)
{
  if (src_total == expected_conflicts && rrc_total == 0)
    return;

  if (fixed_outfiles)
    {
      /* If invoked under the name `yacc', use the output format
	 specified by POSIX.  */
      fprintf(stderr, _("conflicts: "));
      if (src_total > 0)
	fprintf(stderr, _(" %d shift/reduce"), src_total);
      if (src_total > 0 && rrc_total > 0)
	fprintf(stderr, ",");
      if (rrc_total > 0)
	fprintf(stderr, _(" %d reduce/reduce"), rrc_total);
      putc('\n', stderr);
    }
  else
    {
      fprintf(stderr, _("%s contains"), infile);

      if (src_total == 1)
	fprintf(stderr, _(" 1 shift/reduce conflict"));
      else if (src_total > 1)
	fprintf(stderr, _(" %d shift/reduce conflicts"), src_total);

      if (src_total > 0 && rrc_total > 0)
	fprintf(stderr, _(" and"));

      if (rrc_total == 1)
	fprintf(stderr, _(" 1 reduce/reduce conflict"));
      else if (rrc_total > 1)
	fprintf(stderr, _(" %d reduce/reduce conflicts"), rrc_total);

      putc('.', stderr);
      putc('\n', stderr);
    }
}


static void
count_sr_conflicts (int state)
{
  register int i;
  register int k;
  register int mask;
  register shifts *shiftp;
  register unsigned *fp1;
  register unsigned *fp2;
  register unsigned *fp3;
  register int symbol;

  src_count = 0;

  shiftp = shift_table[state];
  if (!shiftp) return;

  for (i = 0; i < tokensetsize; i++)
    {
      shiftset[i] = 0;
      lookaheadset[i] = 0;
    }

  k = shiftp->nshifts;
  for (i = 0; i < k; i++)
    {
      if (! shiftp->shifts[i]) continue;
      symbol = accessing_symbol[shiftp->shifts[i]];
      if (ISVAR(symbol)) break;
      SETBIT(shiftset, symbol);
    }

  k = lookaheads[state + 1];
  fp3 = lookaheadset + tokensetsize;

  for (i = lookaheads[state]; i < k; i++)
    {
      fp1 = LA + i * tokensetsize;
      fp2 = lookaheadset;

      while (fp2 < fp3)
	*fp2++ |= *fp1++;
    }

  fp1 = shiftset;
  fp2 = lookaheadset;

  while (fp2 < fp3)
    *fp2++ &= *fp1++;

  mask = 1;
  fp2 = lookaheadset;
  for (i = 0; i < ntokens; i++)
    {
      if (mask & *fp2)
	src_count++;

      mask <<= 1;
      if (mask == 0)
	{
	  mask = 1;
	  fp2++;
	}
    }
}


static void
count_rr_conflicts (int state)
{
  register int i;
  register int j;
  register int count;
  register unsigned mask;
  register unsigned *baseword;
  register unsigned *wordp;
  register int m;
  register int n;

  rrc_count = 0;

  m = lookaheads[state];
  n = lookaheads[state + 1];

  if (n - m < 2) return;

  mask = 1;
  baseword = LA + m * tokensetsize;
  for (i = 0; i < ntokens; i++)
    {
      wordp = baseword;

      count = 0;
      for (j = m; j < n; j++)
	{
	  if (mask & *wordp)
	    count++;

	  wordp += tokensetsize;
	}

      if (count >= 2) rrc_count++;

      mask <<= 1;
      if (mask == 0)
	{
	  mask = 1;
	  baseword++;
	}
    }
}


void
print_reductions (int state)
{
  register int i;
  register int j;
  register int k;
  register unsigned *fp1;
  register unsigned *fp2;
  register unsigned *fp3;
  register unsigned *fp4;
  register int rule;
  register int symbol;
  register unsigned mask;
  register int m;
  register int n;
  register int default_LA;
  register int default_rule = 0;
  register int cmax;
  register int count;
  register shifts *shiftp;
  register errs *errp;
  int nodefault = 0;

  for (i = 0; i < tokensetsize; i++)
    shiftset[i] = 0;

  shiftp = shift_table[state];
  if (shiftp)
    {
      k = shiftp->nshifts;
      for (i = 0; i < k; i++)
	{
	  if (! shiftp->shifts[i]) continue;
	  symbol = accessing_symbol[shiftp->shifts[i]];
	  if (ISVAR(symbol)) break;
	  /* if this state has a shift for the error token,
	     don't use a default rule.  */
	  if (symbol == error_token_number) nodefault = 1;
	  SETBIT(shiftset, symbol);
	}
    }

  errp = err_table[state];
  if (errp)
    {
      k = errp->nerrs;
      for (i = 0; i < k; i++)
	{
	  if (! errp->errs[i]) continue;
	  symbol = errp->errs[i];
	  SETBIT(shiftset, symbol);
	}
    }

  m = lookaheads[state];
  n = lookaheads[state + 1];

  if (n - m == 1 && ! nodefault)
    {
      default_rule = LAruleno[m];

      fp1 = LA + m * tokensetsize;
      fp2 = shiftset;
      fp3 = lookaheadset;
      fp4 = lookaheadset + tokensetsize;

      while (fp3 < fp4)
	*fp3++ = *fp1++ & *fp2++;

      mask = 1;
      fp3 = lookaheadset;

      for (i = 0; i < ntokens; i++)
	{
	  if (mask & *fp3)
	    fprintf(foutput, _("    %-4s\t[reduce using rule %d (%s)]\n"),
		    tags[i], default_rule, tags[rlhs[default_rule]]);

	  mask <<= 1;
	  if (mask == 0)
	    {
	      mask = 1;
	      fp3++;
	    }
	}

      fprintf(foutput, _("    $default\treduce using rule %d (%s)\n\n"),
	      default_rule, tags[rlhs[default_rule]]);
    }
  else if (n - m >= 1)
    {
      cmax = 0;
      default_LA = -1;
      fp4 = lookaheadset + tokensetsize;

      if (! nodefault)
	for (i = m; i < n; i++)
	  {
	    fp1 = LA + i * tokensetsize;
	    fp2 = shiftset;
	    fp3 = lookaheadset;
  
	    while (fp3 < fp4)
	      *fp3++ = *fp1++ & (~(*fp2++));
  
	    count = 0;
	    mask = 1;
	    fp3 = lookaheadset;
	    for (j = 0; j < ntokens; j++)
	      {
		if (mask & *fp3)
		  count++;
  
		mask <<= 1;
		if (mask == 0)
		  {
		    mask = 1;
		    fp3++;
		  }
	      }
  
	    if (count > cmax)
	      {
		cmax = count;
		default_LA = i;
		default_rule = LAruleno[i];
	      }
  
	    fp2 = shiftset;
	    fp3 = lookaheadset;
  
	    while (fp3 < fp4)
	      *fp2++ |= *fp3++;
	  }

      for (i = 0; i < tokensetsize; i++)
        shiftset[i] = 0;

      if (shiftp)
        {
          k = shiftp->nshifts;
          for (i = 0; i < k; i++)
	    {
	      if (! shiftp->shifts[i]) continue;
	      symbol = accessing_symbol[shiftp->shifts[i]];
	      if (ISVAR(symbol)) break;
	      SETBIT(shiftset, symbol);
	    }
        }

      mask = 1;
      fp1 = LA + m * tokensetsize;
      fp2 = shiftset;
      for (i = 0; i < ntokens; i++)
	{
	  int defaulted = 0;

	  if (mask & *fp2)
	    count = 1;
	  else
	    count = 0;

	  fp3 = fp1;
	  for (j = m; j < n; j++)
	    {
	      if (mask & *fp3)
		{
		  if (count == 0)
		    {
		      if (j != default_LA)
			{
			  rule = LAruleno[j];
			  fprintf(foutput, _("    %-4s\treduce using rule %d (%s)\n"),
				  tags[i], rule, tags[rlhs[rule]]);
			}
		      else defaulted = 1;

		      count++;
		    }
		  else
		    {
		      if (defaulted)
			{
			  rule = LAruleno[default_LA];
			  fprintf(foutput, _("    %-4s\treduce using rule %d (%s)\n"),
				  tags[i], rule, tags[rlhs[rule]]);
			  defaulted = 0;
			}
		      rule = LAruleno[j];
		      fprintf(foutput, _("    %-4s\t[reduce using rule %d (%s)]\n"),
			      tags[i], rule, tags[rlhs[rule]]);
		    }
		}

	      fp3 += tokensetsize;
	    }

	  mask <<= 1;
	  if (mask == 0)
	    {
	      mask = 1;
	      /* We tried incrementing just fp1, and just fp2; both seem wrong.
		 It seems necessary to increment both in sync.  */
	      fp1++;
	      fp2++;
	    }
	}

      if (default_LA >= 0)
	{
	  fprintf(foutput, _("    $default\treduce using rule %d (%s)\n"),
		  default_rule, tags[rlhs[default_rule]]);
	}

      putc('\n', foutput);
    }
}


void
finalize_conflicts (void)
{
  FREE(conflicts);
  FREE(shiftset);
  FREE(lookaheadset);
}
Commit	Line	Data
08089d5d	1	/* Find and resolve or report look-ahead conflicts for bison,
b65534e5	2	Copyright (C) 1984, 1989, 1992 Free Software Foundation, Inc.
08089d5d DM	3
	4	This file is part of Bison, the GNU Compiler Compiler.
	5
	6	Bison is free software; you can redistribute it and/or modify
	7	it under the terms of the GNU General Public License as published by
	8	the Free Software Foundation; either version 2, or (at your option)
	9	any later version.
	10
	11	Bison is distributed in the hope that it will be useful,
	12	but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	GNU General Public License for more details.
	15
	16	You should have received a copy of the GNU General Public License
	17	along with Bison; see the file COPYING. If not, write to
c49a8e71 JT	18	the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
c49a8e71 JT	19	Boston, MA 02111-1307, USA. */
08089d5d	20
08089d5d DM	21	#include <stdio.h>
	22	#include "system.h"
	23	#include "machine.h"
7612000c	24	#include "alloc.h"
08089d5d DM	25	#include "files.h"
	26	#include "gram.h"
	27	#include "state.h"
	28
	29
08089d5d DM	30	extern char **tags;
	31	extern int tokensetsize;
	32	extern char *consistent;
	33	extern short *accessing_symbol;
	34	extern shifts **shift_table;
	35	extern unsigned *LA;
	36	extern short *LAruleno;
	37	extern short *lookaheads;
	38	extern int verboseflag;
d2729d44 JT	39	extern int fixed_outfiles;
d2729d44 JT	40
4a120d45 JT	41	extern void initialize_conflicts PARAMS((void));
	42	extern void conflict_log PARAMS((void));
	43	extern void verbose_conflict_log PARAMS((void));
	44	extern void print_reductions PARAMS((int));
	45	extern void finalize_conflicts PARAMS((void));
	46
	47	static void set_conflicts PARAMS((int));
	48	static void resolve_sr_conflict PARAMS((int, int));
	49	static void flush_shift PARAMS((int, int));
	50	static void log_resolution PARAMS((int, int, int, char *));
	51	static void total_conflicts PARAMS((void));
	52	static void count_sr_conflicts PARAMS((int));
	53	static void count_rr_conflicts PARAMS((int));
08089d5d DM	54
08089d5d DM	55	char any_conflicts;
08089d5d DM	56	errs **err_table;
08089d5d DM	57	int expected_conflicts;
4a120d45	58	static char *conflicts;
08089d5d DM	59
	60
	61	static unsigned *shiftset;
	62	static unsigned *lookaheadset;
	63	static int src_total;
	64	static int rrc_total;
	65	static int src_count;
	66	static int rrc_count;
	67
	68
	69	void
d2729d44	70	initialize_conflicts (void)
08089d5d DM	71	{
	72	register int i;
	73	/* register errs sp; JF unused /
	74
	75	conflicts = NEW2(nstates, char);
	76	shiftset = NEW2(tokensetsize, unsigned);
	77	lookaheadset = NEW2(tokensetsize, unsigned);
	78
	79	err_table = NEW2(nstates, errs *);
	80
	81	any_conflicts = 0;
	82
	83	for (i = 0; i < nstates; i++)
	84	set_conflicts(i);
	85	}
	86
	87
4a120d45	88	static void
d2729d44	89	set_conflicts (int state)
08089d5d DM	90	{
	91	register int i;
	92	register int k;
	93	register shifts *shiftp;
	94	register unsigned *fp2;
	95	register unsigned *fp3;
	96	register unsigned *fp4;
	97	register unsigned *fp1;
	98	register int symbol;
	99
	100	if (consistent[state]) return;
	101
	102	for (i = 0; i < tokensetsize; i++)
	103	lookaheadset[i] = 0;
	104
	105	shiftp = shift_table[state];
	106	if (shiftp)
	107	{
	108	k = shiftp->nshifts;
	109	for (i = 0; i < k; i++)
	110	{
	111	symbol = accessing_symbol[shiftp->shifts[i]];
	112	if (ISVAR(symbol)) break;
	113	SETBIT(lookaheadset, symbol);
	114	}
	115	}
	116
	117	k = lookaheads[state + 1];
	118	fp4 = lookaheadset + tokensetsize;
	119
	120	/* loop over all rules which require lookahead in this state */
	121	/* first check for shift-reduce conflict, and try to resolve using precedence */
	122
	123	for (i = lookaheads[state]; i < k; i++)
	124	if (rprec[LAruleno[i]])
	125	{
	126	fp1 = LA + i * tokensetsize;
	127	fp2 = fp1;
	128	fp3 = lookaheadset;
	129
	130	while (fp3 < fp4)
	131	{
	132	if (fp2++ & fp3++)
	133	{
	134	resolve_sr_conflict(state, i);
	135	break;
	136	}
	137	}
	138	}
	139
	140	/* loop over all rules which require lookahead in this state */
	141	/* Check for conflicts not resolved above. */
	142
	143	for (i = lookaheads[state]; i < k; i++)
	144	{
	145	fp1 = LA + i * tokensetsize;
	146	fp2 = fp1;
	147	fp3 = lookaheadset;
	148
	149	while (fp3 < fp4)
	150	{
	151	if (fp2++ & fp3++)
	152	{
	153	conflicts[state] = 1;
154	any_conflicts = 1;
155	}
156	}
157
158	fp2 = fp1;
159	fp3 = lookaheadset;
160
161	while (fp3 < fp4)
162	fp3++ \|= fp2++;
163	}
164	}
165
166
167
168	/* Attempt to resolve shift-reduce conflict for one rule
169	by means of precedence declarations.
170	It has already been checked that the rule has a precedence.
171	A conflict is resolved by modifying the shift or reduce tables
172	so that there is no longer a conflict. */
173
4a120d45	174	static void
d2729d44	175	resolve_sr_conflict (int state, int lookaheadnum)
08089d5d DM	176	{
	177	register int i;
	178	register int mask;
	179	register unsigned *fp1;
	180	register unsigned *fp2;
	181	register int redprec;
b65534e5	182	errs errp = (errs ) xmalloc (sizeof(errs) + ntokens * sizeof(short));
08089d5d DM	183	short *errtokens = errp->errs;
	184
	185	/* find the rule to reduce by to get precedence of reduction */
	186	redprec = rprec[LAruleno[lookaheadnum]];
	187
	188	mask = 1;
	189	fp1 = LA + lookaheadnum * tokensetsize;
	190	fp2 = lookaheadset;
	191	for (i = 0; i < ntokens; i++)
	192	{
	193	if ((mask & fp2 & fp1) && sprec[i])
	194	/* Shift-reduce conflict occurs for token number i
	195	and it has a precedence.
	196	The precedence of shifting is that of token i. */
	197	{
	198	if (sprec[i] < redprec)
	199	{
a083fbbf	200	if (verboseflag) log_resolution(state, lookaheadnum, i, _("reduce"));
08089d5d DM	201	fp2 &= ~mask; / flush the shift for this token */
	202	flush_shift(state, i);
	203	}
	204	else if (sprec[i] > redprec)
	205	{
a083fbbf	206	if (verboseflag) log_resolution(state, lookaheadnum, i, _("shift"));
08089d5d DM	207	fp1 &= ~mask; / flush the reduce for this token */
	208	}
	209	else
	210	{
	211	/* Matching precedence levels.
	212	For left association, keep only the reduction.
	213	For right association, keep only the shift.
	214	For nonassociation, keep neither. */
	215
	216	switch (sassoc[i])
	217	{
	218
	219	case RIGHT_ASSOC:
a083fbbf	220	if (verboseflag) log_resolution(state, lookaheadnum, i, _("shift"));
08089d5d DM	221	break;
	222
	223	case LEFT_ASSOC:
a083fbbf	224	if (verboseflag) log_resolution(state, lookaheadnum, i, _("reduce"));
08089d5d DM	225	break;
	226
	227	case NON_ASSOC:
a083fbbf	228	if (verboseflag) log_resolution(state, lookaheadnum, i, _("an error"));
08089d5d DM	229	break;
	230	}
	231
	232	if (sassoc[i] != RIGHT_ASSOC)
	233	{
	234	fp2 &= ~mask; / flush the shift for this token */
	235	flush_shift(state, i);
	236	}
	237	if (sassoc[i] != LEFT_ASSOC)
	238	{
	239	fp1 &= ~mask; / flush the reduce for this token */
	240	}
	241	if (sassoc[i] == NON_ASSOC)
	242	{
	243	/* Record an explicit error for this token. */
	244	*errtokens++ = i;
	245	}
	246	}
	247	}
	248
	249	mask <<= 1;
	250	if (mask == 0)
	251	{
	252	mask = 1;
	253	fp2++; fp1++;
	254	}
	255	}
	256	errp->nerrs = errtokens - errp->errs;
	257	if (errp->nerrs)
	258	{
	259	/* Some tokens have been explicitly made errors. Allocate
	260	a permanent errs structure for this state, to record them. */
	261	i = (char ) errtokens - (char ) errp;
	262	err_table[state] = (errs *) xmalloc ((unsigned int)i);
	263	bcopy (errp, err_table[state], i);
	264	}
	265	else
	266	err_table[state] = 0;
b65534e5	267	free(errp);
08089d5d DM	268	}
	269
	270
	271
	272	/* turn off the shift recorded for the specified token in the specified state.
	273	Used when we resolve a shift-reduce conflict in favor of the reduction. */
	274
4a120d45	275	static void
d2729d44	276	flush_shift (int state, int token)
08089d5d DM	277	{
	278	register shifts *shiftp;
	279	register int k, i;
	280	/* register unsigned symbol; JF unused */
	281
	282	shiftp = shift_table[state];
	283
	284	if (shiftp)
	285	{
	286	k = shiftp->nshifts;
	287	for (i = 0; i < k; i++)
	288	{
	289	if (shiftp->shifts[i] && token == accessing_symbol[shiftp->shifts[i]])
	290	(shiftp->shifts[i]) = 0;
	291	}
	292	}
	293	}
	294
	295
4a120d45	296	static void
d2729d44	297	log_resolution (int state, int LAno, int token, char *resolution)
08089d5d DM	298	{
08089d5d DM	299	fprintf(foutput,
a083fbbf	300	_("Conflict in state %d between rule %d and token %s resolved as %s.\n"),
08089d5d DM	301	state, LAruleno[LAno], tags[token], resolution);
	302	}
	303
	304
	305	void
d2729d44	306	conflict_log (void)
08089d5d DM	307	{
	308	register int i;
	309
	310	src_total = 0;
	311	rrc_total = 0;
	312
	313	for (i = 0; i < nstates; i++)
	314	{
	315	if (conflicts[i])
	316	{
	317	count_sr_conflicts(i);
	318	count_rr_conflicts(i);
	319	src_total += src_count;
	320	rrc_total += rrc_count;
	321	}
	322	}
	323
	324	total_conflicts();
	325	}
	326
	327
	328	void
d2729d44	329	verbose_conflict_log (void)
08089d5d DM	330	{
	331	register int i;
	332
	333	src_total = 0;
	334	rrc_total = 0;
	335
	336	for (i = 0; i < nstates; i++)
	337	{
	338	if (conflicts[i])
	339	{
	340	count_sr_conflicts(i);
	341	count_rr_conflicts(i);
	342	src_total += src_count;
	343	rrc_total += rrc_count;
	344
a083fbbf	345	fprintf(foutput, _("State %d contains"), i);
08089d5d DM	346
08089d5d DM	347	if (src_count == 1)
a083fbbf	348	fprintf(foutput, _(" 1 shift/reduce conflict"));
08089d5d	349	else if (src_count > 1)
a083fbbf	350	fprintf(foutput, _(" %d shift/reduce conflicts"), src_count);
08089d5d DM	351
08089d5d DM	352	if (src_count > 0 && rrc_count > 0)
a083fbbf	353	fprintf(foutput, _(" and"));
08089d5d DM	354
08089d5d DM	355	if (rrc_count == 1)
a083fbbf	356	fprintf(foutput, _(" 1 reduce/reduce conflict"));
08089d5d	357	else if (rrc_count > 1)
a083fbbf	358	fprintf(foutput, _(" %d reduce/reduce conflicts"), rrc_count);
08089d5d DM	359
	360	putc('.', foutput);
	361	putc('\n', foutput);
	362	}
	363	}
	364
	365	total_conflicts();
	366	}
	367
	368
4a120d45	369	static void
d2729d44	370	total_conflicts (void)
08089d5d	371	{
08089d5d DM	372	if (src_total == expected_conflicts && rrc_total == 0)
	373	return;
	374
	375	if (fixed_outfiles)
	376	{
	377	/* If invoked under the name `yacc', use the output format
	378	specified by POSIX. */
a083fbbf	379	fprintf(stderr, _("conflicts: "));
08089d5d	380	if (src_total > 0)
a083fbbf	381	fprintf(stderr, _(" %d shift/reduce"), src_total);
08089d5d DM	382	if (src_total > 0 && rrc_total > 0)
	383	fprintf(stderr, ",");
	384	if (rrc_total > 0)
a083fbbf	385	fprintf(stderr, _(" %d reduce/reduce"), rrc_total);
08089d5d DM	386	putc('\n', stderr);
	387	}
	388	else
	389	{
a083fbbf	390	fprintf(stderr, _("%s contains"), infile);
08089d5d DM	391
08089d5d DM	392	if (src_total == 1)
a083fbbf	393	fprintf(stderr, _(" 1 shift/reduce conflict"));
08089d5d	394	else if (src_total > 1)
a083fbbf	395	fprintf(stderr, _(" %d shift/reduce conflicts"), src_total);
08089d5d DM	396
08089d5d DM	397	if (src_total > 0 && rrc_total > 0)
a083fbbf	398	fprintf(stderr, _(" and"));
08089d5d DM	399
08089d5d DM	400	if (rrc_total == 1)
a083fbbf	401	fprintf(stderr, _(" 1 reduce/reduce conflict"));
08089d5d	402	else if (rrc_total > 1)
a083fbbf	403	fprintf(stderr, _(" %d reduce/reduce conflicts"), rrc_total);
08089d5d DM	404
	405	putc('.', stderr);
	406	putc('\n', stderr);
	407	}
	408	}
	409
	410
4a120d45	411	static void
d2729d44	412	count_sr_conflicts (int state)
08089d5d DM	413	{
	414	register int i;
	415	register int k;
	416	register int mask;
	417	register shifts *shiftp;
	418	register unsigned *fp1;
	419	register unsigned *fp2;
	420	register unsigned *fp3;
	421	register int symbol;
	422
	423	src_count = 0;
	424
	425	shiftp = shift_table[state];
	426	if (!shiftp) return;
	427
	428	for (i = 0; i < tokensetsize; i++)
	429	{
	430	shiftset[i] = 0;
	431	lookaheadset[i] = 0;
	432	}
	433
	434	k = shiftp->nshifts;
	435	for (i = 0; i < k; i++)
	436	{
	437	if (! shiftp->shifts[i]) continue;
	438	symbol = accessing_symbol[shiftp->shifts[i]];
	439	if (ISVAR(symbol)) break;
	440	SETBIT(shiftset, symbol);
	441	}
	442
	443	k = lookaheads[state + 1];
	444	fp3 = lookaheadset + tokensetsize;
	445
	446	for (i = lookaheads[state]; i < k; i++)
	447	{
	448	fp1 = LA + i * tokensetsize;
	449	fp2 = lookaheadset;
	450
	451	while (fp2 < fp3)
	452	fp2++ \|= fp1++;
	453	}
	454
	455	fp1 = shiftset;
	456	fp2 = lookaheadset;
	457
	458	while (fp2 < fp3)
	459	fp2++ &= fp1++;
	460
	461	mask = 1;
	462	fp2 = lookaheadset;
	463	for (i = 0; i < ntokens; i++)
	464	{
	465	if (mask & *fp2)
	466	src_count++;
	467
	468	mask <<= 1;
	469	if (mask == 0)
	470	{
	471	mask = 1;
	472	fp2++;
	473	}
	474	}
	475	}
	476
477
4a120d45	478	static void
d2729d44	479	count_rr_conflicts (int state)
08089d5d DM	480	{
	481	register int i;
	482	register int j;
	483	register int count;
	484	register unsigned mask;
	485	register unsigned *baseword;
	486	register unsigned *wordp;
	487	register int m;
	488	register int n;
	489
	490	rrc_count = 0;
	491
	492	m = lookaheads[state];
	493	n = lookaheads[state + 1];
	494
	495	if (n - m < 2) return;
	496
	497	mask = 1;
	498	baseword = LA + m * tokensetsize;
	499	for (i = 0; i < ntokens; i++)
	500	{
	501	wordp = baseword;
	502
	503	count = 0;
	504	for (j = m; j < n; j++)
	505	{
	506	if (mask & *wordp)
	507	count++;
	508
	509	wordp += tokensetsize;
	510	}
	511
	512	if (count >= 2) rrc_count++;
	513
	514	mask <<= 1;
	515	if (mask == 0)
	516	{
	517	mask = 1;
	518	baseword++;
	519	}
	520	}
	521	}
	522
	523
	524	void
d2729d44	525	print_reductions (int state)
08089d5d DM	526	{
	527	register int i;
	528	register int j;
	529	register int k;
	530	register unsigned *fp1;
	531	register unsigned *fp2;
	532	register unsigned *fp3;
	533	register unsigned *fp4;
	534	register int rule;
	535	register int symbol;
	536	register unsigned mask;
	537	register int m;
	538	register int n;
	539	register int default_LA;
2686a6e7	540	register int default_rule = 0;
08089d5d DM	541	register int cmax;
	542	register int count;
	543	register shifts *shiftp;
	544	register errs *errp;
	545	int nodefault = 0;
	546
	547	for (i = 0; i < tokensetsize; i++)
	548	shiftset[i] = 0;
	549
	550	shiftp = shift_table[state];
	551	if (shiftp)
	552	{
	553	k = shiftp->nshifts;
	554	for (i = 0; i < k; i++)
	555	{
	556	if (! shiftp->shifts[i]) continue;
	557	symbol = accessing_symbol[shiftp->shifts[i]];
	558	if (ISVAR(symbol)) break;
	559	/* if this state has a shift for the error token,
	560	don't use a default rule. */
	561	if (symbol == error_token_number) nodefault = 1;
	562	SETBIT(shiftset, symbol);
	563	}
	564	}
	565
	566	errp = err_table[state];
	567	if (errp)
	568	{
	569	k = errp->nerrs;
	570	for (i = 0; i < k; i++)
	571	{
	572	if (! errp->errs[i]) continue;
	573	symbol = errp->errs[i];
	574	SETBIT(shiftset, symbol);
	575	}
	576	}
	577
	578	m = lookaheads[state];
	579	n = lookaheads[state + 1];
	580
	581	if (n - m == 1 && ! nodefault)
	582	{
	583	default_rule = LAruleno[m];
	584
	585	fp1 = LA + m * tokensetsize;
	586	fp2 = shiftset;
	587	fp3 = lookaheadset;
	588	fp4 = lookaheadset + tokensetsize;
	589
	590	while (fp3 < fp4)
	591	fp3++ = fp1++ & *fp2++;
	592
	593	mask = 1;
	594	fp3 = lookaheadset;
	595
	596	for (i = 0; i < ntokens; i++)
	597	{
	598	if (mask & *fp3)
a083fbbf	599	fprintf(foutput, _(" %-4s\t[reduce using rule %d (%s)]\n"),
08089d5d DM	600	tags[i], default_rule, tags[rlhs[default_rule]]);
	601
	602	mask <<= 1;
	603	if (mask == 0)
	604	{
	605	mask = 1;
	606	fp3++;
	607	}
	608	}
	609
a083fbbf	610	fprintf(foutput, _(" $default\treduce using rule %d (%s)\n\n"),
08089d5d DM	611	default_rule, tags[rlhs[default_rule]]);
	612	}
	613	else if (n - m >= 1)
	614	{
	615	cmax = 0;
	616	default_LA = -1;
	617	fp4 = lookaheadset + tokensetsize;
	618
	619	if (! nodefault)
	620	for (i = m; i < n; i++)
	621	{
	622	fp1 = LA + i * tokensetsize;
	623	fp2 = shiftset;
	624	fp3 = lookaheadset;
	625
	626	while (fp3 < fp4)
b65534e5	627	fp3++ = fp1++ & (~(*fp2++));
08089d5d DM	628
	629	count = 0;
	630	mask = 1;
	631	fp3 = lookaheadset;
	632	for (j = 0; j < ntokens; j++)
	633	{
	634	if (mask & *fp3)
	635	count++;
	636
	637	mask <<= 1;
	638	if (mask == 0)
	639	{
	640	mask = 1;
	641	fp3++;
	642	}
	643	}
	644
	645	if (count > cmax)
	646	{
	647	cmax = count;
	648	default_LA = i;
	649	default_rule = LAruleno[i];
	650	}
	651
	652	fp2 = shiftset;
	653	fp3 = lookaheadset;
	654
	655	while (fp3 < fp4)
	656	fp2++ \|= fp3++;
	657	}
	658
	659	for (i = 0; i < tokensetsize; i++)
	660	shiftset[i] = 0;
	661
	662	if (shiftp)
	663	{
	664	k = shiftp->nshifts;
	665	for (i = 0; i < k; i++)
	666	{
	667	if (! shiftp->shifts[i]) continue;
	668	symbol = accessing_symbol[shiftp->shifts[i]];
	669	if (ISVAR(symbol)) break;
	670	SETBIT(shiftset, symbol);
	671	}
	672	}
	673
	674	mask = 1;
	675	fp1 = LA + m * tokensetsize;
	676	fp2 = shiftset;
	677	for (i = 0; i < ntokens; i++)
	678	{
	679	int defaulted = 0;
	680
	681	if (mask & *fp2)
	682	count = 1;
	683	else
	684	count = 0;
	685
	686	fp3 = fp1;
	687	for (j = m; j < n; j++)
	688	{
	689	if (mask & *fp3)
	690	{
	691	if (count == 0)
692	{
693	if (j != default_LA)
694	{
695	rule = LAruleno[j];
a083fbbf	696	fprintf(foutput, _(" %-4s\treduce using rule %d (%s)\n"),
08089d5d DM	697	tags[i], rule, tags[rlhs[rule]]);
	698	}
	699	else defaulted = 1;
	700
	701	count++;
	702	}
	703	else
	704	{
	705	if (defaulted)
	706	{
	707	rule = LAruleno[default_LA];
a083fbbf	708	fprintf(foutput, _(" %-4s\treduce using rule %d (%s)\n"),
08089d5d DM	709	tags[i], rule, tags[rlhs[rule]]);
	710	defaulted = 0;
	711	}
	712	rule = LAruleno[j];
a083fbbf	713	fprintf(foutput, _(" %-4s\t[reduce using rule %d (%s)]\n"),
08089d5d DM	714	tags[i], rule, tags[rlhs[rule]]);
	715	}
	716	}
	717
	718	fp3 += tokensetsize;
	719	}
	720
	721	mask <<= 1;
	722	if (mask == 0)
	723	{
	724	mask = 1;
808e2021 RS	725	/* We tried incrementing just fp1, and just fp2; both seem wrong.
	726	It seems necessary to increment both in sync. */
	727	fp1++;
08089d5d DM	728	fp2++;
	729	}
	730	}
	731
	732	if (default_LA >= 0)
	733	{
a083fbbf	734	fprintf(foutput, _(" $default\treduce using rule %d (%s)\n"),
08089d5d DM	735	default_rule, tags[rlhs[default_rule]]);
	736	}
	737
	738	putc('\n', foutput);
	739	}
	740	}
	741
	742
	743	void
d2729d44	744	finalize_conflicts (void)
08089d5d DM	745	{
	746	FREE(conflicts);
	747	FREE(shiftset);
	748	FREE(lookaheadset);
	749	}