Re: <reductions>

[Joel E. Denny]

On Fri, 19 Oct 2007, Wojciech Polak wrote:

> > > What about something like the following?  Under grammar, we could have 
> > > rules/useless, rules/never-used, nonterminals/useless, and 
> > That should be "never-reduced" instead of "never-used".
> > > terminals/unused.
> 
> We would also need a name for "in use" elements
> (to make it consistent):
> 
>  grammar/rules/in-use/rule   (or "used", or other name?)

Or "useful"?  I like that it's the opposite of "useless".

I don't like "used" because a nonterminal or rule that doesn't derive a 
terminal string is "useless" even if it is "used" in some RHS.

> > Or should "useless", "never-reduced", and "unused" be attributes instead?
> 
> Only if those are always mutually exclusive values,
> but they aren't. For instance, a rule can be both
> "in use" and "never-reduced".

If a rule is identified as never reduced because of conflicts, what does 
it mean to say whether it's "in use"?

Perhaps you're noticing that rules listed under "Rules never reduced" are 
also listed under "Grammar".  I see no reason to mimic this in the XML. 
Just list it once and mark it "never reduced".  xml2text.xsl can still 
list it twice.

This issue raises an interesting point.  Consider this grammar, which is a 
slightly modified version of your errors.y example:

  %expect 1
  %%
  exp: e 'e'; 
  e: /* Nothing. */ | 'e';

The empty rule goes under "Rules never reduced" and it appears in the 
grammar before the last rule, so we'd have:

  <useful>
    <rule number="0">...</rule>
    <rule number="1">...</rule>
  </useful>
  <never-reduced>
    <rule number="2">...</rule>
  </never-reduced>
  <useful>
    <rule number="3">...</rule>
  </useful>

Or should we list rules out of order so we don't need multiple "useful" 
and "never-reduced" elements?  Maybe attributes would be cleaner?

> But despite this,
> here is a sample with attributes:
> 
>  grammar/rules/address@hidden'in-use']
>  grammar/rules/address@hidden'useless']
>  grammar/rules/address@hidden'never-reduced']
>  grammar/terminals/address@hidden'in-use']
>  grammar/terminals/address@hidden'unused']
>  grammar/nonterminals/address@hidden'in-use']
>  grammar/nonterminals/address@hidden'useless']

In the context of a parser-generator, @state sounds like it has something 
to do with parser states.  How about @usefulness?

By the way, I think the distinction between "useless" and "never reduced" 
is unclear both in the XML and in Bison's existing .output files.  That 
is, useless rules are never reduced, and rules that are never reduced are, 
in some sense, useless.

When Bison says "useless", it really means (1) "grammatically useless", 
(2) "useless before conflicts", or (3) "useless in grammar".  That is, the 
nonterminal or rule is useless before the parsing technique (LALR(1) in 
Bison's case) is even considered.

By "never reduced", Bison means (1) "useless due to conflicts", (2) 
"useless after conflicts", or (3) "useless in parser".  That is, the rule 
is useless after the parsing technique is considered.

#1 seems clear in both cases, but it's verbose.  The words "before" and 
"after" in #2 sound a little like they have something to do with conflicts 
in predecessor and successor states, and that's not what we mean.  I 
prefer #3, which I think will also look nice in XML.

What do people think?