diff options
| -rw-r--r-- | ChangeLog | 20 | ||||
| -rw-r--r-- | configure.in | 5 | ||||
| -rw-r--r-- | m4/Makefile.am | 1 | ||||
| -rw-r--r-- | m4/stage.m4 | 40 | ||||
| -rw-r--r-- | m4/warning.m4 | 23 | ||||
| -rw-r--r-- | src/LR0.c | 12 | ||||
| -rw-r--r-- | src/closure.c | 12 | ||||
| -rw-r--r-- | src/derives.c | 2 | ||||
| -rw-r--r-- | src/getargs.c | 68 | ||||
| -rw-r--r-- | src/getargs.h | 26 | ||||
| -rw-r--r-- | src/injections.c | 126 | ||||
| -rw-r--r-- | src/lalr.c | 2 | ||||
| -rw-r--r-- | src/main.c | 13 | ||||
| -rw-r--r-- | src/nullable.c | 5 | ||||
| -rw-r--r-- | src/output.c | 12 | ||||
| -rw-r--r-- | src/reader.c | 2 | ||||
| -rw-r--r-- | src/reduce.c | 2 | ||||
| -rw-r--r-- | src/relation.c | 4 | ||||
| -rw-r--r-- | src/system.h | 12 | ||||
| -rw-r--r-- | tests/sets.at | 6 |
20 files changed, 338 insertions, 55 deletions
@@ -1,3 +1,23 @@ +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 diff --git a/configure.in b/configure.in index 1a5a12ff..85ae8615 100644 --- a/configure.in +++ b/configure.in @@ -78,9 +78,7 @@ AC_DEFINE([_GNU_SOURCE],1,[Define to 1 for GNU C library extensions.]) # 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 @@ -102,6 +100,7 @@ jm_FUNC_REALLOC jm_PREREQ_QUOTEARG jm_PREREQ_ERROR AM_WITH_DMALLOC +BISON_PREREQ_STAGE # Gettext. GETTEXT_VERSION=0.11.2 diff --git a/m4/Makefile.am b/m4/Makefile.am index fdadebf8..e2318d60 100644 --- a/m4/Makefile.am +++ b/m4/Makefile.am @@ -17,5 +17,6 @@ mkstemp.m4 \ prereq.m4 \ progtest.m4 \ realloc.m4 \ +stage.m4 \ strerror_r.m4 \ warning.m4 diff --git a/m4/stage.m4 b/m4/stage.m4 new file mode 100644 index 00000000..6f85a5ac --- /dev/null +++ b/m4/stage.m4 @@ -0,0 +1,40 @@ +# -*-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 +]) +]) diff --git a/m4/warning.m4 b/m4/warning.m4 index d169d5a7..c57260f7 100644 --- a/m4/warning.m4 +++ b/m4/warning.m4 @@ -1,4 +1,25 @@ -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" @@ -59,7 +59,7 @@ state_list_append (symbol_number_t symbol, 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); @@ -177,7 +177,7 @@ new_itemsets (state_t *state) { int i; - if (trace_flag) + if (trace_flag & trace_automaton) fprintf (stderr, "Entering new_itemsets, state = %d\n", state->number); @@ -215,7 +215,7 @@ get_state (symbol_number_t symbol, size_t core_size, item_number_t *core) { state_t *sp; - if (trace_flag) + if (trace_flag & trace_automaton) fprintf (stderr, "Entering get_state, symbol = %d (%s)\n", symbol, symbols[symbol]->tag); @@ -223,7 +223,7 @@ get_state (symbol_number_t symbol, size_t core_size, item_number_t *core) 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; @@ -243,7 +243,7 @@ append_states (state_t *state) int j; symbol_number_t symbol; - if (trace_flag) + if (trace_flag & trace_automaton) fprintf (stderr, "Entering append_states, state = %d\n", state->number); @@ -351,7 +351,7 @@ generate_states (void) 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); diff --git a/src/closure.c b/src/closure.c index 70ecab11..994634c0 100644 --- a/src/closure.c +++ b/src/closure.c @@ -132,13 +132,13 @@ set_firsts (void) 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 (); } @@ -168,7 +168,7 @@ set_fderives (void) 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); @@ -199,7 +199,7 @@ closure (item_number_t *core, int n) bitset_iterator iter; - if (trace_flag) + if (trace_flag & trace_sets) print_closure ("input", core, n); bitset_zero (ruleset); @@ -230,7 +230,7 @@ closure (item_number_t *core, int n) c++; } - if (trace_flag) + if (trace_flag & trace_sets) print_closure ("output", itemset, nritemset); } diff --git a/src/derives.c b/src/derives.c index f88b7002..c5b67104 100644 --- a/src/derives.c +++ b/src/derives.c @@ -101,7 +101,7 @@ set_derives (void) *q++ = -1; } - if (trace_flag) + if (trace_flag & trace_sets) print_derives (); free (dset + ntokens); diff --git a/src/getargs.c b/src/getargs.c index 0cec1a03..bc490a85 100644 --- a/src/getargs.c +++ b/src/getargs.c @@ -31,17 +31,73 @@ int defines_flag = 0; 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. | `----------------------*/ @@ -186,7 +242,7 @@ warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\ `----------------------*/ /* 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[] = { @@ -207,7 +263,7 @@ 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 @@ -329,6 +385,10 @@ getargs (int argc, char *argv[]) report_argmatch (optarg); break; + case 'T': + trace_argmatch (optarg); + break; + default: fprintf (stderr, _("Try `%s --help' for more information.\n"), program_name); diff --git a/src/getargs.h b/src/getargs.h index 8b0de9a4..a93fd55f 100644 --- a/src/getargs.h +++ b/src/getargs.h @@ -34,19 +34,31 @@ extern int no_parser_flag; /* for -n */ 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[])); diff --git a/src/injections.c b/src/injections.c new file mode 100644 index 00000000..9deaabdc --- /dev/null +++ b/src/injections.c @@ -0,0 +1,126 @@ +/* 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); +} @@ -457,6 +457,6 @@ lalr (void) compute_FOLLOWS (); compute_lookaheads (); - if (trace_flag) + if (trace_flag & trace_sets) lookaheads_print (stderr); } @@ -48,16 +48,11 @@ char *program_name; | 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; @@ -81,7 +76,7 @@ main (int argc, char *argv[]) getargs (argc, argv); - if (trace_flag) + if (trace_flag & trace_bitsets) bitset_stats_enable (); muscle_init (); @@ -171,7 +166,7 @@ main (int argc, char *argv[]) alloca (0); #endif - if (trace_flag) + if (trace_flag & trace_bitsets) bitset_stats_dump (stderr); return complain_message_count ? EXIT_FAILURE : EXIT_SUCCESS; diff --git a/src/nullable.c b/src/nullable.c index 6a70fa57..9f61fa87 100644 --- a/src/nullable.c +++ b/src/nullable.c @@ -66,9 +66,6 @@ set_nullable (void) 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; @@ -128,7 +125,7 @@ set_nullable (void) XFREE (rsets + ntokens); XFREE (relts); - if (trace_flag) + if (trace_flag & trace_sets) nullable_print (stderr); } diff --git a/src/output.c b/src/output.c index 5f0fa05f..07977a5d 100644 --- a/src/output.c +++ b/src/output.c @@ -183,10 +183,10 @@ static unsigned int *conflict_list = NULL; 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 @@ -216,7 +216,7 @@ table_grow (size_t desired) 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); @@ -1381,7 +1381,7 @@ output_skeleton (void) m4_invoke (tempfile); /* If `debugging', keep this file alive. */ - if (!trace_flag) + if (!(trace_flag & trace_tools)) unlink (tempfile); free (tempfile); diff --git a/src/reader.c b/src/reader.c index cc3a25a7..25877c18 100644 --- a/src/reader.c +++ b/src/reader.c @@ -456,7 +456,7 @@ packgram (void) assert (itemno == nritems); - if (trace_flag) + if (trace_flag & trace_sets) ritem_print (stderr); } diff --git a/src/reduce.c b/src/reduce.c index 57a408b6..986aecd0 100644 --- a/src/reduce.c +++ b/src/reduce.c @@ -451,7 +451,7 @@ reduce_grammar (void) if (nuseless_productions > 0) reduce_grammar_tables (); - if (trace_flag) + if (trace_flag & trace_grammar) { grammar_dump (stderr, "Reduced Grammar"); diff --git a/src/relation.c b/src/relation.c index fc48c28f..7944b16e 100644 --- a/src/relation.c +++ b/src/relation.c @@ -132,7 +132,7 @@ relation_transpose (relation_t *R_arg, int n) 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); @@ -171,7 +171,7 @@ relation_transpose (relation_t *R_arg, int n) 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); diff --git a/src/system.h b/src/system.h index bdf6becb..6250122a 100644 --- a/src/system.h +++ b/src/system.h @@ -104,6 +104,18 @@ char *alloca (); /* 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. | `---------------------*/ diff --git a/tests/sets.at b/tests/sets.at index bd194ead..373271dc 100644 --- a/tests/sets.at +++ b/tests/sets.at @@ -78,7 +78,7 @@ AT_DATA([[input.y]], 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 @@ -162,7 +162,7 @@ g: h; 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 @@ -208,7 +208,7 @@ exp: ; ]]) -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 |