Parse Trees
Introduction: A parse tree pictorially shows how the start symbol of a grammar derives a string in the language. Every terminal string generated by a grammar has at least one corresponding parse tree; every valid parse tree represents a string generated by the grammar (yield of the parse tree). If nonterminal A has a production A -> XYZ, then a parse tree may have an interior node labeled A with three children labeled X, Y, and Z, from left to right:
Formally, given a context-free grammar, a parse tree according to the grammar is a tree with the following properties:
1. The root is labeled by the start symbol.
2. Each leaf is labeled by a terminal or by e.
3. Each interior node is labeled by a nonterminal.
4. If A is the nonterminal labeling some interior node and X\, X2, . . . . , Xn are the labels of the children of that node from left to right, then there must be a production A —> X1X2 . . . . Xn. Here, X\,X2,.. . ,Xn each stand
Tree Terminology
Tree data structures figure prominently in compiling.
- A tree consists of one or more nodes. Nodes may have labels, which in this book typically will be grammar symbols. When we draw a tree, we often represent the nodes by these labels only.
- Exactly one node is the root. All nodes except the root have a unique parent; the root has no parent. When we draw trees, we place the parent of a node above that node and draw an edge between them. The root is then the highest (top) node.
- If node N is the parent of node M, then M is a child of N. The children of one node are called siblings. They have an order, from the left, and when we draw trees, we order the children of a given node in this manner.
- A node with no children is called a leaf. Other nodes — those with one or more children — are interior nodes.
- A descendant of a node N is either N itself, a child of N, a child of a child of N, and so on, for any number of levels. We say node N is an ancestor of node M if M is a descendant of N.
for a symbol that is either a terminal or a nonterminal. As a special case, if A ->• e is a production, then a node labeled A may have a single child labeled e.
Parse Tree Is a graphical representation for a derivation
- Filters out choice regarding replacement order
- Rooted by the start symbol S
- Interior nodes represent nonterminals in N
- Leaf nodes are terminals in T or
- Node A can have children X1 X2 ... Xn if a rule A X1 X2 ... Xn exists
The following is a parse tree for ( id num ) * id