左再帰
E x p r → T e r m E x p r ′ {\displaystyle Expr\rightarrow Term\ Expr'} E x p r ′ → + E x p r | ε {\displaystyle Expr'\rightarrow {}+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 ′ → ∗ T e r m | ε {\displaystyle Term'\rightarrow {}*Term\,|\,\epsilon } F a c t o r → ( E x p r ) | I n t {\displaystyle Factor\rightarrow (Expr)\,|\,Int}
問題は、通常の算術式は左結合性である点にある。この対策として以下のものがある。
対象のプログラミング言語の言語仕様で、演算子は右結合である、としてしまう(対策しない)。
構文に対応するアクション(semantic actions)で工夫する。
再帰ではなくループで繰り返しを実現する文法に書き換える(拡張BNFなどによる構文規則では * を使って表現できる。手続き型の実装には、綺麗に演算子の左結合性も含め変換できる)。
結合性が正しくなるよう、さらに非終端記号を追加する。
再帰下降構文解析を諦め、LALRなどのボトムアップ構文解析を使用する。 yacc(Bison)では operator declarations という %left や %right や %nonassoc という指示で、演算子の結合性を示すことで <expr> = <expr> 'op' <expr> というような曖昧(ambiguous)な形の規則でも、意図した意味に定義できる。