左再帰
E x p r → T e r m E x p r ′ {\displaystyle Expr\rightarrow Term\ Expr'} E x p r ′ → + T e r m E x p r ′ | ε {\displaystyle Expr'\rightarrow {}+Term\ Expr'\,|\,\epsilon } T e r m → F a c t o r T e r m ′ {\displaystyle Term\rightarrow Factor\ Term'} T e r m ′ → ∗ F a c t o r T e r m ′ | ε {\displaystyle Term'\rightarrow {}*Factor\ Term'\,|\,\epsilon } F a c t o r → ( E x p r ) | I n t {\displaystyle Factor\rightarrow (Expr)\,|\,Int}
ここで、'a + a + a' という文字列を入力とすると、前者の文法からは以下の構文木が得られる。
この構文木は左に成長していき、意味的には (a + a) + a を表している。すなわち、この '+' 演算子は左結合として解釈されたことがわかる。
しかし、後者の文法からは、次のような構文木が得られる。
見ての通り、構文木は右に成長しており、意味的には a + (a + a) を表している。つまり、'+' 演算子の結合性が変更され、右結合になっているのである。これは、加算の場合は問題はないが、減算では意味が全く変わってしまう(計算機における計算は、オーバーフローなどで結合法則が成り立たないことがあるので、実際には加算でも問題である)。
(参考: この例の場合、変換された文法は次のように単純化できる)