Thu, 14 Feb 2008 06:56:49 -0600

Related articles |
---|

Full LR(1) parser generator Hyacc 0.9 release txchen@gmail.com (Tom) (2008-02-03) |

Re: Full LR(1) parser generator Hyacc 0.9 release haberg@math.su.se (Hans Aberg) (2008-02-05) |

Re: Full LR(1) parser generator Hyacc 0.9 release txchen@gmail.com (Thomas Chen) (2008-02-07) |

Re: Full LR(1) parser generator Hyacc 0.9 release DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-02-11) |

Re: Full LR(1) parser generator Hyacc 0.9 release haberg_20080207@math.su.se (Hans Aberg) (2008-02-11) |

Re: Full LR(1) parser generator Hyacc 0.9 release txchen@gmail.com (Thomas Chen) (2008-02-12) |

Re: Full LR(1) parser generator Hyacc 0.9 release haberg_20080207@math.su.se (Hans Aberg) (2008-02-13) |

Re: Full LR(1) parser generator Hyacc 0.9 release paul@paulbmann.com (Paul B Mann) (2008-02-14) |

Re: Full LR(1) parser generator Hyacc 0.9 release cfc@shell01.TheWorld.com (Chris F Clark) (2008-02-14) |

Re: Full LR(1) parser generator Hyacc 0.9 release jdenny@ces.clemson.edu (Joel E. Denny) (2008-02-23) |

Re: Full LR(1) parser generator Hyacc 0.9 release cfc@TheWorld.com (Chris F Clark) (2008-02-24) |

Re: Full LR(1) parser generator Hyacc 0.9 release jdenny@ces.clemson.edu (Joel E. Denny) (2008-02-25) |

Re: Full LR(1) parser generator Hyacc 0.9 release paul@paulbmann.com (Paul B Mann) (2008-02-26) |

Re: Full LR(1) parser generator Hyacc 0.9 release cfc@TheWorld.com (Chris F Clark) (2008-02-27) |

[6 later articles] |

From: | "Paul B Mann" <paul@paulbmann.com> |

Newsgroups: | comp.compilers |

Date: | Thu, 14 Feb 2008 06:56:49 -0600 |

Organization: | Compilers Central |

References: | 08-02-019 08-02-022 08-02-030 08-02-037 08-02-040 |

Keywords: | parse, LR(1) |

Posted-Date: | 14 Feb 2008 21:19:18 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.