Shoeisha Technology Media

CodeZine(コードジン)

特集ページ一覧

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

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

  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加
2008/11/26 14:00

 正規表現は、特に文字列操作が中心となるWEB分野におけるプログラミングにおいて、なくてはならない重要な機能です。本稿では正規表現を解釈するエンジンを実際に実装し、正規表現エンジンがどのように動いているのかを解説します。第4回は、各正規表現の演算がどのようにNFAで表現されるかを解説し、この構文木をInterpreterパターンに対応させます。

目次

はじめに

 こんにちは。hirataraです。

 前回は、正規表現文字列をコンパイルし、構文木を作成する部分までを実装しました。今回は各正規表現の演算がどのようにNFAで表現されるかを解説し、この構文木をInterpreterパターンに対応させます。

対象読者

  • 正規表現をもっと知りたい方
  • 情報科学分野に興味がある方
  • 正規表現エンジンを実装する必要がある方

NFA変換のための道具作り

 前回の記事により、入力文字列から構文解析を終えた構文木を作ることができました。今手にしている構文木は、例えば以下のような物です。

a|(bc)*の構文木(図)(再掲)
構文木
a|(bc)*の構文木(コード)(再掲)
Union(
    Character('a'), 
    Star(
        Concat(
            Character('b'), 
            Character('c')
        ) 
    ) 
)

 次のステップでは、この構文木がInterpreterパターンに対応するよう、各ノードにassembleメソッドを実装します。ツリーを潜りながらこのメソッドを再帰的に呼ぶことで、NFAへの変換を実現します。

 実装に入る前に、まずは組み立てに必要な道具を揃えましょう。各ノードから共通して使われるクラスである、ContextクラスとNFAFragmentクラスを導入します。

Contextクラス

 Contextクラスは、NFAの変換時に共有する情報のコンテナです。NFAを作成するには、状態を表す整数値を一意に生成する必要があります。そこで、Contextオブジェクト内の_state_countフィールドに整数値を保持し、generate_stateメソッドでカウントアップしながら一意の値を生成します。

Contextクラス
class Context(object):
    def __init__(self):
        self._state_count = 0

    def new_state(self):
        self._state_count += 1
        return self._state_count

NFAFragmentクラス

 NFAFragmentは、NFAの構成部品となるクラスです。NFAの一部分を表現しており、自由に組み合わせて繋げられる部品です。また、buildメソッドを呼ぶことで、第2回で実装したNondeterministicFiniteAutomatonオブジェクトに変換することが可能です。

 以後の説明では、以下の図をNFAFragmentインスタンスのイメージとして利用します。

フラグメント
フラグメント

 四角で囲まれている部分がNFAFragmentを表します。外から矢印が向いている丸が初期状態で、二重丸で示されているのが受理状態です。初期状態は一つですが、受理状態は複数存在しうるので、図中では2つ書いています。その他の状態の丸や遷移の矢印は、この表記においては省略しています。

コンストラクタとフィールド定義

 以下がNFAFragmentが持つフィールドです。

NFAFragmentクラス(1)
class NFAFragment(object):
    def __init__(self):
        self.start   = None  # 整数型
        self.accepts = None  # frozenset型
        self.map     = dict()

 NondeterministicFiniteAutomatonクラスと同様に、初期状態を表すstartと受理状態の集合を表すacceptsをフィールドとして持っています。NFAを表すにはあともう一つ、遷移関数が必要でした。NFABuilderはNFAの組み立てに使う部品なので、自由に変更をしやすいことが求められます。そこで、変更をしにくいfunction型としてではなく、代わりに変更が容易なdict型を利用して遷移関数を表します。self.mapが、この遷移関数に該当します。

 self.mapは、(状態, 入力文字)のタプルをキーとし、次に遷移する状態の集合を値として持ちます。これはちょうどNFAの遷移関数の引数と戻り値と一致する定義になってますので、self.mapnfa.transitionの関数の形に変更するのは簡単です。

フラグメントの演算

 次に、フラグメントの組み立てに必要なメソッドを作ります。

 まずは、connectメソッドです。このメソッドは、2つの状態from_toを受け取り、文字charによってこの2つの状態を接続します。もっと具体的に言うと、フラグメントの遷移関数に、from_からcharによってtoへ遷移する遷移を付け加える、と言うことです。

 遷移関数は dict型のmapフィールドによって表現されていますので、ここに該当する遷移を表すエントリーを追加することで遷移矢印の追加を実現できます。

NFAFragmentクラス(2)
    def connect(self, from_, char, to):
        slot = self.map.setdefault( (from_, char), set() )
        slot.add(to)

 次に、new_skeltonメソッドですが、このメソッドはフラグメントの新しい骨組みを作るのに使います。このメソッドを呼ぶと、現在のフラグメントと同じ状態と遷移関数を持つフラグメントが生成されます。ただしこのメソッドでは、初期状態(start)と受理状態(accepts)はコピーしませんので、自分で設定する必要があります。

NFAFragmentクラス(3)
    def new_skelton(self):
        # コピーして返す
        new_frag = NFAFragment()
        new_frag.map = deepcopy(self.map)
        return new_frag

 最後に、 特殊メソッドである__or__を定義しています。この定義により、2つのフラグメントfragment1fragment2を、 | 演算子に よってfragment1 | fragment2のように合成することができます。合成されてできる新しいNFAFragmentは、fragment1fragment2の遷移関数を併せた遷移関数を持ちます。ただし、この演算も先ほどのnew_fragmentメソッドと同様に、初期状態と受理状態はコピーしません。

NFAFragmentクラス(4)
    def __or__(self, frag):
        new_frag = self.new_skelton()
        for k, v in frag.map.iteritems():
            new_frag.map[k] = v.copy()

        return new_frag

 この演算を遷移図で考えると、矢印を保持したまま2つのフラグメントを1つの遷移図中に移すと言うことを表します。ただしこの時点ではまだ、2つのフラグメントを結ぶ矢印は存在していません。 | 演算子で合成した後、それぞれのフラグメント間をまたぐ2つの状態に対してconnectメソッドを呼ぶことで、2つのフラグメントを合体させることができます。

フラグメントからNFAを作成

 最後に、組み立て終わってからNFAを作成するメソッドであるbuildメソッド の実装です。

NFAFragmentクラス(5)
    def build(self):
        map_ = self.map
        def transition(state, char):
            return frozenset(map_.get( (state, char), []))

        return nfa.NondeterministicFiniteAutomaton(
            transition,
            self.start,
            self.accepts
            )

 NFAFragmentオブジェクトは、NondeterministicFiniteAutomatonオブジェクトと同様にstartacceptsを持っていますので、これはこのままNondeterministicFiniteAutomatonクラスのコンストラクタへ渡します。遷移関数は、dict型からfunction型に変換する必要があります。これは、self.mapフィールドを内部に保持するtransitionと言う名前のクロージャとして実装しています。中を見てわかるように、引数をそのままmapフィールドのキーとして使い、mapフィールドのバリュー値を戻り値として返却するだけの単純な関数です。


  • ブックマーク
  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • hiratara(ヒラタラ)

    1977年に苫小牧市で生まれる。北海道大学理学部数学科卒。小学生の頃、両親に買い与えられたMZ-2500でプログラミングを始めた。学生時代、CGIの自作に没頭し、それ以降WEB開発の魅力に憑かれる。社会人になっても数学好きは変わらず、専門書を買い集めるのが最近の趣味。 id:hirataraに...

バックナンバー

連載:正規表現エンジンを作ろう
All contents copyright © 2005-2019 Shoeisha Co., Ltd. All rights reserved. ver.1.5