F#に入門したので正規表現エンジンを書いてみた

『F#を知ってほしい』を読んでF#に興味が湧いてきたので、F#を始めてみた。チュートリアルをやるだけだと面白くないので、手頃な習作として正規表現エンジンを作りながらF#の機能を学んでみることにした。

作るもの

ごく簡単な正規表現エンジンを作る。使えるメタ文字は以下の４つのみとする。

• . 任意の一文字にマッチ
• * 0回以上の繰り返しにマッチ
• | 左右どちらかにマッチ
• () グルーピング

効率は一切考えない。計算に時間がかかってもいいし、メモリを大量に使ってもいい。

ファーストステップ

正規表現を表す型 Pattern を書いていく。最初から完全なものを作るのは大変なので、まずは . か特定の一文字（例えば a) を表すものを定義する。

type Pattern =
    | Char of char
    | AnyChar

Pattern は判別共用体として定義される。正規表現 . は AnyChar として表現され、正規表現 a は Char 'a' と表現される。

次に与えられた文字列から Pattern にマッチする部分を取り出す関数を書こう。任意の場所にマッチさせる関数を考えるのは大変なので、文字列の先頭から始まる部分文字列 にマッチする場合のみに限定して考える。また、一般に正規表現にマッチする部分は複数個あるので、戻り値はひとつの値ではなく、値の列になる。

また、戻り値として部分文字列そのものを返す必要はない。先頭から始まる部分文字列であることはわかっているのだから、部分文字列の長さだけ返せば情報としては十分だ。

したがって、マッチ関数のシグネチャは以下のようになる。

// s の先頭から始まる部分文字列の中で pattern にマッチするものの長さを返す
let matchLengths (pattern: Pattern) (s: string) : seq<int> =
    ...

seq という見慣れないものが出てきたが、これは C# でいうところの IEnumerable だ。IEnumerable があるということは yield もある。後で出てくるのでお楽しみに。

では関数本体を書いていこう。

let matchLengths (pattern: Pattern) (s: string) : seq<int> =
    match pattern with
    | Char ch ->
        if s.StartsWith ch then seq [ 1 ] else Seq.empty
    | AnyChar ->
        if s <> "" then seq [ 1 ] else Seq.empty

今のところ Char と AnyChar しかないのですごく簡単だ。Char の場合、s の先頭が所定の文字で始まっているならば、長さ１の文字列にマッチしたことになるので、列 [ 1 ] を返す。そうでないなら何にもマッチしないので Seq.empty を返す。AnyChar の場合、空文字列でなければ長さ１の文字列にマッチする。空文字列であれば何にもマッチしない。（等しくないことを判定する演算子は <> らしい)

（ところで、何故かこの関数は REPL ではコンパイルできなかった。s.StartsWith ch の部分で型が合わないと言われてしまう。REPL ではない普通のコンパイルではちゃんとコンパイルできた。s.StartsWith がオーバーロードされていることと関係がありそうな気がするがよくわからない。）

matchLengths を試してみよう。

matchLengths (Char 'a') "a"
|> Seq.toList
|> printfn "%A" // [1] が出力される

matchLengths (Char 'a') "b"
|> Seq.toList
|> printfn "%A" // [] が出力される

無事期待通りの結果になった。|> はパイプ演算子というらしい。これは左辺の値を右辺の関数に渡す演算子で、これを使うと Ruby のメソッドチェインのような雰囲気でコードを書くことができる。

Alternation

次に | を含む正規表現を使えるようにしよう。Pattern の定義を以下のように拡張する。

type Pattern =
    | Char of char
    | AnyChar
    | Alter of Pattern * Pattern

Alter は Pattern を２つ取るような再帰的な定義になっている。

Alter lhs rhs にマッチする文字列 s の部分文字列は、lhs にマッチする部分文字列と rhs にマッチする部分文字列の和集合だ。これを matchLengths に実装すると以下のようになる。

let rec matchLengths (pattern: Pattern) (s: string) : seq<int> =
    match pattern with
    | Char ch ->
        if s.StartsWith ch then seq [ 1 ] else Seq.empty
    | AnyChar ->
        if s <> "" then seq [ 1 ] else Seq.empty
    | Alter (lhs, rhs) ->
        seq {
            yield! matchLengths lhs s
            yield! matchLengths rhs s
        }

seq { ... } はコンピュテーション式と呼ばれるものらしい。（私はまだコンピュテーション式をいまいちよく理解できていない）

seq { ... } の中では yield や yield! といった構文が使える。例えば seq { yield 1; yield 2 } を評価すると seq [1; 2] が返る。

一方、yield! は yield と似ているが一回 flatten する。例えば

let s1 = seq [1; 2]
let s2 = seq [3; 4]
seq { yield! s1; yield! s2 }

は seq [1; 2; 3; 4] を返す。

したがって、

seq {
    yield! matchLengths lhs s
    yield! matchLengths rhs s
}

は lhs にマッチした部分文字列と rhs にマッチした部分文字列を連結した列になる。

また、seq { ... } は C# の generator と同じように、値が要求されるまで計算が遅延させられる。これを使うと無限シーケンスを定義したりもできるらしい。（今回の例では有限のシーケンスしか登場しない）

Concatenation と Repeat

残るは連結と*だ。さらに空文字列にマッチするパターンも必要だ。Pattern の定義に Zero, Repeat, Concat を加えよう。

type Pattern =
    | Zero
    | Char of char
    | AnyChar
    | Alter of Pattern * Pattern
    | Repeat of Pattern
    | Concat of Pattern * Pattern

matchLengths の実装は以下のようになる。Repeat は空文字列にマッチする場合の処理が微妙にいやらしい。それ以外は結構直観的な実装になっていると思う。

let rec matchLengths (pattern: Pattern) (s: string) : seq<int> =
    match pattern with
    | Zero ->
        seq [ 0 ]
    | Char ch ->
        if s.StartsWith ch then seq [ 1 ] else Seq.empty
    | AnyChar ->
        if s <> "" then seq [ 1 ] else Seq.empty
    | Alter (lhs, rhs) ->
        seq {
            yield! matchLengths lhs s
            yield! matchLengths rhs s
        }
    | Concat (head, tail) ->
        seq {
            for n1 in matchLengths head s do
                for n2 in matchLengths tail (s.Substring n1) do
                    yield n1 + n2
        }
    | Repeat inner ->
        seq {
            for n1 in matchLengths inner s do
                if n1 = 0 then
                    yield 0
                else
                    for n2 in matchLengths pattern (s.Substring n1) do
                        yield n1 + n2
            yield 0
        }

seq { ... } の中では for .. in .. do .. という構文が使える。ネストもできる。この関数では使っていないが、if を使ってフィルタすることもできるらしい。

これで正規表現のマッチャーは完成した。試してみよう。

// <(.*)> を表す Pattern
let p = Concat (Char '<', Concat (Repeat AnyChar, Char '>'))
let s = "<hello>world</hello>"
matchLengths p s
|> Seq.toList
|> printfn "%A"

実行すると [20; 7] が出力された。<hello>world</hello> が20文字で <hello> が7文字なので正しく動いているようだ。やったね

次回コンパイル編？

現状では正規表現を使うためには Pattern を直接組み立てないといけない。これは不便だ。そこで ab*|c.d のような馴染みのある表記から Pattern にコンパイルするコードを書いたので、モチベが続けば次回紹介したい。