[トップ][編集][ノート][編集履歴][一覧][最近の更新][->English]
Topics
Search
Recent Changes
More ...

正規表現

HSP製の正規表現エンジンです．
対応する記号は，'*'，'|'，'('，')'のみです．(他の文法の追加も容易であると思います)
改良求みます．

別途，vain0さんのabdataモジュールが必要です．
https://github.com/vain0/abdata

仕組み

詳しくはこちらを．これのHSP移植版です．
http://mjhd.hatenablog.com/entry/2015/10/07/233926

実行結果

[image]

regexp.hsp 

#include "abdata/abdata/all.as"

#enum global ND_Union = 0
#enum global ND_Star
#enum global ND_Char
#enum global ND_Concat
#enum global ND_Empty

#enum global OP_Char = 0
#enum global OP_Match
#enum global OP_Jump
#enum global OP_Split

#enum global CD_Opecode = 0
#enum global CD_Operand1
#enum global CD_Operand2

/*************************
 * VM
 * 実際にテストを行う仮想マシン
 * Compilerが吐くlistを実行する
 *************************/

#module VM pc, sp, mem, text

#modinit int _mem, str _text
        pc = 0  // 実行中のmemのインデックス
        sp = 0  // 判定中のtextのインデックス
        mem  = _mem  // コンパイルされた正規表現
        text = _text // 対象の文字列
return

// textに対して判定を行う
#modcfunc start local tmp_pc, local tmp_sp, local ins, local result

        result = 0 // 0ならマッチ失敗、1ならマッチ成功

    // memを0からOP_Matchが表れるまで実行する
        repeat
        
                ins = list_get(mem, pc) // 実行する命令
        
                // 命令ごとに処理を分ける
                switch(list_get(ins, CD_Opecode))
        
                        // PCをオペランド1に置き換える
                        case OP_Jump
                                pc = list_get(ins, CD_Operand1) - 1
                        swbreak
        
                        // PCをオペランド1として新しいスレッドを作成
                        // その後、PCをオペランド2として続行
                        case OP_Split   
                                tmp_pc = pc
                                tmp_sp = sp
                                pc = list_get(ins, CD_Operand1)
                                if (start(thismod)) : result = 1: break

                                sp = tmp_sp
                                pc = list_get(ins, CD_Operand2) - 1
                        swbreak
        
                        // textのSP番目の文字が、オペランド1と等しいか判定
                        // 等しくなければスレッドを終了
                        case OP_Char
                                if (peek(text, sp) == list_get(ins, CD_Operand1)) {
                                        sp++
                                } else {
                                        result = 0 : break
                                }
                        swbreak
        
                        // マッチ成功
                        case OP_Match
                                result = 1 : break
                        swbreak
                swend

                pc++ // 次の実行のために、PCを更新する
        
        loop
return result

#modfunc set_pc int _pc
        pc = _pc
return

#modcfunc get_pc
return pc

#modfunc set_sp int _sp
        sp = _sp
return

#modcfunc get_sp
return sp

#global

/*********************************
 * Parser
 * 正規表現から構文木を作成する
 *********************************/

#module Parser pattern, it

#modinit str _pattern
        pattern = _pattern // 正規表現
        it = 0             // 現在処理している文字のインデックス
return

// パースを行う
// 返り値としてtnode(tnx)が返る
#modcfunc parse local result

        result = parse_exp@Parser(thismod)

return result

// 正規表現全体をパース
#modcfunc local parse_exp local result
        
        result = parse_subexp@Parser(thismod)

        // もし、正規表現の最後まで到達しなかった場合、構文エラー
        if (strlen(pattern) != it) {
                dialog "Could not reach EOF"
                return result
        }

return result

// '|'を含む正規表現をパース
#modcfunc local parse_subexp local result, local node1, local node2
        result = parse_subseq@Parser(thismod)

        // '|'であるかどうか
        if (peek(pattern, it) == $7c) {
                // node1は'|'の左側
                // node2は'|'の右側
                
                it++
                node1 = result
                node2 = parse_subexp@Parser(thismod)

                tnode_new result, ND_Union, list_make()

                tnx_addChd result, node1
                tnx_addChd result, node2
        }

return result

// 文字オブジェクトをパース(通常の文字または、'('~')'で表される集合)
#modcfunc local parse_factor local result

        // '('であるかどうか
        if (peek(pattern, it) == $28) {
                it++
                result = parse_subexp@Parser(thismod)
        } else {
                // 通常の文字
                tnode_new result, peek(pattern, it), list_make()
        }

        it++

return result

// 連接文字をパース
#modcfunc local parse_seq local result, local tmp
        tmp = peek(pattern, it)

        // '('または、記号ではない通常の文字
        if (tmp == $28 || (tmp != $7c && tmp != $29 && tmp != $2a && tmp != $00)) {
                return parse_subseq@Parser(thismod)
        }

        tnode_new result, ND_Empty, list_make()
return result

// '*'または文字、'*'または文字と文字の連接をパース
#modcfunc local parse_subseq local result, local node1, local node2, local tmp

        result = parse_star@Parser(thismod)
        
        tmp = peek(pattern, it)
        
        // '('または、記号ではない通常の文字
        if (tmp == $28 || (tmp != $7c && tmp != $29 && tmp != $2a && tmp != $00)) {
                node1 = result
                node2 = parse_subseq@Parser(thismod)
                tnode_new result, ND_Concat, list_make()
                tnx_addChd result, node1
                tnx_addChd result, node2
        }

return result

