タグ : Regexp

PCREは無限の括弧の対応が取れる ~ 再帰も、ネストも、あるんだよ.

追記
ご指摘があり, どうやらPCREはPerl互換正規表現エンジン実装の1つに過ぎないということでタイトルは正確には「Perlの正規表現は無限の括弧の対応が取れる」かもしれません.

こんなの絶対おかしいよ

はい. PCRE すごいです.

僕が正規表現と戯れ始めたのはちょうど1年前. その時, 最初に @shinji_kono 先生に賜った 言葉が

正規表現は たかが 括弧の対応が取れないんですよ.

もうちょっと正確にいうと, 正規表現では

  • (a)
  • (((a)))
  • ((aaa)((bbb)((cc)(d))))
  • (()(()())()(()))()()

のような任意のネストを認めた開き括弧と閉じ括弧の対応がとれない.

というのも, 開き括弧を読み取った時点で, それに対応する閉じ括弧が現れるまで開き括弧の個数 を覚えて置かなければならないからです. 正規表現は 有限 オートマトンで認識できる言語しか表現できないので, 任意個(無限)の括弧に対応した 有限 オートマトンは作れないという話ですね. (もっと強力なプッシュダウン・オートマトン なら可能ですが.)

 

 

ところが

タイトルの通り, PCREさんだとそれが可能です(Perl 5.10からだそうです).

 

(?R)

という構文が正規表現に拡張機能として導入されており, これは パターン全体 を表現するそうです. つまり,

パターンの内部にそのパターン自身を埋め込める

はい. 再帰ですね. PCRE の manual では,

This PCRE pattern solves the nested parentheses problem (assume the PCRE_EXTENDED option is set
so that white space is ignored):

\( ( [^()]++ | (?R) )* \)

という正規表現が紹介されており, この正規表現は空白を無視すると

  • まず, 開括弧にマッチ
  • 続いて
    • 括弧以外の文字列にマッチ(++は貪欲なマッチングで, バックトラックを行わない. これもPerl5.10からの新機能)
    • もしくは, 全体のパターンにマッチ(再帰).

の0回以上の繰り返し.

  • 最後に閉括弧にマッチ.

