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* ⇒ α iff 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
Alan Jo
