曖昧な文法

コンピュータサイエンスにおいて、曖昧な文法とは、複数の左端の導出または構文解析木を持つことができる文字列が存在する文脈自由文法のことである。^[1]空でない文脈自由言語はすべて、たとえば重複規則を導入することで曖昧な文法を許容する。曖昧な文法のみを許容する言語は、本質的に曖昧な言語と呼ばれる。決定論的文脈自由文法は常に曖昧ではなく、曖昧でない文法の重要なサブクラスである。ただし、非決定論的曖昧でない文法も存在する。

コンピュータプログラミング言語の場合、参照文法はぶら下がりelse問題などの問題により、しばしば曖昧になる。存在する場合、これらの曖昧さは通常、優先順位規則やその他の文脈依存の解析規則を追加することで解決され、全体的な句文法は明確になる。^{[要出典]一部の解析アルゴリズム（} Earley ^[2]やGLRパーサーなど）は、構文的に曖昧な文字列から解析ツリー（または「解析フォレスト」）のセットを生成できる。^[3]

最も単純な例は、空の文字列のみで構成される単純な言語の次の曖昧な文法 (開始記号 A 付き) です。

A → A | ε

…つまり、非終端記号 A は、再びそれ自身に、または空の文字列に導出できます。したがって、空の文字列には、規則 A → A が何回使用されるかに応じて、長さ 1、2、3、および任意の長さの左端の導出があります。

この言語には、単一の生成規則で構成される明確な文法もあります。

A → ε

…つまり、このユニークな生成では、言語内でユニークな文字列である空の文字列のみを生成できるということです。

同様に、空でない言語の文法は、重複を追加することで曖昧になる可能性があります。

特定の文字の単項文字列の正規言語、たとえば'a'(正規表現a*) には、明確な文法があります。

A → aA | ε

…しかし、文法も曖昧です。

A → aA | Aa | ε

これらは、右結合ツリー (明確な文法の場合) を生成するか、左結合と右結合の両方を許可することに対応します。これについては、以下で詳しく説明します。

文脈自由文法

A → A + A | A − A | a

文字列 a + a + a には左端に 2 つの導出があるため、あいまいです。

別の例として、文字列 a + a − a には 2 つの解析ツリーがあるため、文法は曖昧です。

ただし、生成される言語は本質的に曖昧ではありません。以下は、同じ言語を生成する曖昧でない文法です。

A → A + a | A − a | a

コンピュータ プログラミング言語における曖昧さの一般的な例として、ぶら下がり else問題があります。多くの言語では、If–then(–else)elseステートメント内の はオプションであるため、ネストされた条件文は、文脈自由文法の観点から複数の方法で認識されることになります。

具体的には、多くの言語では、条件文をif-then形式とif-then-else形式の2つの有効な形式で記述することができます。つまり、else節はオプションになります。^[注1]

ルールを含む文法では

ステートメント → if条件thenステートメント |
             if条件thenステートメントelseステートメント |
            ...
状態→…

曖昧な句構造が現れることがある。

もしaならば bならばs、そうでなければs2

は、次のように解釈できる。

aの場合開始、  b の場合s終了、それ以外はs2
  

または

もしaなら 開始、 もしbならs 、そうでなければs2終了

elseが最初のifと 2 番目の のどちらに関連付けられているかによって異なりますif。

これは、言語によってさまざまな方法で解決されます。文法が修正されて、endif文を必須にしたり、else必須にしたりするなどして、あいまいさがなくなることがあります。また、文法があいまいなままでも、句全体の文法を文脈依存にすることであいまいさが解消されます。たとえば、an をelse最も近い に関連付けるなどifです。後者の場合、文法はあいまいではありませんが、文脈自由文法はあいまいです。^{[説明が必要]}

同じ文字列の複数の導出が存在するだけでは、文法が曖昧であることを示すのに十分ではありません。左端の複数の導出 (または、同等に、複数の構文解析ツリー) のみが曖昧さを示します。

例えば、簡単な文法

S → A + A
A → 0 | 1

は言語{0+0, 0+1, 1+0, 1+1}の明確な文法です。これら4つの文字列はそれぞれ左端の導出が1つしかありませんが、2つの異なる導出があります。たとえば、

S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0

そして

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

前者の導出のみが左端の導出です。

任意の文法が曖昧であるかどうかの決定問題は、ポスト対応問題と同等であることが示されるため、決定不可能である。[ 4 ]少なくとも、^文脈自由文法の曖昧さを検出するための半決定手順を実装したツールは存在する。^[5]

