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

> Token precedence is a way of handling syntax ambiguity. LR(1) grammars
> are all non-ambiguous and LR(1) algorithms are not supposed to handle
> ambiguity. What Joel exactly wanted is an extension that handles
> non-LR(1) grammars (non-LR(1) because of ambiguity) coupled with
> precedence rules.
>
> Hyacc does support token precedence the same way that Yacc and Bison
> does. As I said, this is independent from the LR(1) or LALR(1) algorithms.
>
> [Precedence is not a way of handling ambiguity, it's a way of writing
> a grammar more concisely. Anything you can write with precedence in
> an LR(1) or LALR grammar you could also write by adding more rules, but
> the version using precedence is shorter and easier to follow. -John]
>


First of all, to clarify the precedence-ambiguity issue.


From the viewpoint of the LR parser generation algorithm, precedence
rules actually do resolve the ambiguity created by the short-cut
notation:


Exp -> Exp '+' Exp
              -> Exp '-' Exp
              -> Exp '*' Exp
              -> Exp '/' Exp


The above notation creates shift-reduce (S/R) conflicts and it is the
precedence rules that resolve this ambiguity at parser generation
time, not at the time of parsing or running the generated parser. So
the LR parsing algorithm is unaffected by precedence rules.


At parser generation time, the LR(1) state merging algorithm needs to
determine whether states can be merged based on R/R conflicts and S/R
conflicts that are created by the state merger.


If it tries to merge two states and a R/R conflict emerges, then the
states cannot be merged. If both states had the same R/R conflict
before merging, then they can be merged anyway, because the grammar is
LR(k), where k is greater than 1. This process of keeping the states
separate, is what makes the final state machine LR(1) instead of
LALR(1).


If it tries to merge two states and a S/R conflict emerges, then the
states cannot be merged. However, the ambiguous short-cut productions
listed above, create the same S/R conflicts in BOTH states that are
being merged, so keeping the states separate does not resolve this
ambiguity.


Therefore, a generalized state-merging LR(1) algorithm should be able
to handle precedence rules without any problems.


I think it should be able to handle other conflicts without problems
also, except that it cannot declare the grammar to be LR(1). In other
words, I think it can do what the grammar writer expects with better
results than LALR(1).


I have not proven all of my statements with mathematical proofs. This
is based on my experience in implementing the minimal LR(1) algorithm
used in LRGen 8.3.


If I made a mistake, feel free to make a correction.


Conclusion.


I agree with Chen. The precedence is independent from the LR(1)
and LALR(1) algorithms. The LR(1) algorithm should be able to handle
precedence rules without any problem.




Paul B Mann

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