In the previous example, the parser computes the value of the expression on the fly, while parsing. It is
also possible to build an abstract syntax tree to store an abstract representation of the input. This may
be usefull when several passes are necessary.
This example shows how to parse an expression (infix, prefix or postfix) and convert it in
infix, prefix and postfix notation. The expression is saved in a tree. Each node of the tree
correspond to an operator in the expression. Each leave is a number. Then to write the expression
in infix, prefix or postfix notation, we just need to walk throught the tree in a particular
order.
10.2Abstract syntax trees
The AST of this converter has two types of node:
class Op
is used to store operators (+, -, *, /, ^). It has two sons associated to the sub expressions.
class Atom
is an atomic expression (a number or a symbolic name).
Both classes are instanciated by the __init__ method. The infix, prefix and postfix methods return strings
containing the representation of the node in infix, prefix and postfix notation.
10.3Grammar
10.3.1Infix expressions
The grammar for infix expressions is similar to the grammar used in the previous example.
At first sight postfix and infix grammars may be very similar. Only the position of the operators changes.
So a compound postfix expression is a first expression followed by a second and an operator. This rule is
left recursive. As TPG is a descendant recursive parser, such rules are forbidden to avoid infinite
recursion. To remove the left recursion a classical solution is to rewrite the grammar like
this: