ブライアン・カーニハンとロブ・パイクによる 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])の実装と、パターンのコンパイルフェイズ・チェックフェイズの分離をやってみたいと思います。