⚙

正規表現エンジンの季節らしいので正規表現エンジンを作った

#tech#Rust

2024-11-19

何

先日研究室同期のsosukesuzukiと雑談していたところ，「秋から冬にかけては正規表現エンジンの季節である」という旨の主張[1]をされた．これに対し自分は一から正規表現エンジンを書いたことが無いため有効な反駁をするに値する根拠を持ち合わせていなかったので，ちょうど"正規表現エンジンの季節"だし作ってみてからこの主張に対する検討をしようと思い，正規表現エンジンを作成した．

作ったもの

コードはここに置いた：

https://github.com/lapla-cogito/rustegex

以下の情報は全て本記事執筆時点でのもの：

  • Rust製DFA型正規表現エンジン（正規表現を等価なNFA，DFAの順に変換していく）
  • 文字リテラルはu8に収まる範囲のもの
  • 演算は連接，選択，繰り返しをサポート

アプローチ

一口に正規表現エンジンといっても，その実装アプローチは複数存在する．大きな括りでいうとDFA型のものとVM型のもの，微分型のものがあり，DFA型は正規表現を，それと等価なDFAに変換して，そのDFAが入力文字列を受容するかどうかでマッチングを行う．VM型は正規表現をバイトコードにコンパイルしてから，仮想的なレジスタマシン内でマッチングを行う．パターンがマッチしない場合にはバックトラックを行うことができる半面，ReDoSなどに繋がりうる．微分型では，正規表現に対するBrzozowski微分[2]を考えていって，入力文字列とマッチするかの判定をする．多分本質的な面ではDFA型と同一視してしまって良い気がする[3]が，実装上の違いは大きいと思うのでここではあえて分けた．

今回は正規表現のオートマトンとの関連性を実装を通じて実感したかったので，それが一番よく分かりそうなDFA型のものを作ることにした．

実装

構文解析

正規表現を抽象構文木に変換するステップ．まあこれは凝ったことしていない普通の再帰下降構文解析だと思うので実装を見てください．

今後の説明に必要そうな部分だけ説明しておくと，Lexer構造体は次のような形をしていて：

#[derive(Debug)]
pub struct Lexer<'a> {
    input: std::str::Chars<'a>,
}

この構造体が扱うトークンの種類がこれで：

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Token {
    Character(char),
    UnionOperator,
    StarOperator,
    PlusOperator,
    QuestionOperator,
    LeftParen,
    RightParen,
    Empty,
}

Parserの構造体Parserは次のようにLexerと，現在見ているトークンの情報を持っていて：

#[derive(Debug)]
pub struct Parser<'a> {
    lexer: &'a mut crate::lexer::Lexer<'a>,
    looking: crate::lexer::Token,
}

パーサーにパースを依頼すると次に示すAstNodeの列が返ってくる：

#[derive(Debug, PartialEq)]
pub enum AstNode {
    Char(char),
    Plus(Box<AstNode>),
    Star(Box<AstNode>),
    Question(Box<AstNode>),
    Or(Box<AstNode>, Box<AstNode>),
    Seq(Vec<AstNode>),
    Empty,
}

例えばLexerとParserを次のように使えば

let mut lexer = crate::lexer::Lexer::new("a|b");
let mut parser = Parser::new(&mut lexer);

次のようなASTが得られる：

AstNode::Or(Box::new(AstNode::Char('a')), Box::new(AstNode::Char('b')))

NFAへの変換

正規表現から，それと等価なNFAを構築するステップ．これは再帰的に構成することが可能で，代表的な手法としてはThompsonの構成法がある．

まずNFAを表す構造体を次のようにする．transitionsメンバーのHashSetは((from), (label), (to))の形で遷移を表す．また，labelがNoneならε遷移を表す：

pub type NfaStateID = u64;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Nfa {
    start: NfaStateID,
    accept: std::collections::HashSet<NfaStateID>,
    transitions: std::collections::HashSet<(NfaStateID, Option<char>, NfaStateID)>,
}

遷移を追加したり，2つのNFAをマージするような機会が多いので，これに対応するメソッドも作っておく：

pub fn add_transition(&mut self, from: NfaStateID, char: char, to: NfaStateID) {
    self.transitions.insert((from, Some(char), to));
}

pub fn add_epsilon_transition(&mut self, from: NfaStateID, to: NfaStateID) {
    self.transitions.insert((from, None, to));
}

fn merge_nfa(&mut self, other: &Nfa) {
    self.transitions.extend(other.transitions.clone());
    self.add_epsilon_transition(self.start, other.start);
    for accept in other.accept.iter() {
        self.accept.insert(*accept);
    }
}

あとはAstNodeを見ていって再帰的にNFAを作れば良い．これはnew_from_nodeメソッドに処理内容を書いたが，AstNode::Charについてのみ抜粋すると次のようになる：

