SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

正規表現エンジンを作ろう

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

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

  • X ポスト
  • このエントリーをはてなブックマークに追加

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クラスと同様に2項演算なので、operand1operand2を持っています。これらをassembleしてfrag1frag2を作り、合成することで大本となるフラグメント(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は一つだけ保持します。operandassembleして得られる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を生成してnodeassembleメソッドを呼び出し、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

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
正規表現エンジンを作ろう連載記事一覧

もっと読む

この記事の著者

hiratara(ヒラタラ)

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

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/3164 2008/11/26 14:00

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング