文脈自由文法が曖昧であるとは、どういうことか。

解説

正解は「ある記号列に対して、異なる構文木が2つ以上存在する」です。これは、ある記号列に異なる最左導出が2つ以上あることと同じです。例えば E → E+E | E*E | a という文法では、a+a*a に対して + を根とする木と * を根とする木の2つがあり、演算の優先順位が定まりません。プログラミング言語では、規則を書き換えたり優先順位を定めたりして曖昧さを除きます。「ある記号列を生成する導出の順序が複数ある」だけなら、同じ構文木に対する最左導出と最右導出のように、曖昧でなくても起こります。「生成規則の右辺に非終端記号が2つ以上ある」ことや「文法が生成する言語が無限集合である」ことは、曖昧さと無関係です。