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

Quinn Tyler Jackson schrieb:


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


This example applies to both LL and LR parsers. It should be clear that
a parser generator should handle such cases appropriately.


In the case of an LL parser, a recursive call can occur only after a
token has been consumed. An LR parser also should not perform an epsilon
move, if something else is possible as well.


DoDi

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