左再帰

左再帰（英: Left recursion）とは、形式言語理論における再帰の特殊ケースである。

文脈自由文法において、非終端記号 r が左再帰であるとは、r を置換する任意の文字列の左端の記号が直接 r となるか（直接左再帰）、何回かの置換を経て r になる場合（間接左再帰）を指す。

また、そのような構文規則からそのまま再帰下降構文解析ルーチンを実装すると、実行（ないし評価）すると無限再帰に陥るコードとなる。このコードにおける再帰を指すこともある。

定義

文法が左再帰であるとは、非終端記号からその非終端記号自身を左端に含む文字列が導き出されることを意味する。

直接左再帰

直接左再帰は、次のような形式の生成規則で発生する。

$A \rightarrow A\alpha\,|\,\beta$

ここで、$\alpha$ と $\beta$ は任意の非終端記号と終端記号の並び（文字列）であり、$\beta$ の先頭は A ではない。

例えば、次のような規則があるとする。

$Expr \rightarrow Expr\,+\,Term$

これは直接左再帰である。再帰下降構文解析では次のようなルーチンに対応する。

function Expr() {
Expr(); match('+'); Term();
}

この生成規則を含む文法の再帰下降構文解析は、無限再帰に陥ってしまう。

間接左再帰

間接左再帰を最も単純な形式で定義すると、次のようになる。

$A \rightarrow B\alpha\,|\,C$
$B \rightarrow A\beta\,|\,D$

この場合、$A \Rightarrow B\alpha \Rightarrow A\beta\alpha \Rightarrow ...$ のような導出となる可能性がある。

より一般化すると、非終端記号群 $A_0, A_1, ..., A_n$ についての間接左再帰は次のように定義できる。

$A_0 \rightarrow A_1\alpha_1\,|...$
$A_1 \rightarrow A_2\alpha_2\,|...$
$...$
$A_n \rightarrow A_0\alpha_{(n+1)}\,|...$

ここで、$\alpha_1, \alpha_2, ..., \alpha_n$ は非終端記号と終端記号の並びである。

トップダウン構文解析での左再帰対応

左再帰を含む形式文法は、単純な再帰下降構文解析では構文解析できず、ほぼ等価な右再帰形式に変換しなければならない。一方、LALR法などではそれとは対照的で、右再帰よりも左再帰の方がスタックが深くならない。しかし、最近の研究では、より洗練されたトップダウン構文解析で左再帰型の文法も扱えることが示されている。2006年、Frost と Hafiz は、左再帰を含む曖昧な文法を扱う認識アルゴリズムを示した。2007年、Frost、Hafiz、Callaghan はこのアルゴリズムを拡張し、間接左再帰も直接左再帰も多項式時間で扱える構文解析アルゴリズムとし、非常に曖昧な文法であっても指数関数的な数になる構文木を多項式サイズでコンパクトに表現できることを示した。その後、このアルゴリズムは Haskell で書かれた構文解析器生成器で実装された。その実装の詳細は上記研究者らが PADL'08 で発表した論文で示されている。X-SAIGAには、このアルゴリズムや実装についてのより詳しい記述がある。

左再帰の除去

直接左再帰の除去

直接左再帰を除去する一般的なアルゴリズムは次の通りである。このアルゴリズムには Robert C. Moore の "Removing Left Recursion from Context-Free Grammars" で説明されているものを含めて、いくつかの改善策がある。

次のような形式の生成規則があるとする。

$A \rightarrow A\alpha_1\,|\,...\,|\,A\alpha_n\,|\,\beta_1\,|\,...\,|\,\beta_m$

ここで:

• A は左再帰の非終端記号である。
• $\alpha$ は空でない($\alpha \ne \epsilon$)終端記号と非終端記号の並びである。
• $\beta$ は終端記号と非終端記号の並びであり、先頭は A ではない。

A の生成規則を次の生成規則で置き換える。

$A \rightarrow \beta_1A^\prime\, |\, ...\, |\, \beta_mA^\prime$

