曖昧な文法
任意の文法についてそれが曖昧かどうかという問題を一般に判定する方法は無い。すなわちそのアルゴリズムは存在しない(もし存在するとすれば、停止性問題が判定できてしまう)。
プログラミング言語など、形式言語の構文解析で使われる構文解析器では、解析結果が唯一であることを前提としていることが多い。多義性を扱うこと自体は、構文解析が失敗した場合だけでなく、成功した場合も他にも解析が可能ではないかを探すバックトラックを行えばよいだけである。それ自体よりも、多義的な箇所が複数ある場合に組合せ爆発になるので、それを全て列挙するといったような非現実的な処理を回避し、効率よく多義性を表現するにはどうしたらよいか、というような点は問題となる。
↑ 日本語では「多義的である」と「不確かである」の両方が「曖昧」であるために、何を議論しているのかがわかりにくくなりやすいことに注意。
↑ 日本語での例文に「黒い瞳の大きな女の子」というものがあるように、たいていの自然言語の文法には曖昧性がある。
↑ ここでいう「言語」とは、その言語の統語によって文法にかなっている(grammatical)とされる記号列の集合、という形式言語的な意味での「言語」である。
↑ この議論においては、言語を「記号列の集合」としてのみ扱っている点に注意。ここで示している曖昧さの無い文法からは、演算子が left-associative な構文木しか生成されない。上で示した曖昧さのある文法からは、その曖昧さの結果として、演算子が任意の associativity であるような構文木が生成される。「記号列の集合としての言語」ではなくその意味も考慮に入れると違っているという判断になる場合もありうる。
↑ 細かく言うと字句規則だが。
↑ 具体的には極めて煩雑であるためここでは略す。ネットで見られる解説などを参照のこと。