左再帰
出典: フリー百科事典『ウィキペディア（Wikipedia）』
左再帰（英: Left recursion）とは、計算機科学における再帰の特殊ケースである。
文脈自由文法において、非終端記号 r が左再帰であるとは、r を置換する任意の文字列の左端の記号が直接 r となるか（直接左再帰）、何回かの置換を経て r になる場合（間接左再帰）を指す。
目次 |
[編集] 定義
文法が左再帰であるとは、非終端記号からその非終端記号自身を左端に含む文字列が導き出されることを意味する[1]。
[編集] 直接左再帰
直接左再帰は、次のような形式の生成規則で発生する。
ここで、α と β は任意の非終端記号と終端記号の並び（文字列）であり、β の先頭は A ではない。
例えば、次のような規則があるとする。
これは直接左再帰である。再帰下降構文解析では次のようなルーチンに対応する。
- function Expr() {
- Expr(); match('+'); Term();
- }
この生成規則を含む文法の再帰下降構文解析は、無限再帰に陥ってしまう。
[編集] 間接左再帰
間接左再帰を最も単純な形式で定義すると、次のようになる。
この場合、
のような導出となる可能性がある。
より一般化すると、非終端記号群 A0,A1,...,An についての間接左再帰は次のように定義できる。
- ...
ここで、α1,α2,...,α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]で説明されているものを含めて、いくつかの改善策がある。
次のような形式の生成規則があるとする。
ここで:
- A は左再帰の非終端記号である。
- α は空でない(
)終端記号と非終端記号の並びである。 - β は終端記号と非終端記号の並びであり、先頭は A ではない。
A の生成規則を次の生成規則で置き換える。
そして、次の新たな非終端記号を生成する。
この新たな記号は "tail" または "rest" と呼ばれることが多い。
[編集] 間接左再帰の除去
文法に ε-生成規則がない場合（
のような形式の生成規則がない）、そして環状でない場合（任意の非終端記号 A から 
という形の導出がありえない場合）、次のアルゴリズムで間接左再帰を除去できる。
非終端記号を何らかの固定の順序 A1, ... An で並べる（ループさせるため）。
- for i = 1 to n {
- for j = 1 to i – 1 {
-
- 現在の Aj 生成規則を次のようにする。
- 各生成規則
を次で置き換える。
- 各生成規則
- Ai についての直接左再帰を除去する。
-
- }
- for j = 1 to i – 1 {
- }
[編集] 間違いやすい点
上述の左再帰を除去するための変換は、右再帰型の文法を生成する。しかし、この変形は生成規則群の結合性を変化させる。左再帰は左結合性を有し、右再帰は右結合性を有する。
例えば、次のような文法があるとする。
これに左再帰除去の一般的手法を適用すると、次のような文法が得られる。
ここで、'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 ε
|
Int
見ての通り、構文木は右に成長しており、意味的には a + (a + a) を表している。つまり、'+' 演算子の結合性が変更され、右結合性になっているのである。これは、加算の場合は問題はないが、減算では意味が大幅に変わってしまう。
問題は、通常の算術式は左結合性である点にある。この対策として以下のものがある。
- 文法を左再帰型にする。ボトムアップ構文解析を使用する。
- 結合性が正しくなるよう、さらに非終端記号を追加する。
- yacc や Bison を使う場合は、operator declarations として %left、%right、%nonassoc があり、コンパイラコンパイラに結合性を指示することができる。
[編集] 脚注
- ^ 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
