e.g. An <Exp> can be replaced by
Note that the production (replacement) rules for <Exp>, <Term> and <Factor> are recursive. The rule for <Exp> states that an Expression is a list of Terms separated by `+' or `-' symbols. A Term is a list of Factors separated by `*' or `/' symbols. A Factor is a variable (x, y, ...), or a parenthesized sub-expression, or a unary `-' followed by a Factor.
The operators `*' and '/' bind more tightly to their
operands than `+' and binary `-' because `*' and '/' appear
in the rule for <Term>, closer to the operands (<Factor>).
The rules for <Exp> and <Term> are left recursive. This is because `+', `-', `*' and `/' are left associative: `a-b-c' gives the same parse tree as `(a-b)-c', not `a-(b-c)'.
A grammar like this can be turned into a "recursive descent parser" (a program) by writing a routine for each non-terminal in the grammar. The routines call each other as specified by the replacement rules. Left recursion, that is a replacement that begins with a recursive non-terminal, must be removed so that the parser does not loop. A simple parser of this type can be found in [Parser.c (click)] or [*.java] or [exp.sml].
x+y*z: Full derivation-tree of non-terminals and replacements.
The result of parsing is often returned as a parse-tree based on a simpler abstract syntax. The abstract syntax corresponds to the datatype of parse trees returned by the parser.
x+y*z: Parse tree.
Parentheses '(' and ')' can be used to force a different parsing:
(x+y)*z: Full derivation-tree of non-terminals and replacements.
(x+y)*z: Parse tree.
Note that parentheses do not appear in any parse tree.
They directed the parser to build a certain tree and after
that they are unnecessary.
The structure of the tree shows the binding of operators
to operands without the need
-- 2002 LA, CSSE, Monash