再帰下降構文解析

再帰下降構文解析とは

再帰下降構文解析（Recursive Descent Parsing）は、プログラムの文法構造を解析するためのトップダウン構文解析手法の一つです。この手法では、相互再帰的な手続き（またはそれと同等の非再帰的な手続き）を用いて、文法の各生成規則を実装します。結果として、生成されるパーサーの構造は、元の文法をほぼ正確に反映したものになります。このようなパーサーを再帰下降パーサーと呼びます。

予言的パーサー

バックトラックを行わない再帰下降パーサーは、予言的パーサー（predictive parser）と呼ばれます。予言的構文解析は、文脈自由文法の一種であるLL(k)文法クラスでのみ適用可能です。LL(k)文法では、ある正の整数 k が存在し、構文解析時に次に適用すべき生成規則を、先頭からk個のトークンを調べることで決定できます。LL(k)文法は曖昧さを含まず、左再帰も持ちません。文脈自由文法は左再帰を排除した形式に変換できますが、それだけでLL(k)文法になるわけではありません。予言的パーサーは線形時間で動作するという利点があります。

バックトラック付きパーサー

一方、バックトラックを伴う再帰下降構文解析では、各生成規則を順に試すことで、適用すべき規則を決定します。バックトラック付きパーサーはLL(k)文法以外の文法にも適用できますが、LL(k)以外の文法に対しては、構文解析が有限時間内に完了するかどうかは保証されません。また、完了した場合でも、バックトラックを伴うため、解析には指数関数的な時間を要する可能性があります。

パーサーの実例

以下は、LL(1)形式で記述されたEBNF（Extended Backus-Naur Form）の例です。この例は、ニクラウス・ヴィルトのPL/0|PL_0言語を簡略化したもので、`ident`と`number`は終端記号として扱います。

ebnf
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 ["else" statement] |
"while" condition "do" statement].
condition = "odd" expression |
expression ("="|"#"|"<") expression.
expression = ["+"|"-"] term {("+"|"-") term}.
term = factor {(""|"/") factor}.
factor = ident | number | "(" expression ")".


終端記号は引用符で囲まれています（`ident`と`number`を除く）。非終端記号はそれぞれ文法規則によって定義されています。この文法を忠実に反映した予言的パーサーは、各非終端記号に対応するプロシージャを持ち、トップダウン的に構文解析を進めます。入力コードの最初の単語は大域変数`sym`に格納され、`getsym`関数によって更新されます。

関数型言語での実装

HaskellやMLのような関数型言語では、再帰下降構文解析の実装が特に容易です。例えば、Haskellにおけるモナディックパーシングに関する論文を参照してください。

実用的な例

以下は、再帰下降パーサーに関連するツールやフレームワークの例です。

JavaCC: 再帰下降パーサー生成器（コンパイラコンパイラ）
Coco/R: 再帰下降パーサー生成器
ANTLR: 再帰下降パーサー生成器
Spirit Parser Framework: C++で記述された再帰下降パーサーフレームワークで、プリコンパイルが不要
CodeCodex: C, Java, OCamlでの再帰下降パーサーの例
Parse::RecDescent: Perlによる再帰下降パーサー
pyparsing: Pythonによる再帰下降パーサー

パーサーの種類

Prattパーサ: 演算子の優先順位を扱うのに適した構文解析手法

参考文献

以下は、再帰下降構文解析に関する重要な参考文献です。

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

この記事は、Free On-line Dictionary of Computingの資料を元に、GFDL バージョン1.3以降の条件に基づいて作成されました。

もう一度検索