アルゴリズム

[Python] 再帰的下向き構文解析を実装する方法

2025-01-18更新日: 2025-01-18

再帰的下向き構文解析は、文法規則に基づいて入力をトップダウンで解析する手法です。

Pythonで実装する際は、文法の各非終端記号に対応する関数を定義し、入力を再帰的に処理します。

各関数は、対応する文法規則に従って入力を解析し、成功すれば次のトークンに進み、失敗すればバックトラックします。

トークンの管理にはリストやイテレータを使用し、入力の進行を追跡します。

目次から探す

再帰的下向き構文解析とは
再帰的下向き構文解析の仕組み
Pythonでの再帰的下向き構文解析の実装
実装例：四則演算の構文解析
完全なサンプルコード
- 実行結果
応用例
まとめ

再帰的下向き構文解析とは

再帰的下向き構文解析は、プログラミング言語の文法を解析するための手法の一つです。

この手法では、文法の非終端記号に対応する関数を再帰的に呼び出すことで、入力されたトークン列を解析します。

解析は、文法規則に従って進行し、トークンが正しい構文を形成しているかを確認します。

再帰的下向き構文解析は、特にLL(1)文法に適しており、シンプルな構文解析器を実装する際に広く利用されています。

この手法は、プログラミング言語のインタプリタやコンパイラの基盤となる重要な技術です。

再帰的下向き構文解析の仕組み

トークンと文法の定義

トークンは、プログラムのソースコードを構成する最小単位であり、通常はキーワード、識別子、演算子、リテラルなどが含まれます。

文法は、これらのトークンがどのように組み合わさって構文を形成するかを定義するルールの集合です。

文法は通常、バックウス・ナウア記法(BNF)や拡張バックウス・ナウア記法(EBNF)で表現されます。

トークンの種類	説明
キーワード	プログラミング言語の予約語
識別子	変数や関数の名前
演算子	計算や比較を行う記号
リテラル	定数値(数値や文字列)

非終端記号と終端記号の役割

文法は、終端記号と非終端記号から構成されます。

終端記号は、トークンそのものであり、解析の最終的な出力となります。

一方、非終端記号は、他の記号(終端記号や他の非終端記号)に展開される記号です。

非終端記号は、文法の構造を定義するために使用され、再帰的な関数呼び出しを通じて解析を進めます。

再帰的な関数呼び出しの流れ

再帰的下向き構文解析では、文法の非終端記号に対応する関数が定義されます。

入力トークンが非終端記号に一致する場合、その関数が呼び出され、さらに次のトークンを解析するために再帰的に他の関数が呼び出されます。

このプロセスは、全てのトークンが解析されるまで続きます。

再帰的な呼び出しは、文法の階層構造を反映し、複雑な構文を解析するのに役立ちます。

バックトラッキングの仕組み

バックトラッキングは、解析中にトークンが文法に一致しない場合に、以前の状態に戻って別の選択肢を試みる手法です。

再帰的下向き構文解析では、特定のトークンが期待される非終端記号に一致しない場合、解析を中断し、前の非終端記号に戻って別の文法規則を試すことができます。

これにより、複数の文法規則が存在する場合でも、正しい構文を見つけることが可能になります。

解析の成功と失敗の条件

解析が成功するためには、全てのトークンが文法に従って正しく解析される必要があります。

成功の条件は以下の通りです。

全てのトークンが消費され、文法規則に従った構文が形成されること。
解析中にエラーが発生しないこと。

逆に、解析が失敗する条件は以下の通りです。

トークンが文法に一致しない場合。
解析中に無限再帰が発生する場合。

Pythonでの再帰的下向き構文解析の実装

トークナイザの実装

トークナイザは、ソースコードをトークンに分割する役割を果たします。

以下は、簡単なトークナイザの実装例です。

この例では、数値と演算子をトークンとして認識します。

import re
def tokenizer(source_code):
    # 正規表現を使用してトークンを定義
    token_specification = [
        ('NUMBER',   r'\d+'),         # 数値
        ('PLUS',     r'\+'),          # 加算
        ('MINUS',    r'-'),           # 減算
        ('TIMES',    r'\*'),          # 乗算
        ('DIVIDE',   r'/'),           # 除算
        ('SKIP',     r'[ \t]+'),      # スペースとタブをスキップ
        ('MISMATCH', r'.'),           # その他の文字
    ]
    tok_regex = '|'.join(f'(?P<{pair[0]}>{pair[1]})' for pair in token_specification)
    line_number = 1
    line_start = 0
    for mo in re.finditer(tok_regex, source_code):
        kind = mo.lastgroup
        value = mo.group(kind)
        if kind == 'NUMBER':
            yield ('NUMBER', int(value))
        elif kind in ('PLUS', 'MINUS', 'TIMES', 'DIVIDE'):
            yield (kind, value)
        elif kind == 'SKIP':
            continue
        else:
            raise RuntimeError(f'{value}は無効なトークンです。')

