## Syntax tree

A labeled tree corresponding to a derivation

if w in L(G) has parse trees → tell syntactic structure of w

**Tree representations of derivations that eliminate irrelevant production order**

**internal nodes**: nonterminals

**left nodes**: terminals (external nodes)

**frontier**: left-to-right sequence of its external nodes

**yield of a syntax tree**: string defined by its frontier

**relation**: a derivation step

unambiguous :Grammar attribute if there is one parse tree for all each string several derivation : not dangerous several parse tree(ambiguous) : dangerous for grammar

#### but we cannot remove ambiguity every time - inherent ambiguity

## Parse Tree and Derivation

**Claim**: Given a CFG G = (V,T,S,P), for any A ∈ V and α ∈ (V ∪T)*

A* ⇒ α iﬀ there is a derivation tree with root labeled A and whose yield is α

**Proof by induction - pretty complex**

(only-if part) - induction on step

(if part) - induction on the number of internal nodes

Basic figure of (if part)

induction figure of (if part)

**Issue: match derivation well, but not in a concise form**

so we use Abstract Syntax Tree

IH: Induction Hypothesis is hypothesis for prove inductionContext-Freeness: if X ⇒* γ, then αXβ ⇒* αγβ.