Re: Full LR(1) parser generator Hyacc 0.9 release

On Thu, 28 Feb 2008, Chris F Clark wrote:


> A reasonable argument for sure, and one which I would accept. The
> only point I will make counter to it is that many grammars were
> orignally developed with yacc (or earlier bison versions) and any
> precedence and associativity declarations in those grammars would have
> been added with the assumption of how an LALR parser generator uses
> them to resolve the conflicts. This gives us an alternate definition
> of "right", which is right is what is compatible across the different
> tools that the user is using. Compatibility is an important goal in
> itself.


In my IELR(1)-extended version of Bison, LALR(1) definitely remains the
default.


On the other hand (and I don't think this disagrees with your point),
it seems that any grammar that is correct with LALR(1) behavior but
not with canonical LR(1) behavior would be difficult to comprehend and
maintain, and thus the grammar should be rewritten. However, in my
experience, differences from canonical LR(1) are more likely to be
simply mistakes that the developer never noticed.


I have no statistics on this. Do you know of cases where differences
from canonical LR(1) behavior are intended? Do you know of cases
where it is actually cleaner to depend on these differences rather
than avoid them? That would be interesting to see. I suspect it's
rare, and so I would argue that grammars that depend on such
differences are wrong from a software engineering perspective
regardless of whether tools like Bison must support them for backward
compatibility.


> It would be nice if you could find a way to warn users who
> ask for it which inputs would parse differently using conflict
> resolution in the LR and LALR states.


After running IELR(1), I can automatically list actions it changes.
Adding example sentences for each action change should be possible as
well. I recall that Menhir gives example sentences when explaining
conflicts.


> One difficulty that is often overlooked due to its superficial
> simplicity is that grammar maintenance is an order-of-magnitude harder
> and more subtle than program maintenance. (It's one of my big
> quibbles with hand-written recursive descent where people do grammar
> maintenance without formal tools, but that's my personal bugaboo.)
> Small changes in grammars can effect large changes in the languages
> that they accept and people overlook this. This is even more true
> when one starts playing with precedence declarations.


I agree, and the side effects of state merging can be especially difficult
to understand. Better to put this burden on the tool.


> However, it is somewhat uncommon for cases like you posit to exist in
> standardized languages (although most standardized languages have one
> such wart,but it isn't always a grammatic one) because someone on the
> committee is likely a grammar enthusiast (and more importantly, it is
> very rare for them to be solved by using precedence to exclude some
> specific expansion of one alternative of one rule).


> It is important that authors realize that certain problems cannot be
> solved well grammatically.


Like a lot of software engineering work, my work is aimed more at the
common developer than at the experts who understand all the nuances.

Return to the comp.compilers page.
Search the comp.compilers archives again.