オートマトンの単位は落としそうですが、今日から数回に分けてHaskell正規表現エンジンを自作していきたいと思います。

完成図

実は既に手元に完成品があるのですが、今回はHaskell正規表現DSLを構築したいと思います。動作例は以下の通り。

>>> str "hoge" `matches` "hoge"
True
>>> str "hoge" `matches` "fuga"
False
>>> ((str "hoge" |: str "fuga") *:) `matches` "hogefugahogefuga"
True
>>> ((str "hoge" |: str "fuga") *:) `matches` "hogefugahogefugafoobar"
False

str "hoge" が文字列 hogeを、|:が論理和を、*:が任意回の繰り返しを表します。

完成品は以下のリポジトリに上げる(予定)です。

github.com

オートマトン

正規表現エンジンを実装するには、まずオートマトンを作る必要があります。
オートマトンは理論上正規表現と等価な表現力を持っており、通常は正規表現をそのまま解析するのではなく、等価なオートマトンに変換してから文字列のマッチなどの処理を行います(たぶん)。
オートマトンは有限種類の状態からなり、入力文字によってその状態を変化させていく仮想的な機械です。文字列の各文字を先頭から順に入力していき、最終的に到達した状態の種類によって入力文字列が正規表現にマッチしたかどうかを判定します。

オートマトンにも種類はいろいろありますが、基本的に以下のような形で表すことができます。

-- Automaton.hs
module Automaton where

-- 以下2つは後でMapのキーにしたりするので、Ordのインスタンスになっています。
type Alphabet a = (Eq a, Ord a) -- アルファベット
type State s = (Eq s, Ord s) -- 状態

-- 後で使う
(-->) :: a -> b -> (a, b)
a --> b = (a, b)
infix 5 -->

-- オートマトン
class Automaton fa where
  type F fa s :: *
  step :: (State s, Alphabet a) => fa s a -> F fa s -> a -> F fa s
  initStates :: (State s, Alphabet a) => fa s a -> F fa s
  isAcceptStates :: (State s, Alphabet a) => fa s a -> F fa s -> Bool

これが状態型sを持ち、文字aの列[a]を認識するオートマトンfa s aの定義になります。
オートマトンは初期状態と呼ばれる値initStatesと、受理状態と呼ばれる値isAcceptStates, 遷移関数と呼ばれる関数stepの3種類からなります。

それぞれの定義にはF fa sという謎の型が使われていますが、これはとりあえずs自体と同等だと思ってください。オートマトンの種類によってはこのsが同時に複数存在したりする可能性があるので、抽象的な定義になっているだけです。

そうやってAutomatonの定義を読み替えると、以下のようになります。

-- 遷移関数
step :: (State s, Alphabet a) => fa s a -> s -> a -> s
-- 初期状態
initStates :: (State s, Alphabet a) => fa s a -> s
-- 受理状態
isAcceptStates :: (State s, Alphabet a) => fa s a -> s -> Bool

オートマトンfaはそれぞれ自分の状態sを持っており、その状態で文字aが入力されると、次の状態が

s' = step fa s a

となるs'に移ります。
初期状態s0のオートマトンfaに文字列a0:a1:a2:..:an:[]を与えた時、オートマトンは以下のように状態を遷移していきます。

s1 = step fa s0 a0
s2 = step fa s1 a1
...
sn = step fa s(n-1) a(n-1)
s(n+1) = step fa sn an

こうして最後にたどり着いた状態s(n+1)がisAcceptStatesを満たせば、その状態は受理状態であり、入力文字列は受理されたと言います。
最終的には、文字列が受理されることとその文字列が正規表現にマッチしていることが同値になるようなオートマトンを構成していくことになります。

今の説明に従って、オートマトンが文字列を「受理」するかどうかを判定する関数を書いてみましょう。

