Parsing:A Simple Toy Grammar
A simple toy grammar for an assignment statement:
<> => ID = <> ;
<> => <> ( (+|-) <> )*
<> => <> ( (*|/) <> )*
<> => ID | CONST | ( <> )
The grammar has ten terminals (recognized token types): ID, CONST, (, ), +, -, *, /, ;, =
Four non-terminals (each of which will be a separate function in a top-down, recursive-descent, predictive parser): <>, <>, <>, <>
Plus and minus tokens separate terms
Multiply and divide tokens separate factors
The current input token uniquely determines which production must be applied, with no ambiguity. No backtracking will be needed to parse sentences in this language.
Suitable for top-down, recursive-descent, predictive parsing (text p.41): Start with the root non-terminal (<>) and work down toward the terminals, the leaves of the grammar parse tree. The expected terminals in the grammar are matched by the parser against the actual token types returned by the scanner.