連載最終回では、主にNFAエンジンについて説明しました。鬼車等の正規表現エンジンも記事で紹介したエンジンのようにNFAをバイトコードに変換して処理を行っています*1ので、今回の記事が少しでもソースを読む際の助けになればと思います。
さて、記事中で紹介したregexですが、こいつはキャプチャも対応しています。連載の中では一切キャプチャに触れませんでしたので、どのように行っているのか簡単にソースを追っかけてみましょう。
./tryからキャプチャした値にアクセスするには、第３引数に文字列を渡します。そうすれば、\1〜\9をキャプチャした値に変換したり&をマッチした文字列全体に変換したりしてくれます。
% ./try 'a(.+)(c|b)' 'cbacbacba' '\1,\2,&' 1 \1 \2 cbac,b,acbacb
このキャプチャ機能の呼び出しはregsub.c内にありますが、こいつは単に文字列を置換してるだけで面白いことは何もしてません。
実際のキャプチャはregexp.cの regexec() で行います。regexec()はマッチの実行部でして、コンパイル時にはキャプチャに関しては何も準備していません*2。
n個目のかっこによるキャプチャの結果は、regexp.startp[n]からregexp.endp[n]までの文字列として記録されます。(startp[n]とendp[n]は入力文字列中のどれか１文字へのポインタ)。この正規表現のオペコードには括弧に対応したOPENnとCLOSEn*3がありました。ですので、実装としてはOPENnの処理時にstartp[n]を記録、CLOSEnの処理時にendp[n]を記録するだけとなります。
ところで、バックトラックとの関係はどうなるんでしょう？ ソースを読むと、バックトラックをしてる部分*4ではstartpやendpを触っていません。なぜバックトラックを気にしていないかと言うと、startpやendpの格納タイミングをマッチが確定するまで遅らせているからです。このNFAエンジンはBRANCHを再帰呼び出しで表しており、ENDに行き着けば成功が確定し、1が呼び出しの根元まで一気にreturnされてきます。OPENnやCLOSEnではこの成功時の1のreturnの連鎖に割り込むため、分岐していなくても再帰呼び出しを行っています。そして再帰呼び出しで0が返ってきた時は何もせずバックトラックを待ち、1が返ってきた時にだけstartpやendpをセットします。
static int /* 0 failure, 1 success */ regmatch(ep, prog) register struct exec *ep; char *prog; { /* ...... 思いっきり略 ........ */ case OPEN+1: case OPEN+2: case OPEN+3: case OPEN+4: case OPEN+5: case OPEN+6: case OPEN+7: case OPEN+8: case OPEN+9: { register const int no = OP(scan) - OPEN; register char *const input = ep->reginput; if (regmatch(ep, next)) { /* * Don't set startp if some later * invocation of the same parentheses * already has. */ if (ep->regstartp[no] == NULL) ep->regstartp[no] = input; return(1); } else return(0); break; } /* ...... 思いっきり略 ........ */ case END: return(1); /* Success! */ break; /* ...... 思いっきり略 ........ */ }
ここで注意が必要なのは、returnのタイミングでキャプチャするため、入力文字列の後方のキャプチャほど先に実行されると言うことです。具体的には、OPEN9(startp[9])→OPEN8(startp[8])→OPEN7(startp[7])→ ... →OPEN1(startp[1]) と言う順で文字列の格納処理が実行されます。ここで困るのは、キャプチャ部分が繰り返される場合です。「./try '(.)+' 'abc' '\1'」を実行した場合、最後にキャプチャされるcが表示されるのが自然ですが、逆順でキャプチャが実行されるために'a'が最後に保存されてしまいます。これを防ぐため、先にキャプチャされたものを優先とするコードが OPENn や CLOSEn の処理に含まれています。
なお、キャプチャはバックトラックにより巻き戻りの影響は受けませんが、部分文字列を変更する時は初期化せねばなりません。この処理はregtry関数内にあります。
stp = prog->startp; enp = prog->endp; for (i = NSUBEXP; i > 0; i--) { *stp++ = NULL; *enp++ = NULL; }
