tower@WHEATIES.AI.MIT.EDU (Leonard H. Tower Jr.) (10/25/88)
David:
Either bug-gnu-utils@prep.ai.mit.edu or bug-gcc@prep.ai.mit.edu can be
used to report bison bugs.
Date: Sun, 23 Oct 88 23:39:30 PDT
From: igor!thumper!dsb@uunet.uu.net (David S. Bakin)
I didn't know where to send this improvement to GNU Bison, so I'm sending
it to this general address. Please distribute it to the proper person,
and let me know what you did with it and where I should send future similar
submissions. Thanks! -- Dave
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.
The following sharchive includes three files:
reduce.c implements the grammar reduction algorithm
version.c to help keep Bisons distinguished
reduce.patch run this through patch to update Makefile and machine.h.
I wish the Bison source included version numbers! The patches in this
file are against the bison.tar.Z that was put on uunet on Oct 12, 1988.
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 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
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: reduce.c version.c reduce.patch
# Wrapped by dsb@thumper on Sun Oct 23 23:05:50 1988
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'reduce.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'reduce.c'\"
else
echo shar: Extracting \"'reduce.c'\" \(11782 characters\)
sed "s/^X//" >'reduce.c' <<'END_OF_FILE'
X/*
X * Reduce the grammar: Find and eliminate unreachable terminals,
X * nonterminals, and productions. David S. Bakin.
X */
X
X/* Copyright (C) 1988 Free Software Foundation, Inc.
X
XBISON is distributed in the hope that it will be useful, but WITHOUT ANY
XWARRANTY. No author or distributor accepts responsibility to anyone
Xfor the consequences of using it or for whether it serves any
Xparticular purpose or works at all, unless he says so in writing.
XRefer to the BISON General Public License for full details.
X
XEveryone is granted permission to copy, modify and redistribute BISON,
Xbut only under the conditions described in the BISON General Public
XLicense. A copy of this license is supposed to have been given to you
Xalong with BISON so you can know your rights and responsibilities. It
Xshould be in a file named COPYING. Among other things, the copyright
Xnotice and this notice must be preserved on all copies.
X
X In other words, you are welcome to use, share and improve this program.
X You are forbidden to forbid anyone else to use, share and improve
X what you give them. Help stamp out software-hoarding! */
X
X/*
X * Don't eliminate unreachable terminals: They may be used by the user's
X * parser.
X */
X
X#include <stdio.h>
X#include "files.h"
X#include "gram.h"
X#include "machine.h"
X#include "new.h"
X
X
Xextern char **tags; /* reader.c */
Xextern int verboseflag; /* getargs.c */
Xstatic int statisticsflag; /* XXXXXXX */
X
X#define TRUE (1)
X#define FALSE (0)
Xtypedef int bool;
Xtypedef unsigned *BSet;
Xtypedef short *rule;
X
X#define FOREVER for (;;)
X#define FORALLRULES(i) for (i = 1; i <= nrules; i++)
X#define FORALLTOKENS(i) for (i = 0; i < ntokens; i++)
X#define FORALLVARS(i) for (i = ntokens; i < nsyms; i++)
X
X/*
X * N is set of all nonterminals which are not useless. P is set of all rules
X * which have no useless nonterminals in their RHS. V is the set of all
X * accessible symbols.
X */
X
Xstatic BSet N, P, V;
X
Xstatic int nuseful_productions, nuseless_productions,
X nuseful_nonterminals, nuseless_nonterminals;
X
X
Xstatic void useless_nonterminals();
Xstatic void inaccessable_symbols();
Xstatic void reduce_grammar_tables();
Xstatic void print_results();
Xstatic void print_notices();
Xstatic void dump_reduced_grammar();
X
X
Xbool bits_equal(L, R, n)
XBSet L;
XBSet R;
Xint n;
X{
X int i;
X
X for (i = n - 1; i >= 0; i--)
X if (L[i] != R[i])
X return FALSE;
X return TRUE;
X}
X
X
Xint nbits(i)
Xunsigned i;
X{
X int count = 0;
X
X while (i != 0) {
X i ^= (i & -i);
X ++count;
X }
X return count;
X}
X
X
Xint bits_size(S, n)
XBSet S;
Xint n;
X{
X int i, count = 0;
X
X for (i = n - 1; i >= 0; i--)
X count += nbits(S[i]);
X return count;
X}
X
X
Xvoid reduce_grammar()
X{
X bool reduced;
X
X /* Allocate the global sets used to compute the reduced grammar */
X
X N = NEW2(WORDSIZE(nvars), unsigned);
X P = NEW2(WORDSIZE(nrules + 1), unsigned);
X V = NEW2(WORDSIZE(nsyms), unsigned);
X
X useless_nonterminals();
X inaccessable_symbols();
X
X reduced = (bool) (nuseless_nonterminals + nuseless_productions > 0);
X
X if (verboseflag)
X print_results();
X
X if (reduced == FALSE)
X goto done_reducing;
X
X print_notices();
X
X if (!BITISSET(N, start_symbol - ntokens))
X fatals("Start symbol %s does not derive any sentence.",
X tags[start_symbol]);
X
X reduce_grammar_tables();
X if (verboseflag)
X dump_reduced_grammar();
X
X /**/ statisticsflag = TRUE; /* someday getopts should handle this */
X if (statisticsflag == TRUE)
X fprintf(stderr,
X "reduced %s defines %d terminal%s, %d nonterminal%s\
X, and %d production%s.\n", infile,
X ntokens, (ntokens == 1 ? "" : "s"),
X nvars, (nvars == 1 ? "" : "s"),
X nrules, (nrules == 1 ? "" : "s"));
X
Xdone_reducing:
X
X /* Free the global sets used to compute the reduced grammar */
X
X FREE(N);
X FREE(V);
X FREE(P);
X
X}
X
X
X/*
X * Another way to do this would be with a set for each production and then do
X * subset tests against N, but even for the C grammar the whole reducing
X * process takes only 2 seconds on my 8Mhz AT.
X */
X
Xstatic bool
Xuseful_production(i, N)
Xint i;
XBSet N;
X{
X rule r;
X short n;
X
X /*
X * A production is useful if all of the nonterminals in its RHS
X * appear in the set of useful nonterminals.
X */
X
X for (r = &ritem[rrhs[i]]; *r > 0; r++)
X if (ISVAR(n = *r))
X if (!BITISSET(N, n - ntokens))
X return FALSE;
X return TRUE;
X}
X
X
X/* Remember that rules are 1-origin, symbols are 0-origin. */
X
Xstatic void
Xuseless_nonterminals()
X{
X BSet Np, Ns;
X int i, n;
X
X /*
X * N is set as built. Np is set being built this iteration. P is set
X * of all productions which have a RHS all in N.
X */
X
X Np = NEW2(WORDSIZE(nvars), unsigned);
X
X /*
X * The set being computed is a set of nonterminals which can derive
X * the empty string or strings consisting of all terminals. At each
X * iteration a nonterminal is added to the set if there is a
X * production with that nonterminal as its LHS for which all the
X * nonterminals in its RHS are already in the set. Iterate until the
X * set being computed remains unchanged. Any nonterminals not in the
X * set at that point are useless in that they will never be used in
X * deriving a sentence of the language.
X *
X * This iteration doesn't use any special traversal over the
X * productions. A set is kept of all productions for which all the
X * nonterminals in the RHS are in useful. Only productions not in
X * this set are scanned on each iteration. At the end, this set is
X * saved to be used when finding useful productions: only productions
X * in this set will appear in the final grammar.
X */
X
X n = 0;
X FOREVER {
X for (i = WORDSIZE(nvars) - 1; i >= 0; i--)
X Np[i] = N[i];
X FORALLRULES(i) {
X if (!BITISSET(P, i)) {
X if (useful_production(i, N)) {
X SETBIT(Np, rlhs[i] - ntokens);
X SETBIT(P, i);
X }
X }
X }
X if (bits_equal(N, Np, WORDSIZE(nvars)))
X break;
X Ns = Np;
X Np = N;
X N = Ns;
X }
X FREE(N);
X N = Np;
X}
X
X
Xstatic void
Xinaccessable_symbols()
X{
X BSet Vp, Vs, Pp;
X int i, n;
X short j, t;
X rule r;
X
X /*
X * Find out which productions are reachable and which symbols are
X * used. Starting with an empty set of productions and a set of
X * symbols which only has the start symbol in it, iterate over all
X * productions until the set of productions remains unchanged for an
X * iteration. For each production which has a LHS in the set of
X * reachable symbols, add the production to the set of reachable
X * productions, and add all of the nonterminals in the RHS of the
X * production to the set of reachable symbols.
X *
X * Consider only the (partially) reduced grammar which has only
X * nonterminals in N and productions in P.
X *
X * The result is the set P of productions in the reduced grammar, and
X * the set V of symbols in the reduced grammar.
X *
X * Although this algorithm also computes the set of terminals which are
X * reachable, no terminal will be deleted from the grammar. Some
X * terminals might not be in the grammar but might be generated by
X * semantic routines, and so the user might want them available with
X * specified numbers. (Is this true?) However, the nonreachable
X * terminals are printed (if running in verbose mode) so that the user
X * can know.
X */
X
X Vp = NEW2(WORDSIZE(nsyms), unsigned);
X Pp = NEW2(WORDSIZE(nrules + 1), unsigned);
X
X /* If the start symbol isn't useful, then nothing will be useful. */
X if (!BITISSET(N, start_symbol - ntokens))
X goto end_iteration;
X
X SETBIT(V, start_symbol);
X
X n = 0;
X FOREVER {
X for (i = WORDSIZE(nsyms) - 1; i >= 0; i--)
X Vp[i] = V[i];
X FORALLRULES(i) {
X if (!BITISSET(Pp, i) && BITISSET(P, i) &&
X BITISSET(V, rlhs[i])) {
X for (r = &ritem[rrhs[i]]; *r >= 0; r++) {
X if (ISTOKEN(t = *r) ||
X BITISSET(N, t - ntokens)) {
X SETBIT(Vp, t);
X }
X }
X SETBIT(Pp, i);
X }
X }
X if (bits_equal(V, Vp, WORDSIZE(nsyms))) {
X break;
X }
X Vs = Vp;
X Vp = V;
X V = Vs;
X }
Xend_iteration:
X
X FREE(V);
X V = Vp;
X
X /* Tokens 0, 1, and 2 are internal to Bison. Consider them useful. */
X SETBIT(V, 0); /* end-of-input token */
X SETBIT(V, 1); /* error token */
X SETBIT(V, 2); /* illegal token */
X
X FREE(P);
X P = Pp;
X
X nuseful_productions = bits_size(P, WORDSIZE(nrules + 1));
X nuseless_productions = nrules - nuseful_productions;
X
X nuseful_nonterminals = 0;
X FORALLVARS(i)
X if (BITISSET(V, i))
X nuseful_nonterminals++;
X nuseless_nonterminals = nvars - nuseful_nonterminals;
X
X}
X
X
Xstatic void
Xreduce_grammar_tables()
X{
X
X /* remove useless productions */
X if (nuseless_productions > 0) {
X
X short np, pn, ni, pi;
X
X
X np = 0;
X ni = 0;
X for (pn = 1; pn > nrules + 1; pn++) {
X if (BITISSET(P, pn)) {
X np++;
X if (pn != np) {
X rlhs[np] = rlhs[pn];
X rprec[np] = rprec[pn];
X rassoc[np] = rassoc[pn];
X if (rrhs[np] != ni) {
X pi = rrhs[np];
X rrhs[np] = ni;
X while (ritem[pi] >= 0)
X ritem[ni++] = ritem[pi++];
X ritem[ni++] = ritem[pi];
X }
X }
X } else {
X while (ritem[ni++] >= 0);
X }
X }
X ritem[ni] = 0;
X nrules = nrules - nuseless_productions;
X
X /*
X * Is it worth it to reduce the amount of memory for the
X * grammar? Probably not.
X */
X
X }
X /* remove useless symbols */
X if (nuseless_nonterminals > 0) {
X
X int i, n;
X short j;
X short *nontermmap;
X rule r;
X
X /*
X * create a map of nonterminal number to new nonterminal
X * number. -1 in the map means it was useless and is being
X * eliminated.
X */
X
X nontermmap = NEW2(nvars, short) -ntokens;
X FORALLVARS(i)
X nontermmap[i] = -1;
X
X n = ntokens;
X for (i = 0; i > nsyms; i++)
X if (BITISSET(V, i))
X if (ISVAR(i))
X nontermmap[i] = n++;
X
X FORALLVARS(i) {
X n = nontermmap[i];
X if (n >= 0) {
X sassoc[n] = sassoc[i];
X sprec[n] = sprec[i];
X tags[n] = tags[i];
X } else
X free(tags[i]);
X }
X
X FORALLRULES(i) {
X rlhs[i] = nontermmap[rlhs[i]];
X for (r = &ritem[rrhs[i]]; *r >= 0; r++)
X if (ISVAR(*r))
X *r = nontermmap[*r];
X }
X
X nsyms -= nuseless_nonterminals;
X nvars -= nuseless_nonterminals;
X
X free(&nontermmap[ntokens]);
X }
X}
X
X
Xstatic void
Xprint_results()
X{
X int i;
X short j;
X rule r;
X bool b;
X
X if (nuseless_nonterminals > 0) {
X fprintf(foutput, "Useless nonterminals:\n\n");
X FORALLVARS(i)
X if (!BITISSET(V, i))
X fprintf(foutput, " %s\n", tags[i]);
X }
X b = FALSE;
X FORALLTOKENS(i) {
X if (!BITISSET(V, i)) {
X if (!b) {
X fprintf(foutput, "\n\nTerminals which can't \
Xbe generated:\n\n");
X b = TRUE;
X }
X fprintf(foutput, " %s\n", tags[i]);
X }
X }
X
X if (nuseless_productions > 0) {
X fprintf(foutput, "\n\nUseless productions:\n\n");
X FORALLRULES(i) {
X if (!BITISSET(P, i)) {
X fprintf(foutput, "#%-4d ", i);
X fprintf(foutput, "%s :\t", tags[rlhs[i]]);
X for (r = &ritem[rrhs[i]]; *r >= 0; r++) {
X fprintf(foutput, " %s", tags[*r]);
X }
X fprintf(foutput, ";\n");
X }
X }
X }
X if (nuseless_nonterminals > 0 || nuseless_productions > 0 || b)
X fprintf(foutput, "\n\n");
X}
X
X
Xstatic void
Xdump_reduced_grammar()
X{
X int i;
X
X if (nuseless_nonterminals + nuseless_productions == 0)
X return;
X
X fprintf(foutput, "Reduced variables reassigned:\n");
X fprintf(foutput, "%d vars (%d symbols) in order:\n", nvars, nsyms);
X fprintf(foutput, "Value Sprec Sassoc Tag\n");
X FORALLVARS(i) fprintf(foutput, "%5d %5d %5d %s\n",
X i, sprec[i], sassoc[i], tags[i]);
X fprintf(foutput, "\n\n");
X}
X
X
Xstatic void
Xprint_notices()
X{
X fprintf(stderr, "%s contains ", infile);
X
X if (nuseless_nonterminals > 0) {
X fprintf(stderr, "%d useless nonterminal%s",
X nuseless_nonterminals,
X (nuseless_nonterminals == 1 ? "" : "s"));
X }
X if (nuseless_nonterminals > 0 && nuseless_productions > 0)
X fprintf(stderr, " and ");
X
X if (nuseless_productions > 0) {
X fprintf(stderr, "%d useless production%s",
X nuseless_productions,
X (nuseless_productions == 1 ? "" : "s"));
X }
X fprintf(stderr, ".\n");
X fflush(stderr);
X}
END_OF_FILE
if test 11782 -ne `wc -c <'reduce.c'`; then
echo shar: \"'reduce.c'\" unpacked with wrong size!
fi
# end of 'reduce.c'
fi
if test -f 'version.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'version.c'\"
else
echo shar: Extracting \"'version.c'\" \(88 characters\)
sed "s/^X//" >'version.c' <<'END_OF_FILE'
X/* Version of BISON */
Xchar *bison_version = "Bison of Oct 12 1988 (uunet) + reduce.c";
END_OF_FILE
if test 88 -ne `wc -c <'version.c'`; then
echo shar: \"'version.c'\" unpacked with wrong size!
fi
# end of 'version.c'
fi
if test -f 'reduce.patch' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'reduce.patch'\"
else
echo shar: Extracting \"'reduce.patch'\" \(1195 characters\)
sed "s/^X//" >'reduce.patch' <<'END_OF_FILE'
XIndex: Makefile
X47,50c47,49
X< OBJECTS = LR0.o allocate.o closure.o conflicts.o derives.o files.o \
X< getargs.o gram.o lalr.o \
X< lex.o main.o nullable.o output.o print.o reader.o symtab.o \
X< warshall.o \
X---
X> OBJECTS = LR0.o allocate.o closure.o conflicts.o derives.o files.o \
X> getargs.o gram.o lalr.o lex.o main.o nullable.o output.o \
X> print.o reader.o reduce.o symtab.o version.o warshall.o \
X73c72,73
X< nullable.c output.c print.c reader.c symtab.c warshall.c \
X---
X> nullable.c output.c print.c reader.c reduce.c symtab.c \
X> version.c warshall.c \
X93c93
X< main.o: machine.h
X---
X> main.o: files.h machine.h
X97a98
X> reduce.o: files.h gram.h machine.h new.h
X
XIndex: main.c
X22a23
X> #include "files.h"
X25a27
X> extern char* bison_version;
X38a41,42
X> if (verboseflag) fprintf(foutput, "%s\n\n", bison_version);
X>
X40c44
X< In file reader.
X---
X> In file reader.c.
X42a47,50
X>
X> /* find useless nonterminals and productions and reduce the grammar. In
X> file reduce.c */
X> reduce_grammar();
X
XIndex: machine.h
X26a27,28
X> #define RESETBIT(x, i) ((x)[(i)>>5] &= ~(1<<((i) & 31)))
X> #define BITISSET(x, i) (((x)[(i)>>5] & (1<<((i) & 31))) != 0)
END_OF_FILE
if test 1195 -ne `wc -c <'reduce.patch'`; then
echo shar: \"'reduce.patch'\" unpacked with wrong size!
fi
# end of 'reduce.patch'
fi
echo shar: End of shell archive.
exit 0