Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

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

正規表現と数学

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

 正規表現は、特に文字列操作が中心となるWeb分野におけるプログラミングにおいて、なくてはならない重要な機能です。本稿では正規表現を解釈するエンジンを実際に実装し、正規表現エンジンがどのように動いているのかを解説します。第1回は、正規表現の数学的な定義や実装方法の概要を紹介します。

目次

はじめに

 こんにちは。hirataraです。

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

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

対象読者

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

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

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

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

正規表現とは何か

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

Perl

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

Perlの正規表現
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つの違いを確かめておきましょう。

Javaの正規表現
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モジュール と言う名前で提供されています。

Pythonの正規表現
# -*- 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()と言う2種類のマッチングメソッドがありますので、Javaと同様の比較を行ってみました。実行結果を見ると、 searchメソッドがJavaのfind()matchメソッドがJavaのlookingAt()に一致すると言えそうです。

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

後方一致マッチはないの?

 JavaでもPythonでも、前方一致によるマッチがあるのに対して後方一致によるマッチのメソッドは用意されていません。これは、前方一致の方が正規表現エンジンの原理から言って実現方法が自然だからです。逆に後方一致(つまり部分一致マッチも)は多少強引な方法……具体的には、総当たりでパターンを当たる方法で実装されます。


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

修正履歴

  • 2008/11/15 14:53 ε遷移の解説において、文字列"abc"の分解方法が間違えていたので修正しました。

著者プロフィール

  • hiratara(ヒラタラ)

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

バックナンバー

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