文法規則に基づく関数の定義

次に、文法規則に基づいて関数を定義します。

ここでは、四則演算の文法を考えます。

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.current_token = None
        self.next_token()
    def next_token(self):
        try:
            self.current_token = next(self.tokens)
        except StopIteration:
            self.current_token = None
    def parse_expression(self):
        # 式の解析
        left = self.parse_term()
        while self.current_token and self.current_token[0] in ('PLUS', 'MINUS'):
            op = self.current_token
            self.next_token()
            right = self.parse_term()
            left = (op, left, right)
        return left
    def parse_term(self):
        # 項の解析
        left = self.parse_factor()
        while self.current_token and self.current_token[0] in ('TIMES', 'DIVIDE'):
            op = self.current_token
            self.next_token()
            right = self.parse_factor()
            left = (op, left, right)
        return left
    def parse_factor(self):
        # 因子の解析
        token = self.current_token
        if token[0] == 'NUMBER':
            self.next_token()
            return token
        raise RuntimeError('無効な因子です。')

再帰的な関数呼び出しの実装

上記のparse_expression、parse_term、parse_factor関数は、再帰的に呼び出され、文法に従った構文を解析します。

これにより、式全体を解析することができます。

入力の進行とトークンの消費

トークンの消費は、next_tokenメソッドを使用して行います。

現在のトークンを解析した後、次のトークンに進むことで、入力を進行させます。

これにより、全てのトークンが消費されるまで解析が続きます。

エラーハンドリングの実装

エラーハンドリングは、無効なトークンや文法に従わない入力があった場合に行います。

上記の実装では、無効なトークンや因子に対してRuntimeErrorを発生させることで、エラーを通知します。

これにより、解析中に問題が発生した場合に適切に対処できます。

実装例：四則演算の構文解析

四則演算の文法定義

四則演算の文法は、以下のように定義できます。

この文法では、加算、減算、乗算、除算を含む式を解析します。

式 (Expression) は、項 (Term) の加算または減算から構成される。
項 (Term) は、因子 (Factor) の乗算または除算から構成される。
因子 (Factor) は、数値または括弧で囲まれた式である。

この文法をもとに、再帰的下向き構文解析を実装します。

トークナイザの実装例

前述のトークナイザを使用して、ソースコードをトークンに分割します。

以下は、トークナイザの使用例です。

source_code = "3 + 5 * (2 - 8)"
tokens = tokenizer(source_code)
print(list(tokens))  # トークンのリストを表示

このコードを実行すると、次のようなトークンのリストが得られます。

[('NUMBER', 3), ('PLUS', '+'), ('NUMBER', 5), ('TIMES', '*'), ('LPAREN', '('), ('NUMBER', 2), ('MINUS', '-'), ('NUMBER', 8), ('RPAREN', ')')]

各演算子に対応する関数の実装

前述のParserクラスを使用して、各演算子に対応する関数を実装します。

parse_expression、parse_term、parse_factorメソッドは、文法に従って再帰的に呼び出されます。

class Parser:
    # 省略: 前述のParserクラスの実装

再帰的な解析の流れ

トークンを解析するために、Parserクラスのインスタンスを作成し、parse_expressionメソッドを呼び出します。

以下は、解析の流れを示すコードです。

tokens = tokenizer(source_code)
parser = Parser(iter(tokens))
result = parser.parse_expression()
print(result)  # 解析結果を表示

このコードを実行すると、次のような構文木が得られます。

('PLUS', ('NUMBER', 3), ('TIMES', ('NUMBER', 5), ('MINUS', ('NUMBER', 2), ('NUMBER', 8))))

実行結果の確認

最終的に、解析結果を確認するために、構文木を表示します。

構文木は、式の構造を示しており、各演算子とそのオペランドがどのように組み合わさっているかを視覚的に理解するのに役立ちます。

# 解析結果を表示
print(result)

このコードを実行すると、構文木が表示され、四則演算の解析が正しく行われたことを確認できます。

構文木をさらに評価することで、最終的な計算結果を得ることも可能です。

完全なサンプルコード

以下に、再帰的下向き構文解析を用いて四則演算を解析する完全なサンプルコードを示します。

このコードは、トークナイザ、パーサー、そして実行結果を表示する部分を含んでいます。

