40行以内で正規表現エンジンを構築

先日ある記事に遭遇しました。この記事には、Rob PikeがC言語で実装した基本的な正規表現エンジンについて書かれていました。彼のコードをJavaScriptに変換し、さらに誰もが正規表現エンジンを自力で構築できるようにテストコードを追加しました。GitHubレポジトリはこちらです。このブログでは、この実装をウォークスルーして見ていきたいと思います。

問題

この正規表現エンジンは次の構文をサポートします。

最終目標は、最小限のコードで正規表現ユースケースの大部分をカバーできるくらい十分堅牢な構文を提供することです。

1文字と一致させる

まずはじめに、1文字のパターンと1文字で構成される文字列を引数に取り、一致するかしないかを示すブール値を返す関数を作成してみます。1文字のパターンである.はワイルドカードとされ、任意の文字リテラルと一致します。

下記のようなかんじです

matchOne('a', 'a') -> true
matchOne('.', 'z') -> true
matchOne('', 'h') -> true
matchOne('a', 'b') -> false
matchOne('p', '') -> false

function matchOne(pattern, text) {
  if (!pattern) return true // 任意テキストが空パターンと一致する
  if (!text) return false   // パターンは定義されていてもテキストが空の場合、一致はしない
  if (pattern === ".") return true // 任意入力したテキストがワイルドカードと一致する
  return pattern === text
}

同じ長さの文字列と一致させる

次により長いパターンや文字列のサポートを追加していきます。ひとまずここでは、同じ長さの2組のパターン・テキストだけを考えます。解決策が再帰にとても自然に役立つことをたまたま私は知っているので、ここではそれを利用することにします。パターン・テキストの組み合わせから連続する文字のペアに対してmatchOneを繰り返し実行していきます。

function match(pattern, text) {
  if (pattern === "") return true  // ここでのベースケースは、もしパターンが空だった場合、任意入力したテキストは一致とする
  else return matchOne(pattern[0], text[0]) && match(pattern.slice(1), text.slice(1))
}

上記のコードは、パターンとテキストのペアの文字から文字へと実行していきます。最初にpattern[0]とtext[0]を比較し、次にpattern[1]とtext[1]の比較、pattern[i]とtext[i]の比較へと続き、i === pattern.length - 1まで継続します。もし一致がない場合、パターンとテキストが一致しないことが分かります。

例で見てみましょう。match('a.c', 'abc')を呼び出して、matchOne('a', 'a') && match('.c', 'bc')が得られたとします。

関数の検証を継続すると、matchOne('a', 'a') && matchOne('.', 'b') && matchOne('c', 'c') && match("", "")を得ることができます。つまり、true && true && true && trueに等しいことになり、結果は一致するということなります。

＄文字

では、文字列の末尾を一致させる特殊文字$のサポートを追加しましょう。これは単純で、match関数に基本的なケースを一つ追加するだけです。

function match(pattern, text) {
  if (pattern === "") return true
  if (pattern === "$" && text === "") return true
  else return matchOne(pattern[0], text[0]) && match(pattern.slice(1), text.slice(1))
}

^文字

次に文字列の先頭を一致させる特殊文字^のサポートを追加しましょう。ここでsearchという新しい関数を使用することにします。

function search(pattern, text) {
  if (pattern[0] === "^") {
    return match(pattern.slice(1), text)
  }
}

この関数はコードの新しいエントリポイントになります。ここまでは、テキストの始まりの部分のパターンが一致するかを探すだけです。それをパターンの前に^を付与して単に明確化しているだけです。しかし、テキスト中に現れるパターンの場合はどうのようにすればいいのでしょうか。

スタート地点がどこでも一致させる

ここまでの実装では以下の場合にtrueが返されます。

search("^abc", "abc")
search("^abcd", "abcd")

しかし、search("bc", "abcd")に対してはundefinedが返されます。これを、trueが返されるようにしたいのです。

もし、ユーザがテキストの始まりが特定のパターンと一致するよう指定していない場合、テキスト内のあらゆるポイントをスタート地点としたパターンの検索ができるようにしたいですね。これを受けて、パターンが^で始まらない場合は、検索するように実装します。¹

function search(pattern, text) {
  if (pattern[0] === "^") {
    return match(pattern.slice(1), text)
  } else {
    // このコードは、テキストの全てのインデックスに対してmatch(pattern, text.slice(index))を実行。
    // つまり、テキスト全てのスタートポイントに対しパターンの一致を検索。
    return text.split("").some((_, index) => {
      return match(pattern, text.slice(index))
    })
  }
}

？文字

?より前の文字と0個か1個一致するようにします。

以下が例となります

