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

Joel E. Denny wrote:


> On Thu, 14 Feb 2008, Chris F Clark wrote:
>
> > The only exception being that if the left-context of the rules in
> > conflict in the LR(0) tables can resolve the conflict without use of
> > precedence, there will be no conflict in the canonical LR(1) tables
> > (or any of the sets of split tables that have applied a split to
> > resolve that conflict). However, this effect is very rare and of
> > negligable impact. Most grammars using precendence do not have
> > shift-reduce conflicts that can be resolved by state splitting
>
> By splitting state s into states s1 and s2, I assume you mean that s1 and
> s2 will have the same core as s. However, they may have different
> lookahead sets such that their unions are the lookahead sets of s.
>
> If s has a S/R conflict, since s1 and s2 have the same core, they both
> have the conflict's shift action. At least one of them, perhaps s1, must
> have the reduce action or there wouldn't be a S/R conflict in s. Thus, s1
> has the S/R conflict. However, s2 may not.
>
> In other words, state splitting will never remove a S/R conflict entirely
> from the parser tables, but it may prevent some viable prefixes (left
> contexts) from encountering those conflicts. If you have some reference
> discussing the frequency of the latter case, I'd find that very helpful,
> so please share it.


Your argument seems correct. Even if the shift comes from the
extension rather than the core, both states will have the same
extension because they have the same core, so it still holds. Thus,
every s/r conflict present in an SLR(0) machine must be present in a
canonical LR(1) machine.


Now, I don't know the exact frequency of how many s/r conflicts are
resolved for one prefix and not another. I never measured it. It was
rare enough in the grammars that I was interested in to be irrelevant.


Given the proof above, one can see why. I was interested in grammars
that can be fixed by going from LALR to an LR method that splits
states to resolve conflicts, from what I've read similar to your IELR
method. S/R conflicts in grammars are not resolved by the method,
only r/r conflicts are. Therefore, only grammars which had only r/r
conflicts and no s/r conflicts would be resolvable by state splitting.
In practice, many more grammars have s/r conflicts. There are several
common grammar writing idioms that create them. In fact, my
experience is that most r/r conflicts are the result of writers
unintentionally designing an ambiguous language.


Some facts that I recall do influence s/r conflicts. Many rules come
to a reduce action without ever consulting the look-ahead. This is
particularly true of LL grammars. One can also see this by the
efficacy of optimizing shift-reduce steps. One can only perform the
shift-reduce optimization, if seeing the last token in a rule implies
that the rule must reduce. That cannot happen if the rule is part of
a s/r conflict.


> > --in fact (if I recall correctly), state splitting generally
> > resolves reduce-reduce rather than shift-reduce conflicts.
>
> If you're thinking of Pager's weak compatibility test, then this is no
> surprise since it does not examine shifts. Since it's intended for LR(1)
> grammars, it doesn't need to examine shifts since merging states with
> identical cores cannot produce new S/R conflicts.


I wasn't thinking about Pager's algorithm at all, just the fact that
you highlighted previously. As you showed, state splitting doesn't
resolve s/r conflicts (it may isolate them, but the conflict will
still be in some state(s)). However, since I was recalling the facts
from memory, I was just offering a weaker version of the statement you
proved.


> LALR(1), Pager's algorithm, IELR(1), and canonical LR(1) are all parser
> table generation algorithms. When the grammar is non-LR(1) coupled with a
> specification for resolving conflicts, I have found examples where the
> parser tables generated by Pager's algorithm do not accept the same
> language as do the parser tables generated by canonical LR(1). I have not
> found such examples for IELR(1) versus canonical LR(1).


The example where Pager's algorithm parses differently when conflict
resolution is added would be interesting. I don't see how it should
happen, since s/r conflicts should be preserved over all splitting and
merges of the LR states (as you showed above). If the tables
resulting from applying Pager's algorithm, and then applying s/r
conflict resolution differ from the results of applying s/r conflict
resolution to other LR-family tables, it suggests something is wrong.


Hope this helps,
-Chris


******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)

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