1 May 2006 15:05:57 -0400

Related articles |
---|

New LR parser generation algorithm david@tribble.com (David R Tribble) (2006-04-30) |

Re: New LR parser generation algorithm schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-05-01) |

Re: New LR parser generation algorithm schmitz@i3s.unice.fr (Sylvain Schmitz) (2006-05-01) |

Re: New LR parser generation algorithm Francois.Pottier@inria.fr (Francois Pottier) (2006-05-09) |

From: | Sylvain Schmitz <schmitz@i3s.unice.fr> |

Newsgroups: | comp.compilers |

Date: | 1 May 2006 15:05:57 -0400 |

Organization: | Compilers Central |

References: | 06-04-182 |

Keywords: | LR(1), parse |

Posted-Date: | 01 May 2006 15:05:57 EDT |

David R Tribble wrote:

*> I wish to introduce a new LR parser generation algorithm. I call this*

*> the Honalee Algorithm. It produces the minimal collection of*

*> canonical LR(k) item sets for an LR(k) grammar.*

I did not read everything very thoroughly, but I wonder if you avoid

introducing reduce/reduce conflicts further after a merge. Consider

the grammar with rules

S -> aAa | bAb | aBb | bBa

A -> cc

B -> cc

The LR(1) state reached by reading the prefix 'ac' contains the items

{[A -> c : c, a], [B -> c : c, b]},

whereas the state reached after reading the prefix 'bc' contains the items

{[A -> c : c, b], [B -> c : c, a]}.

Do you merge these two item sets? Merging will not result in an

immediate reduce/reduce conflict, but you will end with one after the

next transition on symbol 'c' with item set

{[A -> c c :, a], [A -> c c :, b], [B -> c c :, a], [B -> c c :, b]}.

You might be interested in reading David Pager: _A_Practical_General_

_Method_for_Constructing_LR(k)_Parsers_. Acta Inf. 7: 249-268 (1977) and

David Pager:

_The_lane-tracing_algorithm_for_constructing_LR(k)_parsers_

_and_ways_of_enhancing_its_efficiency_. Inf. Sci. 12(1): 19-42 (1977)

--

Hope that helps,

Sylvain

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.