🐕

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

2024/10/05に公開

Rust

正規表現

tech

概要

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

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

今回、解説するのは「3. 文字列がパターンと一致するか評価する」処理です。
evaluator モジュール(evaluator.rs)に命令列と文字列を受け取り、評価を実施する関数を定義します。

また、実際にパターンマッチする関数をmain.rsに定義して、実行するところも記載します。

evaluator の実装

evaluator モジュールの中に、evaluate関数を定義することで、評価を実行します。
以下のように実装しました。

pub fn evaluate(instructions: &[Instruction], chars: &Vec<char>, mut p_counter: usize, mut index: usize) -> bool {
    loop {
        let instruction: &Instruction = instructions.get(p_counter).unwrap();

        match instruction {
            Instruction::Char(c) => {
                let character = chars.get(index).unwrap();
                if c == character {
                    p_counter += 1;
                    index += 1;
                } else {
                    return false
                }
            }
            Instruction::Match => return true,
            Instruction::Jump(counter) => p_counter = *counter,
            Instruction::Split(counter1, counter2 ) => {
                if evaluate(instructions, chars, *counter1, index) || evaluate(instructions, chars, *counter2, index) {
                    return true
                } else {
                    return false
                }
            }
        }
    }
}

引数はそれぞれ、以下が入ります。

instructions : 命令列
chars : 文字列(正確にはVec型の参照)
p_counter : プログラムカウンタ
index : 文字列のインデックス

上記の関数では、Char, Match, Jump, Splitに対応する処理をそれぞれ実行しています。

Char の処理

Char の処理は以下の部分です。

            Instruction::Char(c) => {
                let character = chars.get(index).unwrap();
                if c == character {
                    p_counter += 1;
                    index += 1;
                } else {
                    return false
                }
            }

命令列の文字c と、文字列から取得してきた文字character を比較し、
文字が一致した場合、プログラムカウンタとインデックスに 1 を加えています。
1 を加えることで、命令と文字を1つ進めます。

一致しない場合は、その文字列はマッチしないため、false を返します。

Match の処理

Matchは命令列の最後に挿入されるもので、
Matchまで到達することは、その文字列はマッチすることを意味するため、 true を返します。

            Instruction::Match => return true,

Jump の処理

Jump は、指定されたプログラムカウンタの命令を実行する命令です。
そのため、Jumpに指定された値counterを、プログラムカウンタに代入します。

            Instruction::Jump(counter) => p_counter = *counter,

Split の処理

Splitは、指定された2つのプログラムカウンタの命令を実行する命令です。
そのため、再帰的にevaluate関数を実行します。
再帰的に実行する際に、引数のp_counterには、Splitで指定された値(counter1, counter2)をそれぞれ指定します。

            Instruction::Split(counter1, counter2 ) => {
                if evaluate(instructions, chars, *counter1, index) || evaluate(instructions, chars, *counter2, index) {
                    return true
                } else {
                    return false
                }
            }

以上の処理で、評価を実行します。上記の関数を実行し、

trueが返ってきた場合はマッチ成功
falseが返ってきた場合はマッチ失敗

です。

パターンマッチを実行してみる

以下のようにpattern_match関数を実装し、パターンマッチを実行します。
これまでに実装した関数を使って、パース～評価までを順に実行しています。

use parser::parse;
use compiler::compile;
use evaluator::evaluate;

fn pattern_match(pattern: &str, line: &str) -> bool {
    let ast = parse(pattern);
    let instructions = compile(&ast);
    let chars: Vec<char> = line.chars().collect();
    evaluate(&instructions, &chars, 0, 0)
}

実際に main 関数で使用して、結果を表示してみます。

fn main() {
    println!("{}", pattern_match("ab*(de|fg)", "abbbfg")); // true を期待
    println!("{}", pattern_match("a?b(d*e|fg)", "bdde"));  // true を期待
    println!("{}", pattern_match("a?b(d*e|fg)", "cbfg"));  // false を期待
}

実行結果は以下です。
期待した通りの結果が得られました。

$ cargo run
   Compiling small-regex v0.1.0 (/...../small-regex)
    Finished dev [unoptimized + debuginfo] target(s) in 1.35s
     Running `target/debug/small-regex`
true
true
false

あとがき

ここまで読んでいただきありがとうございました。

今回の実装を通して、VM型正規表現エンジンの仕組みと Rust の文法を学ぶことができました。
ただ、今回はエラー処理を省いていますが、本来ならつけるべきだと思います。

今回説明した正規表現エンジンに、エラー処理を加える、対応する記号を増やす、など発展させていってもらえればうれしいです。

概要