pub fn new_from_node(node: crate::parser::AstNode, state: &mut NfaState) -> crate::Result<Nfa> {
    match node {
        crate::parser::AstNode::Char(c) => {
            let start = state.new_state();
            let accept = state.new_state();
            let mut nfa = Nfa::new(start, vec![accept]);
            nfa.add_transition(start, c, accept);

            Ok(nfa)
        }
        （中略）
    }
}

単に開始状態と受理状態を作って，その間に遷移を張っているだけ．他のノードの種類だともう少し複雑だがやっていることの原理は同じ．

DFAへの変換

任意のNFAに対して，それと等価なDFAは必ず構築できることが知られている．この変換は例えば部分集合構成法を用いることができる．これはNFAのε-閉包を状態として持つDFAを構築する方法．

なのでまずはNfa構造体に，始点の頂点群を取ってそのε-閉包を求めるメソッドを実装した．これは単純にDFS的に行うことが可能：

pub fn epsilon_closure(
    &self,
    start: std::collections::BTreeSet<crate::automaton::nfa::NfaStateID>,
) -> std::collections::BTreeSet<crate::automaton::nfa::NfaStateID> {
    let mut visited = std::collections::BTreeSet::new();
    let mut to_visit = std::collections::VecDeque::new();

    for &state in start.iter() {
        if !visited.contains(&state) {
            to_visit.push_back(state);
        }
    }

    while let Some(state) = to_visit.pop_front() {
        if visited.contains(&state) {
            continue;
        }
        visited.insert(state);

        for &(from, label, to) in self.transitions() {
            if from == state && label.is_none() && !visited.contains(&to) {
                to_visit.push_back(to);
            }
        }
    }

    visited
}

このepsilon_closureを用いて，NFAを受け取り，それと等価なDFAを返すメソッドを実装した：

pub fn from_nfa(nfa: &crate::nfa::Nfa) -> Self {
    let mut dfa_states = std::collections::BTreeMap::new();
    let mut queue = std::collections::VecDeque::new();

    let start: std::collections::BTreeSet<_> =
        epsilon_closure(nfa, [nfa.start()].iter().cloned().collect())
            .into_iter()
            .collect();

    let start_id = dfa_states.len() as DfaStateID;
    dfa_states.insert(start.clone(), start_id);
    queue.push_back(start.clone());

    let mut dfa = Dfa::new(start_id, std::collections::HashSet::new());

    while let Some(current) = queue.pop_front() {
        let current_id = dfa_states[&current];

        if current.iter().any(|&state| nfa.accept().contains(&state)) {
            dfa.accepts.insert(current_id);
        }

        for c in 1..=u8::MAX {
            let mut next = std::collections::BTreeSet::new();
            for &state in current.iter() {
                for &(from, label, to) in nfa.transitions() {
                    if from == state && Some(c as char) == label {
                        next.extend(epsilon_closure(nfa, [to].iter().cloned().collect()));
                    }
                }
            }

            if next.is_empty() {
                continue;
            }

            if !dfa_states.contains_key(&next) {
                let next_id = dfa_states.len() as DfaStateID;
                dfa_states.insert(next.clone(), next_id);
                queue.push_back(next.clone());
            }

            let next_id = dfa_states[&next];
            dfa.transitions.insert((current_id, c as char, next_id));
        }
    }

    dfa
}

マッチング

ここまでで正規表現から，それと等価なDFAを作れたので，あとは入力をDFAに流してマッチするかどうかを見ればよい．

Future works

様々ある．まずVM型のものは作ってみたいし，そこでReDoSを緩和する仕組みであるキャッシュも実装してみたい．他にも，オートマトン的なアプローチで言えばDFAを最小化する最適化も存在するし．あと使える文字の種類も増やしたい．

（11/22追記：VM型のものと，それにキャッシュも実装した）
（11/26追記：微分型のものも実装した）
（11/27追記：Unicodeの文字リテラルに対応した）

あとなんかこういう正規表現エンジンを作った時にシュッと試せるいい感じの皆使ってるベンチマークがあると良いなと思った．既にあるなら教えてください．

結論

別に秋や冬は特段正規表現エンジンの実装に適した季節ではないという気持ちになった．外はやたら寒いので「オートマトンの気持ちになるために，外出して様々な地点を遷移するぞ～」みたいなことをする気が起きないため．

脚注

  1. 2人が所属する筑波大学情報学群情報科学類で，オートマトンと形式言語という講義が秋学期に存在することが唯一の根拠らしい．根拠として弱すぎる（別に講義では正規表現エンジンを作るわけでもないし） ↩︎

  2. "微分"という訳語を使うことに対しては懐疑的な立場（いや気持ちは分かるけど）だが，他にどう訳すんだと言われたら困るので，困るね〜という感じです ↩︎

  3. ある正規表現から1文字削って得られる正規表現を順に考えていくのは，DFAで1つずつ状態遷移することと同一視できると思うので ↩︎