SHOEISHA iD

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

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

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

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

NFAをDFAに変換し、正規表現エンジンを完成させる

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

正規表現エンジンを完成させる

 まず、今回までに作った部品を振り返ってみましょう。過去の連載において、以下の部品を作製してきました。

  • DFAとNFA(第2回
  • NFAを作るコンパイラ
  • 部分集合構成法(dfa2nfa関数)(今回)

 第2回で説明した通り、今回の正規表現エンジンのインタフェースは以下のようになります。

dfaregモジュールのインタフェース(再掲)
# -*- coding: utf-8 -*-
import dfareg

regexp = dfareg.compile(r"(p(erl|ython|hp)|ruby)")
if regexp.matches("python"): print u"pythonがマッチしました"
if regexp.matches("ruby")  : print u"rubyがマッチしました"
if regexp.matches("VB")    : print u"VBがマッチしました"

 compileを呼ぶとコンパイル済みの正規表現オブジェクトが返って来て、matchesメソッドでマッチングを行います。よって、compileメソッドの戻り値である、正規表現オブジェクトの実装が必要です。

Regexpクラス

 Regexpクラスはコンパイル済みの正規表現です。この連載では、正規表現をDFAに変換していました。よって、RegexpクラスはDFAを内部に持ち、ラップしたようなクラスになります。コンストラクタで正規表現をコンパイルし、コンパイルの結果生成されたDFAを内部に保持します。

コンストラクタ

 コンストラクタは以下のようになります。

Regexpクラス(1)
class Regexp(object):
    def __init__(self, regexp):
        self.regexp = regexp
        self.dfa     = None
        self._compile()

    def _compile(self):
        # コンパイル
        lexer_        = Lexer(self.regexp)
        parser_       = Parser(lexer_)
        nfa           = parser_.expression()
        # 部分集合構成法
        self.dfa      = nfa2dfa(nfa)

 入力された正規表現は、regexpフィールドに念のため保存しておきます。そして、_compileメソッドにおいてこの正規表現のコンパイルを行っています。コンパイルには、第3回で作ったコンパイラを使います。まず、字句解析機であるLexerオブジェクトを作成し、トークンが得られるようにします。これを構文解析機であるParserオブジェクトに渡します。最後に、文法規則の開始記号にあたるexpressionメソッドをParserオブジェクトに対して呼び出すことで、構文木の作成とNFAへの変換を実行させます。

 NFAが作成されたら、これを今回実装した部分集合構成法により、DFAに変換します。部分集合構成法に関しては、nfa2dfa関数を呼ぶだけです。

マッチング

 コンパイル済みの正規表現に対して、文字列のマッチングを指示するメソッドであるmatchesメソッドを実装します。

Regexpクラス(2)
def matches(self, string):
    runtime = self.dfa.get_runtime()
    return runtime.does_accept(string)

 第2回で実装した、DFAの動作をシミュレートさせるメソッドを利用します。まず、コンパイル済みのDFAからget_runtimeメソッドによってDFARuntimeオブジェクトを取り出します。そして、does_acceptメソッドによってstringがこのDFAに受理されるかどうか、チェックしてそのままマッチング結果として返却します。

仕上げ

 これが最後の工程です。当初予定していたインタフェースに合うように、compileメソッドを用意します。これは、以下のようにRegexpオブジェクトを作って返すだけです。

dfareg/__init__.py
def compile(regexp):
    return Regexp(regexp)

 これで、正規表現エンジンが完成しました。

まとめ

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

  • NFAからDFAを作る
  • 部分集合構成法
  • 正規表現エンジンの完成

 次回はこの正規表現エンジンを実際に動かし、NFAエンジンと比較をしてみます。

参考資料

  1. 計算理論の基礎』Michael Sipser 著、渡辺治・太田和夫 訳、共立出版、2000年4月

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

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

もっと読む

この記事の著者

hiratara(ヒラタラ)

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

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

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

この記事をシェア

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

おすすめ

アクセスランキング

アクセスランキング

イベント

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

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

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

メールバックナンバー

アクセスランキング

アクセスランキング