文脈自由文法
任意の u , v ∈ ( V ∪ Σ ) ∗ {\displaystyle u,v\in (V\cup \Sigma )^{*}} について、 u ⇒ ∗ v {\displaystyle u{\stackrel {*}{\Rightarrow }}v} (あるいは u ⇒⇒ v {\displaystyle u\Rightarrow \Rightarrow v} )であるとは、 u ⇒ u 1 ⇒ u 2 ⋯ ⇒ u k ⇒ v {\displaystyle u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v} となるような ∃ u 1 , u 2 , ⋯ u k ∈ ( V ∪ Σ ) ∗ , k ≥ 0 {\displaystyle \exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0} が成り立つ場合である。
導出過程は導出される文字列上にある種の階層構造を描くことでも表される。例として左端導出による「1 + 1 + 1」に対する階層構造を見てみよう。導出過程は以下のようになる。
S→S+S (1) S→S+S+S (1) S→1+S+S (2) S→1+1+S (2) S→1+1+1 (2)
{ { { 1 }S + { 1 }S }S + { 1 }S }S
ここで { ... }S は S から導出された部分文字列を意味している。これに対応する階層構造は以下のような木構造になる。
この木構造をその文字列の「具象構文木」と呼ぶ(抽象構文木も参照されたい)。この場合、上述の左端導出も右端導出も同じ構文木になるが、左端導出には以下のような別の導出過程が存在する。
S→ S + S (1) S→ 1 + S (2) S→ 1 + S + S (1) S→ 1 + 1 + S (2) S→ 1 + 1 + 1 (2)
これによって定義される構文木は以下のようになる。
この文法のように、ある文字列を導出する構文木が複数考えられる文法を「曖昧な文法」(Ambiguous Grammar)と呼ぶ。このような文法の構文解析は、生成規則の適用順序を毎回決定しなければならないため難しい。