Rust で正規表現エンジンを実装した話 その②
概要
その①で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
Discussion