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

> 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.

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