module regelt; import std.string; import std.stdio; class RegeLT { //---------------------------------------------------------------------- // データ構造 // 普通のNFA。DFAの方が処理は楽なんだけど作るのがめんどい //---------------------------------------------------------------------- const State I; // 始状態 const State F; // 終状態 const Rule[] D; // 状態遷移表 const int K; // 括弧の個数 alias int State; static class Rule { State[] eps; // ε遷移先 State[char] chr; // 文字が来たときの遷移先 State[int] o_paren; // キャプチャ開始するときの遷移先 State[int] c_paren; // キャプチャ終了するときの遷移先 } //---------------------------------------------------------------------- // コンストラクタ // 正規表現を構文解析して↑のテーブルを構築。適当に //---------------------------------------------------------------------- this( string re ) { with( new Parser(re) ) I=cur, E(), D=tbl, F=cur, K=paren_id; } static class Parser { this( string re ) { this.re = re; gen_state(); } // 遷移表構築用の補助データ ----------- Rule[] tbl; State cur = -1; void gen_state() { tbl ~= new Rule; ++cur; } int paren_id = 0; void eps(State a, State b) { if(a!=b) tbl[a].eps ~= b; } void eps_op(State a, State b, int p) { tbl[a].o_paren[p] = b; } void eps_cp(State a, State b, int p) { tbl[a].c_paren[p] = b; } void tran(State a, State b, char c) { tbl[a].chr[c] = b; } // 字句解析 --------------------------- string re; char next() { gen_state(); scope(exit)re=re[1..$]; return re[0]; } bool eat(char c) { if(!re.length || re[0]!=c) return false; next(); return true; } bool is_not(string s) { return re.length && s.find(re[0])<0; } // 構文解析 --------------------------- void E() // E ::= S ('|' S)* { State s = cur; gen_state(); State[] ee; do { eps(s,cur); S(); ee~=cur; } while( eat('|') ); foreach(e; ee) eps(e, cur); } void S() // S ::= (U '*'?)* { while( is_not(")|") ) { State s = cur; U(); if( eat('*') ) eps(s, cur), eps(cur-1,s); } } void U() // U ::= '(' E ')' | '.' | letter { char c = next(); if( c == '(' ) { int pid = ++paren_id; eps_op(cur-1, cur, pid), E(), eat(')'), eps_cp(cur-1, cur, pid); } else if( c == '.' ) foreach(cc; " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPPRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~") tran(cur-1, cur, cc); else tran(cur-1, cur, c); } } //---------------------------------------------------------------------- // デバッグ用表示 // 状態遷移表。一番数字が小さいのが始状態で大きいのが終状態です //---------------------------------------------------------------------- void print() { foreach(i,r; D) { foreach(e; r.eps) writeln(i, "------->", e); foreach(c,e; r.chr) writeln(i, "--'",c,"'-->", e); foreach(p,e; r.o_paren) writeln(i, "---(",p,"-->", e); foreach(p,e; r.c_paren) writeln(i, "---)",p,"-->", e); } } //---------------------------------------------------------------------- // マッチする箇所を検索する処理 // [0] がマッチ箇所の先頭index // [1] がマッチ箇所の終端(の１個後ろ)index // [2] が$1の先頭index // [3] が$1の終端(の１個後ろ)index // ... // みたいな配列を返す。マッチしなかった場合は null。 // 部分式が部分的にマッチしてない場合は int.min が入ってるはず。 // /(a)|(b)|(c)/.search("xxxbxxx") ） => [3,4,-,-,3,4,-,-] みたいな。 // // - - - - - // // 文字列全体と正規表現がマッチするかの判定は、 // // - NFAの全ステートで "このステートにたどりつけるか？" を覚えといて // それを一文字読み込むたびに更新していくことで、バックトラックなしで実行可能。 // // ところでこの "このステートにたどりつけるか？" :: boolean // より色々情報を増やしてみることができる // // - "このステートに来られのは何文字目からオートマトン動かし始めた時か？" :: int // を持たせておくと、文字列全体とのマッチだけではなくて、マッチする一部分を // 検索できるようになる。 // i文字目から始めたときもj文字目から始めたときも同じステートにたどり着くなら // i // にして全通りのマッチ箇所を一気に洗い出すということもできる。 // 複数の情報が合流するとこの処理は、booleanの場合 || で int の場合 min だったわけだけど、 // set の場合は set_union になる。|| も min も O(1) だったので全体の処理時間は // O(N) になったけど、set_union は最悪 O(N) だから全体は O(N^2) になる。 // ただし、set を遅延評価することで O(N + M) // M=最終的なマッチパターンの個数 // に落とすことは可能。 // // - あるいは "(略)" :: int[] // を覚えておくことで、(...) による部分式キャプチャの位置まで覚えながら検索 // || や min や set_union に当たる処理 ("unify" と総称することにしよう) // は、やっぱり最左最長優先でてきとうに。 //---------------------------------------------------------------------- MatchData search( string S ) { MatchData[] M = new MatchData[F+1]; // ステート毎にMatchDataを覚えとく void read_char( char c ) { MatchData[] MM = new MatchData[F+1]; foreach(q,p; M) // ステート q が if(p !is null) // マッチ途中で if(auto qq = c in D[q].chr) // 文字 c での遷移先が qq なら unify( MM[*qq], p ); // マッチデータを qq に統合 M = MM; } void epsilon_closure( int i ) { for(bool upd=true; upd;) // どっかで更新がある間は繰り返す { upd = false; foreach(q,p; M) // ステート q が if( p !is null ) // マッチ途中だったら { // ε遷移先にその情報を統合 foreach(qq; D[q].eps) upd |= unify( M[qq], p ); foreach(k,qq; D[q].o_paren) upd |= unify( M[qq], o_paren(p,k,i) ); // 括弧の時は情報更新 foreach(k,qq; D[q].c_paren) upd |= unify( M[qq], c_paren(p,k,i) ); // 括弧の時は情報更新 } } } MatchData Result; for(int i=0; i<=S.length; ++i) // メインループ { if(i) read_char( S[i-1] ); // 一文字読み込む unify( M[I], start(i) ); // ここからマッチ開始してみるテスト epsilon_closure(i); // ε遷移しまくり if( M[F] !is null ) unify( Result, eom(M[F],i) ); // ここで、Result に入っているマッチデータより // 他の全ての M[q] のデータの方が優先度的に劣るようであれば // 即座にループを打ち切って return Result してよい。 // というかしないと遅い。けどめんどいので省略。 } return Result; } //---------------------------------------------------------------------- // マッチデータの処理 //---------------------------------------------------------------------- alias int[] MatchData; MatchData start(int i) { MatchData m = new int[2+K*2]; m[0] = i; m[1..$] = int.min; return m; } MatchData o_paren( MatchData m, int k, int i ) { MatchData mm = m.dup; mm[2*k] = i; return mm; } MatchData c_paren( MatchData m, int k, int i ) { MatchData mm = m.dup; mm[2*k+1] = i; return mm; } MatchData eom( MatchData m, int i ) { MatchData mm = m.dup; mm[1] = i; return mm; } bool better_worse( MatchData a, MatchData b ) { if( a is null ) return false; if( b is null ) return true; if( a[0] < b[0] ) return true; // 最左 if( a[0] > b[0] ) return false; for(int k=1; k<2*K+2; ++k) { if( a[k] > b[k] ) return true; // 最長/最右 if( a[k] < b[k] ) return false; } return true; } bool unify( ref MatchData a, MatchData b ) { if( better_worse(a,b) ) return false; a = b; return true; } } unittest { auto a = new RegeLT("((ab)|(a))(b|)"); a.print; writeln( a.search("abc") ); string r, s; foreach(_; 0..26) r ~= "(a|)"; foreach(_; 0..26) r ~= "a"; foreach(_; 0..26) s ~= "a"; auto m = (new RegeLT(r)).search(s.idup); writeln( m ); } void main( string[] argv ) { if( argv.length == 1 ) { writeln( "Usage:" ); writeln( " regelt regexp < file" ); } else { auto r = new RegeLT( argv[1] ); string s; while( (s=readln) !is null ) writeln( r.search(s) ); } }