[gnu.utils.bug] Grammar reduction in bison

dsb@UUNET.UU.NET (David S. Bakin) (11/13/88)

On October 23 I sent out a modification to Bison which did grammar reduction,
but it had bugs.  This is the corrected version.  (For those who didn't get
the previous version, to use this insert a call to reduce_grammar() immediately
after the call to reader() in main.c.)

This is from the original posting:

   This "patch" to GNU Bison adds an algorithm to reduce the input grammar,
   detecting useless productions and nonterminals and inacessable symbols.
   If Bison detects useless productions or symbols it will emit a message,
   and when using the -v flag will list the useless productions and symbols
   in the output file.  If it turns out that the grammar cannot derive any
   sentence from the start symbol then Bison will emit a message and stop.
   These messages help when debugging a grammar.

   I'm happy to look at bugs in this code, just mail me a message with the
   grammar file that misbehaved and an indication of what went wrong.

   (For more information on reducing grammars, and the algorithms used in
   here, see Aho & Ullman "The Theory of Parsing, Translation, and Compiling;
   Volume I".)

-- Dave

----------------------------------------------------------
Dave Bakin				    (408) 496-3600
c/o Rational; 3320 Scott Blvd.; Santa Clara, CA 95054-3197
Internet:  dsb@rational.com	 Uucp:  ...!uunet!igor!dsb
                            ...!{elxsi|sun}!aeras!igor!dsb

------------------------CUT HERE-----------------------------------------------

/*
 * Reduce the grammar:  Find and eliminate unreachable terminals,
 * nonterminals, and productions.  David S. Bakin.
 */

/* Copyright (C) 1988 Free Software Foundation, Inc.

BISON is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY.  No author or distributor accepts responsibility to anyone
for the consequences of using it or for whether it serves any
particular purpose or works at all, unless he says so in writing.
Refer to the BISON General Public License for full details.

Everyone is granted permission to copy, modify and redistribute BISON,
but only under the conditions described in the BISON General Public
License.  A copy of this license is supposed to have been given to you
along with BISON so you can know your rights and responsibilities.  It
should be in a file named COPYING.  Among other things, the copyright
notice and this notice must be preserved on all copies.

 In other words, you are welcome to use, share and improve this program.
 You are forbidden to forbid anyone else to use, share and improve
 what you give them.   Help stamp out software-hoarding!  */

/*
 * Don't eliminate unreachable terminals:  They may be used by the user's
 * parser.
 */

#include <stdio.h>
#include "files.h"
#include "gram.h"
#include "machine.h"
#include "new.h"


extern char   **tags;		/* reader.c */
extern int      verboseflag;	/* getargs.c */
static int      statisticsflag;	/* XXXXXXX */

#define TRUE	(1)
#define FALSE	(0)
typedef int bool;
typedef unsigned *BSet;
typedef short  *rule;

#define FOREVER	for (;;)
#define FORALLRULES(i)	for (i = 1; i <= nrules; i++)
#define FORALLTOKENS(i)	for (i = 0; i < ntokens; i++)
#define FORALLVARS(i)	for (i = ntokens; i < nsyms; i++)

/*
 * N is set of all nonterminals which are not useless.  P is set of all rules
 * which have no useless nonterminals in their RHS.  V is the set of all
 * accessible symbols.
 */

static BSet     N, P, V;

static int      nuseful_productions, nuseless_productions,
                nuseful_nonterminals, nuseless_nonterminals;


static void useless_nonterminals();
static void inaccessable_symbols();
static void reduce_grammar_tables();
static void print_results();
static void print_notices();
void dump_grammar();


bool  bits_equal(L, R, n)
BSet L;
BSet R;
int n;
{
	int i;

	for (i = n - 1; i >= 0; i--)
		if (L[i] != R[i])
			return FALSE;
	return TRUE;
}


int nbits(i)
unsigned i;
{
	int count = 0;

	while (i != 0) {
		i ^= (i & -i);
		++count;
	}
	return count;
}


int bits_size(S, n)
BSet S;
int n;
{
	int i, count = 0;

	for (i = n - 1; i >= 0; i--)
		count += nbits(S[i]);
	return count;
}


void reduce_grammar()
{
	bool reduced;

	/* Allocate the global sets used to compute the reduced grammar */

	N = NEW2(WORDSIZE(nvars), unsigned);
	P = NEW2(WORDSIZE(nrules + 1), unsigned);
	V = NEW2(WORDSIZE(nsyms), unsigned);

	useless_nonterminals();
	inaccessable_symbols();

	reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);

	if (verboseflag)
		print_results();

	if (reduced == FALSE)
		goto done_reducing;

	print_notices();

	if (!BITISSET(N, start_symbol - ntokens))
		fatals("Start symbol %s does not derive any sentence.",
		       tags[start_symbol]);

	reduce_grammar_tables();
	/* if (verboseflag) {
	       fprintf(foutput, "REDUCED GRAMMAR\n\n");
	       dump_grammar();
	   }
	*/

	 /**/ statisticsflag = FALSE; /* someday getopts should handle this */
	if (statisticsflag == TRUE)
		fprintf(stderr,
			"reduced %s defines %d terminal%s, %d nonterminal%s\
, and %d production%s.\n", infile,
			ntokens, (ntokens == 1 ? "" : "s"),
			nvars,   (nvars   == 1 ? "" : "s"),
			nrules,  (nrules  == 1 ? "" : "s"));

done_reducing:

	/* Free the global sets used to compute the reduced grammar */

	FREE(N);
	FREE(V);
	FREE(P);

}


