6.3.2 Abstract Syntax Tree (AST)

An abstract syntax tree is a parse tree stripped of unnecessary information such as singleton productions (e.g., ETF). Each nonleaf represents an operator and each leaf represents an operand.

Thus A + B might have the following parse tree and abstract syntax tree:

S := A + B * C has abstract syntax tree:

which can be represented in parenthesized form as

(:= ("S" + ("A" * ("B" "C") ) ) )

The parenthesized form is often used by the compiler designer for debugging output. It is essentially a preorder transversal of the tree.

IF A<B THEN Max := B is represented

and A[i]:=B is

Even though ASt's are more convenient for optimization, there is a one-one correspondence between AST's and Polish postfix:

Thus, AST's can be easily converted to Polish prefix if desired. The "tree" can be seen by starting at the right-hand end and taking the upper of the two arrows as the left child and the lower as the right child.

_{Send questions and comments to: Karen Lemone}