[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;

void initialize_conflicts PARAMS((void));
void set_conflicts PARAMS((int));
void resolve_sr_conflict PARAMS((int, int));
void flush_shift PARAMS((int, int));
void log_resolution PARAMS((int, int, int, char *));
void conflict_log PARAMS((void));
void verbose_conflict_log PARAMS((void));
void total_conflicts PARAMS((void));
void count_sr_conflicts PARAMS((int));
void count_rr_conflicts PARAMS((int));
void print_reductions PARAMS((int));
void finalize_conflicts PARAMS((void));

char any_conflicts;
char *conflicts;
errs **err_table;
int expected_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);
}


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

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

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


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();
}


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);
    }
}


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++;
	}
    }
}


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