A DERIVATION TREE (PARSE TREE, SYNTAX TREE) IS A TREE REPRESENTING THE STRUCTURE OF A DERIVATION IN A CONTEXT-FREE GRAMMAR. THE DEFINING CONDITIONS — a tree is a derivation tree for G = (V, T, P, S) if: 1. THE ROOT IS LABELLED S, the start symbol. 2. EVERY INTERNAL NODE IS LABELLED WITH A VARIABLE from V. 3. EVERY LEAF IS LABELLED WITH A TERMINAL, or with ε. 4. IF an internal node is labelled A and its children, LEFT TO RIGHT, are labelled X₁ X₂ … Xₖ, THEN A → X₁X₂…Xₖ MUST BE A PRODUCTION OF G. 5. A node labelled ε must be the ONLY child of its parent (corresponding to a production A → ε). ── THE YIELD ─────────────────────────────────────────────── THE YIELD of a derivation tree is the string obtained by reading its LEAVES LEFT TO RIGHT. L(G) = { yield of T : T is a derivation tree of G with root S and all leaves terminal } A tree whose leaves include variables is a PARTIAL derivation tree, corresponding to a sentential form rather than a sentence. ── THE CENTRAL PROPERTY ──────────────────────────────────── A DERIVATION TREE RECORDS **WHICH** PRODUCTIONS WERE USED AND **WHERE**, BUT NOT THE **ORDER** IN WHICH THEY WERE APPLIED. That is precisely what makes the tree useful. Many different derivations correspond to the same tree, because the choice of which variable to expand next is an arbitrary scheduling decision that carries no structural information. THE PRECISE CORRESPONDENCE, which is a standard exam statement: · Every derivation tree corresponds to EXACTLY ONE LEFTMOST derivation. · Every derivation tree corresponds to EXACTLY ONE RIGHTMOST derivation. · A tree may correspond to MANY derivations in general. SO LEFTMOST DERIVATIONS AND DERIVATION TREES ARE IN ONE-TO-ONE CORRESPONDENCE, which is why ambiguity can be defined equivalently in terms of either. ── A WORKED EXAMPLE ──────────────────────────────────────── Grammar: E → E + T | T, T → T * F | F, F → ( E ) | id The derivation tree for id + id * id : E / | \ E + T | /|\ T T * F | | | F F id | | id id YIELD, reading leaves left to right: id + id * id ✓ THE LEFTMOST DERIVATION recorded by this tree: E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + T * F ⇒ id + F * F ⇒ id + id * F ⇒ id + id * id THE RIGHTMOST DERIVATION recorded by the SAME tree: E ⇒ E + T ⇒ E + T * F ⇒ E + T * id ⇒ E + F * id ⇒ E + id * id ⇒ T + id * id ⇒ F + id * id ⇒ id + id * id EIGHT STEPS EACH, THE SAME EIGHT PRODUCTIONS, APPLIED IN DIFFERENT ORDERS, PRODUCING THE SAME TREE. That is the central property made concrete. AND NOTE THE STRUCTURE: the multiplication sits BELOW the addition, in a subtree of its own, so any evaluation that walks the tree bottom-up computes id * id first. THE GRAMMAR'S LAYERING HAS BECOME THE TREE'S SHAPE. ── SUBTREES AND THE RECURSIVE STRUCTURE ──────────────────── A SUBTREE rooted at a node labelled A is itself a derivation tree for A, and its yield is derivable from A. THIS IS WHAT MAKES INDUCTION ON DERIVATION TREES WORK, and it is the standard technique for proving that a grammar generates the language it is claimed to generate: prove the claim for the base productions, then assume it for subtrees and prove it for a node combining them. IT IS ALSO WHAT THE PUMPING LEMMA FOR CONTEXT-FREE LANGUAGES exploits — a sufficiently deep tree must repeat a variable on some root-to-leaf path, and the subtree between the two occurrences can be duplicated or removed.

── PARSE TREE VERSUS ABSTRACT SYNTAX TREE ────────────────── A distinction worth knowing, since compilers use both: PARSE TREE (concrete syntax tree) Contains EVERY grammar symbol, including punctuation, parentheses and every intermediate variable. It records the derivation faithfully and is therefore verbose: parsing id + id * id produces a tree with E, T and F nodes even where they add no information. ABSTRACT SYNTAX TREE (AST) Keeps only the SEMANTICALLY MEANINGFUL structure. The same expression becomes: + / \ id * / \ id id The chain E → T → F → id collapses to a single leaf, and the parentheses vanish because the SHAPE now carries what they specified. COMPILERS BUILD A PARSE TREE CONCEPTUALLY AND AN AST ACTUALLY, because every later phase — type checking, optimisation, code generation — operates on the AST. ── TRAVERSALS AND EVALUATION ─────────────────────────────── Walking the tree in different orders serves different purposes: INORDER (left, root, right) on an expression tree reproduces the INFIX notation, and needs parentheses to be unambiguous. PREORDER (root, left, right) gives PREFIX / POLISH notation: + id * id id POSTORDER (left, right, root) gives POSTFIX / REVERSE POLISH: id id id * + POSTFIX NEEDS NO PARENTHESES AND NO PRECEDENCE RULES, because the tree structure has been linearised — which is why stack machines and calculators use it, and why compilers emit code in essentially postorder. EVALUATION is a postorder traversal: evaluate both children, then apply the operator. FOR THE TREE ABOVE, POSTORDER GIVES id id id * + — the multiplication's operands appear together and are combined before the addition, which is exactly the required order of computation. THE TREE HAS DETERMINED THE SEMANTICS. ── WHY THE TREE MATTERS MORE THAN THE DERIVATION ─────────── The derivation is a HISTORY of how the string was produced; the tree is a STRUCTURE describing what the string means. A COMPILER DOES NOT CARE WHICH ORDER THE PARSER EXPANDED VARIABLES IN. It cares only about the resulting shape, because the shape determines evaluation order, scope nesting, and which operands belong to which operator. THIS IS WHY AMBIGUITY IS DEFINED IN TERMS OF TREES rather than derivations: two derivations of the same string are harmless if they yield the same tree, and are a genuine problem only when the trees differ — because then the string has two possible MEANINGS. ── CONSTRUCTING A TREE FROM A DERIVATION ─────────────────── THE MECHANICAL PROCEDURE, which is the exam task: 1. Start with the root, labelled S. 2. Take the derivation steps in order. Each step expands one variable A using A → X₁…Xₖ. 3. Find the node for that occurrence of A and give it children X₁ … Xₖ, left to right. 4. Continue until no variables remain. 5. CHECK: read the leaves left to right and confirm they give the target string. THE REVERSE TASK — reading a derivation off a tree — is equally standard: for the LEFTMOST derivation, repeatedly expand the leftmost unexpanded variable node; for the RIGHTMOST, the rightmost. ── A COMMON ERROR ────────────────────────────────────────── DRAWING THE CHILDREN IN THE WRONG ORDER. The children of a node must appear left to right EXACTLY as they do in the production. A → BC and A → CB are different productions and give different trees with different yields. Since the yield is read left to right, reordering the children silently changes the string the tree generates.