Fri, 07 Nov 2008 14:27:18 +0100

Related articles |
---|

How test if language is LL(k) or LR(k) ? a.moderacja@gmail.com (Borneq) (2008-10-23) |

Re: How test if language is LL(k) or LR(k) ? cfc@shell01.TheWorld.com (Chris F Clark) (2008-10-28) |

Re: How test if language is LL(k) or LR(k) ? sh006d3592@blueyonder.co.uk (Stephen Horne) (2008-10-29) |

Re: How test if language is LL(k) or LR(k) ? rpboland@gmail.com (Ralph Boland) (2008-10-31) |

Re: How test if language is LL(k) or LR(k) ? cfc@shell01.TheWorld.com (Chris F Clark) (2008-11-06) |

Re: How test if language is LL(k) or LR(k) ? torbenm@pc-003.diku.dk (2008-11-07) |

Re: How test if language is LL(k) or LR(k) ? ulf.schwekendiek@googlemail.com (ulf.schwekendiek@googlemail.com) (2008-11-07) |

Re: How test if language is LL(k) or LR(k) ? sh006d3592@blueyonder.co.uk (Stephen Horne) (2008-11-07) |

Re: How test if language is LL(k) or LR(k) ? torbenm@pc-003.diku.dk (2008-11-10) |

Re: How test if language is LL(k) or LR(k) ? cfc@shell01.TheWorld.com (Chris F Clark) (2008-11-10) |

Re: How test if language is LL(k) or LR(k) ? sh006d3592@blueyonder.co.uk (Stephen Horne) (2008-11-12) |

From: | torbenm@pc-003.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) |

Newsgroups: | comp.compilers |

Date: | Fri, 07 Nov 2008 14:27:18 +0100 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 08-10-044 08-10-055 |

Keywords: | LR(1), theory |

Posted-Date: | 07 Nov 2008 11:43:00 EST |

Stephen Horne <sh006d3592@blueyonder.co.uk> writes:

*> For LR, *almost* all context-free grammars are LR(k < infinity), so if*

*> you can prove that the grammar is context-free you are almost there.*

That's not very useful, and not even true. There are many useful

grammars that are not LR(k) for any k and even useful languages for

which there doesn't exits LR(k) grammars for any k.

*> You can always construct an LR(1) - or even LR(0) - state model to*

*> parse a context-free grammar, but if the grammar is not LR(1) that*

*> state model will have shift/reduce or reduce/reduce conflicts.*

*>*

*> Almost all such conflicts can be resolved finitely. This is the logic*

*> behind Tomita and other generalised LR parsing algorithms. The basic*

*> principle is that conflicts are resolved by checking all possibilities*

*> - the Tomita approach being to check them concurrently using stack*

*> duplication, whereas another common approach is to use backtracking.*

This does, however, not give you any k, since the amount you have to

read ahead before backtracking may depend on the input.

*> The basic problem is that sometimes, there are infinite possibilities*

*> to check. This can occur when the grammar contains empty rules - when*

*> there are reductions that pop zero tokens from the stack. However, it*

*> doesn't happen for *all* cases where empty rules are used - except in*

*> the case of LR(0), I think - and it is not reasonable to ban such*

*> rules.*

*>*

*> In such cases, Tomita will give an infinite number of stack*

*> duplicates, whereas the backtracking approach will simply give an*

*> infinite loop.*

Empty productions can be eliminated automatically using a fairly

simple procedure (which, however, may increase the grammar size

quadratically), so these are not the problem. The problem is that you

often have to look to the end of the input before backtracking, which

effectively gives you unbounded lookahead.

If you just want to parse a text with a grammar, there are plenty of

algorithms around (such as Early's universal parser) that will give

you a lazy list of all possible parse trees. But that doesn't help

you decide if the language is LR(k).

*> I have designed an variant of GLR (though I have never implemented it)*

*> which should theoretically give constant-time parsing of any context*

*> free grammar*

I assume you mean "linear-time", as constant-time parsing sounds

implausible. But even linear-time parsing for any context-free

grammar sounds suspect and would be a very big result (if you can

prove it).

*> that can be parsed,*

Any context-free grammar can be parsed, so this restriction is

meaningless.

Torben

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.