左再帰（）とは、言語（普通、形式言語について言うが、自然言語に対しても考えられ得る）の文法（構文規則）にあらわれる再帰的な規則（定義）の特殊な場合で、ある非終端記号を展開した結果、その先頭（最も左）にその非終端記号自身があらわれるような再帰のことである。ナイーブに再帰下降構文解析の関数に変換すると、実行（ないし評価）すると無限再帰に陥る関数になるのだが、通常の算術の式のように左結合（結合法則#結合性を参照）の中置演算子式は一般に左再帰の構文規則になるため、プログラミング言語処理系の実装のために、実用的な観点から対策が検討されてきた。この関数における再帰を指すこともある。文法が左再帰であるとは、非終端記号からその非終端記号自身を左端に含む文字列が導出される、ということである。以下、ラテンアルファベットの大文字（formula_1, formula_2...）は任意の非終端記号を、ギリシャアルファベットの小文字（formula_3, formula_4...）は任意の記号列をあらわすものとする。直接左再帰は、次のような形をした構文規則で発生する。ここで、formula_3 と formula_4 は任意の非終端記号と終端記号の並び（文字列）であり、formula_4 の先頭は A ではない。例えば、次のような規則があるとする。これは直接左再帰である。これをそのまま再帰下降構文解析で実装したものは次のようになる。これを実行すると、無限再帰に陥ってしまう。間接左再帰の単純な例は、次のようなものになる。この場合、formula_8 のような導出となる可能性がある。より一般化すると、非終端記号群 formula_9 についての間接左再帰は次のように定義できる。ここで、formula_10 は非終端記号と終端記号の並びである。左再帰を含む形式文法は、以上のように単純にトップダウンの再帰下降構文解析で構文解析しようとすると無限再帰（無限ループ）に陥るため、なんらかの回避策が必要である。一方、LALR法などのボトムアップ構文解析では対照的に、右再帰よりも左再帰の方がスタックが深くならないので、むしろ効率が良いと言える。以下に示すような近年の研究では、トップダウン構文解析でも左再帰型の文法を扱える手法がいくつか示されている。2006年、Frost と Hafiz は、左再帰を含む曖昧な文法を扱う認識アルゴリズムを示した。2007年、Frost、Hafiz、Callaghan はこのアルゴリズムを拡張し、間接左再帰も直接左再帰も多項式時間で扱える構文解析アルゴリズムとし、非常に曖昧な文法であっても指数関数的な数になる構文木を多項式サイズでコンパクトに表現できることを示した。その後、このアルゴリズムは Haskell で書かれた構文解析器生成器で実装された。その実装の詳細は上記研究者らが PADL'08 で発表した論文で示されている。X-SAIGAには、このアルゴリズムや実装についてのより詳しい記述がある。直接左再帰を除去する一般的なアルゴリズムは次の通りである。このアルゴリズムには Robert C. Moore の "Removing Left Recursion from Context-Free Grammars" で説明されているものを含めて、いくつかの改善策がある。なお、文法をLL(1)にするために必要なことがある「左くくりだし」は似ているが違うものなので注意すること。次のような形式の生成規則があるとする。formula_11ここで:A の生成規則を次の生成規則で置き換える。formula_15そして、次の新たな非終端記号を生成する。formula_16この新たな記号は "tail" または "rest" と呼ばれるので、慣例として "元の記号名_tail" ないし "元の記号名_rest" といった名前を付けられることが多い。文法に formula_17-生成規則がない場合（formula_18 のような形式の生成規則がない）、そして環状でない場合（任意の非終端記号 A から formula_19 という形の導出がありえない場合）、次のアルゴリズムで間接左再帰を除去できる。非終端記号を何らかの固定の順序 formula_20, ... formula_21 で並べる（ループさせるため）。上述の変換は、同じ入力を受理するという意味では等価な変換だが、文法としては左再帰の文法を右再帰に変換してしまっている、ということに注意が必要である。変換された構文規則による構文木は、元の構文規則による構文木とは異なった構造になる。たとえば、通常の算術の式の左結合（結合法則#結合性を参照）の構文規則を変換すると、右結合に変化してしまう。以下、実例で説明する。例えば、次のような文法があるとする。これに左再帰除去の一般的手法を適用すると、次のような文法が得られる。ここで、'a + a + a' という文字列を入力とすると、前者の文法からは以下の構文木が得られる。この構文木は左に成長していき、意味的には (a + a) + a を表している。すなわち、この '+' 演算子は左結合として解釈されたことがわかる。しかし、後者の文法からは、次のような構文木が得られる。見ての通り、構文木は右に成長しており、意味的には a + (a + a) を表している。つまり、'+' 演算子の結合性が変更され、右結合になっているのである。これは、加算の場合は問題はないが、減算では意味が全く変わってしまう（計算機における計算は、オーバーフローなどで結合法則が成り立たないことがあるので、実際には加算でも問題である）。問題は、通常の算術式は左結合性である点にある。この対策として以下のものがある。

出典:wikipedia