左再帰
左再帰(英: Left recursion)とは、言語(普通、形式言語について言うが、自然言語に対しても考えられ得る)の文法(構文規則)にあらわれる再帰的な規則(定義)の特殊な場合で、ある非終端記号を展開した結果、その先頭(最も左)にその非終端記号自身があらわれるような再帰のことである。
ナイーブに再帰下降構文解析の関数に変換すると、実行(ないし評価)すると無限再帰に陥る関数になるのだが、通常の算術の式のように左結合(結合法則#結合性を参照)の中置演算子式は一般に左再帰の構文規則になるため、プログラミング言語処理系の実装のために、実用的な観点から対策が検討されてきた。この関数における再帰を指すこともある。
β {\displaystyle \beta } は終端記号と非終端記号の並びであり、先頭は A ではない。
A の生成規則を次の生成規則で置き換える。
A → β 1 A ′ | . . . | β m A ′ {\displaystyle A\rightarrow \beta _{1}A^{\prime }\,|\,...\,|\,\beta _{m}A^{\prime }}
そして、次の新たな非終端記号を生成する。
A ′ → ε | α 1 A ′ | . . . | α n A ′ {\displaystyle A^{\prime }\rightarrow \epsilon \,|\,\alpha _{1}A^{\prime }\,|\,...\,|\,\alpha _{n}A^{\prime }}
この新たな記号は "tail" または "rest" と呼ばれるので、慣例として "元の記号名_tail" ないし "元の記号名_rest" といった名前を付けられることが多い。