曖昧な文法

曖昧な文法（あいまいなぶんぽう、英: ambiguous grammar〈直訳すると「多義的な文法」〉）とは、構文木が唯一にならないかもしれない文法のことである。ここでは、自然言語は文法自体が不確かであることが多いため、そうではない形式言語に議論を限定するが、自然言語にも同様なことを考えることは可能である。形式言語的な文法を持つ言語が「本質的に曖昧である」とは、その言語を生成できるような文法は曖昧な文法にならざるをえないということである。

以下では、議論を統語（syntax）の曖昧性（ambiguity）に限定し、さらに用語として「文法」ではなく「統語」を使うことができる文脈ではできるだけ「統語」を使う。

例

次の文脈自由文法、

A → A + A | A − A | a

は、曖昧である。記号列 a + a + a の左端導出が2通りになるという例と、記号列 a + a − a の解釈が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 について。

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

なお、この規則から生成される言語は、記号列の集合としての言語としては、「本質的に曖昧」ではない。次のような曖昧さの起きない規則で、同じ記号列の集合を生成できるからである。

A → A + a | A − a | a

プログラミング言語

プログラミング言語ではしばしば型などによって式の意味が異なったりすることがある。しかしそれはここで議論しているような統語の曖昧性ではない（なお、プログラミング言語では、「統語」よりも「構文」という語を使うことが多いので、この節でのみ以下は用語を変える）。またC言語を例にとるとtypedefの機能によって、字面的には全く同じトークンが、識別子ではなく型名になるために構文が静的に解析できない、といった例があるが、それもここで議論しているような曖昧性とは異なる。en:Dangling else の問題は、文脈自由文法として見た場合は曖昧さがあるということだが、構文解析器として実装された時点で曖昧さは無くなっている。

以上のように、構文の曖昧さが実際にあることはあまり無いが、Perlにおける正規表現リテラル中の変数展開と文字クラス記述のように、構文規則的には実際に多義的になっていて、実際に使われている文字種によりヒューリスティク的に解釈が変わるという事例もあるにはある。

曖昧な文法の認識

任意の文法についてそれが曖昧かどうかという問題を一般に判定する方法は無い。すなわちそのアルゴリズムは存在しない（もし存在するとすれば、停止性問題が判定できてしまう）。

プログラミング言語など、形式言語の構文解析で使われる構文解析器では、解析結果が唯一であることを前提としていることが多い。多義性を扱うこと自体は、構文解析が失敗した場合だけでなく、成功した場合も他にも解析が可能ではないかを探すバックトラックを行えばよいだけである。それ自体よりも、多義的な箇所が複数ある場合に組合せ爆発になるので、それを全て列挙するといったような非現実的な処理を回避し、効率よく多義性を表現するにはどうしたらよいか、というような点は問題となる。

パーサジェネレータ

yaccなどのパーサジェネレータの場合、曖昧な文法はパーサを生成する際の内部処理で発見されるコンフリクトとして報告される。なお、これは前述した制限を破るようなものではない。yaccの場合、記述可能な文法は文脈自由文法に限られており、任意の文法について判定できるわけではないし、曖昧な文法ではなくてもコンフリクトになることはある。

実用性を重視したパーサジェネレータでは、中置記法の数式のような文法について、生成規則だけでは曖昧になるような規則で書くことを許し、それを補助するような、演算子について優先順位や結合性（en:Operator associativity）を示す規則を追加することで曖昧さを解決する、というような手法が提供されている。

本質的に曖昧な言語

ある言語（文法によって生成される文字列の集合）は曖昧な文法と曖昧でない文法と対応しているが、曖昧でない文法とは対応しない言語も存在する。本質的に曖昧な言語の例として、$\{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