From: Akim Demaille Date: Fri, 30 Nov 2001 10:49:24 +0000 (+0000) Subject: Instead of mapping the LHS of unused rules to -1, keep the LHS X-Git-Tag: before-m4-back-end~227 X-Git-Url: https://git.saurik.com/bison.git/commitdiff_plain/68f1e3edc304e03b249b64791e4b7d981938bef4 Instead of mapping the LHS of unused rules to -1, keep the LHS valid, but flag the rules as invalid. * src/gram.h (rule_t): `useful' is a new member. * src/print.c (print_grammar): Adjust. * src/derives.c (set_derives): Likewise. * src/reader.c (packgram, reduce_output): Likewise. * src/reduce.c (reduce_grammar_tables): Likewise. * tests/reduce.at (Underivable Rules, Useless Rules): New. --- diff --git a/ChangeLog b/ChangeLog index bfc68edd..ef134526 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,15 @@ +2001-11-30 Akim Demaille + + Instead of mapping the LHS of unused rules to -1, keep the LHS + valid, but flag the rules as invalid. + + * src/gram.h (rule_t): `useful' is a new member. + * src/print.c (print_grammar): Adjust. + * src/derives.c (set_derives): Likewise. + * src/reader.c (packgram, reduce_output): Likewise. + * src/reduce.c (reduce_grammar_tables): Likewise. + * tests/reduce.at (Underivable Rules, Useless Rules): New. + 2001-11-30 Akim Demaille * src/reduce.c (reduce_output): Formatting changes. diff --git a/src/derives.c b/src/derives.c index f0c41165..45fecffe 100644 --- a/src/derives.c +++ b/src/derives.c @@ -63,7 +63,6 @@ void set_derives (void) { int i; - int lhs; shorts *p; short *q; shorts **dset; @@ -74,16 +73,14 @@ set_derives (void) p = delts; for (i = nrules; i > 0; i--) - { - lhs = rule_table[i].lhs; - if (lhs >= 0) - { - p->next = dset[lhs]; - p->value = i; - dset[lhs] = p; - p++; - } - } + if (rule_table[i].useful) + { + int lhs = rule_table[i].lhs; + p->next = dset[lhs]; + p->value = i; + dset[lhs] = p; + p++; + } derives = XCALLOC (short *, nvars) - ntokens; q = XCALLOC (short, nvars + nrules); diff --git a/src/gram.h b/src/gram.h index 531d1d9a..ca55d007 100644 --- a/src/gram.h +++ b/src/gram.h @@ -59,6 +59,8 @@ RULE_TABLE[R].line -- the line where R was defined. + RULE_TABLE[R].useful -- TRUE iff the rule is used. + The right hand side is stored as symbol numbers in a portion of RITEM. @@ -119,6 +121,7 @@ typedef struct rule_s short precsym; short assoc; short line; + bool useful; } rule_t; extern struct rule_s *rule_table; diff --git a/src/print.c b/src/print.c index 977be596..9ac1feb3 100644 --- a/src/print.c +++ b/src/print.c @@ -216,7 +216,7 @@ print_grammar (FILE *out) fprintf (out, " %s\n", _("Number, Line, Rule")); for (i = 1; i <= nrules; i++) /* Don't print rules disabled in reduce_grammar_tables. */ - if (rule_table[i].lhs >= 0) + if (rule_table[i].useful) { fprintf (out, _(" %3d %3d %s ->"), i, rule_table[i].line, tags[rule_table[i].lhs]); diff --git a/src/reader.c b/src/reader.c index 8e7d9949..0cce616d 100644 --- a/src/reader.c +++ b/src/reader.c @@ -1971,6 +1971,7 @@ packgram (void) rule_table[ruleno].lhs = p->sym->value; rule_table[ruleno].rhs = itemno; rule_table[ruleno].line = p->line; + rule_table[ruleno].useful = TRUE; p = p->next; while (p && p->sym) diff --git a/src/reduce.c b/src/reduce.c index 626c195c..190f3577 100644 --- a/src/reduce.c +++ b/src/reduce.c @@ -310,20 +310,12 @@ reduce_grammar_tables (void) } #endif /* 0 */ - /* Disable useless productions, - since they may contain useless nonterms - that would get mapped below to -1 and confuse everyone. */ + /* Disable useless productions. */ if (nuseless_productions > 0) { int pn; - for (pn = 1; pn <= nrules; pn++) - { - if (!BITISSET (P, pn)) - { - rule_table[pn].lhs = -1; - } - } + rule_table[pn].useful = BITISSET (P, pn); } } @@ -338,8 +330,8 @@ nonterminals_reduce (void) int i, n; rule r; - /* Create a map of nonterminal number to new nonterminal number. -1 - in the map means it was useless and is being eliminated. */ + /* Map the nonterminals to their new index: useful first, useless + afterwards. Kept for later report. */ short *nontermmap = XCALLOC (short, nvars) - ntokens; n = ntokens; @@ -379,9 +371,7 @@ nonterminals_reduce (void) for (i = 1; i <= nrules; i++) { - /* Ignore the rules disabled above. */ - if (rule_table[i].lhs >= 0) - rule_table[i].lhs = nontermmap[rule_table[i].lhs]; + rule_table[i].lhs = nontermmap[rule_table[i].lhs]; if (ISVAR (rule_table[i].precsym)) /* Can this happen? */ rule_table[i].precsym = nontermmap[rule_table[i].precsym]; @@ -396,7 +386,7 @@ nonterminals_reduce (void) nsyms -= nuseless_nonterminals; nvars -= nuseless_nonterminals; - free (&nontermmap[ntokens]); + free (nontermmap + ntokens); } @@ -436,11 +426,11 @@ reduce_output (FILE *out) int i; fprintf (out, "%s\n\n", _("Useless rules:")); for (i = 1; i <= nrules; i++) - if (!BITISSET (P, i)) + if (!rule_table[i].useful) { rule r; fprintf (out, "#%-4d ", i); - fprintf (out, "%s :\t", tags[rule_table[i].lhs]); + fprintf (out, "%s:", tags[rule_table[i].lhs]); for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++) fprintf (out, " %s", tags[*r]); fputs (";\n", out); diff --git a/tests/reduce.at b/tests/reduce.at index 73856df9..f3875822 100644 --- a/tests/reduce.at +++ b/tests/reduce.at @@ -108,3 +108,101 @@ AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, ]]) AT_CLEANUP + + + +## --------------- ## +## Useless Rules. ## +## --------------- ## + +AT_SETUP([Useless Rules]) + +AT_DATA([[input.y]], +[[%verbose +%output="input.c" +%token useful +%% +exp: useful; +useless1: '1'; +useless2: '2'; +useless3: '3'; +useless4: '4'; +useless5: '5'; +useless6: '6'; +useless7: '7'; +useless8: '8'; +useless9: '9'; +]]) + +AT_CHECK([[bison input.y]], 0, [], +[[input.y contains 9 useless nonterminals and 9 useless rules +]]) + +AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, +[[Useless nonterminals: + useless1 + useless2 + useless3 + useless4 + useless5 + useless6 + useless7 + useless8 + useless9 +Terminals which are not used: + '1' + '2' + '3' + '4' + '5' + '6' + '7' + '8' + '9' +Useless rules: +#2 useless1: '1'; +#3 useless2: '2'; +#4 useless3: '3'; +#5 useless4: '4'; +#6 useless5: '5'; +#7 useless6: '6'; +#8 useless7: '7'; +#9 useless8: '8'; +#10 useless9: '9'; +]]) + +AT_CLEANUP + + + +## ------------------- ## +## Underivable Rules. ## +## ------------------- ## + +AT_SETUP([Underivable Rules]) + +AT_DATA([[input.y]], +[[%verbose +%output="input.c" +%token useful +%% +exp: useful | underivable; +underivable: indirection; +indirection: underivable; +]]) + +AT_CHECK([[bison input.y]], 0, [], +[[input.y contains 2 useless nonterminals and 3 useless rules +]]) + +AT_CHECK([[sed -n '/^Grammar/q;/^$/!p' input.output]], 0, +[[Useless nonterminals: + underivable + indirection +Useless rules: +#2 exp: underivable; +#3 underivable: indirection; +#4 indirection: underivable; +]]) + +AT_CLEANUP