正規表現エンジンを作ろう （4）

正規表現の構文木からNFAを作る

Concatクラス

　Concatクラスは、連結を表します。つまり、単に文字を並べて書いた物であり、Concat(A, B)と言うノードは、ABと言う正規表現になります。

　Concatノードを表すNFAは、以下のように構築できます。

Concatノードを表すNFA

　図の見方はもう分かりますね？ 一つ注意が必要なのは、左側のフラグメントで、受理状態だった状態が受理状態ではなくなっていることです。代わりに、受理状態だった状態から後半のフラグメントの開始状態へ、空文字（""）による遷移を追加する必要があります。

　では、この図がきちんと連結演算を示しているか見てみましょう。入力された文字列は、そのまま前半のフラグメントで評価されます。ところが、前半のフラグメントの受理状態は通常の状態になってますので、前半のフラグメントに受理されていた文字列はこのNFAには受理されません。代わりに、空文字で（つまり、入力文字を変化させずに）後半のフラグメントの開始状態にジャンプします。そして、残りの文字は後半のフラグメントによって受理されるかを判定されます。

　以上をまとめると、まず前半のフラグメントで受理され、残りの文字列が後半のフラグメントで受理されるような文字列がこのNFAに受理されます。つまり、(正規表現A)(正規表現B)と連結した正規表現と等価のNFAとなっています。

　では、Concatクラスの実装です。

Concatノード

class Concat(object):
    def __init__(self, operand1, operand2):
        self.operand1 = operand1
        self.operand2 = operand2

    def assemble(self, context):
        frag1 = self.operand1.assemble(context)
        frag2 = self.operand2.assemble(context)
        frag = frag1 | frag2

        for state in frag1.accepts:
            frag.connect(state, "", frag2.start)

        frag.start   = frag1.start
        frag.accepts = frag2.accepts

        return frag

　Unionクラスと同様に２項演算なので、operand1とoperand2を持っています。これらをassembleしてfrag1とfrag2を作り、合成することで大本となるフラグメント（frag）を作ります。その後、赤い部分の追加を行います。全てのfrag1の受理状態から、frag2の初期状態へ空文字列（""）で遷移するようにconnectしています。

　最後に、図より、初期状態はfrag1の初期状態、受理状態はfrag2の受理状態となります。

Starクラス

　Starクラスは、繰り返しを表します。Star(A)と言うノードは、A*です。つまり、正規表現Aを0個以上並べた文字列にマッチします。繰り返し演算は、NFAでは以下のように構築します。

Starノードを表すNFA

　この演算は1項演算なので、関連するフラグメントは1つだけです。赤い部分を見てみると、初期状態となる受理状態を一個加え、そこからフラグメントに空文字で遷移させてます。また、フラグメントの受理状態からフラグメントの初期状態に戻る、ループを表す空文字列での遷移も追加されてます。

　この構成で繰り返し演算を表現できていることを確かめましょう。まず、初期状態が受理状態なので、「0回の繰り返し」は受理されます。そして、フラグメントの受理状態に辿り着くとすぐに空文字で初期状態に戻されるので、このフラグメントに受理される内容を1回以上繰り返したものも全て受理されます。

　実装は以下のようになります。

Starノード

class Star(object):
    def __init__(self, operand):
        self.operand = operand

    def assemble(self, context):
        frag_orig = self.operand.assemble(context)
        frag = frag_orig.new_skelton()

        for state in frag_orig.accepts:
            frag.connect(state, "", frag_orig.start)

        s = context.new_state()
        frag.connect(s, "", frag_orig.start)

        frag.start = s
        frag.accepts = frag_orig.accepts | frozenset([s])

        return frag

　1項演算子なので、operandは一つだけ保持します。operandをassembleして得られるfrag_origを元に、骨組みとなるフラグメント（frag）を作ります。そして、まず、フラグメントの受理状態から初期状態に空文字列での遷移を加えます。その後、新しい状態sを加え、ここからフラグメントの初期状態へ遷移を追加します。

　図より、初期状態は追加した状態のs、受理状態は、フラグメントの受理状態と加えた状態sを併せたものとなります。

　以上でNFAの作成は終わりです。このようにフラグメントを再帰的に合体させていくことで、複雑な正規表現であってもルールに従ってNFAに変換することができます。

NFAの構成方法への工夫

　今回のNFAの構成は、『計算理論の基礎』（Michael Sipser著）の書籍内のものを利用しました。しかし、これらの正規表現と等価なNFAは他にもありますので、いつも今回の構成とまったく同じになると言うわけではありません。構成方法によっては、実装が容易になったり、NFAの状態遷移数が減って実行効率が上がったりします。

　『Regular Expression Matching Can Be Simple And Fast 』（Russ Cox著）では、今回の3演算の他に ? や + などの演算に該当するNFAも作っています。正規表現"a+"は、前述したように"aa*"と書き換えられますが、直接この記事のNFA構成を使った方が状態数が減って効率的になります。

　また、書籍『COMPILERS』（AHO,LAM,SETHI,ULLMAN 著）の中ではε遷移を利用して、受理状態が複数ではなく必ず1つだけになるようにまとめています。この構成により、集合の概念を扱いにくいC言語などでも、フラグメントの接続が容易にできるようになります。

構文木からNFAを作る

　ノードが全て実装できましたので、構文木をNFAに変換する部分を実装します。この部分は、すでに前回Parserクラスの説明で実装していました。

Parserクラス(6)(再掲)

    def expression(self):
        # expression -> subexpr EOF
        node     = self.subexpr()
        self.match(Token.EOF)

        # 構文木を実行し、NFAを作る
        context  = Context()
        fragment = node.assemble(context)
        return fragment.build()

　expressionメソッドは、正規表現をコンパイルして構文木（node）にします。構文木が完成したら、Contextを生成してnodeのassembleメソッドを呼び出し、NFA変換を実行させます。NFAはフラグメントの形で生成されて戻ってきますので、buildメソッドによってNondeterministicFiniteAutomatonオブジェクトに変換してから、戻りとして返却します。

まとめ

　今回は、以下の内容を説明しました。

• 構文木からNFAを作る
  • NFAFragmentクラス
  • 各演算に対するNFAの構築法

　次回はNFAをDFAに変換する部分集合構成法を解説し、今まで作った部品を組み合わせて正規表現エンジンを完成させます。

参考資料

1. 『計算理論の基礎』Michael Sipser 著、渡辺治・太田和夫 訳、共立出版、2000年4月
2. 『Compilers Principles, Techniques, & Tools』 Alfred V. Aho・Monica S. Lam・Ravi Sethi・Jeffrey D. Ullman 著、Addison-Wesley、2007年10月
3. Russ Cox『Regular Expression Matching Can Be Simple And Fast』