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 subexpression, 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: `abc' gives the same parse tree as `(ab)c', not `a(bc)'. A grammar like this can be turned into a "recursive descent parser" (a program) by writing a routine for each nonterminal 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 nonterminal, 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 derivationtree of nonterminals and replacements. The result of parsing is often returned as a parsetree 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 derivationtree of nonterminals 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  L.A.


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Saturday, 24Feb2024 21:48:10 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 