// '*'をパース
#modcfunc local parse_star local result, local tmp
        result = parse_factor@Parser(thismod)

        // '*'であるかどうか
        if (peek(pattern, it) == $2a) {
                tmp = result
                tnode_new result, ND_Star, list_make()
                tnx_addChd result, tmp

                it++
        }
return result

#global


/*************************
 * Compiler
 * 構文木からVM用のバイトコードを生成する
 *************************/

#module Compiler pc, ast

#modinit int _ast
        pc  = 0    // 現在コンパイル中のインデックス
        ast = _ast // 構文木
return

// コンパイルを行う
// 返り値としてバイトコードのlistが返る
#modcfunc compile local result, local tmp

        list_new result

        pc = 0

        // コンパイル
        compile_node@Compiler thismod, ast, result

        // 最後にOP_Matchを追加する
        list_new tmp
        list_add tmp, OP_Match
        list_add tmp, 0
        list_add tmp, 0

        list_add result, tmp

return result

// ノード単位のコンパイル
// 再帰的に実行される
// 変換先のバイトコードに関しては以下を参照
// http://qiita.com/yyu/items/84b1a00459408d1a7321#%E6%AD%A3%E8%A6%8F%E8%A1%A8%E7%8F%BE%E3%81%8B%E3%82%89%E3%83%90%E3%82%A4%E3%83%88%E3%82%B3%E3%83%BC%E3%83%89%E3%81%B8%E3%81%AE%E5%A4%89%E6%8F%9B
#modfunc local compile_node int node, int code, local tmp, local tmp1, local tmp2

        switch(tnode_get(node))
                case ND_Concat // 連接

                        // 二つの要素をそれぞれ順にコンパイルする
                        compile_node@Compiler thismod, tnxChd(node, 0), code
                        compile_node@Compiler thismod, tnxChd(node, 1), code

                swbreak
                
                case ND_Star // '*'

                        list_new tmp
                        list_add tmp, OP_Split
                        list_add tmp, pc + 1
                        list_add tmp, 0

                        list_add code, tmp

                        tmp1 = pc

                        pc++

                        compile_node@Compiler thismod, tnxChd(node, 0), code

                        list_new tmp
                        list_add tmp, OP_Jump
                        list_add tmp, tmp1
                        list_add tmp, 0

                        list_add code, tmp

                        pc++

                        list_ref(list_get(code, tmp1), CD_Operand2) = pc

                swbreak
                
                case ND_Union // '|'
                        list_new tmp
                        list_add tmp, OP_Split
                        list_add tmp, pc + 1
                        list_add tmp, 0

                        list_add code, tmp

                        tmp1 = pc

                        pc++

                        compile_node@Compiler thismod, tnxChd(node, 0), code

                        list_new tmp
                        list_add tmp, OP_Jump
                        list_add tmp, 0
                        list_add tmp, 0

                        list_add code, tmp

                        tmp2 = pc

                        pc++

                        compile_node@Compiler thismod, tnxChd(node, 1), code

                        list_ref(list_get(code, tmp1), CD_Operand2) = tmp2 + 1
                        list_ref(list_get(code, tmp2), CD_Operand1) = pc

                swbreak
                
                case ND_Empty

                swbreak
                
                default // ND_Char
                        list_new tmp
                        list_add tmp, OP_Char
                        list_add tmp, tnode_get(node)
                        list_add tmp, 0

                        list_add code, tmp

                        pc++
                swbreak
        swend

return

#global


/*************************
 * Regexp
 * 正規表現を管理する
 *************************/

#module Regexp code

#modinit str _pattern, local par, local com, local ast
        // 正規表現をパース
        newmod par, Parser, _pattern
        ast = parse(par)
        delmod par
        
        // 構文木をコンパイル
        newmod com, Compiler, ast
        code = compile(com)
        delmod com
        
        // デバッグ用
        // バイトコードの様子が見れます
        /*repeat list_size(code)
                buf = strf("%d: ", cnt)
                ins = list_get(code, cnt)
                op1 = list_get(ins, CD_Operand1)
                op2 = list_get(ins, CD_Operand2)
                tmp = " "
                switch list_get(list_get(code, cnt), CD_Opecode)
                        case OP_Split
                                buf += strf("SPLIT %d, %d", op1, op2)
                        swbreak
                        case OP_Jump
                                buf += strf("JUMP %d", op1)
                        swbreak
                        case OP_Char
                                poke tmp, 0, op1
                                buf += strf("CHAR %s", tmp)
                        swbreak
                        case OP_Match
                                buf += "MATCH"
                        swbreak
                swend
        
                logmes buf
        loop*/

        tnode_delete ast
return

#modterm
        IterateBegin code, list
                list_delete it
        IterateEnd

        list_delete code
return

// 判定を行う
// マッチに成功すれば1、失敗すれば0が返る
#modcfunc match str _text, local machine, local result
        newmod machine, VM, code, _text
        result = start(machine)
        delmod machine
return result

#global


/***********************************
 *         サンプル
 ***********************************/
        
pattern = "(Objective-)*C(++|#)*"
lang = "B", "C", "C++", "C#", "Objective-C", "D"

newmod clike, Regexp, pattern

mes "Pattern:" + pattern
mes

repeat length(lang)
        if (match(clike, lang(cnt)) == 1) {
                color 0, 128, 0
                mes strf("%s is C-like!", lang(cnt))
        } else {
                color 128, 0, 0
                mes strf("%s", lang(cnt))
        }
loop

delmod clike

参考

http://qiita.com/yyu/items/84b1a00459408d1a7321
http://codezine.jp/article/corner/237

Last modified : 2015/10/10 03:01:06 JST
WiLiKi 0.5.3 running on Gauche 0.9.2