左再帰のソースを表示

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

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

== 定義 ==
文法が左再帰であるとは、非終端記号からその非終端記号自身を左端に含む文字列が導出される、ということである<ref>[http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion'  Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.]JPR02</ref>。

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

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

{{Indent|<math>A \rightarrow A\alpha\,|\,\beta</math>}}

ここで、<math>\alpha</math> と <math>\beta</math> は任意の[[非終端記号]]と[[終端記号]]の並びであり、<math>\beta</math> の先頭は A ではない。

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

{{Indent|<math>Expr \rightarrow Expr\,+\,Term</math>}}

これは直接左再帰である。これをそのまま[[再帰下降構文解析]]で実装したものは次のようになる。
 function Expr() {
     Expr();  match('+');  Term();
 }
これを実行すると、無限再帰に陥ってしまう。

=== 間接左再帰 ===
間接左再帰の単純な例は、次のようなものになる。
{{Indent|
<math>A \rightarrow B\alpha\,|\,C</math><br />
<math>B \rightarrow A\beta\,|\,D</math>
}}
この場合、<math>A \Rightarrow B\alpha \Rightarrow A\beta\alpha \Rightarrow ... </math> のような導出となる可能性がある。

より一般化すると、非終端記号群 <math>A_0, A_1, ..., A_n</math> についての間接左再帰は次のように定義できる。
{{Indent|
<math>A_0 \rightarrow A_1\alpha_1\,|...</math><br />
<math>A_1 \rightarrow A_2\alpha_2\,|...</math><br />
<math>...</math><br />
<math>A_n \rightarrow A_0\alpha_{(n+1)}\,|...</math>
}}
ここで、<math>\alpha_1, \alpha_2, ..., \alpha_n</math> は非終端記号と終端記号の並びである。

== トップダウン構文解析での左再帰対応 ==
左再帰を含む[[形式文法]]は、以上のように単純にトップダウンの[[再帰下降構文解析]]で[[構文解析]]しようとすると無限再帰（[[無限ループ]]）に陥るため、なんらかの回避策が必要である。一方、[[LALR法]]などの[[ボトムアップ構文解析]]では対照的に、右再帰よりも左再帰の方がスタックが深くならないので、むしろ効率が良いと言える。以下に示すような近年の研究では、[[トップダウン構文解析]]でも左再帰型の文法を扱える手法がいくつか示されている。2006年、Frost と Hafiz は、左再帰を含む[[曖昧な文法]]を扱う[[有限オートマトン|認識]]アルゴリズムを示した<ref name="FrostHafiz2006"> 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.</ref>。2007年、Frost、Hafiz、Callaghan はこのアルゴリズムを拡張し、間接左再帰も直接左再帰も[[多項式時間]]で扱える[[構文解析]]アルゴリズムとし、非常に曖昧な文法であっても指数関数的な数になる[[構文木]]を多項式サイズでコンパクトに表現できることを示した<ref name="FrostHafizCallaghan 2007"> 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.</ref>。その後、このアルゴリズムは [[Haskell]] で書かれた構文解析器生成器で実装された。その実装の詳細は上記研究者らが PADL'08 で発表した論文で示されている<ref name="FrostHafizCallaghan 2008"> 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.</ref>。[http://www.cs.uwindsor.ca/~hafiz/proHome.html X-SAIGA]には、このアルゴリズムや実装についてのより詳しい記述がある。

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

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

<math>A \rightarrow A\alpha_1\,|\,...\,|\,A\alpha_n\,|\,\beta_1\,|\,...\,|\,\beta_m </math>

ここで:
* A は左再帰の非終端記号である。
* <math>\alpha</math> は空でない(<math>\alpha \ne \epsilon </math>)終端記号と非終端記号の並びである。
* <math>\beta</math> は終端記号と非終端記号の並びであり、先頭は A ではない。

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

<math>A \rightarrow \beta_1A^\prime\, |\, ...\,  |\,  \beta_mA^\prime</math>

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

<math>A^\prime \rightarrow \epsilon\, |\, \alpha_1A^\prime\,  |\,  ...\, |\, \alpha_nA^\prime</math>

この新たな記号は "tail" または "rest" と呼ばれるので、慣例として "元の記号名_tail" ないし "元の記号名_rest" といった名前を付けられることが多い。

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

非終端記号を何らかの固定の順序 <math>A_1</math>, ... <math>A_n</math> で並べる（ループさせるため）。
{{Indent|
for i <nowiki>=</nowiki> 1 to n {
{{Indent|
for j <nowiki>=</nowiki> 1 to i – 1 {
{{Indent|
* 現在の <math>A_j</math> 生成規則を次のようにする。
<math>A_j \rightarrow \delta_1 | ... | \delta_k</math>
* 各生成規則 <math>A_i \rightarrow A_j \gamma</math> を次で置き換える。
<math>A_i \rightarrow \delta_1\gamma | ... | \delta_k\gamma</math>
* <math>A_i</math> についての直接左再帰を除去する。
}} } }} } }}

=== 注意点 ===
上述の変換は、同じ入力を受理するという意味では等価な変換だが、文法としては左再帰の文法を右再帰に変換してしまっている、ということに注意が必要である。変換された構文規則による[[構文木]]は、元の構文規則による構文木とは異なった構造になる。たとえば、通常の算術の式の左結合（[[結合法則#結合性]]を参照）の構文規則を変換すると、右結合に変化してしまう。以下、実例で説明する。

例えば、次のような文法があるとする。
{{Indent|
<math>Expr \rightarrow Expr\,+\,Term\,|\,Term</math><br />
<math>Term \rightarrow Term\,*\,Factor\,|\,Factor</math><br />
<math>Factor \rightarrow (Expr)\,|\,Int</math>
}}
これに左再帰除去の一般的手法を適用すると、次のような文法が得られる。
{{Indent|
<math>Expr \rightarrow Term\ Expr'</math><br />
<math>Expr' \rightarrow {} + Term\ Expr'\,|\,\epsilon</math><br />
<math>Term \rightarrow Factor\ Term'</math><br />
<math>Term' \rightarrow {} * Factor\ Term'\,|\,\epsilon</math><br />
<math>Factor \rightarrow (Expr)\,|\,Int</math>
}}
ここで、'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   <math>\epsilon</math>
                                                  |
                                                 Int

見ての通り、構文木は右に成長しており、意味的には a + (a + a) を表している。つまり、'+' 演算子の結合性が変更され、右結合になっているのである。これは、加算の場合は問題はないが、減算では意味が全く変わってしまう（計算機における計算は、オーバーフローなどで結合法則が成り立たないことがあるので、実際には加算でも問題である）。

(参考: この例の場合、変換された文法は次のように単純化できる)
{{Indent|
<math>Expr \rightarrow Term\ Expr'</math><br />
<math>Expr' \rightarrow {} + Expr\,|\,\epsilon</math><br />
<math>Term \rightarrow Factor\ Term'</math><br />
<math>Term' \rightarrow {} * Term\,|\,\epsilon</math><br />
<math>Factor \rightarrow (Expr)\,|\,Int</math>
}}
問題は、通常の算術式は左結合性である点にある。この対策として以下のものがある。
* 対象のプログラミング言語の言語仕様で、演算子は右結合である、としてしまう（対策しない）。
* 構文に対応するアクション（semantic actions）で工夫する<ref>サンプル https://gist.github.com/anonymous/11277124 を参照</ref>。
* 再帰ではなくループで繰り返しを実現する文法に書き換える（拡張BNFなどによる構文規則では * を使って表現できる。手続き型の実装には、綺麗に演算子の左結合性も含め変換できる<ref>サンプル https://gist.github.com/anonymous/11277136 を参照</ref>）。
* 結合性が正しくなるよう、さらに非終端記号を追加する<!--英語版から引き継いでる記述ですが、可能なのか？-->{{要出典|date=2014年4月}}。
* [[再帰下降構文解析]]を諦め、LALRなどの[[ボトムアップ構文解析]]を使用する。
** [[yacc]]（[[Bison]]）では ''operator declarations'' という %left や %right や %nonassoc という指示で、演算子の結合性を示すことで &lt;expr&gt; = &lt;expr&gt; 'op' &lt;expr&gt; というような曖昧（ambiguous）な形の規則でも、意図した意味に定義できる。

== 脚注 ==
{{Reflist}}

== 外部リンク ==
* 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
* [http://lambda.uta.edu/cse5317/notes/node21.html Practical Considerations for LALR(1) Grammars]
* [http://www.cs.uwindsor.ca/~hafiz/proHome.html X-SAIGA] - eXecutable SpecificAtIons of GrAmmars

{{DEFAULTSORT:ひたりさいき}}
[[Category:構文解析 (プログラミング)]]
[[Category:形式言語]]
[[Category:再帰]]