LARA

Avoiding Left Recursion in Recursive Descent

Instead of

polynomial ::= term ("" | "+" polynomial)

consider grammar defining the same language:

polynomial ::= ("" | polynomial "+") term

we need to parse polynomial, so we check which alternative to parse, so we check whether the current symbol is parsed by polynomial, so

we need to parse polynomial, so we check which alternative to parse, so we check whether the current symbol is parsed by polynomial, so

we need to parse polynomial, so we check which alternative to parse, so we check whether the current symbol is parsed by polynomial, so …

This does not work, because it contains left-recursive alternative

polynomial ::= polynomial "+" term

For recursive descent parsing, we need right-recursive rules, which work, like

polynomial ::= term "+" polynomial

Simple forms of right recursion can be expressed using repetition (and become while loops), which work.