北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

正規表現エンジンを作ろう(4)

連載も第四回となりました。今回が正規表現エンジンを作る上で一番重要な部分で*1正規表現とNFAの関係を説明しています。結局は当たり前のことしか言ってないんですが、そこはコロンブスの卵でして、知ってるのと知らないのとでは大違いです。

さて、この連載ではNFAをPythonで定義通りに忠実に実装しています。

この連載ではその数学的な概念を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は、以下のような条件を満たす遷移関数しか表現できません:

  1. 各状態からは、1状態にだけしか遷移しない(DFA的)*3
  2. またはε遷移の場合、遷移先は必ず2つ(2つに枝分かれ)*4

第四回で紹介している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への遷移を先に試行するようにすると繰り返しが優先されるため、最長一致的な動作となります。

*1:DFAエンジンに関して言えば、次回の部分集合構成法も超重要です。

*2:正確に言うと分岐するからツリー?

*3:遷移図で言えば、各状態から矢印は1本だけ出ている

*4:この条件がなければDFAになるが、選択演算と繰り返し演算がある限り3.の条件からは逃げられない。

*5:この考えによると、1本道と2分岐があればNFAを実現可能と言うことになる。この見方はNFAエンジンでNFAを「直列なバイトコード」として表現する際に役立つ。