Rust で正規表現エンジンを実装した話 その③
概要
その①でVM型の正規表現エンジンは以下の3つの処理を行っていると説明しました。
- パターンをパースし、抽象構文木(AST)を生成する
- ASTから命令列を生成する
- 文字列がパターンと一致するか評価する
今回、解説するのは「2. ASTから命令列を生成する」処理です。
compiler モジュール(compiler.rs)に 命令列を表す型と、AST から命令列を生成する関数を実装します。
命令列と処理順所
compiler モジュールでは、ASTを解析して、命令の実行位置を示すプログラムカウンタと命令列を生成します。
命令には以下の４種類があります。
- Char : 文字列のマッチングを行い、現在の文字列と指定された文字が一致する場合、次の命令に進める命令
- Match : マッチ成功を表す命令
- Jump : 指定されたプログラムカウンタの命令を実行する
- Split : 指定された2つのプログラムカウンタの命令を実行する
これらの命令を組み合わせ、正規表現を評価します。
例えば、パターンにab(c|d)が指定された場合、ASTは以下になります。
Char(a)
Char(b)
Or(
Char(c),
Char(d)
)
上記の AST を解析した場合、以下のプログラムカウンタ(PC)と命令が生成されます。
PC : 命令
0000 : Char(a)
0001 : Char(b)
0002 : Split(0003, 0005)
0003 : Char(c)
0004 : Jump(0006)
0005 : Char(d)
0006 : Match
評価は以下の順序で実行されます。
評価対象の文字列としてabcを受け取った、以下の順序で評価が実行されます。
- a が現在の文字列として渡され、Char(a) 命令が実行されます。
a と ()内の a が一致するため、次の命令に進みます。 - b が現在の文字列として渡され、Char(b) 命令が実行されます。
b と ()内の b が一致するため、次の命令に進みます。 - Split(0003, 0005)命令が実行されます。
0003 の命令である Char(c) と 0005 の命令である Char(d) がそれぞれ実行されます。 - c が現在の文字列として渡され、Char(c) 命令が実行されます。
c と ()内の c が一致するため、次の命令に進みます。 - Jump(0006) が実行され、0006 の命令である Match が実行されます。
- Match が実行されたので、マッチ成功となります。
上記の 1～6 の順序で評価が実行され、
パターンab(c|d)に対して、文字列abcが一致すると評価されます。
compiler の実装
ここから、命令列・Compiler型を定義し、
AST から命令列を生成する関数を実装ていきます。
命令列
列挙型Instructionを、以下の内容で実装しました。
列挙型の各値が4つの命令を表しています。
#[derive(Debug, PartialEq)]
pub enum Instruction {
Char(char),
Match,
Jump(usize),
Split(usize, usize),
}
Compiler 型
Compiler 型は以下の内容で実装しました。
まずgen_codeを実行し、その中でgen_exprを実行します。
gen_exprは、受け取った AST に対応する関数を実行して、命令列を生成します。
「対応する関数」の説明は、下で行っていきます。
#[derive(Default, Debug)]
struct Compiler {
p_counter: usize, // プログラムカウンタ
instructions: Vec<Instruction> // 命令列
}
impl Compiler {
fn gen_code(&mut self, ast: &AST) {
self.gen_expr(ast);
self.instructions.push(Instruction::Match);
}
fn gen_expr(&mut self, ast: &AST) {
match ast {
AST::Char(c) => self.gen_char(*c),
AST::Or(e1, e2) => self.gen_or(e1, e2),
AST::Plus(ast) => self.gen_plus(ast),
AST::Star(ast) => self.gen_star(ast),
AST::Question(ast) => self.gen_question(ast),
AST::Seq(v) => self.gen_seq(v),
}
}
fn gen_char() {
unimplemented!()
}
fn gen_or() {
unimplemented!()
}
fn gen_plus() {
unimplemented!()
}
fn gen_star() {
unimplemented!()
}
fn gen_question() {
unimplemented!()
}
fn gen_seq() {
unimplemented!()
}
}
gen_char の実装
gen_charは、AST::Char型に対応する命令を生成します。
Instruction::Charを生成します。
fn gen_char(&mut self, c: char) {
self.p_counter += 1;
self.instructions.push(Instruction::Char(c));
}
gen_or の実装
gen_orは、AST::Orに対応する命令を生成します。
AST::Or(Char(a), Char(b))というASTを受け取った場合、
以下の命令を生成します。
0000 : Split(0001, 0003)
0001 : Char(a)
0002 : Jump(0004)
0003 : Char(b)
0004 : ...次のASTに対応する命令
以下のように実装しました。
fn gen_or(&mut self, expr1: &AST, expr2: &AST) {
let split_counter: usize = self.p_counter;
// カウンタをインクリメントし、split を挿入する
// 第二引数は、expr2のコードの開始のカウンタを指定するため、この時点では決まらない
// ここでは仮の数値(0)を入れて。数値は後で更新する
self.p_counter += 1;
self.instructions.push(Instruction::Split(self.p_counter, 0));
// 1つ目の AST を再帰的に処理する
self.gen_expr(expr1);
let jump_counter: usize = self.p_counter;
// カウンタをインクリメントし、split を挿入する。
// 引数は、expr2 のコードの次のカウンタを指定するため、この時点では決まらない
// ここでは仮の数値(0)を入れて。数値は後で更新する
self.p_counter += 1;
self.instructions.push(Instruction::Jump(0));
// Splitの第二引数を更新する
if let Some(Instruction::Split(_, right)) = self.instructions.get_mut(split_counter) {
*right = self.p_counter;
};
// 2つ目の AST を再帰的に処理する
self.gen_expr(expr2);
// Jumpの引数を更新する
if let Some(Instruction::Jump(arg)) = self.instructions.get_mut(jump_counter) {
*arg = self.p_counter;
}
}
gen_plus の実装
gen_plusは、AST::Plusに対応する命令を生成します。
AST::Plus(Char(a))というASTを受け取った場合、
以下の命令を生成します。
0000 : Char(a)
0001 : Split(0000, 0002)
0002 : ...次のASTに対応する命令
以下のように実装しました。
fn gen_plus(&mut self, ast: &AST) {
let left: usize = self.p_counter;
// AST を再帰的に処理する
self.gen_expr(ast);
// カウンタをインクリメントし Split を挿入する
self.p_counter += 1;
self.instructions.push(Instruction::Split(left, self.p_counter));
}
gen_star の実装
gen_starは、AST::Starに対応する命令を生成します。
AST::Star(Char(a))というASTを受け取った場合、
以下の命令を生成します。
0000 : Split(0001, 0003)
0001 : Char(a)
0002 : Jump(0000)
0003 : ...次のASTに対応する命令
以下のように実装しました
fn gen_star(&mut self, ast: &AST) {
let split_count: usize = self.p_counter;
// カウンタをインクリメントし、split を挿入する
// 第二引数は、後に出てくる Jump のカウンタの数値を示すものであり、この時点では決まらないので仮の数値(ここでは 0 )を入れる
// 仮の数値は、Jump を挿入した後に更新する
self.p_counter += 1;
self.instructions.push(Instruction::Split(self.p_counter, 0));
// AST を再帰的に処理する
self.gen_expr(ast);
// カウンタをインクリメントし、Jump を挿入する
self.p_counter += 1;
self.instructions.push(Instruction::Jump(split_count));
// 仮の数値としていた Split の第二引数を更新する
if let Some(Instruction::Split(_, right)) = self.instructions.get_mut(split_count) {
*right = self.p_counter;
}
}
gen_question の実装
gen_questionは、AST::Questionに対応する命令を生成します。
AST::Question(Char(a))というASTを受け取った場合、
以下の命令を生成します。
0000 : Split(0001, 0002)
0001 : Char(a)
0002 : ...次のASTに対応する命令
以下のように実装しました
fn gen_question(&mut self, ast: &AST) {
let split_count: usize = self.p_counter;
// カウンタをインクリメントし、split を挿入する
// 第二引数は、この時点では決まらないので仮の数値(ここでは 0 )を入れる
// 仮の数値は、後に更新する
self.p_counter += 1;
self.instructions.push(Instruction::Split(self.p_counter, 0));
// AST を再帰的に処理する
self.gen_expr(ast);
// 仮の数値としていた Split の第二引数を更新する
if let Some(Instruction::Split(_, right)) = self.instructions.get_mut(split_count) {
*right = self.p_counter;
}
}
gen_seq の実装
gen_seqは、AST::Seqに対応する命令を生成します。
AST::Seqの中身はAST::Seq(vec![Char(a), Char(b)])のように配列となっています。
配列の中のASTに対して、それぞれgen_exprを実行し、命令を生成します。
以下のように実装しました。
fn gen_seq(&mut self, vec:&Vec<AST>) {
for ast in vec {
self.gen_expr(ast)
}
}
Compiler 型の実装は以上です。
最後に、外に公開するAPIとなる関数compileを実装します。
pub fn compile(ast: &AST) -> Vec<Instruction> {
let mut compiler: Compiler = Compiler::default();
compiler.gen_code(ast);
compiler.instructions
}
上記の関数は、以下の処理をしています。
- Compiler 型をデフォルト値で初期化
- 命令列を生成
- 生成された命令列を返す
Discussion