Why must left recursion be eliminated in top-down parsers?
2025
Why must left recursion be eliminated in top-down parsers?
- A.
It causes infinite recursion during parsing
- B.
It leads to ambiguity in the grammar
- C.
It slows down the execution of compiled programs
- D.
It cannot be represented using regular expressions
Attempted by 42 students.
Show answer & explanation
Correct answer: A
Top-down parsers, such as Recursive Descent and LL parsers, expand grammar rules recursively from the start symbol. If a grammar contains left recursion, a non-terminal immediately calls itself before consuming any input.
Example:
Expr → Expr + Term | Term
Here, Expr tries to expand into Expr + Term repeatedly, causing infinite recursion. Therefore, left recursion must be eliminated or converted into right recursion for successful top-down parsing.