* src/getargs.h (enum trace_e): New.
* src/getargs.c (trace_args, trace_types, trace_argmatch): New.
(long_options, short_options): --trace/-T takes an optional
argument.
Change all the uses of trace_flag to reflect the new flags.
* tests/sets.at (Firsts, Nullable, Broken Closure): Use --trace=sets.
Strengthen `stage' portability.
* m4/stage.m4 (BISON_PREREQ_STAGE): New.
* configure.in: Use it.
Don't check for malloc.h and sys/times.h.
* src/system.h: Include them when appropriate.
* src/main.c (stage): Compile only when mallinfo, struct mallinfo,
times and struct tms are available.
+2002-07-31 Akim Demaille <akim@epita.fr>
+
+ Let --trace have arguments.
+
+ * src/getargs.h (enum trace_e): New.
+ * src/getargs.c (trace_args, trace_types, trace_argmatch): New.
+ (long_options, short_options): --trace/-T takes an optional
+ argument.
+ Change all the uses of trace_flag to reflect the new flags.
+ * tests/sets.at (Firsts, Nullable, Broken Closure): Use --trace=sets.
+
+ Strengthen `stage' portability.
+
+ * m4/stage.m4 (BISON_PREREQ_STAGE): New.
+ * configure.in: Use it.
+ Don't check for malloc.h and sys/times.h.
+ * src/system.h: Include them when appropriate.
+ * src/main.c (stage): Compile only when mallinfo, struct mallinfo,
+ times and struct tms are available.
+
2002-07-30 Akim Demaille <akim@epita.fr>
In verbose parse error message, don't report `error' as an
# Checks for header files.
AC_HEADER_STDC
-AC_CHECK_HEADERS([ctype.h locale.h malloc.h memory.h stdlib.h string.h \
- sys/times.h unistd.h])
-
+AC_CHECK_HEADERS([ctype.h locale.h memory.h stdlib.h string.h unistd.h])
# Checks for compiler characteristics.
AC_C_CONST
jm_PREREQ_QUOTEARG
jm_PREREQ_ERROR
AM_WITH_DMALLOC
+BISON_PREREQ_STAGE
# Gettext.
GETTEXT_VERSION=0.11.2
prereq.m4 \
progtest.m4 \
realloc.m4 \
+stage.m4 \
strerror_r.m4 \
warning.m4
--- /dev/null
+# -*-Autoconf-*-
+# Checks required to run `stage', a nonportable memory/time tracker.
+#
+# Copyright (C) 2002 Free Software Foundation, Inc.
+#
+# This program 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 of the License, or
+# (at your option) any later version.
+#
+# This program 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 this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+# 02111-1307 USA
+
+# serial 1
+
+AC_DEFUN([BISON_PREREQ_STAGE],
+[AC_CHECK_HEADERS([malloc.h sys/times.h])
+AC_CHECK_FUNCS([mallinfo times])
+
+AC_CHECK_TYPES([struct mallinfo], [], [],
+[$ac_includes_default
+#if HAVE_MALLOC_H
+# include <malloc.h>
+#endif
+])
+
+AC_CHECK_TYPES([struct tms], [], [],
+[$ac_includes_default
+#if HAVE_SYS_TIMES_H
+# include <sys/times.h>
+#endif
+])
+])
-AC_DEFUN(BISON_WARNING,
+# Finding valid warning flags for the C Compiler. -*-Autoconf-*-
+#
+# Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+#
+# This program 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 of the License, or
+# (at your option) any later version.
+#
+# This program 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 this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+# 02111-1307 USA
+
+# serial 1
+
+AC_DEFUN([BISON_WARNING],
[AC_MSG_CHECKING(whether compiler accepts $1)
AC_SUBST(WARNING_CFLAGS)
ac_save_CFLAGS="$CFLAGS"
state_list_t *node = XMALLOC (state_list_t, 1);
state_t *state = state_new (symbol, core_size, core);
- if (trace_flag)
+ if (trace_flag & trace_automaton)
fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n",
nstates, symbol, symbols[symbol]->tag);
{
int i;
- if (trace_flag)
+ if (trace_flag & trace_automaton)
fprintf (stderr, "Entering new_itemsets, state = %d\n",
state->number);
{
state_t *sp;
- if (trace_flag)
+ if (trace_flag & trace_automaton)
fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
symbol, symbols[symbol]->tag);
if (!sp)
sp = state_list_append (symbol, core_size, core);
- if (trace_flag)
+ if (trace_flag & trace_automaton)
fprintf (stderr, "Exiting get_state => %d\n", sp->number);
return sp;
int j;
symbol_number_t symbol;
- if (trace_flag)
+ if (trace_flag & trace_automaton)
fprintf (stderr, "Entering append_states, state = %d\n",
state->number);
while (list)
{
state_t *state = list->state;
- if (trace_flag)
+ if (trace_flag & trace_automaton)
fprintf (stderr, "Processing state %d (reached by %s)\n",
state->number,
symbols[state->accessing_symbol]->tag);
bitset_set (FIRSTS (i), symbol - ntokens);
}
- if (trace_flag)
+ if (trace_flag & trace_sets)
bitsetv_matrix_dump (stderr, "RTC: Firsts Input", firsts);
bitsetv_reflexive_transitive_closure (firsts);
- if (trace_flag)
+ if (trace_flag & trace_sets)
bitsetv_matrix_dump (stderr, "RTC: Firsts Output", firsts);
- if (trace_flag)
+ if (trace_flag & trace_sets)
print_firsts ();
}
for (k = 0; derives[j][k] >= 0; ++k)
bitset_set (FDERIVES (i), derives[j][k]);
- if (trace_flag)
+ if (trace_flag & trace_sets)
print_fderives ();
bitsetv_free (firsts);
bitset_iterator iter;
- if (trace_flag)
+ if (trace_flag & trace_sets)
print_closure ("input", core, n);
bitset_zero (ruleset);
c++;
}
- if (trace_flag)
+ if (trace_flag & trace_sets)
print_closure ("output", itemset, nritemset);
}
*q++ = -1;
}
- if (trace_flag)
+ if (trace_flag & trace_sets)
print_derives ();
free (dset + ntokens);
int locations_flag = 0;
int no_lines_flag = 0;
int no_parser_flag = 0;
-int report_flag = 0;
+int report_flag = report_none;
int token_table_flag = 0;
int yacc_flag = 0; /* for -y */
int graph_flag = 0;
-int trace_flag = 0;
+int trace_flag = trace_none;
const char *skeleton = NULL;
const char *include = NULL;
extern char *program_name;
+
+/*---------------------.
+| --trace's handling. |
+`---------------------*/
+
+static const char * const trace_args[] =
+{
+ /* In a series of synonyms, present the most meaningful first, so
+ that argmatch_valid be more readable. */
+ "none - no report",
+ "automaton - contruction of the automaton",
+ "bitsets - use of bitsets",
+ "grammar - reading, reducing of the grammar",
+ "resource - time and memory (where available)",
+ "sets - grammar sets: firsts, nullable etc.",
+ "tools - m4 invocation and preserve the temporary file",
+ "all - all of the above",
+ 0
+};
+
+static const int trace_types[] =
+{
+ trace_none,
+ trace_automaton,
+ trace_bitsets,
+ trace_grammar,
+ trace_resource,
+ trace_sets,
+ trace_tools,
+ trace_all
+};
+
+
+static void
+trace_argmatch (char *args)
+{
+ ARGMATCH_ASSERT (trace_args, trace_types);
+ if (args)
+ {
+ args = strtok (args, ",");
+ do
+ {
+ int trace = XARGMATCH ("--trace", args,
+ trace_args, trace_types);
+ if (trace == trace_none)
+ trace_flag = trace_none;
+ else
+ trace_flag |= trace;
+ }
+ while ((args = strtok (NULL, ",")));
+ }
+ else
+ trace_flag = trace_all;
+}
+
+
/*----------------------.
| --report's handling. |
`----------------------*/
`----------------------*/
/* Shorts options. */
-const char *short_options = "yvegdhr:ltknVo:b:p:S:";
+const char *short_options = "yvegdhr:ltknVo:b:p:S:T::";
static struct option const long_options[] =
{
{ "verbose", no_argument, 0, 'v' },
/* Hidden. */
- { "trace", no_argument, &trace_flag, 1 },
+ { "trace", optional_argument, 0, 'T' },
/* FIXME: semantic parsers will output an `include' of an
output file: be sure that the naem included is indeed the name of
report_argmatch (optarg);
break;
+ case 'T':
+ trace_argmatch (optarg);
+ break;
+
default:
fprintf (stderr, _("Try `%s --help' for more information.\n"),
program_name);
extern int token_table_flag; /* for -k */
extern int graph_flag; /* for -g */
extern int yacc_flag; /* for -y */
+
+/* --trace. */
+enum trace_e
+ {
+ trace_none = 0,
+ trace_resource = 1 << 0,
+ trace_sets = 1 << 1,
+ trace_bitsets = 1 << 2,
+ trace_tools = 1 << 3,
+ trace_automaton = 1 << 4,
+ trace_grammar = 1 << 5,
+ trace_all = ~0
+ };
extern int trace_flag;
/* --report. */
-enum
+enum report_e
{
- report_none = 0,
- report_states = 1 << 0,
- report_itemsets = 1 << 1,
- report_lookaheads = 1 << 2,
+ report_none = 0,
+ report_states = 1 << 0,
+ report_itemsets = 1 << 1,
+ report_lookaheads = 1 << 2,
report_solved_conflicts = 1 << 3,
- report_all = ~0
+ report_all = ~0
};
-
extern int report_flag;
void getargs PARAMS ((int argc, char *argv[]));
--- /dev/null
+/* Grammar reduction for Bison.
+ Copyright (C) 2002 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. */
+
+/* Reduce the grammar: Look for injections. Akim Demaille. */
+
+#include "system.h"
+#include "quotearg.h"
+#include "bitsetv.h"
+#include "bitsetv-print.h"
+#include "complain.h"
+#include "gram.h"
+#include "getargs.h"
+#include "derives.h"
+#include "injections.h"
+
+/* Set of all nonterminals which are not useless. */
+static bitsetv injects;
+
+#define INJECTS(Var) injects[(Var) - ntokens]
+
+/*-----------------------------------------------------------.
+| Free the global sets used to compute the reduced grammar. |
+`-----------------------------------------------------------*/
+
+void
+injections_new (void)
+{
+ if (!injects)
+ injects = bitsetv_create (nvars, nvars, BITSET_FIXED);
+ else
+ bitsetv_zero (injects);
+}
+
+void
+injections_free (void)
+{
+ bitsetv_free (injects);
+ injects = NULL;
+}
+
+
+/*------------------------------.
+| Dump the list of injections. |
+`------------------------------*/
+
+static void
+injections_print (const char *title)
+{
+ int i, j;
+
+ fprintf (stderr, "%s\n", title);
+ for (i = ntokens; i < nsyms; i++)
+ if (bitset_count (INJECTS (i)))
+ {
+ fprintf (stderr, "\t%s injects\n",
+ quotearg_style (escape_quoting_style, symbols[i]->tag));
+ for (j = 0; j < nvars; j++)
+ if (bitset_test (INJECTS (i), j))
+ fprintf (stderr, "\t\t%s\n",
+ quotearg_style (escape_quoting_style,
+ symbols[j + ntokens]->tag));
+ }
+ fprintf (stderr, "\n\n");
+}
+
+
+/*-----------------------------------------------------------------.
+| Set INJECTS[i, j] if the nonterminal j derives the nonterminal j |
+| (typically, `i -> j' is a rule, plus transitive closure). |
+`-----------------------------------------------------------------*/
+
+static void
+injections_compute (void)
+{
+ int i, j;
+
+ injections_new ();
+ for (i = ntokens; i < nsyms; i++)
+ for (j = 0; derives[i][j] >= 0; ++j)
+ {
+ int symbol = rules[derives[i][j]].rhs[0];
+ if (ISVAR (symbol) && rules[derives[i][j]].rhs[1] < 0)
+ bitset_set (INJECTS (i), symbol - ntokens);
+ }
+
+ if (trace_flag & trace_sets)
+ injections_print ("syntactic direct injections");
+ bitsetv_transitive_closure (injects);
+ if (trace_flag & trace_sets)
+ injections_print ("syntactic injections");
+}
+
+
+
+/*--------------------------------------------------------------.
+| Look for infinitely ambiguous grammars: they contain cycles. |
+`--------------------------------------------------------------*/
+
+void
+injections_check_cycles (void)
+{
+ int i;
+
+ injections_compute ();
+ for (i = ntokens; i < nsyms; i++)
+ if (bitset_test (INJECTS (i), i - ntokens))
+ complain (_("infinitely ambiguous grammar: %s derives itself"),
+ symbols[i]->tag);
+}
compute_FOLLOWS ();
compute_lookaheads ();
- if (trace_flag)
+ if (trace_flag & trace_sets)
lookaheads_print (stderr);
}
| Tracking space and time. |
`--------------------------*/
-#if HAVE_MALLOC_H & HAVE_SYS_TIMES_H
-# include <malloc.h>
-# include <sys/times.h>
-#endif
-
static void
stage (const char *title)
{
-#if HAVE_MALLOC_H & HAVE_SYS_TIMES_H
- if (trace_flag)
+#if HAVE_MALLINFO && HAVE_STRUCT_MALLINFO & HAVE_TIMES & HAVE_STRUCT_TMS
+ if (trace_flag & trace_resource)
{
struct mallinfo minfo = mallinfo ();
struct tms tinfo;
getargs (argc, argv);
- if (trace_flag)
+ if (trace_flag & trace_bitsets)
bitset_stats_enable ();
muscle_init ();
alloca (0);
#endif
- if (trace_flag)
+ if (trace_flag & trace_bitsets)
bitset_stats_dump (stderr);
return complain_message_count ? EXIT_FAILURE : EXIT_SUCCESS;
Supposedly NRITEMS - NRULES is enough. But why take the risk? */
rule_list_t *relts = XCALLOC (rule_list_t, nritems + nvars + 1);
- if (trace_flag)
- fprintf (stderr, "Entering set_nullable\n");
-
nullable = XCALLOC (char, nvars) - ntokens;
s1 = s2 = squeue;
XFREE (rsets + ntokens);
XFREE (relts);
- if (trace_flag)
+ if (trace_flag & trace_sets)
nullable_print (stderr);
}
static int conflict_list_cnt;
static int conflict_list_free;
-/* TABLE_SIZE is the allocated size of both TABLE and CHECK.
- We start with the original hard-coded value: SHRT_MAX
- (yes, not USHRT_MAX). */
-static size_t table_size = SHRT_MAX;
+/* TABLE_SIZE is the allocated size of both TABLE and CHECK. We start
+ with more or less the original hard-coded value (which was
+ SHRT_MAX). */
+static size_t table_size = 32768;
static base_t *table = NULL;
static base_t *check = NULL;
/* The value used in TABLE to denote explicit parse errors
while (table_size <= desired)
table_size *= 2;
- if (trace_flag)
+ if (trace_flag & trace_resource)
fprintf (stderr, "growing table and check from: %d to %d\n",
old_size, table_size);
m4_invoke (tempfile);
/* If `debugging', keep this file alive. */
- if (!trace_flag)
+ if (!(trace_flag & trace_tools))
unlink (tempfile);
free (tempfile);
assert (itemno == nritems);
- if (trace_flag)
+ if (trace_flag & trace_sets)
ritem_print (stderr);
}
\f
if (nuseless_productions > 0)
reduce_grammar_tables ();
- if (trace_flag)
+ if (trace_flag & trace_grammar)
{
grammar_dump (stderr, "Reduced Grammar");
int *nedges = XCALLOC (int, n);
int i, j;
- if (trace_flag)
+ if (trace_flag & trace_sets)
{
fputs ("relation_transpose: input\n", stderr);
relation_print (*R_arg, n, stderr);
XFREE ((*R_arg)[i]);
free (*R_arg);
- if (trace_flag)
+ if (trace_flag & trace_sets)
{
fputs ("relation_transpose: output\n", stderr);
relation_print (new_R, n, stderr);
/* From xstrndup.c. */
char *xstrndup PARAMS ((const char *s, size_t n));
+/* Finding `mallinfo' where available. */
+#if HAVE_MALLOC_H
+# include <malloc.h>
+#endif
+
+
+/* Find `times' where available. */
+#if HAVE_SYS_TIMES_H
+# include <sys/times.h>
+#endif
+
+
/*---------------------.
| Missing prototypes. |
`---------------------*/
e: 'e' | /* Nothing */;
]])
-AT_CHECK([[bison --trace input.y]], [], [], [stderr])
+AT_CHECK([[bison --trace=sets input.y]], [], [], [stderr])
AT_EXTRACT_SETS([stderr], [sets])
AT_CHECK([[cat sets]], [],
[[DERIVES
h: 'h';
]])
-AT_CHECK([[bison --trace input.y]], [], [], [stderr])
+AT_CHECK([[bison --trace=sets input.y]], [], [], [stderr])
AT_CHECK([[sed -n 's/[ ]*$//;/^RTC: Firsts Output BEGIN/,/^RTC: Firsts Output END/p' stderr]], [],
[[RTC: Firsts Output BEGIN
;
]])
-AT_CHECK([[bison --trace input.y]], [], [], [stderr])
+AT_CHECK([[bison --trace=sets input.y]], [], [], [stderr])
AT_EXTRACT_SETS([stderr], [sets])
AT_CHECK([[cat sets]], [],
[[DERIVES
projects / bison.git / commitdiff
