Help us understand the problem. What is going on with this article?

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

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

作るもの

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

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

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

ファーストステップ

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

type Pattern =
    | Char of char
    | AnyChar

Pattern判別共用体として定義される。正規表現 .AnyChar として表現され、正規表現 aChar '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

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

(ところで、何故かこの関数は 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

AlterPattern を2つ取るような再帰的な定義になっている。

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 { ... } の中では yieldyield! といった構文が使える。例えば 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文字なので正しく動いているようだ。やったね :tada:

次回コンパイル編?

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした