RE: Why LL(1) Parsers do not support left recursion?

Quinn Tyler Jackson <qtj-query@shaw.ca>
16 Jul 2006 10:44:06 -0400

          From comp.compilers

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? qtj-query@shaw.ca (Quinn Tyler Jackson) (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? 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? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-21)
RE: Why LL(1) Parsers do not support left recursion? qtj-query@shaw.ca (Quinn Tyler Jackson) (2006-07-21)
[7 later articles]
| List of all articles for this month |

From: Quinn Tyler Jackson <qtj-query@shaw.ca>
Newsgroups: comp.compilers
Date: 16 Jul 2006 10:44:06 -0400
Organization: Compilers Central
References: 06-07-024
Keywords: LL(1), parse

> 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.
>
> My question: why is that? In which case a LL(1) parser can enter
> infinite recursivity?
>
> I can't find a good example that demonstrates that.


expr ::= expr "+" expr;
expr ::= '[0-9]+';


OK, using a top-down approach, parse:


5+2


As soon as you enter expr, you enter expr, which brings you to expr, which
brings you to expr, after which you enter expr, ....


And it only gets deeper.


That can be removed by factoring*, which is an exercise I leave to the
reader.




--
Quinn Tyler Jackson


http://press.ChevalierEditions.com


* Factoring gets you around the issue in a known and legitimate way, but
produces parse trees with many intermediate nodes that must be traversed
before you get to the node type of the actual expression. Something like:


expr
        power
                  mult
                          div
                                  add
                                        number
                                                  integer


Where what you really only need is:


expr
        integer


I have found that trimming the junk intermediate nodes "sooner rather than
later" makes for easier traversal during tree interpretation. YMMV.


Post a followup to this message

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