左再帰
直接左再帰は、次のような形をした構文規則で発生する。
A → A α | β {\displaystyle A\rightarrow A\alpha \,|\,\beta }
ここで、 α {\displaystyle \alpha } と β {\displaystyle \beta } は任意の非終端記号と終端記号の並びであり、 β {\displaystyle \beta } の先頭は A ではない。
例えば、次のような規則があるとする。
E x p r → E x p r + T e r m {\displaystyle Expr\rightarrow Expr\,+\,Term}
これは直接左再帰である。これをそのまま再帰下降構文解析で実装したものは次のようになる。
これを実行すると、無限再帰に陥ってしまう。
直接左再帰を除去する一般的なアルゴリズムは次の通りである。このアルゴリズムには Robert C. Moore の "Removing Left Recursion from Context-Free Grammars" で説明されているものを含めて、いくつかの改善策がある。なお、文法をLL(1)にするために必要なことがある「左くくりだし」は似ているが違うものなので注意すること。
次のような形式の生成規則があるとする。
A → A α 1 | . . . | A α n | β 1 | . . . | β m {\displaystyle A\rightarrow A\alpha _{1}\,|\,...\,|\,A\alpha _{n}\,|\,\beta _{1}\,|\,...\,|\,\beta _{m}}
ここで:
A は左再帰の非終端記号である。
α {\displaystyle \alpha } は空でない( α ≠ ε {\displaystyle \alpha \neq \epsilon } )終端記号と非終端記号の並びである。