短いのに恐ろしい記述力ですね. (てか初見じゃ意味不

これで 括弧のネストに対応できる! 再帰で! 1

 

つまり

正規表現2パーサーが書ける じゃないか! と, 思ったら 404 Blog Not Found で既に紹介されていました. (さすが正規表現フェチ ;-)

perl – parser書くならgoto

こちらは (??{ code }) という正規表現にコードを埋め込む, 動的正規表現という機能を使ってますね.

正規表現好きということなら, Perlの正規表現はしっかりチェックしないといけないなぁ. (強烈…)

http://perldoc.jp/docs/perl/5.10.0/perlreref.pod

 

 

おまけ

今日はじめて知ったんですが,

% man pcrepattern

とすると, PCRE の syntax manual が読めます(OS X だと標準で pcre が入ってます). これは便利. というかこれで今回の再帰構文も知りました.

ちゃんと読んでみよっと.

 

 

Footnotes:

1 もちろん 無限 というのは記述力的にという意味で, 実際はスタックの制限で再帰マッチングにはかぎりがあるのですが. (ツッコムのは野暮です:-p

2 もちろん,PCREの拡張を使って.pureな正規表現ではないですね.

 

 

Pythonで正規表現->DFA変換

CodeZineに

Pythonでの正規表現エンジンの実装講座という記事があったので、実装してみた。
エンジンの仕様は、

  1. DFAによる完全マッチング
  2. 和集合,連結,繰り返しのみをサポートした最小(数学的な)構成
  3. 括弧による演算の優先順位も考慮

のような感じ。

丁寧かつ軽く読みながせる記事なので、実装は記事を参照してほしいです。

使ってみる

SHINYA% python
Python 2.5.1 (r251:54863, Feb  6 2009, 19:02:12)
[GCC 4.0.1 (Apple Inc. build 5465)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from dfareg import *
>>> regexp = Regexp(ur'(A|B)*C')
>>> regexp.matches('AABBC')
True
>>> regexp.matches('C')
True

状態遷移の書き出し

この実装では、状態遷移を辞書(ハッシュ)を持つ(関数)オブジェクトで実装していて、
状態と入力文字を引数とした関数を生成していた。

def transition(state, char): # map is dictionary
    return frozenset(map_.get((state, char), []))

全ての遷移規則がわかるので、この辞書を解析することで完全な状態遷移を書き出す事も少しの変更で可能。
いか記事の実装に付け足したコード。 #CbCは状態遷移言語の意味

# emit CbC-souce, from dfa
def dfa2CbC(dfa, regexp):

    # return state name from set
    def set2name(set_):
        l = list(set_)
        l.sort()
        return '_'.join(str(x) for x in l)

    funcMap = dict()
    funcMap[dfa.start] = set()

    # dfa.map => {(frozenset([1, 15]), 'd'): frozenset([16]), ....}
    #             : frozenset(1, 15) x 'd' -> frozenset([16])

    for v in dfa.map.itervalues():
        funcMap[frozenset(v)] = set()

    for key in dfa.map.iterkeys():
        slot = funcMap.setdefault(key[0], set())
        slot.add(key[1])

    # emit cbc code
    print "#include <stdio.h>\n"
    for k in funcMap.iterkeys():
        print '__code state_' + set2name(k) + "(char* s);"
    print '__code accept();'
    print '__code reject();'
    print """
int main(int argc, char* argv[]) {
\tputs(\"regexp: %s\");
\tputs(\"number of state: %d\");
\tprintf(\"string: %%s\\n\", argv[1]);
\tgoto state_%s(argv[1]);
\treturn 0;
}\n"""
% (regexp, len(funcMap), set2name(dfa.start))

    for k, v in funcMap.iteritems():
        print '__code state_' + set2name(k) + "(char* s) {"
        print "\tswitch(*s++) {"
        for case in v:
            print "\t\tcase '%c': " % (case)
            print "\t\t\tgoto state_%s(s);\n\t\t\tbreak;" % set2name(dfa.map[(frozenset(k), case)])
        if k in dfa.accepts: print "\t\tcase '\\0': goto accept();\n\t\t\tbreak;"
        print "\t\tdefault: goto reject();\n\t}"
        print "}\n"

    print """
__code accept() {
\tprintf(\"\\nstring matches regexp. \\n\\n\");
}\n"""

    print """
__code reject() {
\tprintf(\"\\nstring does not match regexp. \\n\\n\");
}\n"""

__codeは、状態の記述に使う修飾子。
goto (__code)foo(arg);
という記述でfooにargを持って状態遷移を行なう感じ。

これで、実際に'(A|B)*C’を状態遷移に書き下してみる。

#include <stdio.h>

__code state_1_2_3_5_7(char* s);
__code state_1_3_5_6_7(char* s);
__code state_8(char* s);
__code state_1_3_4_5_7(char* s);
__code accept();
__code reject();

int main(int argc, char* argv[]) {
        puts("regexp: (A|B)*C");
        puts("number of state: 4");
        printf("string: %s\n", argv[1]);
        goto state_1_3_5_6_7(argv[1]);
        return 0;
}

__code state_1_2_3_5_7(char* s) {
        switch(*s++) {
                case 'A':
                        goto state_1_2_3_5_7(s);
                        break;
                case 'C':
                        goto state_8(s);
                        break;
                case 'B':
                        goto state_1_3_4_5_7(s);
                        break;
                default: goto reject();
        }
}

__code state_1_3_5_6_7(char* s) {
        switch(*s++) {
                case 'A':
                        goto state_1_2_3_5_7(s);
                        break;
                case 'C':
                        goto state_8(s);
                        break;
                case 'B':
                        goto state_1_3_4_5_7(s);
                        break;
                default: goto reject();
        }
}

__code state_8(char* s) {
        switch(*s++) {
                case '\0': goto accept();
                        break;
                default: goto reject();
        }
}

__code state_1_3_4_5_7(char* s) {
        switch(*s++) {
                case 'A':
                        goto state_1_2_3_5_7(s);
                        break;
                case 'C':
                        goto state_8(s);
                        break;
                case 'B':
                        goto state_1_3_4_5_7(s);
                        break;
                default: goto reject();
        }
}


__code accept() {
        printf("\nstring matches regexp. \n\n");
}


__code reject() {
        printf("\nstring does not match regexp. \n\n");
}

‘(A|B)*C’という正規表現は、4つの状態からなる小さな状態遷移で表現できることが分かる。

CbC

ちなみに、上記生成したC言語チックなコードは、僕の研究室で作られたCbCという言語。
状態遷移の記述に適している言語なので、今回サンプルとして下記だしてみた。
GCCのC-frontendを拡張して既に実装してあるので、上記CbCソースはコンパイルして実行することも可能。
(__code を voidに、 goto foo(args) を foo(args) に変換すればCとして実行できる)

比較とか

生成したソースをコンパイルしてのマッチングと、Python のライブラリとかにある正規表現との比較とかしてみたい。
もっと言えば 生成したソースをJITしてみたりしたい!!

LLVMとかも面白そう。

正規表現エンジンの実装凄く面白いし、最適化とか置くも深いと思う。大学のオートマトンの講義を受けている時にこういうのを触っておけばもっと講義を楽しめたかも ;-)

 
Better Tag Cloud