why top down parser cannot handle left recursion?

Question

I wanted to know why top down parsers cannot handle left recursion and we need to eliminate left recursion due to this as mentioned in dragon book..

Answer 1

Think of what it's doing. Suppose we have a left-recursive production rule A -> Aa | b, and right now we try to match that rule. So we're checking whether we can match an A here, but in order to do that, we must first check whether we can match an A here. That sounds impossible, and it mostly is. Using a recursive-descent parser, that obviously represents an infinite recursion.

It is possible using more advanced techniques that are still top-down, for example see [1] or [2].

[1]: Richard A. Frost and Rahmatullah Hafiz. A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time. SIGPLAN Notices, 41(5):46–54, 2006.
[2]: R. Frost, R. Hafiz, and P. Callaghan, Modular and efficient top-down parsing for ambiguous left-recursive grammars. ACL-IWPT, pp. 109 – 120, 2007.

Answer 2

Top-down parsers cannot handle left recursion A top-down parser cannot handle left recursive productions. To understand why not, let's take a very simple left-recursive grammar.

1. S → a
2. S → S a There is only one token, a, and only one nonterminal, S. So the parsing table has just one entry. Both productions must go into that one table entry.

The problem is that, on lookahead a, the parser cannot know if another a comes after the lookahead. But the decision of which production to use depends on that information.