LoginSignup
14
3

More than 1 year has passed since last update.

正規表現Advent Calendar 2022Day 19
@tnagao7

正規表現の微分を Haskell で実装してみる

Last updated at Posted at 2022-12-18

この記事は 正規表現 Advent Calendar 2022 の 19 日目の記事です．

いったい何番煎じかわかりませんが，正規表現の微分を Haskell で書いてみたときのメモが残っていたので，投下したいと思います．

正規表現の微分とは

正規表現の微分は，Brzozowski が提唱したもの [1] が知られており，Brzozowski 微分 (Brzozowski derivative) とも呼ばれます．

ざっくりと説明するなら，正規表現 $r$ の文字列 $u$ に関する微分とは，$r$ の先頭から $u$ 部分だけを除いた正規表現のことをいいます．

いくつか例を挙げてみます (連接の記号は省略しています)．

  • 正規表現 abc の文字列 a に関する微分は bc
  • 正規表現 abc の文字列 ab に関する微分は c
  • 正規表現 abc の文字列 abc に関する微分は $\varepsilon$ (空文字列)
  • 正規表現 abc の文字列 b に関する微分は $\emptyset$ (空集合)

この正規表現の微分を応用することで，正規表現が検査文字列に照合 (match) するかを判定できます．
検査文字列で正規表現を微分していって，その結果が $\varepsilon$ に照合するならば，その正規表現はその検査文字列に照合すると判定できるわけです．

形式的な定義

ここでは，Owens ら [2] の定式化に沿って，正規表現とその微分の形式的な定義を簡単に見ていきます．

アルファベット $\Sigma$ 上の正規表現を，以下の文法によって定義します．

\begin{eqnarray}
r,s & ::= & \emptyset   & \quad & \text{空集合} \\
    & |   & \varepsilon & & \text{空文字列} \\
    & |   & a           & & a \in \Sigma \\
    & |   & r \cdot s   & & \text{連接} \\
    & |   & r^\ast      & & \text{Kleene閉包} \\ 
    & |   & r + s       & & \text{和集合} \\ 
    & |   & r \mathbin{\&} s & & \text{積集合} \\ 
    & |   & \neg r      & & \text{補集合} \\ 
\end{eqnarray}

例として，アルファベット $\Sigma = \lbrace \mathbf{a}, \mathbf{b} \rbrace$ 上の正規表現とその言語の例をいくつか見てみましょう．

正規表現の例 この正規表現が表す言語
$\emptyset$ $\emptyset$
$\varepsilon$ $\lbrace \varepsilon \rbrace$
$\mathbf{a}$ $\lbrace \mathbf{a} \rbrace$
$\mathbf{b}$ $\lbrace \mathbf{b} \rbrace$
$\mathbf{a}^\ast$ $\lbrace \varepsilon, \mathbf{a}, \mathbf{aa}, \dots \rbrace$
$\mathbf{a} \cdot \mathbf{b}^\ast$ $\lbrace \mathbf{a}, \mathbf{ab}, \mathbf{abb}, \dots \rbrace$
$\mathbf{a} + \mathbf{b}^\ast$ $\lbrace \varepsilon, \mathbf{a}, \mathbf{b}, \mathbf{bb}, \dots \rbrace$

言語 $\mathcal{L} \subseteq \Sigma^\ast$ の文字列 $u \in \Sigma^\ast$ に関する微分 $\partial_u \mathcal{L}$ は，以下のように定義されます．

\partial_u \mathcal{L} = \{ v \ | \ u \cdot v \in \mathcal{L} \}

ここでは言語の微分を考えましたが，正規表現の微分は言語の微分の自然な拡張と考えられます．

正規表現の微分の例をいくつか見てみましょう．

正規表現の微分の例 この正規表現の微分が表す言語
$\partial_\mathbf{a} \emptyset$ $\emptyset$
$\partial_\mathbf{a} \varepsilon$ $\emptyset$
$\partial_\mathbf{a} \mathbf{a}$ $\lbrace \varepsilon \rbrace$
$\partial_\mathbf{a} \mathbf{b}$ $\emptyset$
$\partial_\mathbf{a}(\mathbf{a}^\ast)$ $\lbrace \varepsilon, \mathbf{a}, \mathbf{aa}, \dots \rbrace$
$\partial_\mathbf{a}(\mathbf{a} \cdot \mathbf{b}^\ast)$ $\lbrace \varepsilon, \mathbf{b}, \mathbf{bb}, \dots \rbrace$
$\partial_\mathbf{a}(\mathbf{a} + \mathbf{b}^\ast)$ $\lbrace \varepsilon, \mathbf{b}, \mathbf{bb}, \dots \rbrace$