文脈自由文法の解析効率は、それを受け入れるオートマトンによって決まります。決定性文脈自由文法は、決定性プッシュダウンオートマトンによって受け入れられ、 LRパーサなどの線形時間で解析できます。^{[6]これらは、}プッシュダウンオートマトンによって受け入れられ、 CYKアルゴリズムなどの多項式時間で解析できる文脈自由文法の厳密なサブセットです。

明確な文脈自由文法は非決定的である可能性がある。例えば、0と1のアルファベットの偶数長回文の言語は、明確な文脈自由文法S → 0S0 | 1S1 | εを持つ。この言語の任意の文字列は、最初にすべてのシンボルを読み取らなければ解析できないため、プッシュダウンオートマトンでは、半解析文字列のさまざまな長さに対応するために、代替状態遷移を試行する必要がある。^[7]

それでも、文法の曖昧さを取り除くと、決定論的な文脈自由文法が生成され、より効率的な解析が可能になります。YACC などのコンパイラ ジェネレータには、優先順位や結合性の制約などを使用して、ある種の曖昧さを解決する機能が含まれています。

一部の文脈自由言語 (文法によって生成できる文字列の集合) には、曖昧な文法と曖昧でない文法の両方がありますが、曖昧でない文脈自由文法が存在できない文脈自由言語も存在します。このような言語は、本質的に曖昧であると呼ばれます。

本質的に曖昧な正規言語は存在しない。^{[8] [9]}

本質的に曖昧な文脈自由言語の存在は、1961年にMITの研究報告の中でRohit ParikhによってParikhの定理によって証明されました。 ^[10]

言語は本質的に曖昧である。^[11]${\displaystyle \{x|x=a^{n}b^{m}a^{n^{\prime }}b^{m}{\text{ または }}x=a^{n}b^{m}a^{n}b^{m^{\prime }},{\text{ ただし }}n,n',m,m'\geq 1\}}$

オグデンの補題^[12]は、 などの特定の文脈自由言語が本質的に曖昧であることを証明するために使用できます。証明については このページを参照してください。${\displaystyle \{a^{n}b^{m}c^{m}|m,n\geq 1\}\cup \{a^{m}b^{m}c^{n}|m,n\geq 1\}}$

との和集合は本質的に曖昧である。2つの文脈自由言語の和集合は常に文脈自由であるため、この集合は文脈自由である。しかしホップクロフトとウルマン（1979）は、この和集合言語のいかなる文脈自由文法も という形式の文字列を一意に解析できないことを証明している。^[13]${\displaystyle \{a^{n}b^{n}c^{m}d^{m}\mid n,m>0\}}$${\displaystyle \{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}}$${\displaystyle a^{n}b^{n}c^{n}d^{n},(n>0)}$

文脈自由言語の固有の曖昧性を証明するためのさらなる例と技術の一般的なレビューは、BassinoとNicaud（2011）によって提供されています。^[14]

• GLRパーサー、曖昧で非決定的な文法のためのパーサーの一種
• チャートパーサー、あいまいな文法のための別のタイプのパーサー
• 構文の曖昧さ

• グロス、モーリス（1964年9月）。「最小線形文法の固有の曖昧性」。情報と制御。7 （3）：366-368。doi ：10.1016 / S0019-9958（64）90422-X。
• マイケル、ハリソン(1978)。形式言語理論入門。アディソン・ウェズリー。ISBN 0201029553。
• ホップクロフト、ジョン E.、ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門(第 1 版)。アディソン ウェスレー。ISBN 9780201029888。
• ホップクロフト、ジョン、モトワニ、ラジーヴ、ウルマン、ジェフリー (2001)。オートマトン理論、言語、計算入門(第 2 版)。アディソン ウェスレー。217 ページ。ISBN 9780201441246。
• Brabrand, Claus; Giegerich, Robert; Møller, Anders (2010 年 3 月)。「文脈自由文法の曖昧性の分析」。コンピュータプログラミングの科学。75 ( 3 )。Elsevier: 176–191。CiteSeerX 10.1.1.86.3118。doi  :10.1016/ j.scico.2009.11.002 。

• dk.brics.grammar - 文法の曖昧さを解析するツール。
• CFGAnalyzer - 言語の普遍性、曖昧性、および同様の特性に関して文脈自由文法を分析するためのツール。