import re
# トークナイザの実装
def tokenizer(source_code):
    token_specification = [
        ('NUMBER',   r'\d+'),         # 数値
        ('PLUS',     r'\+'),          # 加算
        ('MINUS',    r'-'),           # 減算
        ('TIMES',    r'\*'),          # 乗算
        ('DIVIDE',   r'/'),           # 除算
        ('LPAREN',   r'\('),          # 左括弧
        ('RPAREN',   r'\)'),          # 右括弧
        ('SKIP',     r'[ \t]+'),      # スペースとタブをスキップ
        ('MISMATCH', r'.'),           # その他の文字
    ]
    tok_regex = '|'.join(f'(?P<{pair[0]}>{pair[1]})' for pair in token_specification)
    for mo in re.finditer(tok_regex, source_code):
        kind = mo.lastgroup
        value = mo.group(kind)
        if kind == 'NUMBER':
            yield ('NUMBER', int(value))
        elif kind in ('PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN'):
            yield (kind, value)
        elif kind == 'SKIP':
            continue
        else:
            raise RuntimeError(f'{value}は無効なトークンです。')
# パーサーの実装
class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.current_token = None
        self.next_token()
    def next_token(self):
        try:
            self.current_token = next(self.tokens)
        except StopIteration:
            self.current_token = None
    def parse_expression(self):
        left = self.parse_term()
        while self.current_token and self.current_token[0] in ('PLUS', 'MINUS'):
            op = self.current_token
            self.next_token()
            right = self.parse_term()
            left = (op, left, right)
        return left
    def parse_term(self):
        left = self.parse_factor()
        while self.current_token and self.current_token[0] in ('TIMES', 'DIVIDE'):
            op = self.current_token
            self.next_token()
            right = self.parse_factor()
            left = (op, left, right)
        return left
    def parse_factor(self):
        token = self.current_token
        if token[0] == 'NUMBER':
            self.next_token()
            return token
        elif token[0] == 'LPAREN':
            self.next_token()
            expr = self.parse_expression()
            if self.current_token[0] == 'RPAREN':
                self.next_token()
                return expr
            raise RuntimeError('対応する右括弧がありません。')
        raise RuntimeError('無効な因子です。')
# メイン処理
if __name__ == "__main__":
    source_code = "3 + 5 * (2 - 8)"
    tokens = tokenizer(source_code)
    parser = Parser(iter(tokens))
    result = parser.parse_expression()
    print(result)  # 解析結果を表示

実行結果

このコードを実行すると、次のような構文木が得られます。

(('PLUS', '+'), ('NUMBER', 3), (('TIMES', '*'), ('NUMBER', 5), (('MINUS', '-'), ('NUMBER', 2), ('NUMBER', 8))))

この構文木は、与えられた数式の構造を示しており、各演算子とそのオペランドがどのように組み合わさっているかを視覚的に理解するのに役立ちます。

応用例

複雑な文法の解析

再帰的下向き構文解析は、複雑な文法を持つプログラミング言語やデータフォーマットの解析にも応用できます。

例えば、ネストされた構造や複数の演算子を持つ式を解析するために、文法規則を拡張することが可能です。

これにより、より高度な文法を持つ言語の解析器を構築することができます。

条件分岐やループの解析

条件分岐(if文)やループ(for文、while文)を含む文法を解析するために、再帰的下向き構文解析を利用することができます。

これらの構文は、特定の条件に基づいて異なるコードブロックを実行するため、文法規則を追加して解析器を拡張することで、これらの構文を正しく解析することが可能です。

関数呼び出しの解析

関数呼び出しを含む文法を解析する際にも、再帰的下向き構文解析が役立ちます。

関数の定義と呼び出しを解析するために、文法規則を追加し、引数のリストや戻り値の型を考慮することで、関数呼び出しを正確に解析することができます。

これにより、プログラミング言語の機能をより豊かにすることができます。

プログラミング言語のインタプリタ作成

再帰的下向き構文解析は、プログラミング言語のインタプリタを作成する際の基盤技術として広く利用されています。

文法を解析し、構文木を生成することで、プログラムの実行を制御することができます。

インタプリタは、ユーザーが記述したコードを逐次実行し、結果を返すため、再帰的下向き構文解析はその中心的な役割を果たします。

JSONやXMLの解析

再帰的下向き構文解析は、データフォーマットの解析にも応用できます。

例えば、JSONやXMLのような構造化データを解析するために、文法規則を定義し、トークナイザを実装することで、データを正確に解析し、プログラム内で利用できる形式に変換することが可能です。

これにより、データの読み込みや書き込みを効率的に行うことができます。

まとめ

この記事では、再帰的下向き構文解析の基本的な概念から実装方法、応用例までを詳しく解説しました。

再帰的下向き構文解析は、プログラミング言語やデータフォーマットの解析において非常に有用な手法であり、特にシンプルな文法に対して効果的です。

これを機に、実際に自分で解析器を作成してみることで、プログラミングのスキルをさらに向上させてみてはいかがでしょうか。