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

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.

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