左再帰

左再帰（英: Left recursion）とは、言語（普通、形式言語について言うが、自然言語に対しても考えられ得る）の文法（構文規則）にあらわれる再帰的な規則（定義）の特殊な場合で、ある非終端記号を展開した結果、その先頭（最も左）にその非終端記号自身があらわれるような再帰のことである。

ナイーブに再帰下降構文解析の関数に変換すると、実行（ないし評価）すると無限再帰に陥る関数になるのだが、通常の算術の式のように左結合（結合法則#結合性を参照）の中置演算子式は一般に左再帰の構文規則になるため、プログラミング言語処理系の実装のために、実用的な観点から対策が検討されてきた。この関数における再帰を指すこともある。

定義

文法が左再帰であるとは、非終端記号からその非終端記号自身を左端に含む文字列が導出される、ということである^[1]。

以下、ラテンアルファベットの大文字（ $A$ , $B$ ,...）は任意の非終端記号を、ギリシャアルファベットの小文字（ $\alpha$ , $\beta$ ,...）は任意の記号列をあらわすものとする。

直接左再帰

直接左再帰は、次のような形をした構文規則で発生する。

$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 は、左再帰を含む曖昧な文法を扱う認識アルゴリズムを示した^[2]。2007年、Frost、Hafiz、Callaghan はこのアルゴリズムを拡張し、間接左再帰も直接左再帰も多項式時間で扱える構文解析アルゴリズムとし、非常に曖昧な文法であっても指数関数的な数になる構文木を多項式サイズでコンパクトに表現できることを示した^[3]。その後、このアルゴリズムは Haskell で書かれた構文解析器生成器で実装された。その実装の詳細は上記研究者らが PADL'08 で発表した論文で示されている^[4]。X-SAIGAには、このアルゴリズムや実装についてのより詳しい記述がある。

左再帰の除去

直接左再帰の除去

直接左再帰を除去する一般的なアルゴリズムは次の通りである。このアルゴリズムには Robert C. Moore の "Removing Left Recursion from Context-Free Grammars" ^[5]で説明されているものを含めて、いくつかの改善策がある。なお、文法をLL(1)にするために必要なことがある「左くくりだし」は似ているが違うものなので注意すること。

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

$A\rightarrow A\alpha _{1}\,|\,...\,|\,A\alpha _{n}\,|\,\beta _{1}\,|\,...\,|\,\beta _{m}$

ここで:

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

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

$A\rightarrow \beta _{1}A^{\prime }\,|\,...\,|\,\beta _{m}A^{\prime }$

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

$A^{\prime }\rightarrow \epsilon \,|\,\alpha _{1}A^{\prime }\,|\,...\,|\,\alpha _{n}A^{\prime }$

この新たな記号は "tail" または "rest" と呼ばれるので、慣例として "元の記号名_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' という文字列を入力とすると、前者の文法からは以下の構文木が得られる。

                           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) を表している。つまり、'+' 演算子の結合性が変更され、右結合になっているのである。これは、加算の場合は問題はないが、減算では意味が全く変わってしまう（計算機における計算は、オーバーフローなどで結合法則が成り立たないことがあるので、実際には加算でも問題である）。

(参考: この例の場合、変換された文法は次のように単純化できる)

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

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

対象のプログラミング言語の言語仕様で、演算子は右結合である、としてしまう（対策しない）。
構文に対応するアクション（semantic actions）で工夫する^[6]。
再帰ではなくループで繰り返しを実現する文法に書き換える（拡張BNFなどによる構文規則では * を使って表現できる。手続き型の実装には、綺麗に演算子の左結合性も含め変換できる^[7]）。
結合性が正しくなるよう、さらに非終端記号を追加する^[要出典]。
再帰下降構文解析を諦め、LALRなどのボトムアップ構文解析を使用する。
- yacc（Bison）では operator declarations という %left や %right や %nonassoc という指示で、演算子の結合性を示すことで <expr> = <expr> 'op' <expr> というような曖昧（ambiguous）な形の規則でも、意図した意味に定義できる。

脚注

^ Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
^ Frost, R. and Hafiz, R. (2006) " A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time." ACM SIGPLAN Notices, Volume 41 Issue 5, Pages: 46 - 54.
^ Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague.
^ Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167-181, January 2008, San Francisco.
^ Removing Left Recursion from Context-Free Grammars
^ サンプル https://gist.github.com/anonymous/11277124 を参照
^ サンプル https://gist.github.com/anonymous/11277136 を参照

外部リンク

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

[1] Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02

[FrostHafiz2006-2] Frost, R. and Hafiz, R. (2006) " A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time." ACM SIGPLAN Notices, Volume 41 Issue 5, Pages: 46 - 54.

[FrostHafizCallaghan_2007-3] Frost, R., Hafiz, R. and Callaghan, P. (2007) " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars ." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 - 120, June 2007, Prague.

[FrostHafizCallaghan_2008-4] Frost, R., Hafiz, R. and Callaghan, P. (2008) " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167-181, January 2008, San Francisco.

[5] Removing Left Recursion from Context-Free Grammars

[6] サンプル https://gist.github.com/anonymous/11277124 を参照

[7] サンプル https://gist.github.com/anonymous/11277136 を参照

[1]

[2]

[3]

[4]

[5]

[6]

[7]