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

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.


> --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.


Some quick responses to a few other discussions I saw in this thread....


I'm not opposed to seeing Pager's algorithm added as an option to Bison.
However, it is not what I'm after, and so I don't have much time to help
with it right now.


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).


A grammar does not need to be ambiguous for IELR(1) to be helpful.


I have not published a full explanation of the IELR(1) algorithm yet. I
have not proposed IELR(1) to the other Bison developers yet.

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