タグ : Python

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