/*
 * Another way to do this would be with a set for each production and then do
 * subset tests against N, but even for the C grammar the whole reducing
 * process takes only 2 seconds on my 8Mhz AT.
 */

static bool 
useful_production(i, N)
int  i;
BSet N;
{
	rule  r;
	short n;

	/*
	 * A production is useful if all of the nonterminals in its RHS
	 * appear in the set of useful nonterminals.
	 */

	for (r = &ritem[rrhs[i]]; *r > 0; r++)
		if (ISVAR(n = *r))
			if (!BITISSET(N, n - ntokens))
				return FALSE;
	return TRUE;
}


/* Remember that rules are 1-origin, symbols are 0-origin. */

static void 
useless_nonterminals()
{
	BSet Np, Ns;
	int  i, n;

	/*
	 * N is set as built.  Np is set being built this iteration. P is set
	 * of all productions which have a RHS all in N.
	 */

	Np = NEW2(WORDSIZE(nvars), unsigned);

	/*
	 * The set being computed is a set of nonterminals which can derive
	 * the empty string or strings consisting of all terminals. At each
	 * iteration a nonterminal is added to the set if there is a
	 * production with that nonterminal as its LHS for which all the
	 * nonterminals in its RHS are already in the set.  Iterate until the
	 * set being computed remains unchanged.  Any nonterminals not in the
	 * set at that point are useless in that they will never be used in
	 * deriving a sentence of the language.
	 * 
	 * This iteration doesn't use any special traversal over the
	 * productions.  A set is kept of all productions for which all the
	 * nonterminals in the RHS are in useful.  Only productions not in
	 * this set are scanned on each iteration.  At the end, this set is
	 * saved to be used when finding useful productions: only productions
	 * in this set will appear in the final grammar.
	 */

	n = 0;
	FOREVER {
		for (i = WORDSIZE(nvars) - 1; i >= 0; i--)
			Np[i] = N[i];
		FORALLRULES(i) {
			if (!BITISSET(P, i)) {
				if (useful_production(i, N)) {
					SETBIT(Np, rlhs[i] - ntokens);
					SETBIT(P, i);
				}
			}
		}
		if (bits_equal(N, Np, WORDSIZE(nvars)))
			break;
		Ns = Np;
		Np = N;
		N = Ns;
	}
	FREE(N);
	N = Np;
}


