再帰下降構文解析

再帰下降構文解析は、相互再帰型の手続きで構成されるLL法のトップダウン構文解析であり、各プロシージャが文法の各生成規則を実装することが多い。従って、生成されるプログラムの構造はほぼ正確にその文法を反映したものとなる。そのような実装の構文解析器を再帰下降パーサと呼ぶ。

1. 概要
-----

バックトラックのない再帰下降パーサを 予言的パーサと呼ぶ。予言的構文解析は文脈自由文法の一種であるLL文法クラスでのみ可能であり、ある正の整数 k が存在し、再帰下降構文解析で次に使用すべき生成規則を選択するのに k 個のトークンを調べることで決定可能である。LL文法には曖昧さがなく、左再帰も含まれない。文脈自由文法は左再帰のない形式に変換可能だが、左再帰を排除しただけでLL文法となるわけではない。予言的パーサは線形時間で動作する。

バックトラックのある再帰下降構文解析では、各生成規則を毎回試すことで適用すべき生成規則を決定する。バックトラックのある再帰下降構文解析はLL文法以外にも適用できるが、LL以外の文法で有限時間以内に構文解析が完了するかどうかは保証されない。また完了したとしても、バックトラックのある再帰下降構文解析は指数関数時間を要する。

予言的パーサはよく使われているものの、文法をLL形式に変換するよりも、LR法やLALR法のパーサを作成することも多い。

2. パーサの例
--------

以下の文法はLL形式のEBNFの例である。単純化のため、//ident// と //number// は終端記号とされている:

program = block "." .

block = ["const" ident "=" number {"," ident "=" number} ";"] ["var" ident {"," ident} ";"] {"procedure" ident ";" block ";"} statement .

statement = [ident ":=" expression | "call" ident | "begin" statement {";" statement} "end" | "if" condition "then" statement | "while" condition "do" statement ] .

condition = "odd" expression | expression  expression .

expression = ["+"|"-"] term "-") term} .

term = factor "/") factor} .

factor = ident | number | "" .<WtXmlEndTag />

終端記号は引用符で囲まれている。各非終端記号は文法規則で定義されている。

以下に示す予言的パーサが上記文法を正確に反映している点に注意されたい。各非終端記号に対応したプロシージャが存在している。構文解析はトップダウン的に行われ、全非終端記号が処理されるまで行われる。入力コードの先頭の単語は大域変数 //sym// に格納されている。そして大域関数 //getsym// を使うことで //sym// を更新する。

typedef enum {ident, number, lparen, rparen, times, slash, plus, minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon, endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma, varsym, procsym, period, oddsym} Symbol;

Symbol sym; void getsym; void error; void expression;

int accept { if  { getsym; return 1; } return 0; }

int expect { if ) return 1; error; return 0; }

void factor { if ) {

} else if ) {

} else if ) { expression; expect; } else { error; getsym; } }

void term { factor; while  { getsym; factor; } }

void expression { if  getsym; term; while  { getsym; term; } }

void condition { if ) { expression; } else { expression; if  { getsym; expression; } else { error; getsym; } } }

void statement { if ) { expect; expression; } else if ) { expect; } else if ) { do { statement; } while ); expect; } else if ) { condition; expect; statement; } else if ) { condition; expect; statement; } }

void block { if ) { do { expect; expect; expect; } while ); expect; } if ) { do { expect; } while ); expect; } while ) { expect; expect; block; expect; } statement; }

void program { getsym; block; expect; }<WtXmlEndTag />

3. 関数型言語での実装
------------

HaskellやMLなどの関数型言語での再帰下降構文解析の実装は特に簡単である。例えば、[1] を参照されたい。

4. 実例
-----

JavaCC - 再帰下降パーサ生成器
Coco/R - 再帰下降パーサ生成器
ANTLR - 再帰下降パーサ生成器
[2] - C++言語による再帰下降パーサ生成フレームワーク。プリコンパイル段階が不要。
[3] - C言語、Java言語、OCaml での再帰下降パーサの例
[4]: Perl による各種再帰下降パーサ
[5]: Python による各種再帰下降パーサ

5. 種類
-----

Prattパーサ

6. 参考文献
-------

The Dragon book, Alfred V. Aho, Ravi Sethi, and Jeffrey D Ullman, 特に Section 4.4.
//Modern Compiler Implementation in Java, Second Edition//, Andrew Appel, 2002, ISBN 0-521-82060-X.
//Recursive Programming Techniques//, W.H. Burge, 1975, ISBN 0-201-14450-6
//Crafting a Compiler with C//, Charles N Fischer and Richard J LeBlanc, Jr, 1991, ISBN 0-8053-2166-7.
//Compiling with C# and Java//, Pat Terry, 2005, ISBN 0-321-26360-X, 624
//Algorithms + Data Structures = Programs//, Niklaus Wirth, 1975, ISBN 0-13-022418-9
//Compiler Construction//, Niklaus Wirth, 1996, ISBN 0-201-40353-6