曖昧な文法

曖昧な文法について

曖昧な文法（あいまいなぶんぽう）とは、特定の文に対して構文解析を行った際に、異なる解釈が生じる可能性がある文法を指します。これは、生成される構文木が一意でない場合に起こります。この曖昧さは、自然言語においても見られますが、ここでは主に形式言語の文法に焦点を当てます。

曖昧さの例

例えば、次の文脈自由文法は曖昧です:

```
A → A + A | A - A | a
```

この文法に従って生成された記号列「`a + a + a`」は、左端導出が2通り存在します。また、記号列「`a + a - a`」も2通りの解釈が可能です:

1. `(a + a) - a`
2. `a + (a - a)`

これに対し、異なるルールを用いることで同じ記号列を生成することはでき、その場合には曖昧ではありません。たとえば、次の文法:

```
A → A + a | A - a | a
```

は、記号列の集合としては曖昧さを持ちません。これは文法の設計による違いであり、曖昧さを解消する手段として用いられます。

プログラミング言語と曖昧さ

プログラミング言語においても、構文解析の際に曖昧さが現れることがあります。例えば、C言語では`typedef`によって、同じトークンが型名として解釈されることがありますが、これも一種の曖昧さです。しかし、統語的な曖昧さとは異なり、ほとんどの場合、プログラミング言語の構文解析器は一意の解析結果を期待しています。

具体的に言えば、Perlにおける正規表現リテラルなどは、統語的には多義的であり、実行時のコンテキストによって異なる解釈がなされることがあります。こうした曖昧さは、ヒューリスティックな要素を伴っている場合が多く、FLAGSなどの文脈に依存することがあります。

曖昧な文法の認識

任意の文法が曖昧かどうかを判断する一般的な方法は存在しないため、曖昧さを扱う際には、解析の過程を経て、他に解釈できるものがないかを探る技術が用いられます。このとき、曖昧さが複数存在する場合、処理が複雑化し、効率的な解決策が求められます。

パーサジェネレータと曖昧さ

yaccなどのパーサジェネレータにおいては、曖昧な文法はコンフリクトとして検出されます。しかし、すべての文法が簡単に曖昧さを判断できるわけではありません。実用性を重視する中で、生成規則だけでは曖昧になる場合に、演算子の優先順位や結合性を明示するなどの工夫を加えて、曖昧さを解決するアプローチが取られています。

本質的に曖昧な言語

一部の言語は曖昧な文法と一対一で対応できない場合があります。本質的に曖昧な言語の例として、特定の文法から生成される文字列のセットが挙げられます。文脈自由言語の和集合として存在するこれらの言語は、構文解析の際に曖昧さを持たずに解析する方法が存在しないこともあります。

参考文献

最後に、文法の曖昧さに関する詳細な理解を深めるには、以下の文献を参考にしてください:

• - A. Aho, R. Sethi, J. Ullman, Compilers: Principles, Techniques, and Tools. 1986.
• - 原田憲一 訳、『コンパイラ—原理・技法・ツール<1>』サイエンス社、1990年。
• - Introduction to Automata Theory, Languages and Computation. 2001.

もう一度検索