次のあいまいな文法の一部を見てください。 入力‘1 - 2 * 3’が2通りに構文解析されうるので、 この文法はあいまいです。
expr: expr '-' expr | expr '*' expr | expr '<' expr | '(' expr ')' ... ;
構文解析器が、‘1’、‘-’、‘2’というトークンを 読み込んだと仮定します。構文解析器は、減算演算子の規則に従って、 これらのトークンを還元するべきでしょうか。 それは、次のトークンに依存します。 もちろん、次のトークンが‘)’ならば、還元する必要があります。 なぜならば、もしシフトすると、‘- 2 )’またはそれで始まる 記号列を還元する必要が生じ、そのような規則はないからです。 しかし、次のトークンが‘*’または‘<’ならば、 シフトと還元のどちらも可能です。 どちらを選んでも構文解析を完了できますが、解析の結果は異なります。
Bison字句解析器がどちらの処理をすべきか決めるために、 構文解析の結果を考慮する必要があります。 もし、次の演算子トークンopがシフトされるならば、 還元して差を求める可能性を許すために、 opは最初に還元される必要があります。 その結果は、‘1 - (2 op 3)’となります。 逆に、opをシフトする前に減算を還元するならば、 結果は‘(1 - 2) op 3’となります。 明らかに、シフトと還元のどちらが起こるべきかの選択は、 演算子‘-’とopの相対的な優先順位に依存します。 ‘*’は先にシフトされるべきですが、‘<’は違います。
‘1 - 2 - 5’のような例ではどうなるでしょうか。 ‘(1 - 2) - 5’と処理するべきでしょうか。 それとも、‘1 - (2 - 5)’と処理するべきでしょうか。 ほとんどの演算子については前者が適し、これを、 左結合性(left association)と呼びます。 後者の右結合性(right association)は、代入演算子に適します。 左結合性か右結合性かの判断は、スタックに‘1 - 2’が含まれ、 先読みトークンが‘-’である場合の、シフトか還元かの選択です。 シフトを選ぶと、右結合的になります。