(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 <akim@epita.fr>
+
+ * 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 <akim@epita.fr>
* src/reduce.c (inaccessable_symbols): Fix a buglet: because of a
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 <drepper@gnu.ai.mit.edu>\n"
"Language-Team: German <de@li.org>\n"
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 <ngarcia-pedrajas@acm.org>\n"
"Language-Team: Spanish <es@li.org>\n"
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 <tsoome@ut.ee>\n"
"Language-Team: Estonian <et@li.org>\n"
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 <robitail@IRO.UMontreal.CA>\n"
"Language-Team: French <traduc@traduc.org>\n"
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 <bonzini@gnu.org>\n"
"Language-Team: Italian <it@li.org>\n"
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 <yamad@mb.infoweb.ne.jp>\n"
"Language-Team: Japanese <ja@li.org>\n"
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 <branderh@debian.org>\n"
"Language-Team: Dutch <nl@li.org>\n"
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 <dima@Chg.RU>\n"
"Language-Team: Russian <ru@li.org>\n"
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 <goeran@uddeborg.pp.se>\n"
"Language-Team: Swedish <sv@li.org>\n"
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 <altugbayram_2000@yahoo.com>\n"
"Language-Team: Turkish <gnu-tr-u12a@lists.sourceforge.net>\n"
/* 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.
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. |
`------------------------*/
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;
}
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;
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));
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);
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;
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);
- }
+ }
}
{
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);
}
}
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. */
}
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++)
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 ();
+## ------------------- ##
+## 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. ##
## ------------------- ##
projects / bison.git / commitdiff
