# Re: New LR parser generation algorithm

## Sylvain Schmitz <schmitz@i3s.unice.fr>1 May 2006 15:05:57 -0400

From comp.compilers

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)
| List of all articles for this month |

 From: Sylvain Schmitz 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