🦁

Rust で正規表現エンジンを実装した話その②

2024/10/05に公開

Rust

正規表現

tech

概要

その①でVM型の正規表現エンジンは以下の3つの処理を行っていると説明しました。

パターンをパースし、抽象構文木(AST)を生成する
ASTから命令列を生成する
文字列がパターンと一致するか評価する

今回、解説するのは「1. パターンをパースし、抽象構文木(AST)を生成する」処理です。
parser モジュール(parser.rs)に AST を表す型と、ASTを生成する関数を実装します。

parser の実装

parserはパターンから、以下のAST型オブジェクトを生成します。

pub enum AST {
    Char(char),             // 文字に対応する型
    Plus(Box<AST>),         // '+'に対応する型
    Star(Box<AST>),         // '*'に対応する型
    Question(Box<AST>),     // '?'に対応する型
    Or(Box<AST>, Box<AST>), // '|'に対応する型
    Seq(Vec<AST>),　        // 連接に対応する型
}

例えばa|bというパターンを受け取った場合、
Or(Char(a), Char(b))というASTを生成します。

ASTの生成は、parse関数で行います。
for文で、パターンから1文字ずつ取り出し、
match式で、取り出した文字列に対応した処理を実行します。

以下、parse関数の実装です。
match式の中の各文字列に対する処理は、この後実装を記載します。

pub fn parse(pattern: &str) -> AST {
    let mut seq: Vec<AST> = Vec::new(); // 現在のコンテキスト
    let mut seq_or: Vec<AST> = Vec::new(); // Orのコンテキスト
    let mut stack: Vec<(Vec<AST>, Vec<AST>)> = Vec::new(); // コンテキストを一時的に退避させるスタック

    let mut is_escape: bool = false;

    for c in pattern.chars() {
        if is_escape {
            // エスケープ文字を受け取ったときの処理
            unimplemented!();
        }

        match c {
            '+' | '*' | '?' => {
                // +, *, ? を受け取ったときの処理
                unimplemented!();
            },
            '(' => {
                // ( を受け取ったときの処理
                unimplemented!();
            },
            ')' => {
                // ) を受け取ったときの処理
                unimplemented!();
            }
            '|' => {
                // | を受け取ったときの処理
                unimplemented!();
            },
            '\\' => is_escape = true,
            _ => seq.push(AST::Char(c))
        };
    }

    if !stack.is_empty() {
        panic!()
    }

    if !seq.is_empty() {
        seq_or.push(AST::Seq(seq));
    }

    fold_or(seq_or)
}

以下、各文字列に対する処理を実装していきます。

通常の文字のパース

通常の文字のパースは、文字列に対応するASTを生成し、seqに追加する。
実装した処理は以下です。

        match c {
            // (略)
            _ => seq.push(AST::Char(c))
        };

エスケープ文字のパース

エスケープ文字のパースは、パターンから取り出した文字が\\だったときに、
その次の文字をエスケープ文字としてASTを生成する。
実装した処理は以下です。

    for c in pattern.chars() {
        if is_escape {
            seq.push(parse_escape(c));
            is_escape = false;
            continue;
        }

        match c {
            // (略)
            '\\' => is_escape = true,
    }

\\を受け取った場合、is_escapeをtrueにする
is_escapeがtrueになったことで、次のループでif文内の処理を実行する。
parse_escape関数(この後実装する)でASTを生成し、生成したASTをseqに追加する。
is_escapeをfalseに変更する。

parse_escape関数は文字を受け取り、受け取った文字がエスケープ文字で使用可能な文字の場合、ASTを生成する。
エスケープ文字として使用可能な文字は、\\, (, ), |, +, *, ?の7種類。

parse_escape関数の実装は以下です。
受け取った文字がエスケープ文字で使用不可能な場合、プログラムを強制終了するようになっています。
(その①で記載した通り、エラー処理は考慮していません)

fn parse_escape(c: char) -> AST {
    match c {
        '\\' | '(' | ')' | '|' | '+' | '*' | '?' => AST::Char(c),
        _ => panic!(),
    }
}

+, *, ? のパース

*, +, ?のパースは、直前のASTを取得し、
*, +, ?に対応したASTを生成し、seqに追加する。

実装した処理は以下です。

        match c {
            '*' | '+' | '?' => {
                let prev_ast: AST = seq.pop().unwrap();
                let ast: AST = parse_qualifier(c, prev_ast);
                seq.push(ast);
            },

上記の処理は、以下を行っています。

seq.pop()で直前のASTを取得し、変数prev_astに格納。
parse_qualifier関数(この後実装する)で、*, +, ?に対応するASTを生成。
生成したASTをseq.push(ast)でseqに追加。

parse_qualifier関数は、文字と直前のASTを受け取り、受け取った文字に対応したASTを生成します。
parse_qualifier関数の実装は以下です。

fn parse_qualifier(c: char, prev: AST) -> AST{
    match c {
        '*' => AST::Plus(Box::new(prev)),
        '+' => AST::Star(Box::new(prev)),
        '?' => AST::Question(Box::new(prev)),
        _ => unreachable!()
    }
}

例えば、パターンがa+の場合、

受け取る文字列 : +
直前のAST : Char(a)

となり、parse_qualifierを実行すると、Plus(Char(a))というASTが生成されます。

| のパース

|のパースは、|の前のASTを別の配列に退避させます。
実装した処理は以下です。

        match c {
            // (略)
            '|' => {
                seq_or.push(AST::Seq(seq));
                seq = Vec::new();
            }

上記の処理は以下を行っています。

seq_orにseqを追加。
seqを空にする。

例えば、a|bというパターンの場合、

|を処理する際、seqにはChar(a)が含まれている。
このChar(a)をseq_orに追加し、seqを空にする。

( のパース

(のパースは、(を受け取った時点でのASTを、stackに退避させます。

        match c {
            // (略)
            '(' => {
                stack.push((seq, seq_or));
                seq = Vec::new();
                seq_or = Vec::new();
            }

上記の処理は以下を行っています。

seq, seq_orをstackに追加。
seq, seq_orを空にする。

) のパース

stack から AST を取り出し、seq, seq_orにそれぞれ代入します。

        match c {
            // (略)
            ')' => {
                let (mut prev, prev_or) = stack.pop().unwrap();

                if !seq.is_empty() {
                    seq_or.push(AST::Seq(seq));
                }
                prev.push(fold_or(seq_or));

                seq = prev;
                seq_or = prev_or;
            }

途中で実行している、fold_orは以下の実装です。
seq_orから or のAST を生成します。

fn fold_or(mut seq_or: Vec<AST>) -> AST {
    if seq_or.len() > 1 {
        let mut ast: AST = seq_or.pop().unwrap();
        seq_or.reverse();
        for s in seq_or {
            ast = AST::Or(Box::new(s), Box::new(ast));
        }
        ast
    } else {
        seq_or.pop().unwrap()
    }
}

parser の完成形

parser モジュール(parser.rs)の完成形は以下です。
GitHub - parser.rs

概要