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

NFAとDFAを実装する

　正規表現は、特に文字列操作が中心となるWEB分野におけるプログラミングにおいて、なくてはならない重要な機能です。本稿では正規表現を解釈するエンジンを実際に実装し、正規表現エンジンがどのように動いているのかを解説します。第2回は、正規表現エンジンの実際の評価器となる、NFAとDFAを実装します。

はじめに

　こんにちは。hirataraです。

　本稿は、正規表現エンジン作成の第2回目です。前回は正規表現の数学的な側面を説明しました。今回は正規表現エンジンの実際の評価器となる、NFAとDFAを実装します。

対象読者

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

必要な環境

　サンプルはPython2.5で開発しましたが、2.4の環境でも動くはずです。

• Python2.5 が動作する環境

実装する正規表現の仕様

　今回から正規表現エンジンの実装に入りますが、実際に手を動かし始める前に、到達すべきゴールを明確にしておきましょう。まず、連載中に実装する正規表現の仕様を決定します。この連載では数学的な定義である3つの正規表現のみを実装し、正規表現が本当にDFAと等価であり、DFAをシミュレートすることで実装できることを確かめます。

文法

　これから作るDFAエンジンが解釈する文法は、以下の通りとします。これらの文法は、前回示した数学的な3つの演算と対応しています。他、優先順位を示す括弧や、エスケープ文字の規則を含んでいます。

文法規則

記法	意味
A|B	AかBのどちらか（和集合）
AB	文字列AB（連結）
A*	Aの0個以上の繰り返し
(～)	演算の優先順位
\ + 任意の文字	1文字の「任意の文字」（エスケープ）

　例えば、以下のようなものです。

例

正規表現	意味
p(erl|hp|ython)|ruby	「perl」「ruby」等にマッチ
山田(太|一|次|三)郎	「山田太郎」「山田次郎」等にマッチ
ww*|\(笑\)	「www」「(笑)」等にマッチ

API

　簡単のために部分マッチには対応せず、全文一致のみを行います。Pythonのreモジュールと似たインタフェースにしつつ、メソッド名はJavaに matches() と言う全文一致のメソッド名がありますので、これを拝借します。

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がマッチしました"

　dfareg.compileを呼ぶと、コンパイルされた正規表現が返ってきます。この正規表現に対して、matchesメソッドによって、文字列がマッチするかしないかを判別できます。

実装の流れ

　実装は、以下のような順序で進めます。今回は1.を行います。

1. NFAとDFAの実装
2. 正規表現のコンパイル（構文木の作成）
3. 構文木からNFAを作成
4. NFAからDFAへの変換
5. 全てを組み合わせて完成！

NFAの実装

　それでは、DFAエンジンの実装に入ります。まず、NFAをPythonコードとして実装しましょう。NFAは第1回で説明した通り、入力として文字を一文字ずつ受け取り、受け取った文字と現在の内部状態に応じて自分の内部状態を非決定的に変化させていく仮想機械です。NFAは、以下のように状態遷移図で書き表されるのでした。

NFAの状態遷移図（再掲）

NFAの内部表現を決める

　NFAは、オブジェクトとして表現することにします。

　なお、オブジェクトとするのはNFA（遷移図全体）です。NFAの状態（遷移図上の円）一つ一つをオブジェクトとして表すわけではないので、間違えないように注意して下さい。

　NFAクラスがどんなフィールドを持つとよいかについては、NFAの数学的な定義を参考にします。

NFAの定義

　NFAの数学的な定義は、以下の5つの要素からなります。

• 状態の集合（丸）
• 文字の集合（Unicode文字）
• 遷移関数（矢印）
  • 引数: 今の状態, 文字 or 空文字（ε）
  • 戻り値: 次の状態の集合
• 開始状態（最初の矢印がさす丸）
• 受理状態の集合（二重丸）

　この5つの要素を、先に示した遷移図上の要素と対応させながら詳しく見てみましょう。

　まず、「状態の集合」とは、図中の丸を全て集めたものとなります。その中で、スタート地点の丸が「開始状態」、二重丸がついているものを集めたものが「受理状態の集合」です。「文字の集合」は矢印につけられるラベル（文字）として図中に現れます。

　状態遷移図中の矢印は、全部をまとめて関数で表します。この関数は、現在の「状態」と入力「文字」を引数とし、次の「状態」の集合を戻り値とします。例えば、1の状態から2の状態に'a'の文字で移る矢印と1の状態から4の状態に'a'の文字で移る矢印は、func(1, 'a')が{2, 4}を返すことで表されます。

数学の要素とPythonの型の対応

　定義中に「集合」と「関数」が出てきましたが、幸い、Pythonにはこのどちらも組み込み型として存在しています。集合はfrozenset型で、関数はfunction型です。今回はこれらの型をそのまま利用します。また、「状態」に関しては、オブジェクトではなく単なる整数値として表すことにします。

集合にset型を使わない理由

　Pythonではset型と言う型がありますが、今回はあえてfrozenset型を使っています。この2つの型の違いは、変更可能か変更不可能かと言う部分です。frozenset型を使うのは、以下の2つの理由によります。

• 【数学的な集合の性質による理由】数学的な"集合"は、静的な概念である。よって、不可変なオブジェクトの方が概念にマッチしやすい。
• 【実装上の理由】set型は可変であるため、set型の要素となることができない。この後「集合の集合」の実装が必要なので、set型の要素にできるものを"集合"としなければならない。

　frozensetは、 frozenset([ frozenset([1, 2]), frozenset([3, 4]) ]) のように入れ子にできますが、setはエラーとなります。

setは入れ子にできない

>>> set([ set([1,2]), set([3,4]) ])
Traceback (most recent call last):
  File "", line 1, in 
TypeError: set objects are unhashable

実装に必要な要素の選定

　さて、数学的にはこの5つの要素によってNFAを表現しますが、わざわざ指定しなくても明らかであるため、実装には必要がないものがあります。

　まず、明らかに自明なのが「文字の集合」です。プログラミング言語で利用する正規表現ではUnicode文字列の判定をすることが目的ですので、入力されうるアルファベットは、「全てのUnicode文字」を固定で利用しても問題ありません。

　また、「状態の集合」ですが、これは「初期状態」と、その後の「遷移関数」による遷移で取りうる戻り値を全て集めたものとなりますので、「遷移関数」の値域さえしっかり定義されていれば必要ありません（注1）。

　よって、実装に必要なものは残りの「遷移関数」「開始状態」「受理状態の集合」の3つだけです。

注1

　厳密に言うと、NFAの「状態の集合」の要素は有限個であることが求められますので、遷移関数の戻り値の集合の全ての和集合も、有限個の整数となっている必要はあります。