CST 8152 - Parsing - The Toy Grammar
A simple recursive Toy Grammar for an assignment
statement, consisting of four productions:
ID = <expression> ;
<term> ( (+|-) <term> )*
<factor> ( (*|/) <factor> )*
ID | CONST | ( <expression> )
- The grammar has ten terminals
(recognized token types):
ID, CONST, (,
), +, -, *, /, ;, =
- The grammar has four non-terminals
(each of which will be coded as a separate function in a
top-down, recursive-descent, predictive parser):
<expression>, <term>, <factor>
- Plus and minus tokens separate the terms
of the expression.
- Multiply and divide tokens separate factors
of the terms.
- The current input token uniquely
determines which of the four productions must be applied,
with no ambiguity. No backtracking will be needed to
parse sentences in this language.
- This grammar is suitable for top-down,
recursive-descent, predictive parsing (text p.41): Start
with the root non-terminal (<assignment>) 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.
- If the parsing succeeds without error, the
input is a correct sentence in the language.