あいまいな文法とあいまいでない文法の違い

NS 主な違い あいまいな文法とあいまいでない文法の間には、あいまいな文法は、複数の左端の派生を持つことができる文字列が存在する文脈自由文法ですが、あいまいでない文法は、すべての有効な文字列が一意の左端の派生を持つ文脈自由文法です。

文法とは、自然言語の構文規則を指します。 1956年、コンピューターサイエンティストは、コンピューター言語を書くための文法の数学的モデルを導入しました。特定の文法を使用して言語のすべての文字列を導出できる場合、その言語はその文法から生成されたと言われます。文脈自由文法は文法の一種です。この文法は文脈自由言語を生成します。文脈自由文法は、あいまいな場合もあれば、あいまいでない場合もあります。特定の文字列について、2つ以上の派生がある場合、その文法はあいまいであると言われます。特定の文字列について、一意の左端の派生のみがある場合、その文法はあいまいでない文法であると言われます。

あいまいな文法、あいまいでない文法

あいまいな文法とは

文字列に2つ以上の派生が存在する場合、文法はあいまいであると言われます。

図1：あいまいな文法

次のように定義された文法があると仮定します。

G =（{S}、{a + b、+、*}、P、S}。生成ルールは次のとおりです。S-> S + S | S * S | a | b。文字列a + a * bを生成します。

考えてみてください、S-> S + S

左端のSを「a」に置き換えると、次のようになります。

S-> a + S

SをS * Sに置き換えるのは次のとおりです。

S-> a + S * S

左端のSを「a」に置き換えると、以下の出力が得られます。

S-> a + a * S

Sを「b」に置き換えると、次の出力が得られます。

S-> a + a * b

これは、生成するために必要な文字列です。

他のプロダクションルールを使用すると、

S-> S * S

左端にS + Sを適用すると、Sは次のようになります。

S-> S + S * S

左端のSを「a」に置き換えます。

S-> a + S * S

左端のSを「a」に置き換えて、

S-> a + a * S

Sを「b」に置き換えると、次の出力が得られます。

S-> a + a * b

ここでも、必要な文字列が生成されました。したがって、文字列を生成するための派生は複数あります。したがって、それはあいまいな文法です。

曖昧さのない文法とは

あいまいな文法では、特定の文字列には一意の左端の派生があります。以下の制作ルールを参照してください。

S-> L | a、L-> LS | NS

S-> Lルールを検討してください。 Lの代わりにLSを使用してください。

S-> LS

最初のLをSに置き換えます。

S-> S S

左端のSを「a」に置き換えると、以下の出力が得られます。

S-> a S

Sを「a」に置き換えると次のようになります。

S-> a a

したがって、文字列には一意の左端の派生があります。ですから、それは曖昧さのない文法です。

あいまいな文法とあいまいでない文法の違い

意味

あいまいな文法は、複数の左端の派生または解析ツリーを持つことができる文字列が存在する文脈自由文法です。曖昧さのない文法は、すべての有効な文字列が一意の左端の派生または解析ツリーを持つ文脈自由文法です。

左端の派生の数

あいまいな文法では、文字列は2つ以上の左端の派生を持つことができますが、あいまいでない文法では、文字列は一意の左端の派生を持つことができます。

結論

文脈自由文法は、あいまいな場合もあれば、あいまいでない場合もあります。あいまいな文法とあいまいでない文法の違いは、あいまいな文法は、複数の左端の派生を持つことができる文字列が存在する文脈自由文法であり、あいまいでない文法は、すべての有効な文字列が一意の左端の派生を持つ文脈自由文法であるということです。。

リファレンス：

1.「あいまいな文法」。ウィキペディア、ウィキメディア財団、2018年7月17日、こちらから入手可能2。「コンパイラの設計|あいまいな文法。」 GeeksforGeeks、2018年2月10日、こちらから入手可能3。「あいまいな文法」、Neso Academy、2017年3月29日、こちらから入手できます。