From c3b407f430a6c4bab6f0ef5160bb0c34290f3abb Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Sun, 7 Apr 2002 17:36:38 +0000 Subject: [PATCH] * src/gram.h, src/gram.c (rules_rhs_length): New. (ritem_longest_rhs): Use it. * src/gram.h (rule_t): `number' is a new member. * src/reader.c (packgram): Set it. * src/reduce.c (reduce_grammar_tables): Move the useless rules at the end of `rules', and count them out of `nrules'. (reduce_output, dump_grammar): Adjust. * src/print.c (print_grammar): It is no longer needed to check for the usefulness of a rule, as useless rules are beyond `nrules + 1'. * tests/reduce.at (Reduced Automaton): New test. --- ChangeLog | 13 +++++ po/de.po | 2 +- po/es.po | 2 +- po/et.po | 2 +- po/fr.po | 2 +- po/it.po | 2 +- po/ja.po | 2 +- po/nl.po | 2 +- po/ru.po | 2 +- po/sv.po | 2 +- po/tr.po | 2 +- src/gram.c | 39 ++++++++------ src/gram.h | 6 +++ src/print.c | 24 ++++----- src/reader.c | 1 + src/reduce.c | 132 +++++++++++++++++++++++------------------------- tests/reduce.at | 83 ++++++++++++++++++++++++++++++ 17 files changed, 210 insertions(+), 108 deletions(-) diff --git a/ChangeLog b/ChangeLog index aa0df7b6..57c51505 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,16 @@ +2002-04-07 Akim Demaille + + * src/gram.h, src/gram.c (rules_rhs_length): New. + (ritem_longest_rhs): Use it. + * src/gram.h (rule_t): `number' is a new member. + * src/reader.c (packgram): Set it. + * src/reduce.c (reduce_grammar_tables): Move the useless rules at + the end of `rules', and count them out of `nrules'. + (reduce_output, dump_grammar): Adjust. + * src/print.c (print_grammar): It is no longer needed to check for + the usefulness of a rule, as useless rules are beyond `nrules + 1'. + * tests/reduce.at (Reduced Automaton): New test. + 2002-04-07 Akim Demaille * src/reduce.c (inaccessable_symbols): Fix a buglet: because of a diff --git a/po/de.po b/po/de.po index 8b737c0a..d0cd3ebf 100644 --- a/po/de.po +++ b/po/de.po @@ -5,7 +5,7 @@ msgid "" msgstr "" "Project-Id-Version: bison 1.25\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 1996-10-10 17:54 MET DST\n" "Last-Translator: Ulrich Drepper \n" "Language-Team: German \n" diff --git a/po/es.po b/po/es.po index 180c3226..f3a70a9a 100644 --- a/po/es.po +++ b/po/es.po @@ -30,7 +30,7 @@ msgid "" msgstr "" "Project-Id-Version: GNU bison 1.25\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 2002-03-14 19:34+0100\n" "Last-Translator: Nicolás García-Pedrajas \n" "Language-Team: Spanish \n" diff --git a/po/et.po b/po/et.po index bd136c31..f09406d3 100644 --- a/po/et.po +++ b/po/et.po @@ -5,7 +5,7 @@ msgid "" msgstr "" "Project-Id-Version: bison 1.28d\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 2001-08-29 17:06+02:00\n" "Last-Translator: Toomas Soome \n" "Language-Team: Estonian \n" diff --git a/po/fr.po b/po/fr.po index 23ccb1cd..d0f20e87 100644 --- a/po/fr.po +++ b/po/fr.po @@ -6,7 +6,7 @@ msgid "" msgstr "" "Project-Id-Version: GNU bison 1.28d\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 2001-08-29 20:00-0500\n" "Last-Translator: Michel Robitaille \n" "Language-Team: French \n" diff --git a/po/it.po b/po/it.po index d3164bbc..5a400e02 100644 --- a/po/it.po +++ b/po/it.po @@ -5,7 +5,7 @@ msgid "" msgstr "" "Project-Id-Version: bison 1.31\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 2002-01-18 12:40 CET\n" "Last-Translator: Paolo Bonzini \n" "Language-Team: Italian \n" diff --git a/po/ja.po b/po/ja.po index b07d5a48..e8f88f79 100644 --- a/po/ja.po +++ b/po/ja.po @@ -5,7 +5,7 @@ msgid "" msgstr "" "Project-Id-Version: GNU bison 1.28\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 1999-09-28 21:10+0900\n" "Last-Translator: Daisuke Yamashita \n" "Language-Team: Japanese \n" diff --git a/po/nl.po b/po/nl.po index 4623bc91..85e962d9 100644 --- a/po/nl.po +++ b/po/nl.po @@ -5,7 +5,7 @@ msgid "" msgstr "" "Project-Id-Version: bison 1.25\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 1996-08-27 15:34 MET DST\n" "Last-Translator: Erick Branderhorst \n" "Language-Team: Dutch \n" diff --git a/po/ru.po b/po/ru.po index 5f4ed2d0..ef6e52ff 100644 --- a/po/ru.po +++ b/po/ru.po @@ -5,7 +5,7 @@ msgid "" msgstr "" "Project-Id-Version: bison 1.29\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 2001-09-09 13:49+04:00\n" "Last-Translator: Dmitry S. Sivachenko \n" "Language-Team: Russian \n" diff --git a/po/sv.po b/po/sv.po index 2b180b34..d7111cb2 100644 --- a/po/sv.po +++ b/po/sv.po @@ -6,7 +6,7 @@ msgid "" msgstr "" "Project-Id-Version: bison 1.30c\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 2001-11-18 15:17+0100\n" "Last-Translator: Göran Uddeborg \n" "Language-Team: Swedish \n" diff --git a/po/tr.po b/po/tr.po index 0fd40e51..f7195dce 100644 --- a/po/tr.po +++ b/po/tr.po @@ -5,7 +5,7 @@ msgid "" msgstr "" "Project-Id-Version: bison 1.28c\n" -"POT-Creation-Date: 2002-04-07 18:07+0200\n" +"POT-Creation-Date: 2002-04-07 19:13+0200\n" "PO-Revision-Date: 2001-09-10 10:54GMT\n" "Last-Translator: Altug Bayram \n" "Language-Team: Turkish \n" diff --git a/src/gram.c b/src/gram.c index f6f39f5a..57333e3e 100644 --- a/src/gram.c +++ b/src/gram.c @@ -1,5 +1,5 @@ /* Allocate input grammar variables for bison, - Copyright 1984, 1986, 1989, 2001 Free Software Foundation, Inc. + Copyright 1984, 1986, 1989, 2001, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -51,6 +51,21 @@ int pure_parser; int error_token_number; +/*--------------------------------------. +| Return the number of symbols in RHS. | +`--------------------------------------*/ + +int +rule_rhs_length (rule_t *rule) +{ + int res = 0; + short *rhsp; + for (rhsp = rule->rhs; *rhsp >= 0; ++rhsp) + ++res; + return res; +} + + /*------------------------. | Dump RITEM for traces. | `------------------------*/ @@ -76,23 +91,15 @@ ritem_print (FILE *out) size_t ritem_longest_rhs (void) { - int length; - int max; + int max = 0; int i; - length = 0; - max = 0; - for (i = 0; i < nritems; ++i) - if (ritem[i] >= 0) - { - length++; - } - else - { - if (length > max) - max = length; - length = 0; - } + for (i = 1; i < nrules + 1; ++i) + { + int length = rule_rhs_length (&rules[i]); + if (length > max) + max = length; + } return max; } diff --git a/src/gram.h b/src/gram.h index 61631640..b12a8a91 100644 --- a/src/gram.h +++ b/src/gram.h @@ -124,6 +124,10 @@ typedef enum typedef struct rule_s { + /* The number of the rule in the source. It is usually the index in + RULES too, except if there are useless rules. */ + short number; + short lhs; short *rhs; short prec; @@ -166,6 +170,8 @@ extern int pure_parser; extern int error_token_number; +/* Report the length of the RHS. */ +int rule_rhs_length PARAMS ((rule_t *rule)); /* Dump RITEM for traces. */ void ritem_print PARAMS ((FILE *out)); diff --git a/src/print.c b/src/print.c index 7be9f63d..90779600 100644 --- a/src/print.c +++ b/src/print.c @@ -366,19 +366,17 @@ print_grammar (FILE *out) fprintf (out, "%s\n\n", _("Grammar")); fprintf (out, " %s\n", _("Number, Line, Rule")); for (i = 1; i < nrules + 1; i++) - /* Don't print rules disabled in reduce_grammar_tables. */ - if (rules[i].useful) - { - fprintf (out, _(" %3d %3d %s ->"), - i - 1, rules[i].line, escape (symbols[rules[i].lhs]->tag)); - rule = rules[i].rhs; - if (*rule >= 0) - while (*rule >= 0) - fprintf (out, " %s", escape (symbols[*rule++]->tag)); - else - fprintf (out, " /* %s */", _("empty")); - fputc ('\n', out); - } + { + fprintf (out, _(" %3d %3d %s ->"), + i - 1, rules[i].line, escape (symbols[rules[i].lhs]->tag)); + rule = rules[i].rhs; + if (*rule >= 0) + while (*rule >= 0) + fprintf (out, " %s", escape (symbols[*rule++]->tag)); + else + fprintf (out, " /* %s */", _("empty")); + fputc ('\n', out); + } fputs ("\n\n", out); diff --git a/src/reader.c b/src/reader.c index 1f16f73a..b0b9d885 100644 --- a/src/reader.c +++ b/src/reader.c @@ -1687,6 +1687,7 @@ packgram (void) while (p) { bucket *ruleprec = p->ruleprec; + rules[ruleno].number = ruleno; rules[ruleno].lhs = p->sym->number; rules[ruleno].rhs = ritem + itemno; rules[ruleno].line = p->line; diff --git a/src/reduce.c b/src/reduce.c index 58bf43ea..b7a7f456 100644 --- a/src/reduce.c +++ b/src/reduce.c @@ -220,70 +220,64 @@ inaccessable_symbols (void) bitset_set (V1, rules[i].precsym); } + +/*-------------------------------------------------------------------. +| Put the useless productions at the end of RULES, and adjust NRULES | +| accordingly. | +`-------------------------------------------------------------------*/ + static void reduce_grammar_tables (void) { - /* This is turned off because we would need to change the numbers in - the case statements in the actions file. + /* Flag useless productions. */ + { + int pn; + for (pn = 1; pn < nrules + 1; pn++) + rules[pn].useful = bitset_test (P, pn); + } - We don't disable it via CPP so that it is still checked with the - rest of the code, to avoid its becoming completely obsolete. + /* Map the nonterminals to their new index: useful first, useless + afterwards. Kept for later report. */ + { + int useful = 1; + int useless = nrules + 1 - nuseless_productions; + rule_t *rules_sorted = XMALLOC (rule_t, nrules + 1) - 1; + int i; + for (i = 1; i < nrules + 1; ++i) + rules_sorted[rules[i].useful ? useful++ : useless++] = rules[i]; + free (rules + 1); + rules = rules_sorted; - FIXME: I think the comment above demonstrates this code must be - turned off for *semantic* parser, not in the general case. Try - to understand this better --akim. */ + /* Also reorder ritems. */ + { + short *ritems_sorted = XCALLOC (short, nitems + 1); + short *ritemsp = ritems_sorted; + for (i = 1; i < nrules + 1; ++i) + { + short *rhsp = rules[i].rhs; + rules[i].rhs = ritemsp; + for (/* Nothing. */; *rhsp >= 0; ++rhsp) + *ritemsp++ = *rhsp; + *ritemsp++ = -i; + } + *ritemsp++ = 0; + free (ritem); + ritem = ritems_sorted; + } + nrules -= nuseless_productions; + } - if (0) - /* remove useless productions */ - if (nuseless_productions > 0) + /* Adjust NRITEMS and NITEMS. */ + { + int r; + int length; + for (r = nrules + 1; r < nrules + 1 + nuseless_productions; ++r) { - short np, pn, ni, pi; - - np = 0; - ni = 0; - for (pn = 1; pn < nrules + 1; pn++) - if (bitset_test (P, pn)) - { - np++; - if (pn != np) - { - rules[np].lhs = rules[pn].lhs; - rules[np].line = rules[pn].line; - rules[np].prec = rules[pn].prec; - rules[np].assoc = rules[pn].assoc; - rules[np].rhs = rules[pn].rhs; - if (rules[np].rhs - ritem != ni) - { - pi = rules[np].rhs - ritem; - rules[np].rhs = ritem + ni; - while (ritem[pi] >= 0) - ritem[ni++] = ritem[pi++]; - ritem[ni++] = -np; - } - } - else - { - while (ritem[ni++] >= 0) - /* Nothing. */; - } - } - - ritem[ni] = 0; - nrules -= nuseless_productions; - nitems = ni; - nritems = ni; - - /* Is it worth it to reduce the amount of memory for the - grammar? Probably not. */ + length = rule_rhs_length (&rules[r]); + nritems -= length + 1; + nitems -= length + 1; } - - /* Disable useless productions. */ - if (nuseless_productions > 0) - { - int pn; - for (pn = 1; pn < nrules + 1; pn++) - rules[pn].useful = bitset_test (P, pn); - } + } } @@ -378,16 +372,15 @@ reduce_output (FILE *out) { int i; fprintf (out, "%s\n\n", _("Useless rules:")); - for (i = 1; i < nrules + 1; i++) - if (!rules[i].useful) - { - rule r; - fprintf (out, "#%-4d ", i - 1); - fprintf (out, "%s:", symbols[rules[i].lhs]->tag); - for (r = rules[i].rhs; *r >= 0; r++) - fprintf (out, " %s", symbols[*r]->tag); - fputs (";\n", out); - } + for (i = nrules + 1; i < nuseless_productions + nrules + 1; i++) + { + rule r; + fprintf (out, "#%-4d ", rules[i].number - 1); + fprintf (out, "%s:", symbols[rules[i].lhs]->tag); + for (r = rules[i].rhs; *r >= 0; r++) + fprintf (out, " %s", symbols[*r]->tag); + fputs (";\n", out); + } fputs ("\n\n", out); } } @@ -411,7 +404,7 @@ dump_grammar (FILE *out) fprintf (out, "\n\n"); fprintf (out, "Rules\n-----\n\n"); fprintf (out, "Num (Prec, Assoc, Useful, Ritem Range) Lhs -> Rhs (Ritem range) [Num]\n"); - for (i = 1; i < nrules + 1; i++) + for (i = 1; i < nrules + nuseless_productions + 1; i++) { int rhs_count = 0; /* Find the last RHS index in ritems. */ @@ -429,7 +422,7 @@ dump_grammar (FILE *out) } fprintf (out, "\n\n"); fprintf (out, "Rules interpreted\n-----------------\n\n"); - for (i = 1; i < nrules + 1; i++) + for (i = 1; i < nrules + nuseless_productions + 1; i++) { fprintf (out, "%-5d %s :", i, symbols[rules[i].lhs]->tag); for (r = rules[i].rhs; *r >= 0; r++) @@ -499,7 +492,8 @@ reduce_grammar (void) fatal (_("Start symbol %s does not derive any sentence"), symbols[start_symbol]->tag); - reduce_grammar_tables (); + if (nuseless_productions > 0) + reduce_grammar_tables (); if (nuseless_nonterminals > 0) nonterminals_reduce (); diff --git a/tests/reduce.at b/tests/reduce.at index e2ae283f..b3a79ba2 100644 --- a/tests/reduce.at +++ b/tests/reduce.at @@ -173,6 +173,89 @@ AT_CLEANUP +## ------------------- ## +## Reduced Automaton. ## +## ------------------- ## + +# Check that the automaton is that as the for the grammar reduced by +# hand. + +AT_SETUP([Reduced Automaton]) + +# The non reduced grammar. +# ------------------------ +AT_DATA([[not-reduced.y]], +[[/* A useless token. */ +%token useless_token +/* A useful one. */ +%token useful +%verbose +%output="not-reduced.c" + +%% + +exp: useful { /* A useful action. */ } + | non_productive { /* A non productive action. */ } + ; + +not_reachable: useful { /* A not reachable action. */ } + ; + +non_productive: non_productive useless_token + { /* Another non productive action. */ } + ; +]]) + +AT_CHECK([[bison not-reduced.y]], 0, [], +[[not-reduced.y contains 2 useless nonterminals and 3 useless rules +]]) + +AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' not-reduced.output]], 0, +[[Useless nonterminals: + not_reachable + non_productive +Terminals which are not used: + useless_token +Useless rules: +#2 exp: non_productive; +#3 not_reachable: useful; +#4 non_productive: non_productive useless_token; +]]) + +# The reduced grammar. +# -------------------- +AT_DATA([[reduced.y]], +[[/* A useless token. */ +%token useless_token +/* A useful one. */ +%token useful +%verbose +%output="reduced.c" + +%% + +exp: useful { /* A useful action. */ } +// | non_productive { /* A non productive action. */ } */ + ; + +//not_reachable: useful { /* A not reachable action. */ } +// ; + +//non_productive: non_productive useless_token +// { /* Another non productive action. */ } +// ; +]]) + +AT_CHECK([[bison reduced.y]]) + +# Comparing the parsers. +cp reduced.c expout +AT_CHECK([sed 's/not-reduced/reduced/g' not-reduced.c], 0, [expout]) + +AT_CLEANUP + + + ## ------------------- ## ## Underivable Rules. ## ## ------------------- ## -- 2.45.2