曖昧な文法

掛け算と足し算から成る式を生成する文法を考える。

文法1

<expr> -> <expr> * <expr> | <expr> + <expr> | ( <expr> ) | a

これを使って、a*a+aを導出してみる。

導出1

<expr>
-> <expr> * <expr>
-> a * <expr>
-> a * <expr> + <expr>
-> a * a + <expr>
-> a * a + a

導出2

<expr>
-> <expr> + <expr>
-> <expr> * <expr> + <expr>
-> ... -> a * a + a

導出1の構文木は、

<expr>
├<expr>-a
├*
└<expr>┬<expr>-a
       ├+
       └<expr>-a

導出2の構文木は、

<expr>
├<expr>┬<expr>-a
│      ├*
│      └<expr>-a
├+
└<expr>-a

となる。

このように、1つの文法から同じ文字列が異なる仕方で導出される場合があり得る。

文法2

<expr> -> <expr> + <term> | <term>
<term> -> <term> * <factor> | <factor>
<factor> -> ( <expr> ) | a

文法1と文法2は、全く同じ言語を生成するが、文法2は曖昧ではない。文法2でのa*a+aの構文木は、以下のものだけである。

<expr>
├<expr>┬<term>-<factor>-a
│      ├*
│      └<factor>-a
├+
└<term>-<factor>-a

この導出過程を具体的に書くと

<expr>
-> <expr> + <term>
-> <term> * <factor> + <term>
-> <factor> * <factor> + <term>
-> a * <factor> + <term>
-> a * a + <term>
-> a * a + <factor>
-> a * a + a

という過程と

<expr>
-> <expr> + <term>
-> <expr> + <factor>
-> <expr> + a
-> <term> * <factor> + a
-> <term> * a + a
-> <factor> * a + a
-> a * a + a

という過程の少なくとも2通りが考えられるように見える（実はもっと）が、どちらも同じ構文木に対応する。

導出順序の曖昧さを避けるために、「最も左の変数を導出する」仕方を最左導出と呼ぶ。 その上で、ある文法から複数の最左導出で生成される文字列が存在するとき、その文法は曖昧であると定義する。

参考文献

Michael Sipser, 計算理論の基礎, 共立出版. amazon