曖昧文法と曖昧でない文法の主な違いは、曖昧文法とは、左端の派生が複数存在する文字列が存在する文脈自由文法であり、曖昧でない文法とは、すべての有効な文字列の左端の派生が一意である文脈自由文法であるということである。
文法とは、自然言語における構文規則を指す。
1956年、コンピュータ科学者がコンピュータ言語を記述するための文法の数学的モデルを発表した。
ある文法を用いて言語のすべての文字列を導出することができれば、その言語はその文法から生成されたと言うことができる。
文脈自由文法は文法の一種である。
この文法は文脈自由言語を生成する。
文脈自由文法は、曖昧であっても曖昧でなくてもよい。
ある文字列に対して、2つ以上の導出がある場合、その文法は曖昧であると言われる。
ある文字列に対して、左端の派生が唯一ユニークであれば、その文法は曖昧でない文法と言われる。
曖昧な文法って何？
ある文字列に対して2つ以上の導出が存在する場合、その文法は曖昧であると言われる。
図1：曖昧模糊とした文法
以下のように定義された文法があるとする。
G= ({S}, {a+b, +, *}, P, S}. 生成規則は以下の通りです。
S -> S+S | SS | a | b. String a+ a´b を生成する必要があると仮定する。
を考えると、S -> S+S
左端のSに’a’を代入すると、次のようになる。
S-> a +S
SにS*Sを代入すると次のようになる。
S-> a + S´*S
一番左のSに’a’を代入すると、以下の出力になる。
S -> a+ aenta*S
S に ‘b’ を代入すると、以下の出力が得られる。
S -> a + a * b
これが生成に必要な文字列である。
もうひとつの生成規則を使うと
S -> S * S
一番左のSにS+Sを適用すると、以下のようになります。
S -> S+S * S
left mostのSに’a’を代入する。
S -> a + S * S
左端のSに’a’を代入すると
S -> a + a * S
Sに’b’を代入すると、以下の出力が得られる。
S -> a + a *b
ここでも、必要な文字列が生成された。
したがって、文字列を生成するための導出は1つ以上存在する。
よって、曖昧文法です。
Unambiguous Grammar（曖昧さのない文法）とは？
曖昧模糊とした文法では、ある文字列の左端の派生が一意です。
以下の生成規則を参照。
S -> L | a, L -> LS | S
S -> Lルールを考える。
Lの代わりにLSを代入せよ。
S -> LS
最初のLに代えて、Sを代入する。
S -> S S
一番左のSに’a’を代入すると，次のような出力になる．
S -> a S
Sに’a’を代入すると、以下のようになる。
S -> a a
したがって、文字列は左端の導出が一意です。
したがって、これは曖昧さのない文法です。
曖昧な文法と曖昧でない文法の違い
定義
曖昧な文法とは、複数の左端の派生または解析木を持つことができる文字列が存在する文脈自由文法のことである。
曖昧でない文法とは、すべての有効な文字列が一意の左端の派生物または解析木を持つ文脈自由文法です。
左端の導出数
曖昧な文法では、文字列は2つ以上の左端導出を持つことができますが、曖昧でない文法では、文字列は一意な左端導出を持ちます。
結論
文脈自由文法には、曖昧文法と曖昧でない文法があります。
曖昧文法と曖昧でない文法の違いは、曖昧文法とは、左端の派生が複数存在する文字列が存在する文脈自由文法であり、曖昧でない文法とは、すべての有効な文字列の左端の派生が一意である文脈自由文法であるということである。
