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

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

各ノードの実装

　では、構文木の各ノードのassembleメソッドを実装し、正規表現をNFAに変換する部分を作ります。Character、Union、Concat、Starクラスについて、一つずつ変換の方法を説明します。

　これらの４つのノードはInterpreterパターンで実装します。どのノードもassembleメソッドを持っており、NFAFragmentの作成の一端を担っています。下位のノードが存在する場合は、下位のノードのassembleメソッドを呼んでNFAFragmentを作ってもらい、得られたフラグメントに自分のノードが表す演算を施して上位に返却します。このように互いのノードが協調し、再帰的にNFAを組み立てます。

Characterクラス

　Characterクラスは、1文字の正規表現を表します。例えば、 Character('a')で表されるノードは、'a'一文字にマッチする正規表現を表します。この正規表現を表すNFAは、以下のように作ることができます。

Characterノードを表すNFA

　説明するまでもなく、初期状態から 'a' が入力されると受理状態（二重丸）に遷移しますので、 'a' はこのNFAに受理されます。また、他の文字の遷移はないので、 'a' 以外の１文字は受け付けません。さらに、 'aa' のように 'a' の後にさらに入力があると、受理状態からの遷移先がないために受理状態にとどまることができず、これもまた受理されません。なので、このNFAは 'a' 一文字の文字列だけを受理します。

　この図を元に、フラグメントを作りましょう。黄色い枠が、作るべきフラグメントです。赤で書いている部分が、新しく作成しなければならない部分です。図から、2つの状態とその状態間の 'a' による遷移を作らなければいけないことが分かると思います。実装は、この図に忠実に行います。

Characterノード

class Character(object):
    def __init__(self, char):
        self.char = char

    def assemble(self, context):
        frag = NFAFragment()
        s1 = context.new_state()
        s2 = context.new_state()
        frag.connect(s1, self.char, s2)

        frag.start = s1
        frag.accepts = frozenset([s2])

        return frag

　assembleメソッドを見ると、新しいフラグメントを作り、新しい状態を2つ作成してから、互いにこのCharacterノードが表す文字列である self.charで繋いでいます。図から、初期状態は遷移元の状態であるs1、受理状態はs2となります。受理状態は複数あり、集合として表現されることに気をつけて下さい。frozensetでラップする必要があります。

Unionクラス

　Unionクラスは、和集合演算を表します。Union(A, B)と言うノードは、 A|B という | で結ばれた正規表現を表します。この、 | 演算をNFAで構築すると以下のようになります。

Unionノードを表すNFA

　縦に2つ並んでいる四角が、正規表現Aから作られたフラグメントと正規表現Bから作られたフラグメントです。図中のεは空文字（''）を表します。赤い部分が追加された部分で、新しい状態が一つと、その状態から空文字（''）で2つのフラグメントに遷移する矢印が追加されていることがわかります。

　このNFAが | 演算をきちんと表しているか、ちょっと検証してみましょう。開始状態におかれたこのNFAは、いきなり空文字によって2つのフラグメントに遷移します。この遷移の際、入力されたのはあくまでも空文字列なので、入力文字はまだ１文字も読みまれずにそのまま残っていることがポイントです。これにより、それぞれのフラグメントには、大本のNFAに入力されたのと同じ入力文字が入力されることになります。ちょうど、2つのフラグメントが同時に入力された文字列の判定を進めるようなイメージです。

　NFAでは、されうる遷移のうちいずれかが受理状態に辿り着けばその文字列は受理されたことになります。つまり、フラグメントAで受理状態に着いても、フラグメントBで受理状態に着いても、その文字列は受理されたことになります。これは、正規表現Aか正規表現Bのいずれかにマッチする文字列が受理されることを意味します。よって、 | 演算の定義を満たしていることがわかります。

　それでは、実装を見てみます。

Unionノード

class Union(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

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

        frag.start = s
        frag.accepts = frag1.accepts | frag2.accepts

        return frag

　| 演算は２項演算なので、Unionノードはoperand1とoperand2の二つのノードを保持しています。この2つのノードに対してassembleを呼ぶことで、和集合演算の対象とすべきフラグメントが得られます。これを、frag1とfrag2としています。

　まず、フラグメントの骨組みを作るために、frag1とfrag2を合成してfragを作ります。ちょうど、黄色い四角にフラグメントを2つ置いた状態だと思って下さい。ここに、図を見ながら必要な要素を追加します。まず、新しい状態sを追加し、そこから空文字でそれぞれのフラグメントの開始状態（frag1とfrag2）に接続をしています。

　最後に、図を参考にして開始状態と受理状態をセットします。開始状態は追加した新しい状態s、受理状態は双方のフラグメントの和集合となることがわかります。