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.