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

はじめに

　こんにちは。hirataraです。

　私が初めて正規表現を使ったのは、PerlによるCGIでの文字列処理でした。それから私はPerlを使い続け、今では正規表現なしのコーディングは考えられないほど、正規表現を当たり前の機能として日常的に使っています。昔は標準では正規表現をサポートしていなかったJavaも、今では正規表現をサポートするようになりました。Javaだけではなく、今日ではほとんどの高級言語にとって、正規表現はなくてはならない機能であると言っても過言ではないほどメジャーな機能となっています。

　本記事では、この正規表現の舞台裏に光を当てます。一見すると作ることが難しそうな正規表現エンジンですが、その根底には数学的な概念があり、その概念さえ知っていれば基礎となる機能の実装はそんなに難しくありません。この連載ではその数学的な概念をPythonを使って表現しながら、実際に動作する正規表現エンジンを作り上げます。

対象読者

　言語はPythonで書いていますが、Pythonの知識がない方でも、考え方は読んで理解して頂けると思います。以下を前提とします。

• 基礎的なプログラミングができる方
• 正規表現を使える方

　また、以下のような方に読んで頂けると幸いです。

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

正規表現とは何か

　ご存知の通り、正規表現は文字列を評価・操作するためにプログラミング言語に用意された機能の一つです。詳しくは『詳説 正規表現』（Jeffrey E.F. Friedl著）や『正規表現の問題集』（山岸賢治著）などを読んで頂けるのが一番ですが、念のため正規表現がどのようなものか、簡単に復習してみましょう。

Perl

　PerlやRubyでは、言語に正規表現を利用するための文法が直接組み込まれています。Perlにおいて、「=~」は Binding Operator と呼ばれ、左辺の文字列を右辺の正規表現で処理させるために用います。スラッシュの間(/～/)に挟まれた部分が正規表現として見なされます。以下の用例では $hoge の中に"[fb]oo"にマッチする部分文字列があるかを調べています。

my $hoge = 'foo';
print "マッチしました\n" if $hoge =~ /[fb]oo/;

　なお、後述する他の言語と違ってPerlでは正規表現のコンパイル結果オブジェクトを意識せずに利用するインタフェースになってはいますが、 qr//表記を使ったり、 /～/o のように最後に o をつけると他の言語と同様にコンパイル結果を使い回すことができます。

Java

　Javaや.NET系等の言語では、正規表現の機能はライブラリとして提供されます。Javaでは、java.util.regexパッケージにPatternとMatcherと言うクラスがあります。Patternがコンパイルされた正規表現を表し、MatcherがPatternに対するマッチング実行時の情報を取り扱います。

　Matcherには、動作の微妙に違う find()、lookingAt()、matches() と言う3つのマッチング判定メソッドがあります。後の説明で使うので、以下のコードでこの3つの違いを確かめておきましょう。

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test{
    static public void main(final String[] args){
        final Pattern p = Pattern.compile("[fb]oo");

        final String hoge1 = "foo";
        final String hoge2 = "foo bar";
        final String hoge3 = "hoge foo bar";

        for(final String str : new String[]{hoge1, hoge2, hoge3}){
           final Matcher m = p.matcher(str);
           System.out.println("【" + str + "のマッチ結果】");
           if(m.find()     ) System.out.println("findでマッチしました");
           if(m.lookingAt()) System.out.println("lookingAtでマッチしました");
           if(m.matches()  ) System.out.println("matchesでマッチしました");
        }

    }
}

/*
実行結果

【fooのマッチ結果】
findでマッチしました
lookingAtでマッチしました
matchesでマッチしました
【foo barのマッチ結果】
findでマッチしました
lookingAtでマッチしました
【hoge foo barのマッチ結果】
findでマッチしました
*/

　実行結果をみて分かる通り、matches()は完全マッチ、lookingAt()は前方一致によるマッチ、find()は部分文字列によるマッチの判定をします。

Python

　最後に、今回の実装言語に当たるPythonの事情を見ておきましょう。Pythonの正規表現のライブラリは reモジュール と言う名前で提供されています。

# -*- coding: utf-8 -*-
import re

hoge1 = "foo"
hoge2 = "foo bar"
hoge3 = "hoge foo bar"
regexp = re.compile(r"[fb]oo")

for str in (hoge1, hoge2, hoge3):
    print u"【%sのマッチ結果】" % hoge1
    if regexp.match(str) : print u"matchでマッチしました"
    if regexp.search(str): print u"searchでマッチしました"

# 実行結果
# 
# 【fooのマッチ結果】
# matchでマッチしました
# searchでマッチしました
# 【fooのマッチ結果】
# matchでマッチしました
# searchでマッチしました
# 【fooのマッチ結果】
# searchでマッチしました

　Pythonの正規表現オブジェクトにもmatch()とsearch()と言う２種類のマッチングメソッドがありますので、Javaと同様の比較を行ってみました。実行結果を見ると、 searchメソッドがJavaのfind()、matchメソッドがJavaのlookingAt()に一致すると言えそうです。

　reモジュールには、他にもfindallやfinditerのように、文字列全体を連続して走査してマッチ部分を一度に取り出すインタフェースが用意されています。