Re: New LR parser generation algorithm

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

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