Parse Tree


# Syntax tree
A labeled tree corresponding to a derivation
if w in L(G) has parse trees → tell syntactic structure of w
<details><summary>

**Tree representations of derivations that eliminate irrelevant production order**</summary>

1. **internal nodes **: nonterminals
2. **left nodes **: terminals (external nodes)
3. **frontier **: left-to-right sequence of its external nodes
4. **yield of a syntax tree **: string defined by its frontier
5. **relation** : a derivation step
</details>



> **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 α
> ![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F1646381c-f68e-44e1-ac4a-e884e71a0076%2FUntitled.png?table=block&id=22a86668-dc65-40db-98b5-1f5b441942de&cache=v2)



<details><summary>

**Proof by induction - pretty complex**</summary>

(only-if part) - induction on step
> **Basis **: If A* ⇒ α in a single step, then A → α is a production in P. There is a tree of height 1 with root A and leaves the symbols in α
> **Induction**
> 1. Let A* ⇒ α in k + 1 steps. Then, A ⇒* α_1Xα_2 ⇒ α_1γα_2 = α, where X → γ is a production.
> 2. In k step we assume there is a tree τ with root A and yields α_1Xα_2 fro induction (IH)
> 3. Let γ = X_1···Xn, where X_i ∈ V∪T
> 4. We construct a (k + 1)th tree by adding leaves X1,...,Xn by making them children of X


(if part) - induction on the number of internal nodes
> **Basis : **If there is only one internal node, then it must look like. Then, α = X_1···Xn and A → α is a **production**. Thus, A ⇒* α
> **Induction**
> 1. let if k internal nodes, then  A ⇒* α (IH)
> 2. Assume same case that α is a yield of a tree k + 1 internal nodes. 
> 3. Let X_1,X_2,...,Xn be the children of the root ordered from the left. Note that not all X_i are leaves(all is basis case), and A → X_1X_2···Xn is a production
> 4. let αi be the yield of the tree rooted at Xi, whether X_i is leaf or not, since parent order determine descendents' order, **α = α_1α_2...α_n**
> 5. Each sub-tree rooted at **X_i has at most k internal nodes**. Therefore, X_i ⇒* α_i (by IH)
> 6. Thus, A = X_1X_2···X_n ⇒* α_1X_2···Xn ⇒* α_1α_2···Xn ⇒* α1···α_n = α
> 
</details>

![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fabf529c1-b9c1-4662-97a2-8b805513cd11%2FUntitled.png?table=block&id=0cda05a2-3ae1-4eec-9606-7392be8dbafb&cache=v2)
Basic figure of (if part)

![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fb0f314fd-466b-446d-8c4b-405e9ca8dcb7%2FUntitled.png?table=block&id=7b22b0bc-d651-405f-869d-002fe9d864c6&cache=v2)
induction figure of (if part)

### **Issue: match derivation well, but not in a concise form**
so we use [Abstract Syntax Tree](https://texonom.com/abstract-syntax-tree-ec68a9b8a4414916b837334579a6c297) 


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