search("ab?c", "ac") -> true
search("ab?c", "abc") -> true
search("a?b?c?", "abc") -> true
search("a?b?c?", "") -> true

まず、matchを変更し、？文字の存在を検出するようにします。そして、それ以外の部分は後程説明するmatchQuestion関数に任せることにしましょう。

function match(pattern, text) {
  if (pattern === "") {
    return true
  } else if (pattern === "$" && text === "") {
    return true
  // pattern[0].ではなくpattern[1]を見ていることに注意。
  // pattern[0]が文字と0個か1個一致する
  } else if (pattern[1] === "?") {
    return matchQuestion(pattern, text)
  } else {
    return matchOne(pattern[0], text[0]) && match(pattern.slice(1), text.slice(1))
  }
}

matchQuestionは下記2つのケースを扱います：

1. ?以前の文字は一致しない。しかし、それ以外のテキスト(?以降の文字全て)がパターンの残りの部分に一致。
2. ?以前の文字が一致、さらに(一致した文字は除く)残りのテキストもパターンの残りの部分に一致。

上記のいずれかが成立した場合、matchQuestionはtrueを返します。

まず1番目のケースを見てみましょう。どのようにすれば、テキストがパターンの_?構文以外の部分と一致すること分かるのでしょうか。どのようにして?以前の文字が0回現れることを確認すればいいのでしょうか。パターンから2文字抜き(1つは?前の1つ目の文字で、もう1つは?)、そしてmatch関数を呼び出します。

function matchQuestion(pattern, text) {
  return match(pattern.slice(2), text);
}

2番目のケースは少し難しくなりますが、前にもやったように既に使用した関数を再び使用します。

function matchQuestion(pattern, text) {
  if (matchOne(pattern[0], text[0]) && match(pattern.slice(2), text.slice(1))) {
    return true;
  } else {
    return match(pattern.slice(2), text);
  }
}

もし、text[0]がpattern[0]と一致し、(matchOneで一致した部分を除いた)残りのテキストが一致すれば成功です。下記のようにコードを書き換えることができます。

function matchQuestion(pattern, text) {
  return (matchOne(pattern[0], text[0]) && match(pattern.slice(2), text.slice(1))) || match(pattern.slice(2), text);
}

この実装の後半のアプローチが私は個人的にお気に入りで、OR演算子によってtrueを返す条件が2種類あることが明示されているところが気に入っています。

*文字

*以前の文字が0回あるいは複数回一致するようにします。

下記が全てtrueを返すように実装してみます。

search("a", "")
search("a", "aaaaaaa")
search("a*b", "aaaaaaab")

?文字の時と同様に、match関数内のmatchStar関数に任せます。

function match(pattern, text) {
  if (pattern === "") {
    return true
  } else if (pattern === "$" && text === "") {
    return true
  } else if (pattern[1] === "?") {
    return matchQuestion(pattern, text)
  } else if (pattern[1] === "*") {
    return matchStar(pattern, text)
  } else {
    return matchOne(pattern[0], text[0]) && match(pattern.slice(1), text.slice(1))
  }
}

matchQuestion同様matchStarは、次2つのケースに対応する必要があります。

1. *以前の文字は一致しない。しかし、それ以外のテキスト(*以降の文字全て)がパターンの残りの部分に一致。
2. *以前の文字が一致、さらに(一致した文字を除いた)残りのテキストもパターンの残りの部分に一致。

結果が一致になるケースが2つあるため(0個一致する場合と、複数一致する場合があります)、今回もOR演算子を使ってmatchStarを構成することができそうです。さらに、ケース1においては、matchStarはmatchQuestionの場合と全く同じで、match(pattern.slice(2), text)を使って同様に実装できます。つまり、ここで必要なのは、ケース2を満たす式を立てることだけです。

function matchStar(pattern, text) {
  return (matchOne(pattern[0], text[0]) && match(pattern, text.slice(1))) || match(pattern.slice(2), text);
}

リファクタリング

ここらへんでsearchをシンプルにしつつスマートな実装にします。Peter Norvigの授業で学んだ技を使用します。

function search(pattern, text) {
  if (pattern[0] === "^") {
    return match(pattern.slice(1), text)
  } else {
    return match(".*" + pattern, text)
  }
}

*文字を使用すると、パターンが文字列内のどこに現れてもヒットさせることができるようになります。なお先頭に.*を付け加えた場合、パターンの前に現れる任意の数の任意の文字を一致させることが可能です。

まとめ

これだけ洗練され一般化されたプログラムを簡素で美しいコードに表現できるのは素晴らしいことです。ソースコードの全貌はこのGitHubレポジトリをご覧ください。

この正規表現エンジンのファジングについては追加投稿があるので、こちらをお読みください。

注釈: