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:

def parsePolynomial = {
  parseTerm
  if (lex.current==PLUS) {
    lex.next
    parsePolynomial
  }
}

We obtained tail-recursive version equivalent to a while loop:

def parsePolynomial =
  parseTerm
  while (lex.current==PLUS) {
    lex.next
    parseTerm
  }
}