そして、次の新たな非終端記号を生成する。

$A^\prime \rightarrow \epsilon\, |\, \alpha_1A^\prime\, |\, ...\, |\, \alpha_nA^\prime$

この新たな記号は "tail" または "rest" と呼ばれることが多い。

間接左再帰の除去

文法に $\epsilon$-生成規則がない場合（$A \rightarrow ... | \epsilon | ...$ のような形式の生成規則がない）、そして環状でない場合（任意の非終端記号 A から $A \Rightarrow ... \Rightarrow A$ という形の導出がありえない場合）、次のアルゴリズムで間接左再帰を除去できる。

非終端記号を何らかの固定の順序 $A_1$, ... $A_n$ で並べる（ループさせるため）。

for i = 1 to n {

for j = 1 to i – 1 {

• 現在の $A_j$ 生成規則を次のようにする。

$A_j \rightarrow \delta_1 | ... | \delta_k$

• 各生成規則 $A_i \rightarrow A_j \gamma$ を次で置き換える。

$A_i \rightarrow \delta_1\gamma | ... | \delta_k\gamma$

• $A_i$ についての直接左再帰を除去する。

}

}

間違いやすい点

上述の左再帰を除去するための変換は、右再帰型の文法を生成する。しかし、この変形は生成規則群の結合性を変化させる。左再帰は左結合性を有し、右再帰は右結合性を有する。

例えば、次のような文法があるとする。

$Expr \rightarrow Expr\,+\,Term\,|\,Term$
$Term \rightarrow Term\,*\,Factor\,|\,Factor$
$Factor \rightarrow (Expr)\,|\,Int$

これに左再帰除去の一般的手法を適用すると、次のような文法が得られる。

$Expr \rightarrow Term\ Expr'$
$Expr' \rightarrow {} + Term\ Expr'\,|\,\epsilon$
$Term \rightarrow Factor\ Term'$
$Term' \rightarrow {} * Factor\ Term'\,|\,\epsilon$
$Factor \rightarrow (Expr)\,|\,Int$

ここで、'a + a + a' という文字列を前者の文法で、（左再帰を扱える）LALR法のパーサを使って構文解析すると、以下の構文木が得られる。

                           Expr
                         /      \
                       Expr  + Term
                     /  |  \        \
                   Expr + Term    Factor
                    |       |        |
                  Term    Factor    Int
                    |        |
                  Factor    Int
                    |
                   Int  

この構文木は左に成長していき、'+' 演算子は左結合性であるため、意味的には (a + a) + a を表している。

しかし、後者の文法で構文解析すると、次のような構文木が得られる。

                            Expr ---
                           /        \
                         Term      Expr' --
                          |       /  |     \ 
                        Factor   +  Term   Expr' ------
                          |          |      |  \       \
                         Int       Factor   +  Term   Expr'
                                     |           |      |
                                    Int        Factor   $\epsilon$
                                                 |
                                                Int

見ての通り、構文木は右に成長しており、意味的には a + (a + a) を表している。つまり、'+' 演算子の結合性が変更され、右結合性になっているのである。これは、加算の場合は問題はないが、減算では意味が大幅に変わってしまう。

問題は、通常の算術式は左結合性である点にある。この対策として以下のものがある。

• 文法を左再帰型にする。ボトムアップ構文解析を使用する。
• 結合性が正しくなるよう、さらに非終端記号を追加する。
• 構文に対応するアクションで工夫する。
• yacc や Bison を使う場合は、operator declarations として %left、%right、%nonassoc があり、パーサジェネレータに結合性を指示することができる。

外部リンク

• http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf
• http://www.cs.umd.edu/class/fall2002/cmsc430/lec4.pdf
• http://www.wvutech.edu/mclark/Systems%20Programming/Removing%20Left%20Recursion.pdf
• Practical Considerations for LALR(1) Grammars
• X-SAIGA - eXecutable SpecificAtIons of GrAmmars