Lecture Notes
Reading
Chapter 5 Parse Trees
Parse Trees ( sometimes referred to as Abstract Syntax Trees (AST) ) are used as an internal representation of a sourced program (recall that the parser generates a parse-tree representation of the correctly parsed program).
A parse tree preserves rules for associativity, commutativity, and precedence as defined by the grammar.
A parse tree consists of two different kinds of nodes:
- Internal Nodes - correspond to nonterminals from the grammar
- Leaf Nodes - correspond to the terminals of the grammar as found in the parsed source program.
For traversing through a parse tree, we use Depth-first Search, left-to-right traversal.
For example, consider the context-free grammar rule:
$A$ -> $aBc$
Then, the corresponding part of a parse tree generated would look like:
A
/ |
a B c
where a and c are terminals and leaf nodes; B is an internal node that will have child nodes when the nonterminal B is developed in derivation.
Grammar Attributes
For each grammar symbol x, we can define a set of attribute values $A(x)$. For each parse-tree node, we can associate various attributes, which will fall into one of three categories:
- Intrinsic - terminals already associated w/ the parse-tree node (ex: value of a literal “Hello”). They are computed from the node itself.
- Synthesized - are computed based on attributes found in the node’s children (ex: binary expression 2 + 3.4 has the type double as the + operator applied to a double and integer type will result in a double). The synthesized attribute will propagate information up the parse tree.
- Inherited - are comuputed (or directly inherited) from sibling nodes or the parent node.