プログラミング

再帰下降パーサーの実装方法

最終更新： 14/03/2025
1 分の読み

再帰下降パーサー (Recursive Descent Parser) の完全ガイド

再帰下降パーサーは、構文解析の一つの手法で、プログラムのソースコードを解釈し、構文木（パースツリー）を生成するために用いられます。この手法は、構文規則が文法的に直線的な形で表現される文法、特にLL(1)文法に適しています。本記事では、再帰下降パーサーをJavaで実装する方法を詳しく解説します。

再帰下降パーサーの基本概念

再帰下降パーサーは、文法規則に基づいて一つずつ関数を呼び出しながら入力を解析します。各文法規則に対して再帰的に対応する関数を用意することが基本となります。言い換えれば、文法規則ごとに一つの再帰的な関数を対応させ、それによって構文解析を行います。

関連記事

再帰下降パーサーは、直感的に理解しやすく、手動で実装するのに適していますが、文法が左再帰を含んでいる場合には使用できません。左再帰を含む文法の場合には、別の手法（例えば、LL(1)パーサー）を検討する必要があります。

再帰下降パーサーの実装

ここでは、シンプルな算術式（加算と乗算を含む）を解析する再帰下降パーサーをJavaで実装してみましょう。

ステップ1: 必要なクラスを準備

まず、入力をトークンに分割するための「トークナイザー」クラスを作成します。また、文法の構造に合わせてパーサークラスを作成します。

java
import java.util.*;

public class RecursiveDescentParser {
    private String input;
    private int pos;
    private char currentChar;

    public RecursiveDescentParser(String input) {
        this.input = input;
        this.pos = 0;
        this.currentChar = input.charAt(pos);
    }

    private void advance() {
        pos++;
        if (pos < input.length()) {
            currentChar = input.charAt(pos);
        } else {
            currentChar = '\0'; // 終端文字
        }
    }

    private void eat(char c) {
        if (currentChar == c) {
            advance();
        } else {
            throw new RuntimeException("Unexpected character: " + currentChar);
        }
    }

    public int parse() {
        return expr();
    }

    // 式の解析 (加算と乗算)
    private int expr() {
        int result = term(); // 最初に乗算・除算を解析
        while (currentChar == '+' || currentChar == '-') { // 加算・減算を解析
            if (currentChar == '+') {
                eat('+');
                result += term();
            } else if (currentChar == '-') {
                eat('-');
                result -= term();
            }
        }
        return result;
    }

    // 項の解析 (乗算と除算)
    private int term() {
        int result = factor(); // 最初に数値を解析
        while (currentChar == '*' || currentChar == '/') { // 乗算・除算を解析
            if (currentChar == '*') {
                eat('*');
                result *= factor();
            } else if (currentChar == '/') {
                eat('/');
                result /= factor();
            }
        }
        return result;
    }

    // 因子の解析 (括弧または数字)
    private int factor() {
        if (currentChar == '(') {
            eat('(');
            int result = expr();
            eat(')');
            return result;
        } else if (Character.isDigit(currentChar)) {
            int result = 0;
            while (Character.isDigit(currentChar)) {
                result = result * 10 + (currentChar - '0');
                advance();
            }
            return result;
        } else {
            throw new RuntimeException("Unexpected character: " + currentChar);
        }
    }

    public static void main(String[] args) {
        String input = "3+5*(2-8)";
        RecursiveDescentParser parser = new RecursiveDescentParser(input);
        int result = parser.parse();
        System.out.println("Result: " + result);
    }
}

ステップ2: トークンの解析

再帰下降パーサーは、文法規則に従って順番に解析を進めます。expr()、term()、factor() という関数がそれぞれ文法に対応しています。例えば、expr()は加算と減算を解析し、term()は乗算と除算を解析します。factor()は括弧の中の式や単なる数値を解析します。

ステップ3: 実行

上記のコードでは、数式「3+5*(2-8)」を解析しています。最初にexpr()が呼び出され、加算と乗算を順に解析します。括弧内の式も再帰的に解析され、その結果が最終的な計算結果として得られます。

java
Result: -13

この出力は、式「3+5*(2-8)」の計算結果である「-13」を示しています。

再帰下降パーサーの利点

  1. シンプルで直感的: 再帰下降パーサーは非常に直感的で、文法をそのまま再帰的な関数として表現できます。
  2. カスタマイズ可能: 特定の文法に合わせて容易にカスタマイズできるため、柔軟に使えます。
  3. デバッグが容易: 再帰的に処理を行うため、各段階での解析が容易にトレースできます。

再帰下降パーサーの限界

  1. 左再帰に弱い: 左再帰（例えば A -> A + B のような規則）を含む文法には対応できません。左再帰の文法を扱う場合は、文法を変換するか、他のパーサー手法を使う必要があります。
  2. 効率の問題: 非常に複雑な文法や長い入力に対しては、再帰的な関数呼び出しが多くなり、効率が悪くなることがあります。

結論

再帰下降パーサーは、比較的簡単で理解しやすく、特にLL(1)文法のように直線的な文法に適しています。この手法を使えば、簡単な言語の構文解析を手軽に実装することができます。しかし、左再帰や複雑な文法には向いていないため、その場合は文法の変換や他の解析手法を使用する必要があります。

再帰下降パーサーは、コンパイラやインタプリタを学ぶ上で重要な技術です。実際に自分で構文解析を実装してみることで、プログラミング言語の動作について深く理解することができます。

最終更新： 14/03/2025
1 分の読み
Back to top button