Re: look for LR(k) grammar

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
http://www.cs.man.ac.uk/~pjj/complang/g2lr.html, 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.


Tom

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