Left Factoring Recursive Descent
Consider a variant of grammar with this definition:
polynomial ::= term | term "+" polynomial
How to write parsePolynomial procedure for this grammar?
- 'term' can be arbitrarily complex
- which alternative to choose?
Solution: apply left-factoring:
polynomial ::= term ("" | "+" polynomial)
Now we can construct parser:
We obtained tail-recursive version equivalent to a while loop: