ロブ・パイクの正規表現マッチャを拡張する

ブライアン・カーニハンとロブ・パイクによる The practice of programming (邦題:プログラミング作法) に掲載されている正規表現マッチャを拡張したいと思います。

※ O’Reilly から出版された Beautiful Code: Leading Programmers Explain How They Think (邦題: ビューティフル コード)にも掲載されており、該当部分の全文は公式サイトで読むことができます。

前提

元の正規表現マッチャは、以下の表現をサポートしています。

• 任意文字指定子: .
• くりかえし指定子: *
• 位置指定子: ^$

まず、正規表現マッチャを評価する為に main() 関数を追加しました。

#include <stdio.h>

/* match: テキスト中の任意位置にある正規表現を探索 */
int match(char *regexp, char *text)
{
  if (regexp[0] == '^')
    return matchhere(regexp+1, text);
  do { /* 文字列が空の場合でも調べる必要あり */
    if (matchhere(regexp, text))
      return 1;
  } while (text++ != '\0');
  return 0;
}
/* matchhere: テキストの先頭位置にある正規表現のマッチ */
int matchhere(char *regexp, char *text)
{
  if (regexp[0] == '\0')
    return 1;
  if (regexp[1] == '')
    return matchstar(regexp[0], regexp+2, text);
  if (regexp[0] == '$' && regexp[1] == '\0')
    return text == '\0';
  if (text!='\0' && (regexp[0]=='.' || regexp[0]==text))
    return matchhere(regexp+1, text+1);
  return 0;
}
/* matchstar: 「c」型の正規表現をテキストの先頭位置からマッチ */
int matchstar(int c, char *regexp, char *text)
{
  do { /* 「」は「0回以上の繰り返し」であることに注意 */
    if (matchhere(regexp, text))
      return 1;
  } while (text != '\0' && (*text++ == c || c == '.'));
  return 0;
}

int main(int argc, char** argv)
{
  int r;
  if ( argc != 3 ) {
    printf("Too few or many arguments for regex.\n");
    return 2;
  }
  printf("%s\n", (r = match(argv[1], argv[2])) ? "Match" : "No match" );
  return !r;
}

これで、

gcc -o myregex myregex.c

すると、実行バイナリが作成され

./myregex regex-pattern source-string

とタイプする事により、挙動を確認することができます。引数は、シェルによる展開を避ける為、クォートで囲むことをオススメします。

拡張1: 「c+(直前のパターンが1回以上くりかえす)」表現を追加する。

上の37行目にあるコメント『「*」は「0回以上の繰り返し」であることに注意』が最大のヒントになります。「+」は1回以上のくりかえしですので、0回でもマッチする do ～ while 文による検索ではなく、while 文で実現すれば良いはずです。

ということで、次の関数を追加しました。

/* matchcorss: 「c+」型の正規表現をテキストの先頭位置からマッチ */
int matchcross(int c, char *regexp, char *text)
{
  while (text != '\0' && (*text++ == c || c == '.')) {
    if (matchhere(regexp, text))
      return 1;
  }
  return 0;
}

1回もマッチすることがなければ、return 0をして検索を終了します。また、呼び出し元となる matchhere() 関数を次のように変更します。

/* matchhere: テキストの先頭位置にある正規表現のマッチ */
int matchhere(char *regexp, char *text)
{
  if (regexp[0] == '\0')
    return 1;
  if (regexp[1] == '')
    return matchstar(regexp[0], regexp+2, text);
  /* ここから */
  if (regexp[1] == '+')
    return matchcross(regexp[0], regexp+2, text);
  /* ここまで追加 */
  /* … */

matchstar() を呼び出しているところと同じように、regexp[1] が + だった場合、matchcross() を呼び出しています。

これを実行してみると

$ ./myregex '^co+l' 'cool'
Match

$ ./myregex '^c+l' 'cool'
No Match

ちゃんと動いているようです。

「c?(直前のパターンが0回もしくは1回)」表現を追加する。

直前のパターンが0回、もしくは1回マッチすればいいので、次のような関数を追加しました。

int matchquestion(int c, char regexp, char *text)
{
  if (text == c)
    text++;
  return matchhere(regexp, text, 0);
}

仮引数は、matchstar() や matchcross() と同じです。ポインタ text が指している場所にある文字が c と同じなら、text をインクリメントします。 同じでない場合は、「0回マッチした」ということですので、ポインタ text はそのままで検索をすすめていきます。

呼び出し元となる matchhere() はこんな感じになりました。

/* matchhere: テキストの先頭位置にある正規表現のマッチ */
int matchhere(char *regexp, char *text)
{
  if (regexp[0] == '\0')
    return 1;
  if (regexp[1] == '')
    return matchstar(regexp[0], regexp+2, text);
  if (regexp[1] == '+')
    return matchcross(regexp[0], regexp+2, text);
  /* ここから */
  if (regexp[1] == '?')
    return matchquestion(regexp[0], regexp+2, text);
  /* ここまで追加 */
  /* … */

くりかえし指定子ですので、おんなじですね。

$ ./myregex 'colour' 'color'
No Match

$ ./myregex 'colou?r' 'color'
Match

$ ./myregex 'colou?r' 'colour'
Match

ちゃんと動いてます。

指定子のエスケープに対応する

正規表現では、文字 * や . そのものを指定したい場合、それぞれ * や . といったバックスラッシュを用いたエスケープを行います。

それに対応します。

考え方としては、エスケープ文字が指定子の前にあれば、その指定子を単なる文字として解釈するわけですが、まずは matchhere() を修正してみましょう。

int matchhere(char *regexp, char *text)
{
  if (regexp[0] == '\0')
    return 1;

  /* 直前がバックスラッシュじゃない場合のみ、指定子として処理する */
  if (regexp[0] != '\\') {
    if (regexp[1] == '*')
      return matchstar(regexp[0], regexp+2, text);
    if (regexp[1] == '+')
      return matchcross(regexp[0], regexp+2, text);
    if (regexp[1] == '?')
      return matchquestion(regexp[0], regexp+2, text);
  }
  else {
    /* バックスラッシュだった場合、regexp をインクリメントして検索を続ける。 */
    return matchhere(regexp+1, text);
  }
  /* ... */

これで、くりかえし指定子のエスケープができるようになりました。さて、問題は次の位置指定子と任意文字のマッチングの部分です。

if (regexp[0] == '$' && regexp[1] == '\0')
  return *text == '\0';

if (text!='\0' && (regexp[0]=='.' || regexp[0]==text))
  return matchhere(regexp+1, text+1);

くりかえし指定子の処理突入部の場合、「regexp[0]が直前のパターン、regexp[1]が指定子」というペアでしたが、これらの文では、regexp[0]が指定子であり、直前のパターンを判断する手立てがありません。

直前のパターンがエスケープ文字かどうか、つまり、matchehere() が呼び出された時点で、エスケープされているのかどうかを知ることができればいいわけです。

matchhere() を次のように変更しました。

/* int matchhere(char *regexp, char *text) */
int matchhere(char *regexp, char *text, int esc)
{
/* … */

第3引数の int esc は、直前でエスケープして呼び出された場合には 0 以外が入るようにします。既存の match()、matchstar()、matchcross()、matchquestion() 内で呼んでいる matchhere() は、全て第3引数を 0 にして呼び出すように修正をします。

さらに、matchhere() を

int matchhere(char *regexp, char *text, int esc)
{
  if (regexp[0] == '\0')
    return 1;

  if (regexp[0] != '\\') {
    if (regexp[1] == '*')
      return matchstar(regexp[0], regexp+2, text);
    if (regexp[1] == '+')
      return matchcross(regexp[0], regexp+2, text);
    if (regexp[1] == '?')
      return matchquestion(regexp[0], regexp+2, text);
  }
  else {
    return matchhere(regexp+1, text + esc, 1); /* エスケープされている事を教える */
  }

  if (!esc && regexp[0] == '$' && regexp[1] == '\n')
    return *text == '\n';

  if (*text!='\n' && ((!esc && regexp[0]=='.') || regexp[0]==*text))
    return matchhere(regexp+1, text+1, 0);

  return 0;
}

のように変更します。条件式のところどころに、esc を差し込んでいます。順に追っていってみます。

15行目の

return matchhere(regexp+1, text + esc, 1);

は、regexp[0]がエスケープ文字だった場合に、第3引数を 1 に設定して matchhere() を呼び出します。また、第2引数の text + esc は、「エスケープされていたら1文字進め、そうでなければ現在のポインタの指す位置から」という意味になります。エスケープされており、かつこの return 文のスコープに入ってきたという事は、パターン「\」が指定されたことになります。エスケープされておらず、この return 文が実行される場合は、「\」以外のパターン「」や「\w」などの場合であり、それぞれ、文字「」「w」として解釈されるようになります。

次に、18行目の

if (!esc && regexp[0] == '$' && regexp[1] == '\0')

ですが、ここは「エスケープされていない$があり、かつパターンの文末」を意味しています。エスケープされていたら、マッチしません。

最後の、21行目

if (text!='\0' && ((!esc && regexp[0]=='.') || regexp[0]==text))

では、パターン「.」を弾いています。

これを試してみると

$ ./myregex '.++.+=.+' '12+34=46′
Match

$ ./myregex '^\abc' '\abc'
No Match

$ ./myregex '^\abc' '\abc'
Match

しっかり動いているようです。

ここまでの機能を盛り込んだソースコード

2つのくりかえし指定子とエスケープを実装した後のコードです。

#include <stdio.h>

/* match: テキスト中の任意位置にある正規表現を探索 */
int match(char *regexp, char *text)
{
  if (regexp[0] == '^')
    return matchhere(regexp+1, text, 0);
  do { / 文字列が空の場合でも調べる必要あり /
    if (matchhere(regexp, text, 0))
      return 1;
  } while (text++ != '\0');
  return 0;
}
/* matchhere: テキストの先頭位置にある正規表現のマッチ */
int matchhere(char *regexp, char *text, int esc)
{
  if (regexp[0] == '\0')
    return 1;

  /* くりかえし */
  if (regexp[0] != '\\') {
    if (regexp[1] == '*')
      return matchstar(regexp[0], regexp+2, text);
    if (regexp[1] == '+')
      return matchcross(regexp[0], regexp+2, text);
    if (regexp[1] == '?')
      return matchquestion(regexp[0], regexp+2, text);
  }
  else {
    return matchhere(regexp+1, text + esc, 1);
  }

  /* 文末 */
  if (!esc && regexp[0] == '$' && regexp[1] == '\n')
    return *text == '\n';

  /* その他、任意文字 */
  if (*text!='\n' && ((!esc && regexp[0]=='.') || regexp[0]==*text))
    return matchhere(regexp+1, text+1, 0);

  return 0;

}
/* matchstar: 「c」型の正規表現をテキストの先頭位置からマッチ */
int matchstar(int c, char *regexp, char *text)
{
  do { /* 「」は「0回以上の繰り返し」であることに注意 */
    if (matchhere(regexp, text, 0))
      return 1;
  } while (text != '\0' && (text++ == c || c == '.'));
  return 0;
}
/* matchcorss: 「c+」型の正規表現をテキストの先頭位置からマッチ */
int matchcross(int c, char *regexp, char *text)
{
  while (text != '\0' && (text++ == c || c == '.')) {
    if (matchhere(regexp, text, 0))
      return 1;
  }
  return 0;
}
/* matchquestion: c? */
int matchquestion(int c, char *regexp, char *text)
{
  if (text == c)
    text++;
  return matchhere(regexp, text, 0);
}

int main(int argc, char** argv)
{
  int r;
  if ( argc != 3 ){
    printf("Too few or many arguments for regex.\n");
    return 2;
  }
  printf("%s\n", (r = match(argv[1], argv[2])) ? "Match" : "No match" );
  return !r;
}

次回は、範囲パターン([a-z])の実装と、パターンのコンパイルフェイズ・チェックフェイズの分離をやってみたいと思います。