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) {; parseTerm }

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

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