連載も第四回となりました。今回が正規表現エンジンを作る上で一番重要な部分で*1、正規表現とNFAの関係を説明しています。結局は当たり前のことしか言ってないんですが、そこはコロンブスの卵でして、知ってるのと知らないのとでは大違いです。
さて、この連載ではNFAをPythonで定義通りに忠実に実装しています。
この実装は概念を理解するのには有用なのですが、実用的な正規表現エンジンとしては明らかにオーバースペックです。Regular Expression Matching Can Be Simple And FastでのC++での実装を見ながら、現実的なNFA表現の落としどころを簡単に見てみましょう。
C++実装のNFAの説明
C++の実装では、NFAを構造体のリスト構造としています。定義はこうです。
struct State { int c; State *out; State *out1; int lastlist; };
この実装では、状態は整数値ではなく単方向リスト*2を形成する構造体の1要素です。そして、各構造体のcとoutとout1が遷移関数を表します。これは概念的には、以下のような遷移関数を意味します。
// s: 現在の状態, c: 入力文字, ret: 出力(状態の集合) void transition(State *s, char c, List *ret){ if(s->c == Split && c == '\0'){ // ε遷移 ret->s[ret->n++] = s->out; ret->s[ret->n++] = s->out1; }else if(s->c == (int)c){ // 通常文字での遷移 ret->s[ret->n++] = s->out; } return; }
正規表現エンジンに必要な最低限の遷移関数
今回の連載のPython実装と比べて大きく違う部分は、この遷移関数の部分です。連載の実装では汎用的なNFAを表現できるように、遷移関数にはどんな関数も使用可能にしていました。しかし、実際正規表現エンジンを作ることだけ考えれば、C++の実装で十分です。この実装のNFAは、以下のような条件を満たす遷移関数しか表現できません：
第四回で紹介しているNFA構成法の図を見て考えてみるとわかりますが、これだけあれば正規表現を表すNFAは構成できてしまいます。まず、文字による分岐ですが、これが登場するのはCharacterノードだけです。Characterノードの図を見ると、矢印は一つだけなので、文字も遷移先も1つだけです。
そして、εでの枝分かれですが、これは連結演算の時は1つ(枝分かれなし)、選択演算のときは2つです。繰り返し演算の図も枝分かれなしに見えますが、繰り返し演算の場合は受理状態からε遷移をしています。受理状態は連結演算においてε遷移を加えられる可能性がありますので、最大で1+1 = 2個に枝分かれします。
と言うことで、εでの枝分かれは1つか2つと言うことになりましたが、εでの枝分かれが一つで間に受理状態をはさまない場合は、ε遷移を省略できてしまいます。1 -('a')→ 2 -('')→ 3 は、1 -('a')→ 3 と一緒です。よって、εでの枝分かれは2つだけです。
以上をまとめると、正規表現を表すNFAに関しては、1文字によって別の状態にDFA的に遷移するか、εで2つに枝分かれするかだけで表現できるということになります。*5
最長一致の実現
C++実装ではε遷移を outとout1 で表しましたが、これにはもう一つ重要な利点があります。連載のNFAでは、数学の概念に従って遷移先を集合としました。よって、枝分かれの順序付けがありません。一方、C++の実装ではoutが1番目で、out1が2番目と言うように遷移先に優先順位がつけられます。これにより、バックトラックでの最長一致の原則が実現できるようになります。
具体的には、繰り返し演算において、繰り返しを行う遷移がoutに、行わない遷移がout1に入るようにします。そしてNFAの評価時に、outへの遷移を先に試行するようにすると繰り返しが優先されるため、最長一致的な動作となります。
