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

Related articles |
---|

look for LR(k) grammar txchen@gmail.com (Tom) (2008-12-15) |

Re: look for LR(k) grammar felipeangriman@gmail.com (Felipe Angriman) (2008-12-15) |

Re: look for LR(k) grammar pjj@cs.man.ac.uk (Pete Jinks) (2008-12-17) |

Re: look for LR(k) grammar txchen@gmail.com (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 txchen@gmail.com (Tom) (2009-01-15) |

From: | Tom <txchen@gmail.com> |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.