Recursive Descent for Polynomials

In context-free grammars we have seen a grammar of polynomials.

Consider first this version of grammar:

  polynomial ::= term ("+" term)*
  term ::= factor ("*" factor)*
  factor ::= constant | variable | "(" polynomial ")"

This grammar version is very nice for recursive descent parsing

Here is a parser for this grammar: polynomials.pscala

Note correspondence:

(“+” term)*

⇒ while (lex.current=PLUS) { lex.next; parseTerm }

Example: running the code above on “x + y*(u+3)”

remaining input	recursion stack
x + y*(u+3)	polynomial
x + y*(u+3)	polynomial,term
x + y*(u+3)	polynomial,term,factor
+ y*(u+3)	polynomial,term
+ y*(u+3)	polynomial
y*(u+3)	polynomial
y*(u+3)	polynomial,term
y*(u+3)	polynomial,term,factor
*(u+3)	polynomial,term
(u+3)	polynomial,term
(u+3)	polynomial,term,factor
u+3)	polynomial,term,factor
u+3)	polynomial,term,factor,polynomial
…	polynomial,term,factor,polynomial,…
)	polynomial,term,factor,polynomial
)	polynomial,term,factor
	polynomial,term,factor
	polynomial,term
	polynomial

For statements, we use keyword to decide what we are about to parse:

“if” X | “while” Y

⇒ if (lex.current=IF) parseX else if (lex.current=WHILE) parseY