|look for LR(k) grammar email@example.com (Tom) (2008-12-15)|
|Re: look for LR(k) grammar firstname.lastname@example.org (Felipe Angriman) (2008-12-15)|
|Re: look for LR(k) grammar email@example.com (Pete Jinks) (2008-12-17)|
|Re: look for LR(k) grammar firstname.lastname@example.org (Tom) (2008-12-18)|
|Re: look for LR(k) grammar cfc@shell01.TheWorld.com (Chris F Clark) (2008-12-20)|
|Re: look for LR(k) grammar email@example.com (Tom) (2009-01-15)|
|Date:||Thu, 15 Jan 2009 23:52:28 -0800 (PST)|
|References:||08-12-086 08-12-087 08-12-099 08-12-102|
|Posted-Date:||16 Jan 2009 07:04:01 EST|
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
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.
Return to the
Search the comp.compilers archives again.