Arithmetic Expressions |
|
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]. 1. x+y*z:
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. 2. (x+y)*z: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
|
|
|