static void 
inaccessable_symbols()
{
	BSet  Vp, Vs, Pp;
	int   i, n;
	short j, t;
	rule  r;

	/*
	 * Find out which productions are reachable and which symbols are
	 * used.  Starting with an empty set of productions and a set of
	 * symbols which only has the start symbol in it, iterate over all
	 * productions until the set of productions remains unchanged for an
	 * iteration.  For each production which has a LHS in the set of
	 * reachable symbols, add the production to the set of reachable
	 * productions, and add all of the nonterminals in the RHS of the
	 * production to the set of reachable symbols.
	 * 
	 * Consider only the (partially) reduced grammar which has only
	 * nonterminals in N and productions in P.
	 * 
	 * The result is the set P of productions in the reduced grammar, and
	 * the set V of symbols in the reduced grammar.
	 * 
	 * Although this algorithm also computes the set of terminals which are
	 * reachable, no terminal will be deleted from the grammar. Some
	 * terminals might not be in the grammar but might be generated by
	 * semantic routines, and so the user might want them available with
	 * specified numbers.  (Is this true?)  However, the nonreachable
	 * terminals are printed (if running in verbose mode) so that the user
	 * can know.
	 */

	Vp = NEW2(WORDSIZE(nsyms), unsigned);
	Pp = NEW2(WORDSIZE(nrules + 1), unsigned);

	/* If the start symbol isn't useful, then nothing will be useful. */
	if (!BITISSET(N, start_symbol - ntokens))
		goto end_iteration;

	SETBIT(V, start_symbol);

	n = 0;
	FOREVER {
		for (i = WORDSIZE(nsyms) - 1; i >= 0; i--)
			Vp[i] = V[i];
		FORALLRULES(i) {
			if (!BITISSET(Pp, i) && BITISSET(P, i) && 
			    BITISSET(V, rlhs[i])) {
				for (r = &ritem[rrhs[i]]; *r >= 0; r++) {
					if (ISTOKEN(t = *r) ||
					    BITISSET(N, t - ntokens)) {
						SETBIT(Vp, t);
					}
				}
				SETBIT(Pp, i);
			}
		}
		if (bits_equal(V, Vp, WORDSIZE(nsyms))) {
			break;
		}
		Vs = Vp;
		Vp = V;
		V = Vs;
	}
end_iteration:

	FREE(V);
	V = Vp;

	/* Tokens 0, 1, and 2 are internal to Bison.  Consider them useful. */
	SETBIT(V, 0);		/* end-of-input token */
	SETBIT(V, 1);		/* error token */
	SETBIT(V, 2);		/* illegal token */

	FREE(P);
	P = Pp;

	nuseful_productions = bits_size(P, WORDSIZE(nrules + 1));
	nuseless_productions = nrules - nuseful_productions;

	nuseful_nonterminals = 0;
	FORALLVARS(i)
		if (BITISSET(V, i))
			nuseful_nonterminals++;
	nuseless_nonterminals = nvars - nuseful_nonterminals;

}


static void 
reduce_grammar_tables()
{

	/* remove useless productions */
	if (nuseless_productions > 0) {

		short np, pn, ni, pi;

		np = 0;
		ni = 0;
		FORALLRULES(pn) {
		    if (BITISSET(P, pn)) {
			np++;
			if (pn != np) {
			    rlhs[np] = rlhs[pn];
			    rprec[np] = rprec[pn];
			    rassoc[np] = rassoc[pn];
			    rrhs[np] = rrhs[pn];
			    if (rrhs[np] != ni) {
				pi = rrhs[np];
				rrhs[np] = ni;
				while (ritem[pi] >= 0)
				  ritem[ni++] = ritem[pi++];
				ritem[ni++] = -np;
			    }
			} else {
			    while (ritem[ni++] >= 0);
			}
		    }
		}
		ritem[ni] = 0;
		nrules -= nuseless_productions;
		nitems = ni;

		/*
		 * Is it worth it to reduce the amount of memory for the
		 * grammar? Probably not.
		 */

	}
	/* remove useless symbols */
	if (nuseless_nonterminals > 0) {

		int    i, n;
		short  j;
		short *nontermmap;
		rule   r;

		/*
		 * create a map of nonterminal number to new nonterminal
		 * number. -1 in the map means it was useless and is being
		 * eliminated.
		 */

		nontermmap = NEW2(nvars, short) - ntokens;
		FORALLVARS(i) nontermmap[i] = -1;

		n = ntokens;
		FORALLVARS(i)
			if (BITISSET(V, i))
			    nontermmap[i] = n++;

		FORALLVARS(i) {
			n = nontermmap[i];
			if (n >= 0) {
			    sassoc[n] = sassoc[i];
			    sprec[n] = sprec[i];
			    tags[n] = tags[i];
			} else {
			    free(tags[i]);
			}
		}

		FORALLRULES(i) rlhs[i] = nontermmap[rlhs[i]];

		for (r = ritem; *r; r++)
		  if (ISVAR(*r))
		    *r = nontermmap[*r];

		nsyms -= nuseless_nonterminals;
		nvars -= nuseless_nonterminals;

		free(&nontermmap[ntokens]);
	}
}


