先月末に正規表現の勉強会をしました(http://dev.ariel-networks.com/articles/workshop/regex/)。

良い内容だと思っているのですが、いまいち盛り上がりませんでした。 後日、あるベテランプログラマーに、「Perlなんて言うからダメです。今時の若者はPerlなんて使いません」とたしなめられました。 普段、ぼくはPerlよりsedやawkを使う方が多いのですが、sedやawkでは話が通じないと思い、Perlに日和ったつもりでした。判断が甘かったようです。

今月も続きをやる予定です。 本当はNFAとDFAの話をしたいのですが、また受けが悪そうなので、その辺はさらっと流して、Javaで使う正規表現を全面に押すつもりです。

Java1.4以降、java.util.regexとして標準パッケージで正規表現が使えます。 もうひとつ有名なのはJakartaのregexpです(http://jakarta.apache.org/regexp/index.html)。 その他、利用可能な正規表現の実装は http://regex.info/java.html にまとまっています。

java.util.regexのサンプルコードです。 引数で正規表現のパターンを渡して、標準入力から入力テキストを渡します。

// java5 standard regex test
import java.io.*;
import java.util.*;
import java.util.regex.*;

public class MyRegex {
    public void doit(String pattern) {
        Pattern regex = Pattern.compile(pattern);

        BufferedReader fin = new BufferedReader(new InputStreamReader(System.in));
        try {
            while (true) {
                System.out.println("input any text");
                String s = fin.readLine();

                Matcher m = regex.matcher(s);
                if (m.matches()) {
                    int count = m.groupCount();
                    System.out.format("count = %d\n", count);
                    for (int i = 1; i <= count; i++) {
                        System.out.format("group: %s\n", m.group(i));
                    }
                }
            }
        } catch (IOException e) {
            ;
        }
    }
    
    public static void main(String argv[]) {
        MyRegex re = new MyRegex();
        if (argv.length != 1) {
            System.err.println("need one argument. regex-pattern");
            System.exit(0);
        }
        re.doit(argv[0]);
    }
}

次はJakartaのregexpのサンプルコードです。動作は同じです。

// jakarta regexp test
import java.io.*;
import java.util.*;
import org.apache.regexp.*;

public class MyRegexp {
    public void doit(String pattern) {
        RE regex = new RE(pattern);

        BufferedReader fin = new BufferedReader(new InputStreamReader(System.in));
        try {
            while (true) {
                System.out.println("input any text");
                String s = fin.readLine();

                if (regex.match(s)) {
                    int count = regex.getParenCount();
                    System.out.format("count = %d\n", count);
                    for (int i = 1; i < count; i++) {
                        System.out.format("group: %s\n", regex.getParen(i));
                    }
                }
            }
        } catch (IOException e) {
            ;
        }
    }
    
    public static void main(String argv[]) {
        MyRegexp re = new MyRegexp();
        if (argv.length != 1) {
            System.err.println("need one argument. regex-pattern");
            System.exit(0);
        }
        re.doit(argv[0]);
    }
}

どちらも実装はNFAです。 「詳説 正規表現」ではNFAとDFAを見分けられる(可能性が高い)パターン例が載っています。 NFAだとバックトラックの嵐で異常に時間がかかるのに対し、DFAではすぐに終わるパターンです。

次のようなパターンが載っています。

• 正規表現パターン: X(.+)+X
• 入力テキスト: =XX===========================================================

実装がNFAであれば、無限に近いぐらいCPUが占有される(可能性が高い)、と書かれています。

まずperl, sed, grepで確認してみましたが、どれもすぐに終わります。perlとsedは刺さっても良さそうなものですが。何か細工があるのでしょうか。

Emacsを試すと、見事に刺さりました(isearch-forward-regexp)。

次のPythonも試してみました。これも刺さりました。

#!/usr/bin/python
import re
input = '=XX=========================================================================='
m = re.compile('X(.+)+X').search(input)
print input[m.start(1):m.end(1)]

さて、Javaの番です。 java.util.regexは、すぐに返ってきました。実装はNFAのはずですが(ソースを見て確認済み)、回避しています。さすが、我らがJavaです。

しかし、Jakartaのregexpは刺さりました。そんなものです。