Re: look for LR(k) grammar

Tom <>
Thu, 15 Jan 2009 23:52:28 -0800 (PST)

          From comp.compilers

Related articles
look for LR(k) grammar (Tom) (2008-12-15)
Re: look for LR(k) grammar (Felipe Angriman) (2008-12-15)
Re: look for LR(k) grammar (Pete Jinks) (2008-12-17)
Re: look for LR(k) grammar (Tom) (2008-12-18)
Re: look for LR(k) grammar (Chris F Clark) (2008-12-20)
Re: look for LR(k) grammar (Tom) (2009-01-15)
| List of all articles for this month |

From: Tom <>
Newsgroups: comp.compilers
Date: Thu, 15 Jan 2009 23:52:28 -0800 (PST)
Organization: Compilers Central
References: 08-12-086 08-12-087 08-12-099 08-12-102
Keywords: parse, LR(1)
Posted-Date: 16 Jan 2009 07:04:01 EST

Hi Chris,

I was working on the lane-tracing algorithm.
Indeed I started from LR(0) table,
and obtain LR(1) parsing table by splitting states.

Then I proceed to try extending this to LR(k). My impression is that
for LR(k) one does not need more state splitting, and just trace back
the states to get more contexts. The statement here
"state splitting is no help in increasing k" confirmed my thought.
Did you get this from other source or from your hands-on experience
on LR(k)?

It is right that what I mean was more rules and not
exactly states. Here is a grammar that I came up with that involves
2 levels of rules (instead of just 1) in this manner:

S : a A D a ;
S : b A D b ;
S : a B D b ;
S : b C E;

A : a ;
B : a ;

D : e d ;
C : B e ;
E : d a ;

The last grammar you mentioned as LR(closed) indeed is a little
unusual. As expected, my algorithm does not generate any LR(k)
component for it, as tracing back ends at state 0 and comes up with
nothing to resolve the reduce/reduce conflict.

It seems to me that a lot of people realize that state-splitting and
trace back to the states where conflicts occur is the path to LR(k) in
concept. But as LR(2) grammar exmaples shown at, the LR(1) parsing
machine of such grammars does not necessarily contain reduce/reduce
conflicts, therefore such an approach of trace back to the states
where reduce/reduce conflicts occur does not work here. This is
puzzling to me.


Post a followup to this message

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