Haskellで簡単な正規表現を実装した【KMCアドベントカレンダー8日目】
KMCアドベントカレンダー8日目の記事です。
講義で正規表現とかオートマトンをちゃんと学んだので、Haskellの修行も兼ねて簡単な正規表現を実装しました。理論とか実装とかダルいと思うので、おまけだけ読むと楽しいかも知れません。
理論
決定性有限オートマトン(DFA)
有限オートマトンとは、
- 状態集合(s_0, s_1, .., s_N)
- 入力記号(a, b, c, など)
- 受理状態集合
- 初期状態(s_0)
- 状態遷移関数
によって定義される数学的モデルです。ある入力記号列が与えられると、それを左から読みながら状態を移動していきます（最初は初期状態にいる）。状態の移動は状態遷移関数に依存します。状態遷移関数は、現在の状態と入力記号を受け取って、遷移先の状態を返すような関数です。例えば「s_0にいる状態で'a'を読んだら、s_1に移動する」というような遷移を定義します。全ての記号を読み終わった時に受理状態ならば、その入力記号列は「受理される」と言います。
非決定性有限オートマトン(NFA)
状態遷移関数による遷移先が複数存在するとき「非決定性がある」と言います。例えば「s_0にいる状態で'a'を読んだら、s_1またはs_2に移動する」というような遷移です。こうした非決定性が出現した場合はどちらのルートも探索します。最終的に入力記号列が受理されるようなルートが一つでも存在するならば、その言語は受理されると定義されます。また、空文字(ε)による遷移を許す場合もあり、この時ε-NFAというような書き方をします（以下ENFA）。ENFAとNFAはDFAに変換できることが知られています。
正規表現
形式的には、特殊な記号は'|'と'*'しか認めません。つまりORと繰り返しのみです。
実装（覚書に近い要約なので恐らく何も伝わらない）
Haskell Regular Expression を略して Hegex というライブラリ名で実装しました。基本的に正規表現は、パターン文字列をオートマトンに変換したあとに、そのオートマトンをマッチさせたい文字列でシミュレートするという実装方針を取るようです。変換をNFAで止めて非決定性を幅優先探索する手法も存在しますが、今回はDFAまで変換しています。
GitHubリポジトリ : https://github.com/yu-i9/Hegex
また、実装に際しては 正規表現エンジンをつくろう が非常に参考になりました。
Hegex.Tree
パターン文字列をトークン列に変換したあと、構文木に変換しています。不正なパターンへの対応としてEitherではなく例外を投げていますが、どうせ不正なパターンならば意味はないのだから、その場で落として良いだろうという判断によるものです。不正な入力はこの段階で完全に排除するので、あとの実装が楽になります。
Hegex.NFA
構文木をENFAに変換します。ε遷移を活用し、構文木の各パーツについて始点と終点がそれぞれ1状態になるように構成していきます（詳しい構成法は実際にコードを読んで図を書いてみてください）。すると、Stateモナドで構成中のNFAを保持しながら両端のインデックスを計算するだけで良くなるので簡潔に書くことができます。
Hegex.DFA
ENFAをNFA経由でDFAに変換します。ENFAからNFAへの変換ではε遷移を消さなければいけません。これは、ε遷移先の状態に関する全ての遷移をもとの状態の遷移に統合することで実現できます。NFAからDFAへの変換では、非決定性を排除しなければいけません。ここでは部分集合構成法を使います。ここでは、遷移する可能性がある状態の集合そのものを新たな状態としてしまう方法です。NFAの状態数は有限なので、その冪集合の大きさも有限で、いつかは遷移の探索をし尽くせることがわかります。
テスト
Haskellの単体テスト最前線を参考に、自動テストを実装しました。カバレッジなど考えることが多くて（結局考えきれてない）テストもちゃんと勉強しなければと思いました。
おまけ1 - 7の倍数にマッチする正規表現オブジェクト
あしぃさん(id:asi1024)に7の倍数にマッチするオートマトンの話を聞いたので書いてみました。このマッチャーを正規表現で得ようとすると非常に大変です。こちらで生成スクリプトを書いて吐き出している方がおりますが、およそ500MBだそうです。とても自力で書けるようなものではありません。しかし、そのオートマトンは驚くほど簡潔です。上の桁から7で割った余りについて遷移していくことで8状態で実現できます。（例えば、ひと桁目を7で割った余りが1ならば次は4で余り0の状態へと遷移する）。8状態のオートマトンくらいなら自力で構成できます。自分で実装したからこそ、決め打ちした生のデータ構造を投げ込む荒業が使えている感じがしますね。以下がプログラムです。実際には遷移関数をベタ書きするのも十分つらかったのでスクリプトで生成しています。遷移関数の読み方は((読んだ記号, 現在の状態), 遷移先の状態)です。
-- src/ Multiple7Matcher.hs import Hegex import qualified Data.Map as Map import qualified Data.Set as Set import System.Environment main :: IO () main = do (str:_) <- getArgs print $ matcher str matcher :: String -> Bool matcher = getMatcherWithDFA 7 dfatrans (Set.singleton 0) where dfatrans = Map.fromList [(('0', 7), 0), (('7', 7), 0), (('1', 7), 1), (('8', 7), 1), (('2', 7), 2), (('9', 7), 2), (('3', 7), 3), (('4', 7), 4), (('5', 7), 5), (('6', 7), 6), (('0', 0), 0), (('7', 0), 0), (('1', 0), 1), (('8', 0), 1), (('2', 0), 2), (('9', 0), 2), (('3', 0), 3), (('4', 0), 4), (('5', 0), 5), (('6', 0), 6), (('0', 1), 3), (('7', 1), 3), (('1', 1), 4), (('8', 1), 4), (('2', 1), 5), (('9', 1), 5), (('3', 1), 6), (('4', 1), 0), (('5', 1), 1), (('6', 1), 2), (('0', 2), 6), (('7', 2), 6), (('1', 2), 0), (('8', 2), 0), (('2', 2), 1), (('9', 2), 1), (('3', 2), 2), (('4', 2), 3), (('5', 2), 4), (('6', 2), 5), (('0', 3), 2), (('7', 3), 2), (('1', 3), 3), (('8', 3), 3), (('2', 3), 4), (('9', 3), 4), (('3', 3), 5), (('4', 3), 6), (('5', 3), 0), (('6', 3), 1), (('0', 4), 5), (('7', 4), 5), (('1', 4), 6), (('8', 4), 6), (('2', 4), 0), (('9', 4), 0), (('3', 4), 1), (('4', 4), 2), (('5', 4), 3), (('6', 4), 4), (('0', 5), 1), (('7', 5), 1), (('1', 5), 2), (('8', 5), 2), (('2', 5), 3), (('9', 5), 3), (('3', 5), 4), (('4', 5), 5), (('5', 5), 6), (('6', 5), 0), (('0', 6), 4), (('7', 6), 4), (('1', 6), 5), (('8', 6), 5), (('2', 6), 6), (('9', 6), 6), (('3', 6), 0), (('4', 6), 1), (('5', 6), 2), (('6', 6), 3) ]
おまけ2 - Haskellの正規表現ライブラリ
Haskellの正規表現ライブラリ(Text.Regex.Posix)は異常なほどに強力です。Perlなどでお馴染みの =~ 演算子でマッチングを行うわけですが、その結果は多相型になっています。例を見たほうが早いでしょう。
>>> "abc" =~ "(a|b)" :: Bool -- マッチしたかどうか True >>> "abc" =~ "ab" :: String -- マッチした最初の文字列 "ab" >>> "abc" =~ "(a|b)" :: Int -- マッチした回数 2 >>> "abc" =~ "(a|b)" :: [String] -- マッチした全ての文字列 ["a", "b"]
これはほんの序の口です。タプルなども活用すれば、誇張でもなんでもなくマッチングに関するあらゆる情報を手に入れることができます。