曖昧な文法のソースを表示

'''曖昧な文法'''（あいまいなぶんぽう、{{lang-en-short|ambiguous grammar}}〈直訳すると「多義的な文法」〉）とは、[[構文木]]が唯一にならないかもしれない文法のことである。ここでは、[[自然言語]]は文法自体が不確か<ref>日本語では「多義的である」と「不確かである」の両方が「曖昧」であるために、何を議論しているのかがわかりにくくなりやすいことに注意。</ref>であることが多いため、そうではない[[形式言語]]に議論を限定するが、自然言語にも同様なことを考えることは可能である<ref>日本語での例文に「黒い瞳の大きな女の子」というものがあるように、たいていの自然言語の文法には曖昧性がある。</ref>。形式言語的な文法を持つ言語<ref>ここでいう「言語」とは、その言語の統語によって文法にかなっている（grammatical）とされる記号列の集合、という形式言語的な意味での「言語」である。</ref>が「本質的に曖昧である」とは、その言語を生成できるような文法は曖昧な文法にならざるをえないということである。

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

== 例 ==
次の[[文脈自由文法]]、
:A → A + A | A − A | a
は、曖昧である。記号列 a + a + a の[[文脈自由文法#導出と構文木|左端導出]]が2通りになるという例と、記号列 a + a &minus; a の解釈が2通りあるという例を示す。

{| border="0"
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; || A || → A + A         
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| A || → A + A   
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + A  
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → A + A + A
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + A + A
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → a + A + A
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + a + A
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → a + a + A
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + a + a
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → a + a + a
|}

記号列 a + a &minus; a について。
* (a + a) &minus; a
* a + (a &minus; a)

なお、この規則から生成される言語は、記号列の集合としての言語としては、「本質的に曖昧」ではない。次のような曖昧さの起きない規則で、同じ記号列の集合を生成できるからである。<ref>この議論においては、言語を「記号列の集合」としてのみ扱っている点に注意。ここで示している曖昧さの無い文法からは、演算子が left-associative な構文木しか生成されない。上で示した曖昧さのある文法からは、その曖昧さの結果として、演算子が任意の associativity であるような構文木が生成される。「記号列の集合としての言語」ではなくその意味も考慮に入れると違っているという判断になる場合もありうる。</ref>
:A → A + a | A − a | a

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

以上のように、構文の曖昧さが実際にあることはあまり無いが、Perlにおける正規表現リテラル中の変数展開と文字クラス記述のように、構文規則的には<ref>細かく言うと字句規則だが。</ref>実際に多義的になっていて、実際に使われている文字種により[[ヒューリスティクス|ヒューリスティク]]的に解釈が変わるという事例もあるにはある。<ref>具体的には極めて煩雑であるためここでは略す。[https://8-p.info/perl-interpolation/ ネットで見られる解説]などを参照のこと。</ref>

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

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

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

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

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

== 注 ==
<references/>

== 参考文献 ==
* [[アルフレッド・エイホ|A. Aho]], R. Sethi, J. Ullman, ''Compilers: Principles, Techniques, and Tools.'' Bell  Laboratories, 1986. ISBN 0-201-10088-6
** 原田憲一 訳、『コンパイラ&mdash;原理・技法・ツール<1>』サイエンス社、1990年。ISBN 4781905854
** 原田憲一 訳、『コンパイラ&mdash;原理・技法・ツール<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

== 外部リンク ==
*[http://www.brics.dk/grammar dk.brics.grammar - a grammar ambiguity analyzer]

{{DEFAULTSORT:あいまいなふんほう}}
[[Category:形式言語]]