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

Relevant Pages

  • Re: Changes to Scheduled Recs on Extender not saved
    ... > There is a conflict management update that might sound useful for you. ... I don't have a USB tuner. ... if done on the MCE machine. ... I tested this tonight and set it to resolve a conflict. ...
    (microsoft.public.windows.mediacenter)
  • Re: [GIT] Security subsystem changes for 2.6.38
    ... all the random stuff that went into my tree too. ... would you care about "resolve a conflict" anyway? ... And during the merge window, ...
    (Linux-Kernel)
  • Re: [PATCH] power: Rename get_current to fix build failure / name conflict
    ... This patch changes the name of get_current function pointer to ... get_battery_current to resolve a name conflict with the get_current ... This conflict resulted in a build-failurefor the sh4 arch ...
    (Linux-Kernel)
  • Re: Its going to get nasty...
    ... There is a conflict to be resolved: if they give the gypsies what they want, then other people living within the local area won't get what *they* want. ... but it's moral responsibility is greater than the predjudices of the electorate. ... The authorities cannot and should not resolve these conflicts by giving one group everything they want at the expense of another group. ...
    (uk.legal)
  • Replica says conflicts but no conflict tables
    ... to resolve, ... My database has only 1 conflict table: ... I recall a database replica where I ran ...
    (microsoft.public.access.replication)