正規表現の文字 $a$ に関する微分は，以下のようにして再帰的な計算で求めることができます．

\begin{eqnarray}
\partial_a \varepsilon & = & \emptyset \\
\partial_a a           & = & \varepsilon \\
\partial_a b           & = & \emptyset \quad \text{for $b \neq a$} \\
\partial_a \emptyset   & = & \emptyset \\
\partial_a(r \cdot s)  & = & \partial_a r \cdot s + \nu(r) \cdot \partial_a s \\
\partial_a(r^\ast)     & = & \partial_a r \cdot r^\ast \\ 
\partial_a(r + s)      & = & \partial_a r + \partial_a s \\
\partial_a(r \mathbin{\&} s) & = & \partial_a r \mathbin{\&} \partial_a s \\ 
\partial_a(\neg r)     & = & \neg(\partial_a r) \\ 
\end{eqnarray}

ここで，補助関数 $\nu(r)$ は，$r$ が空文字列に照合しうる (nullable) なら $\varepsilon$，そうでないなら $\emptyset$ とします．

[1] では，上記の計算結果が実際に正規表現の微分になっていることの証明が示されています．

Haskell による実装

ということで，正規表現の微分とそれに基づく正規表現の照合エンジンを Haskell で実装してみました．

ただ，十分にテストできておらず，バグがありそうな気がしているので，あくまで参考程度にご覧ください (間違いがあればご指摘ください)．

-- 正規表現
data Regex = EmptySet
           | Epsilon
           | Symbol Char
           | Concat Regex Regex
           | Star Regex
           | Union Regex Regex
           | Inter Regex Regex
           | Compl Regex
           deriving (Eq, Show)

-- 補助関数
nu :: Regex -> Regex
nu EmptySet     = EmptySet
nu Epsilon      = Epsilon
nu (Symbol a)   = EmptySet
nu (Concat r s) = Inter (nu r) (nu s)
nu (Star r)     = Epsilon
nu (Union r s)  = Union (nu r) (nu s)
nu (Inter r s)  = Inter (nu r) (nu s)
nu (Compl r)    = if (nu r) == EmptySet then Epsilon else EmptySet

-- 正規表現の微分
deriv :: Char -> Regex -> Regex
deriv a EmptySet     = EmptySet
deriv a Epsilon      = EmptySet
deriv a (Symbol b)   = if a == b then Epsilon else EmptySet
deriv a (Concat r s) = Union (Concat (deriv a r) s) (Concat (nu r) (deriv a s))
deriv a (Star r)     = Concat (deriv a r) (Star r)
deriv a (Union r s)  = Union (deriv a r) (deriv a s)
deriv a (Inter r s)  = Inter (deriv a r) (deriv a s)
deriv a (Compl r)    = Compl (deriv a r)

-- 空文字列への照合可否
match_epsilon :: Regex -> Bool
match_epsilon EmptySet     = False
match_epsilon Epsilon      = True
match_epsilon (Symbol a)   = False
match_epsilon (Concat r s) = match_epsilon r && match_epsilon s
match_epsilon (Star r)     = True
match_epsilon (Union r s)  = match_epsilon r || match_epsilon s
match_epsilon (Inter r s)  = match_epsilon r && match_epsilon s
match_epsilon (Compl r)    = not (match_epsilon r)

-- 正規表現の照合判定
matches :: Regex -> String -> Bool
matches r s = match_epsilon $ foldl (flip deriv) r s

-- ab*
regex = Concat (Symbol 'a') (Star (Symbol 'b'))

main = do
  print $ matches regex "abb"  -- => True
  print $ matches regex "abc"  -- => False

実行してみると，次のように出力されたので，うまく動いているような気がします．

% runghc regex.hs 
True
False

まとめ

Brzozowski による正規表現の微分について眺めてみました．
たまにはこういう車輪の再発明みたいな開発をするのも楽しいですね！

参考文献

14
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
3