再帰下降構文解析

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

概要

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

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

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

パーサの例

以下の文法はLL(1)形式のEBNFの例である（ニクラウス・ヴィルトのPL/0言語）。単純化のため、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 | "(" expression ")" .

終端記号は引用符で囲まれている（identとnumber以外）。各非終端記号は文法規則で定義されている。

以下に示す予言的パーサが上記文法を正確に反映している点に注意されたい。各非終端記号に対応したプロシージャが存在している。構文解析はトップダウン的に行われ、全非終端記号が処理されるまで行われる。入力コード（プログラムの部分）の先頭の単語は大域変数 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);
void error(const char msg[]);
void expression(void);

int accept(Symbol s) {
    if (sym == s) {
        getsym();
        return 1;
    }
    return 0;
}

int expect(Symbol s) {
    if (accept(s))
        return 1;
    error("expect: unexpected symbol");
    return 0;
}

void factor(void) {
    if (accept(ident)) {
        ;
    } else if (accept(number)) {
        ;
    } else if (accept(lparen)) {
        expression();
        expect(rparen);
    } else {
        error("factor: syntax error");
        getsym();
    }
}

void term(void) {
    factor();
    while (sym == times || sym == slash) {
        getsym();
        factor();
    }
}

void expression(void) {
    if (sym == plus || sym == minus)
        getsym();
    term();
    while (sym == plus || sym == minus) {
        getsym();
        term();
    }
}

void condition(void) {
    if (accept(oddsym)) {
        expression();
    } else {
        expression();
        if (sym == eql || sym == neq || sym == lss ||
            sym == leq || sym == gtr || sym == geq) {
            getsym();
            expression();
        } else {
            error("condition: invalid operator");
            getsym();
        }
    }
}

void statement(void) {
    if (accept(ident)) {
        expect(becomes);
        expression();
    } else if (accept(callsym)) {
        expect(ident);
    } else if (accept(beginsym)) {
        do {
            statement();
        } while (accept(semicolon));
        expect(endsym);
    } else if (accept(ifsym)) {
        condition();
        expect(thensym);
        statement();
    } else if (accept(whilesym)) {
        condition();
        expect(dosym);
        statement();
    }
}

void block(void) {
    if (accept(constsym)) {
        do {
            expect(ident);
            expect(eql);
            expect(number);
        } while (accept(comma));
        expect(semicolon);
    }
    if (accept(varsym)) {
        do {
            expect(ident);
        } while (accept(comma));
        expect(semicolon);
    }
    while (accept(procsym)) {
        expect(ident);
        expect(semicolon);
        block();
        expect(semicolon);
    }
    statement();
}

void program(void) {
    getsym();
    block();
    expect(period);
}

関数型言語での実装

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

実例

• JavaCC - 再帰下降パーサ生成器（コンパイラコンパイラ）
• Coco/R - 再帰下降パーサ生成器
• ANTLR - 再帰下降パーサ生成器
• Spirit Parser Framework - C++言語による再帰下降パーサ生成フレームワーク。プリコンパイル段階が不要。
• CodeCodex: Recursive descent parsing - C言語、Java言語、OCaml での再帰下降パーサの例
• Parse::RecDescent: Perl による各種再帰下降パーサ
• pyparsing: Python による各種再帰下降パーサ

種類

• Prattパーサー

参考文献

• 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

この記事は2008年11月1日以前にFree On-line Dictionary of Computingから取得した項目の資料を元に、GFDL バージョン1.3以降の「RELICENSING」(再ライセンス) 条件に基づいて組み込まれている。