曖昧な文法

計算機科学において、形式文法が曖昧な文法（英: Ambiguous grammar）であるとは、文字列の解釈が複数存在することを意味する（すなわち、構文木が複数対応する）。言語が「本質的に曖昧」であるとは、その言語が曖昧な文法でしか生成できないことを意味する。

プログラミング言語にも曖昧な文法のものがある。その場合、構文解析時に意味的情報を加味しないと正しい解釈ができない。例えば、C言語での次の表記があるとする。

x * y ;

これは、識別子 y を x へのポインタとして宣言しているとも解釈できるし、x と y の乗算の式とも解釈できる（後者の場合、式の値は捨てている）。2つの可能な解釈の一方を選択するため、コンパイラはシンボルテーブルを参照して x が typedef 名としてその時点で定義されているかどうかを確認しなければならない。

例

次の文脈自由文法

A → A + A | A − A | a

は、文字列 a + a + a を解釈するにあたって2種類の解釈が存在するため（左端導出の導出過程が2つ存在する）、曖昧である。

	A	→ A + A		A	→ A + A
		→ a + A			→ A + A + A
		→ a + A + A			→ a + A + A
		→ a + a + A			→ a + a + A
		→ a + a + a			→ a + a + a

また、文字列 a + a − a の解釈は次の2通り存在するため、文法は曖昧である。

• (a + a) − a
• a + (a − a)

しかし、この文法から生成される言語は「本質的に曖昧」ではない。次のような曖昧でない文法でも、同じ言語を生成できる。

A → A + a | A − a | a

曖昧な文法の認識

ある文法が曖昧かどうかという問題は一般に判定不能である。文法の曖昧性を判定できるアルゴリズムは存在しない。もし存在するとすれば、停止性問題（判定不能）を曖昧性問題に変換可能であるため、矛盾が生じる。

決定性構文解析器で曖昧な文法を構文解析することには困難が伴うが、非決定性構文解析では効率が大幅に低下する。一般に構文解析で処理したいものの大半は曖昧でない文法で解釈可能である。曖昧な文法の中には曖昧でない文法に変換できるものもあるが、曖昧な文法を検出できるアルゴリズムがないのと同様、変換の汎用的な手法も存在しない。yacc などのコンパイラコンパイラには、曖昧な部分を曖昧でなくするための機能として、前後関係の制約条件を記述するなどの方式がある。

本質的に曖昧な言語

ある言語（文法によって生成される文字列の集合）は曖昧な文法と曖昧でない文法と対応しているが、曖昧でない文法とは対応しない言語も存在する。本質的に曖昧な言語の例として、$\{a^{n}b^{m}c^{m}d^{n}|n,m>0\}$ と $\{a^{n}b^{n}c^{m}d^{m}|n,m>0\}$ の和集合がある。これは文脈自由言語の和集合なので文脈自由だが、参考文献に挙げた Introduction to Automata Theory... には、2つの言語の積集合 $\{a^{n}b^{n}c^{n}d^{n}|n>0\}$ の部分集合（文脈自由でない）の文字列を曖昧でなく構文解析する方法がないことの証明が掲載されている。

参考文献

• A. Aho, R. Sethi, J. Ullman, Compilers: Principles, Techniques, and Tools. Bell Laboratories, 1986. ISBN 0-201-10088-6
  • 原田憲一 訳、『コンパイラ—原理・技法・ツール<1>』サイエンス社、1990年。ISBN 4781905854
  • 原田憲一 訳、『コンパイラ—原理・技法・ツール<2>』サイエンス社、1990年。ISBN 4781905862
• Programming Languages: Design and Implementation, T. Pratt, M. Zelkowitz. Prentice Hall, 2001
• Introduction to Automata Theory, Languages and Computation. Hopcroft, Motwani, Ullman. Addison Wesley. 2001

外部リンク

• dk.brics.grammar - a grammar ambiguity analyzer