static void 
print_results()
{
	int   i;
	short j;
	rule  r;
	bool  b;

	if (nuseless_nonterminals > 0) {
		fprintf(foutput, "Useless nonterminals:\n\n");
		FORALLVARS(i)
			if (!BITISSET(V, i))
			        fprintf(foutput, "   %s\n", tags[i]);
	}
	b = FALSE;
	FORALLTOKENS(i) {
		if (!BITISSET(V, i)) {
			if (!b) {
				fprintf(foutput, "\n\nTerminals which can't \
be generated:\n\n");
				b = TRUE;
			}
			fprintf(foutput, "   %s\n", tags[i]);
		}
	}

	if (nuseless_productions > 0) {
		fprintf(foutput, "\n\nUseless productions:\n\n");
		FORALLRULES(i) {
			if (!BITISSET(P, i)) {
				fprintf(foutput, "#%-4d  ", i);
				fprintf(foutput, "%s :\t", tags[rlhs[i]]);
				for (r = &ritem[rrhs[i]]; *r >= 0; r++) {
					fprintf(foutput, " %s", tags[*r]);
				}
				fprintf(foutput, ";\n");
			}
		}
	}
	if (nuseless_nonterminals > 0 || nuseless_productions > 0 || b)
		fprintf(foutput, "\n\n");
}


void 
dump_grammar()
{
	int i;
	rule r;

	fprintf(foutput,
		"ntokens = %d, nvars = %d, nsyms = %d, nrules = %d, nitems = %d\n\n",
		ntokens, nvars, nsyms, nrules, nitems);
	fprintf(foutput, "Variables\n---------\n\n");
	fprintf(foutput, "Value  Sprec    Sassoc    Tag\n");
	FORALLVARS(i)
	  fprintf(foutput, "%5d  %5d  %5d  %s\n",
		  i, sprec[i], sassoc[i], tags[i]);
	fprintf(foutput, "\n\n");
	fprintf(foutput, "Rules\n-----\n\n");
	FORALLRULES(i) {
	    fprintf(foutput, "%-5d(%5d%5d)%5d : (@%-5d)", 
		    i, rprec[i], rassoc[i], rlhs[i], rrhs[i]);
	    for (r = &ritem[rrhs[i]]; *r > 0; r++)
	      fprintf(foutput, "%5d", *r);
	    fprintf(foutput, " [%d]\n", -(*r));
	}
	fprintf(foutput, "\n\n");
	fprintf(foutput, "Rules interpreted\n-----------------\n\n");
	FORALLRULES(i) {
	    fprintf(foutput, "%-5d  %s :", i, tags[rlhs[i]]);
	    for (r = &ritem[rrhs[i]]; *r > 0; r++)
	      fprintf(foutput, " %s", tags[*r]);
	    fprintf(foutput, "\n");
	}
	fprintf(foutput, "\n\n");
}


static void 
print_notices()
{
	fprintf(stderr, "%s contains ", infile);

	if (nuseless_nonterminals > 0) {
		fprintf(stderr, "%d useless nonterminal%s",
			nuseless_nonterminals,
			(nuseless_nonterminals == 1 ? "" : "s"));
	}
	if (nuseless_nonterminals > 0 && nuseless_productions > 0)
		fprintf(stderr, " and ");

	if (nuseless_productions > 0) {
		fprintf(stderr, "%d useless production%s",
			nuseless_productions,
			(nuseless_productions == 1 ? "" : "s"));
	}
	fprintf(stderr, ".\n");
	fflush(stderr);
}

/* End of reduce.c */