Parse Tree

Creator
Creator
Seonglae ChoSeonglae Cho
Created
Created
2022 Oct 5 3:50
Editor
Edited
Edited
2022 Oct 5 4:20
Refs
Refs

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
  1. internal nodes : nonterminals
  1. left nodes : terminals (external nodes)
  1. frontier : left-to-right sequence of its external nodes
  1. yield of a syntax tree : string defined by its frontier
  1. 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 α
notion image
 

Proof by induction - pretty complex
(only-if part) - induction on step

(if part) - induction on the number of internal nodes
notion image
Basic figure of (if part)
 
notion image
induction figure of (if part)
 

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

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

Recommendations