18 Jul 2006 14:06:05 -0400

Related articles |
---|

Why LL(1) Parsers do not support left recursion? martin_lapierre@videotron.ca (DevInstinct) (2006-07-16) |

Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-18) |

Re: Why LL(1) Parsers do not support left recursion? tom@infoether.com (Tom Copeland) (2006-07-18) |

Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-07-18) |

Re: Why LL(1) Parsers do not support left recursion? rahul.chaudhry@gmail.com (Rahul Chaudhry) (2006-07-18) |

Re: Why LL(1) Parsers do not support left recursion? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-19) |

Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-21) |

Re: Why LL(1) Parsers do not support left recursion? luvisi@andru.sonoma.edu (Andru Luvisi) (2006-07-21) |

Re: Why LL(1) Parsers do not support left recursion? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-21) |

Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-22) |

Re: Why LL(1) Parsers do not support left recursion? max@gustavus.edu (Max Hailperin) (2006-07-22) |

[25 later articles] |

From: | "Rahul Chaudhry" <rahul.chaudhry@gmail.com> |

Newsgroups: | comp.compilers |

Date: | 18 Jul 2006 14:06:05 -0400 |

Organization: | http://groups.google.com |

References: | 06-07-02406-07-039 |

Keywords: | parse, LL(1) |

Posted-Date: | 18 Jul 2006 14:06:05 EDT |

I think the real problem here can be appreciated with a slightly more

complex example:

S ::= Ab | Ac

A ::= Aa | <epsilon>

Here, the grammar cannot be parsed by a LL(k) parser for any finite k,

as I can always construct a sentence in the language that needs more

than k lookahead to make that decision on the first production from

'S'.

A sentence beginning with k a's needs to look at at least (k+1) symbols

to make the decision on which rule to use to expand 'S'. And expanding

'S' to one of the alternatives is the first step a top down parser has

to do.

The grammar above is just the regular expression a*(b|c). It can easily

be re-written to make it friendly to LL parsing.

An LR (or LALR) parser does bottom up parsing. The reduction to 'S'

from one of the alternatives is that last step for it, and hence it can

handle such a grammar just fine. (Try it with yacc).

Hope this helps,

Rahul

SM Ryan wrote:

*> "DevInstinct" <martin_lapierre@videotron.ca> wrote:*

*> # Hi, first of all, I'm not an expert in the theory of computation.*

*> #*

*> # I've read about LL(1) parsers and I have seen that they do not support*

*> # left recursion, because it is said that it would lead to infinite*

*> # recursivity.*

*>*

*> LL(k) grammars make parsing decisions based on the first k symbols.*

*>*

*> For*

*> S ::= Sb | a*

*> FIRST(Sb,1) = FIRST(S,1) + FIRST(a,1) = {a}*

*> FIRST(a,1) = {a}*

*>*

*> So both alternatives have the same FIRST(1) sets, and you can't decide*

*> which alternative to use. It's not an LL(1) grammar.*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.