-- Automaton.hs
run :: (Automaton fa, State s, Alphabet a) => fa s a -> F fa s -> [a] -> F fa s
run fa ss [] = ss
run fa ss (a:as) = run fa (step fa ss a) as

-- dfa `accepts` str : dfa が列 str を受理すれば True, そうでなければ False
accepts :: (Automaton fa, State s, Alphabet a) => fa s a -> [a] -> Bool
fa `accepts` as = isAcceptStates fa (run fa (initStates fa) as)

次に、オートマトンの実際の実装例を一つ見てみましょう。以下のデータ型DFAは、オートマトンの中でも最も簡単なものである決定性有限オートマトン(Deterministic Finite Automaton)と言われるものです*1

-- Automaton/DFA.hs
module Automaton.DFA
import qualified Data.Map as M
import qualified Data.Set as S

data DFA state alpha = DFA {
    dfaTransTable :: M.Map (state, alpha) state
  , dfaStart :: state
  , dfaAccepts :: S.Set state
  } deriving (Show, Read)

instance Automaton DFA where
  type F DFA s = Maybe s
  step _ Nothing _ = Nothing
  step dfa (Just s) a = M.lookup (s, a) $ dfaTransTable dfa
  initStates dfa = Just (dfaStart dfa)
  isAcceptStates _ Nothing = False
  isAcceptStates dfa (Just s) = isAcceptState dfa s

isAcceptState :: (State s, Alphabet a) => DFA s a -> s -> Bool
isAcceptState dfa s = S.member s $ dfaAccepts dfa

DFAは初期状態をdfaStart, 受理状態を集合dfaAcceptsで表しており、状態sと文字aが来た時に次に遷移する状態をMapの形で持っています。
DFAの状態(F DFA s)はMaybe s型で表され、Nothingは常に失敗となりますが、これは単にMapに遷移先が書かれていなかった場合に無条件で失敗にするための実装上の都合です。

これを使って、簡単なオートマトンを作ってみましょう。
以下は"ab"の任意回の繰り返しを受理するオートマトンです。

-- Example.hs
{-# LANGUAGE
    OverloadedLists #-}
import Automaton
import Automaton.DFA (DFA(..))

n_times_of_ab :: DFA Int Char
n_times_of_ab = DFA {
    dfaTransTable = [
        (s, 'a') --> a
      , (a, 'b') --> b
      , (b, 'a') --> a
      ]
  , dfaStart = s
  , dfaAccepts = [b]
  } where s:a:b:_ = [0..]

OverloadedListsというGHC拡張が使われていますが、これはMapやSet等*2をリストリテラルと同様の表記で書けるようにするための拡張です。


s, a, bは状態です。区別できれば何でも良いので、s:a:b:_ = [0..]というように適当な数値を代入しています。

初期状態はsで、そこから入力文字'a'を受け取ると状態aになります。状態aから入力文字'b'を受け取ると状態bに移り、状態bから入力文字'c'を受け取ると状態aに戻ります。それ以外の場合は失敗(受理されない)です。

f:id:cloudear8:20170209170509p:plain

最終的に状態bにたどり着いていれば、その文字列は受理されたこととなります。

>>> n_times_of_ab `accepts` "" -- 空文字列は受理しない
False
>>> n_times_of_ab `accepts` "ab" -- "ab" の1回の繰り返しなのでok
True
>>> n_times_of_ab `accepts` "abababab" -- "ab" の4回の繰り返しなのでok
True
>>> n_times_of_ab `accepts` "ababababa" -- aで終わってるのでダメ
False
>>> n_times_of_ab `accepts` "aababab" -- 先頭がaaとなっているのでダメ
False
>>> n_times_of_ab `accepts` "bababab" -- bから始まっているのでダメ
False

*1:DFA自体の厳密な定義についてはここでは触れません。気になる方はWikipediaとかに載っているので読んでみてください。 決定性有限オートマトン - Wikipedia

*2:GHC.Exts.IsListのインスタンスである任意の型