dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: #include "stdafx.h"
dcdd144598 2011-02-23        kinaba: #include "RSearch.h"
dcdd144598 2011-02-23        kinaba: #include "kilib/ktlaptr.h"
dcdd144598 2011-02-23        kinaba: using namespace ki;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	文字の種類
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: enum RegToken
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	R_Char,  // 普通の文字
dcdd144598 2011-02-23        kinaba: 	R_Any,   // '.'
dcdd144598 2011-02-23        kinaba: 	R_Lcl,   // '['
dcdd144598 2011-02-23        kinaba: 	R_Rcl,   // ']'
dcdd144598 2011-02-23        kinaba: 	R_Ncl,   // '^'
dcdd144598 2011-02-23        kinaba: 	R_Range, // '-'
dcdd144598 2011-02-23        kinaba: 	R_Lbr,   // '('
dcdd144598 2011-02-23        kinaba: 	R_Rbr,   // ')'
dcdd144598 2011-02-23        kinaba: 	R_Bar,   // '|'
dcdd144598 2011-02-23        kinaba: 	R_Star,  // '*'
dcdd144598 2011-02-23        kinaba: 	R_Plus,  // '+'
dcdd144598 2011-02-23        kinaba: 	R_Quest, // '?'
dcdd144598 2011-02-23        kinaba: 	R_End    // '\0'
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	トークンに分解
dcdd144598 2011-02-23        kinaba: //
dcdd144598 2011-02-23        kinaba: //	行頭を表す^と行末を表す$については上位層で頑張る
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: class RegLexer
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 	RegLexer( const wchar_t* pat, ulong len );
dcdd144598 2011-02-23        kinaba: 	RegToken GetToken();
dcdd144598 2011-02-23        kinaba: 	wchar_t  GetChar() { return chr_; }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	const wchar_t* pat_;
dcdd144598 2011-02-23        kinaba: 	const wchar_t* end_;
dcdd144598 2011-02-23        kinaba: 	const wchar_t* sub_;
dcdd144598 2011-02-23        kinaba: 	wchar_t        chr_;
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	トークンに分解：実装
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline RegLexer::RegLexer( const wchar_t* pat, ulong len )
dcdd144598 2011-02-23        kinaba: 	: pat_( pat )
dcdd144598 2011-02-23        kinaba: 	, end_( pat+len )
dcdd144598 2011-02-23        kinaba: 	, sub_( L"" )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegToken RegLexer::GetToken()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	const wchar_t*& x = (*sub_ ? sub_ : pat_);
dcdd144598 2011-02-23        kinaba: 	if( x == end_ ) return R_End;
dcdd144598 2011-02-23        kinaba: 	switch( *x++ )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 	case L'.': return R_Any;
dcdd144598 2011-02-23        kinaba: 	case L'[': return R_Lcl;
dcdd144598 2011-02-23        kinaba: 	case L']': return R_Rcl;
dcdd144598 2011-02-23        kinaba: 	case L'^': return R_Ncl;
dcdd144598 2011-02-23        kinaba: 	case L'-': return R_Range;
dcdd144598 2011-02-23        kinaba: 	case L'(': return R_Lbr;
dcdd144598 2011-02-23        kinaba: 	case L')': return R_Rbr;
dcdd144598 2011-02-23        kinaba: 	case L'|': return R_Bar;
dcdd144598 2011-02-23        kinaba: 	case L'*': return R_Star;
dcdd144598 2011-02-23        kinaba: 	case L'+': return R_Plus;
dcdd144598 2011-02-23        kinaba: 	case L'?': return R_Quest;
dcdd144598 2011-02-23        kinaba: 	case L'\\': if( x==end_ ) return R_End; switch( *x++ ) {
dcdd144598 2011-02-23        kinaba: 		case L't': chr_=L'\t';            return R_Char;
dcdd144598 2011-02-23        kinaba: 		case L'w': sub_=L"[0-9a-zA-Z_]";  return GetToken();
dcdd144598 2011-02-23        kinaba: 		case L'W': sub_=L"[^0-9a-zA-Z_]"; return GetToken();
dcdd144598 2011-02-23        kinaba: 		case L'd': sub_=L"[0-9]";         return GetToken();
dcdd144598 2011-02-23        kinaba: 		case L'D': sub_=L"[^0-9]";        return GetToken();
dcdd144598 2011-02-23        kinaba: 		case L's': sub_=L"[\t ]";         return GetToken();
dcdd144598 2011-02-23        kinaba: 		case L'S': sub_=L"[^\t ]";        return GetToken();
dcdd144598 2011-02-23        kinaba: 		} // fall through...
dcdd144598 2011-02-23        kinaba: 	default:
dcdd144598 2011-02-23        kinaba: 		chr_ = *(x-1);
dcdd144598 2011-02-23        kinaba: 		return R_Char;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	構文木のノードに振られる値の種類
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: enum RegType
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	N_Char,     // 普通の文字 (ch)
dcdd144598 2011-02-23        kinaba: 	N_Class,    // [...] など (cls)
dcdd144598 2011-02-23        kinaba: 	N_Concat,   // 連接       (left, right)
dcdd144598 2011-02-23        kinaba: 	N_Or,       // |          (left, right)
dcdd144598 2011-02-23        kinaba: 	N_Closure,  // *          (left)
dcdd144598 2011-02-23        kinaba: 	N_Closure1, // +          (left)
dcdd144598 2011-02-23        kinaba: 	N_01,       // ?          (left)
dcdd144598 2011-02-23        kinaba: 	N_Empty     // 空         (--)
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: struct RegClass
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	struct OneRange
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		wchar_t stt;
dcdd144598 2011-02-23        kinaba: 		wchar_t end;
dcdd144598 2011-02-23        kinaba: 	};
dcdd144598 2011-02-23        kinaba: 	OneRange      range;
dcdd144598 2011-02-23        kinaba: 	aptr<RegClass> next;
dcdd144598 2011-02-23        kinaba: 	RegClass( wchar_t s, wchar_t e, RegClass* n )
dcdd144598 2011-02-23        kinaba: 		{ aptr<RegClass> an(n); range.stt=s, range.end=e, next=an; }
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: struct RegNode
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	RegType           type; // このノードの種類
dcdd144598 2011-02-23        kinaba: 	wchar_t             ch; // 文字
dcdd144598 2011-02-23        kinaba: 	aptr<RegClass>     cls; // 文字集合
dcdd144598 2011-02-23        kinaba: 	bool            cmpcls; // ↑補集合かどうか
dcdd144598 2011-02-23        kinaba: 	dptr<RegNode>     left; // 左の子
dcdd144598 2011-02-23        kinaba: 	dptr<RegNode>    right; // 右の子
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	構文木作成
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: class RegParser
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 	RegParser( const unicode* pat );
dcdd144598 2011-02-23        kinaba: 	RegNode* root() { return root_.get(); }
dcdd144598 2011-02-23        kinaba: 	bool err() { return err_; }
dcdd144598 2011-02-23        kinaba: 	bool isHeadType() const { return isHeadType_; }
dcdd144598 2011-02-23        kinaba: 	bool isTailType() const { return isTailType_; }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	RegNode* make_empty_leaf();
dcdd144598 2011-02-23        kinaba: 	RegNode* make_char_leaf( wchar_t c );
dcdd144598 2011-02-23        kinaba: 	RegNode* make_node( RegType t, RegNode* lft, RegNode* rht );
dcdd144598 2011-02-23        kinaba: 	void eat_token();
dcdd144598 2011-02-23        kinaba: 	RegNode* expr();
dcdd144598 2011-02-23        kinaba: 	RegNode* term();
dcdd144598 2011-02-23        kinaba: 	RegNode* factor();
dcdd144598 2011-02-23        kinaba: 	RegNode* primary();
dcdd144598 2011-02-23        kinaba: 	RegNode* reclass();
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	bool    err_;
dcdd144598 2011-02-23        kinaba: 	bool    isHeadType_;
dcdd144598 2011-02-23        kinaba: 	bool    isTailType_;
dcdd144598 2011-02-23        kinaba: 	dptr<RegNode> root_;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	RegLexer lex_;
dcdd144598 2011-02-23        kinaba: 	RegToken nextToken_;
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	構文木作成：実装
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: namespace { static int tmp; }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline RegParser::RegParser( const unicode* pat )
dcdd144598 2011-02-23        kinaba: 	: err_       ( false )
dcdd144598 2011-02-23        kinaba: 	, isHeadType_( *pat==L'^' )
dcdd144598 2011-02-23        kinaba: 	, isTailType_( (tmp=my_lstrlenW(pat), tmp && pat[tmp-1]==L'$') )
dcdd144598 2011-02-23        kinaba: 	, lex_(
dcdd144598 2011-02-23        kinaba: 		(isHeadType_ ? pat+1 : pat),
dcdd144598 2011-02-23        kinaba: 		(my_lstrlenW(pat) - (isHeadType_ ? 1 : 0)
dcdd144598 2011-02-23        kinaba: 		                  - (isTailType_ ? 1 : 0)) )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	eat_token();
dcdd144598 2011-02-23        kinaba: 	root_ = expr();
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline void RegParser::eat_token()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	nextToken_ = lex_.GetToken();
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline RegNode* RegParser::make_empty_leaf()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	RegNode* node = new RegNode;
dcdd144598 2011-02-23        kinaba: 	node->type = N_Empty;
dcdd144598 2011-02-23        kinaba: 	return node;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline RegNode* RegParser::make_char_leaf( wchar_t c )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	RegNode* node = new RegNode;
dcdd144598 2011-02-23        kinaba: 	node->type = N_Char;
dcdd144598 2011-02-23        kinaba: 	node->ch   = c;
dcdd144598 2011-02-23        kinaba: 	return node;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegNode* RegParser::make_node( RegType t, RegNode* lft, RegNode* rht )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	RegNode* node = new RegNode;
dcdd144598 2011-02-23        kinaba: 	node->type = t;
dcdd144598 2011-02-23        kinaba: 	node->left = lft;
dcdd144598 2011-02-23        kinaba: 	node->right= rht;
dcdd144598 2011-02-23        kinaba: 	return node;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegNode* RegParser::reclass()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: //	CLASS   ::= '^'? CHAR (CHAR | -CHAR)*
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	bool neg = false;
dcdd144598 2011-02-23        kinaba: 	if( nextToken_ == R_Ncl )
dcdd144598 2011-02-23        kinaba: 		neg=true, eat_token();
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	RegClass* cls = NULL;
dcdd144598 2011-02-23        kinaba: 	while( nextToken_ == R_Char )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		wchar_t ch = lex_.GetChar();
dcdd144598 2011-02-23        kinaba: 		eat_token();
dcdd144598 2011-02-23        kinaba: 		if( nextToken_ == R_Range )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			eat_token();
dcdd144598 2011-02-23        kinaba: 			if( nextToken_ != R_Char )
dcdd144598 2011-02-23        kinaba: 				err_ = true;
dcdd144598 2011-02-23        kinaba: 			else
dcdd144598 2011-02-23        kinaba: 			{
dcdd144598 2011-02-23        kinaba: 				wchar_t ch2 = lex_.GetChar();
dcdd144598 2011-02-23        kinaba: 				cls = new RegClass( Min(ch,ch2), Max(ch,ch2), cls );
dcdd144598 2011-02-23        kinaba: 				eat_token();
dcdd144598 2011-02-23        kinaba: 			}
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 		else
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			cls = new RegClass( ch, ch, cls );
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	RegNode* node = new RegNode;
dcdd144598 2011-02-23        kinaba: 	node->type   = N_Class;
dcdd144598 2011-02-23        kinaba: 	aptr<RegClass> ncls(cls);
dcdd144598 2011-02-23        kinaba: 	node->cls    = ncls;
dcdd144598 2011-02-23        kinaba: 	node->cmpcls = neg;
dcdd144598 2011-02-23        kinaba: 	return node;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegNode* RegParser::primary()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: //	PRIMARY ::= CHAR
dcdd144598 2011-02-23        kinaba: //              '.'
dcdd144598 2011-02-23        kinaba: //	            '[' CLASS ']'
dcdd144598 2011-02-23        kinaba: //				'(' REGEXP ')'
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	RegNode* node;
dcdd144598 2011-02-23        kinaba: 	switch( nextToken_ )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 	case R_Char:
dcdd144598 2011-02-23        kinaba: 		node = make_char_leaf( lex_.GetChar() );
dcdd144598 2011-02-23        kinaba: 		eat_token();
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	case R_Any:{
dcdd144598 2011-02-23        kinaba: 		node         = new RegNode;
dcdd144598 2011-02-23        kinaba: 		node->type   = N_Class;
dcdd144598 2011-02-23        kinaba: 		aptr<RegClass> ncls(new RegClass( 0, 65535, NULL ));
dcdd144598 2011-02-23        kinaba: 		node->cls    = ncls;
dcdd144598 2011-02-23        kinaba: 		node->cmpcls = false;
dcdd144598 2011-02-23        kinaba: 		eat_token();
dcdd144598 2011-02-23        kinaba: 		}break;
dcdd144598 2011-02-23        kinaba: 	case R_Lcl:
dcdd144598 2011-02-23        kinaba: 		eat_token();
dcdd144598 2011-02-23        kinaba: 		node = reclass();
dcdd144598 2011-02-23        kinaba: 		if( nextToken_ == R_Rcl )
dcdd144598 2011-02-23        kinaba: 			eat_token();
dcdd144598 2011-02-23        kinaba: 		else
dcdd144598 2011-02-23        kinaba: 			err_ = true;
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	case R_Lbr:
dcdd144598 2011-02-23        kinaba: 		eat_token();
dcdd144598 2011-02-23        kinaba: 		node = expr();
dcdd144598 2011-02-23        kinaba: 		if( nextToken_ == R_Rbr )
dcdd144598 2011-02-23        kinaba: 			eat_token();
dcdd144598 2011-02-23        kinaba: 		else
dcdd144598 2011-02-23        kinaba: 			err_ = true;
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	default:
dcdd144598 2011-02-23        kinaba: 		node = make_empty_leaf();
dcdd144598 2011-02-23        kinaba: 		err_ = true;
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 	return node;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegNode* RegParser::factor()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: //	FACTOR  ::= PRIMARY
dcdd144598 2011-02-23        kinaba: //	            PRIMARY '*'
dcdd144598 2011-02-23        kinaba: //			    PRIMARY '+'
dcdd144598 2011-02-23        kinaba: //			    PRIMARY '?'
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	RegNode* node = primary();
dcdd144598 2011-02-23        kinaba: 	switch( nextToken_ )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 	case R_Star: node=make_node(N_Closure,node,NULL); eat_token();break;
dcdd144598 2011-02-23        kinaba: 	case R_Plus: node=make_node(N_Closure1,node,NULL);eat_token();break;
dcdd144598 2011-02-23        kinaba: 	case R_Quest:node=make_node(N_01,node,NULL );     eat_token();break;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 	return node;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegNode* RegParser::term()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: //	TERM    ::= EMPTY
dcdd144598 2011-02-23        kinaba: //	            FACTOR TERM
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	if( nextToken_ == R_End )
dcdd144598 2011-02-23        kinaba: 		return make_empty_leaf();
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	RegNode* node = factor();
dcdd144598 2011-02-23        kinaba: 	if( nextToken_==R_Lbr || nextToken_==R_Lcl
dcdd144598 2011-02-23        kinaba: 	 || nextToken_==R_Char|| nextToken_==R_Any )
dcdd144598 2011-02-23        kinaba: 		node = make_node( N_Concat, node, term() );
dcdd144598 2011-02-23        kinaba: 	return node;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegNode* RegParser::expr()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: //	REGEXP  ::= TERM
dcdd144598 2011-02-23        kinaba: //	            TERM '|' REGEXP
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	RegNode* node = term();
dcdd144598 2011-02-23        kinaba: 	if( nextToken_ == R_Bar )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		eat_token();
dcdd144598 2011-02-23        kinaba: 		node = make_node( N_Or, node, expr() );
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 	return node;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	状態遷移
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: struct RegTrans
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	enum {
dcdd144598 2011-02-23        kinaba: 		Epsilon,
dcdd144598 2011-02-23        kinaba: 		Class,
dcdd144598 2011-02-23        kinaba: 		Char
dcdd144598 2011-02-23        kinaba: 	}              type;
dcdd144598 2011-02-23        kinaba: 	aptr<RegClass>  cls; // この文字集合
dcdd144598 2011-02-23        kinaba: 	                     // orEpsilon が来たら
dcdd144598 2011-02-23        kinaba: 	bool         cmpcls;
dcdd144598 2011-02-23        kinaba: 	int              to; // 状態番号toの状態へ遷移
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	aptr<RegTrans> next; // 連結リスト
dcdd144598 2011-02-23        kinaba: /*
dcdd144598 2011-02-23        kinaba: 	template<class Cmp>
dcdd144598 2011-02-23        kinaba: 	bool match_i( wchar_t c, Cmp )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		c = Cmp::map(c);
dcdd144598 2011-02-23        kinaba: 		RegClass* p = cls.get();
dcdd144598 2011-02-23        kinaba: 		while( p )
dcdd144598 2011-02-23        kinaba: 			if( Cmp::map(p->range.stt)<=c && c<=Cmp::map(p->range.end) )
dcdd144598 2011-02-23        kinaba: 				return true;
dcdd144598 2011-02-23        kinaba: 			else
dcdd144598 2011-02-23        kinaba: 				p = p->next.get();
dcdd144598 2011-02-23        kinaba: 		return false;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: */
dcdd144598 2011-02-23        kinaba: 	bool match_c( wchar_t c )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		for( RegClass* p=cls.get(); p; p=p->next.get() )
dcdd144598 2011-02-23        kinaba: 			if( p->range.stt<=c && c<=p->range.end )
dcdd144598 2011-02-23        kinaba: 				return true;
dcdd144598 2011-02-23        kinaba: 		return false;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	bool match_i( wchar_t c )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		c = IgnoreCase::map(c);
dcdd144598 2011-02-23        kinaba: 		for( RegClass* p=cls.get(); p; p=p->next.get() )
dcdd144598 2011-02-23        kinaba: 			if( IgnoreCase::map(p->range.stt)<=c
dcdd144598 2011-02-23        kinaba: 			 && c<=IgnoreCase::map(p->range.end) )
dcdd144598 2011-02-23        kinaba: 				return true;
dcdd144598 2011-02-23        kinaba: 		return false;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	bool match( wchar_t c, bool caseS )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		bool m = caseS ? match_c( c ) : match_i( c );
dcdd144598 2011-02-23        kinaba: 		return cmpcls ? !m : m;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	構文木->NFA変換
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: class RegNFA
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: public:
dcdd144598 2011-02-23        kinaba: 	RegNFA( const wchar_t* pat );
dcdd144598 2011-02-23        kinaba: 	~RegNFA();
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	int match( const wchar_t* str, int len, bool caseS );
dcdd144598 2011-02-23        kinaba: 	bool isHeadType() const { return parser.isHeadType(); }
dcdd144598 2011-02-23        kinaba: 	bool isTailType() const { return parser.isTailType(); }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	// マッチング処理
dcdd144598 2011-02-23        kinaba: 	int dfa_match( const wchar_t* str, int len, bool caseS );
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	struct st_ele { int st, ps; };
dcdd144598 2011-02-23        kinaba: 	void push(storage<st_ele>& stack, int curSt, int pos);
dcdd144598 2011-02-23        kinaba: 	st_ele pop(storage<st_ele>& stack);
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	void add_transition( int from, wchar_t ch, int to );
dcdd144598 2011-02-23        kinaba: 	void add_transition( int from, aptr<RegClass> cls, bool cmp, int to );
dcdd144598 2011-02-23        kinaba: 	void add_e_transition( int from, int to );
dcdd144598 2011-02-23        kinaba: 	int gen_state();
dcdd144598 2011-02-23        kinaba: 	void gen_nfa( int entry, RegNode* t, int exit );
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: private:
dcdd144598 2011-02-23        kinaba: 	RegParser      parser;
dcdd144598 2011-02-23        kinaba: 	storage<RegTrans*> st;
dcdd144598 2011-02-23        kinaba: 	int      start, final;
dcdd144598 2011-02-23        kinaba: };
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegNFA::RegNFA( const wchar_t* pat )
dcdd144598 2011-02-23        kinaba: 	: parser( pat )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	start = gen_state();
dcdd144598 2011-02-23        kinaba: 	final = gen_state();
dcdd144598 2011-02-23        kinaba: 	gen_nfa( start, parser.root(), final );
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline RegNFA::~RegNFA()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	for( ulong i=0,e=st.size(); i<e; ++i )
dcdd144598 2011-02-23        kinaba: 		delete st[i];
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline void RegNFA::add_transition
dcdd144598 2011-02-23        kinaba: 	( int from, aptr<RegClass> cls, bool cmp, int to )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	RegTrans* x = new RegTrans;
dcdd144598 2011-02-23        kinaba: 	aptr<RegTrans> nn( st[from] );
dcdd144598 2011-02-23        kinaba: 	x->next  = nn;
dcdd144598 2011-02-23        kinaba: 	x->to    = to;
dcdd144598 2011-02-23        kinaba: 	x->type  = RegTrans::Class;
dcdd144598 2011-02-23        kinaba: 	x->cls   = cls;
dcdd144598 2011-02-23        kinaba: 	x->cmpcls= cmp;
dcdd144598 2011-02-23        kinaba: 	st[from] = x;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline void RegNFA::add_transition( int from, wchar_t ch, int to )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	aptr<RegClass> cls(new RegClass(ch,ch,NULL));
dcdd144598 2011-02-23        kinaba: 	add_transition( from, cls, false, to );
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline void RegNFA::add_e_transition( int from, int to )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	RegTrans* x = new RegTrans;
dcdd144598 2011-02-23        kinaba: 	aptr<RegTrans> nn( st[from] );
dcdd144598 2011-02-23        kinaba: 	x->next  = nn;
dcdd144598 2011-02-23        kinaba: 	x->to    = to;
dcdd144598 2011-02-23        kinaba: 	x->type  = RegTrans::Epsilon;
dcdd144598 2011-02-23        kinaba: 	st[from] = x;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: inline int RegNFA::gen_state()
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	st.Add( NULL );
dcdd144598 2011-02-23        kinaba: 	return st.size() - 1;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: void RegNFA::gen_nfa( int entry, RegNode* t, int exit )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	switch( t->type )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 	case N_Char:
dcdd144598 2011-02-23        kinaba: 		//         ch
dcdd144598 2011-02-23        kinaba: 		//  entry ----> exit
dcdd144598 2011-02-23        kinaba: 		add_transition( entry, t->ch, exit );
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	case N_Class:
dcdd144598 2011-02-23        kinaba: 		//         cls
dcdd144598 2011-02-23        kinaba: 		//  entry -----> exit
dcdd144598 2011-02-23        kinaba: 		add_transition( entry, t->cls, t->cmpcls, exit );
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	case N_Concat: {
dcdd144598 2011-02-23        kinaba: 		//         left         right
dcdd144598 2011-02-23        kinaba: 		//  entry ------> step -------> exit
dcdd144598 2011-02-23        kinaba: 		int step = gen_state();
dcdd144598 2011-02-23        kinaba: 		gen_nfa( entry, t->left.get(), step );
dcdd144598 2011-02-23        kinaba: 		gen_nfa( step, t->right.get(), exit );
dcdd144598 2011-02-23        kinaba: 		} break;
dcdd144598 2011-02-23        kinaba: 	case N_Or:
dcdd144598 2011-02-23        kinaba: 		//          left
dcdd144598 2011-02-23        kinaba: 		//         ------>
dcdd144598 2011-02-23        kinaba: 		//  entry ------->--> exit
dcdd144598 2011-02-23        kinaba: 		//          right
dcdd144598 2011-02-23        kinaba: 		gen_nfa( entry, t->left.get(), exit );
dcdd144598 2011-02-23        kinaba: 		gen_nfa( entry, t->right.get(), exit );
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	case N_Closure:
dcdd144598 2011-02-23        kinaba: 		//                       e
dcdd144598 2011-02-23        kinaba: 		//         e          <------        e
dcdd144598 2011-02-23        kinaba: 		//  entry ---> before ------> after ---> exit
dcdd144598 2011-02-23        kinaba: 		//    |                left                ^
dcdd144598 2011-02-23        kinaba: 		//    >------->------------------->------>-|
dcdd144598 2011-02-23        kinaba: 		//                      e
dcdd144598 2011-02-23        kinaba: 	case N_Closure1: {
dcdd144598 2011-02-23        kinaba: 		//                       e
dcdd144598 2011-02-23        kinaba: 		//         e          <------        e
dcdd144598 2011-02-23        kinaba: 		//  entry ---> before ------> after ---> exit
dcdd144598 2011-02-23        kinaba: 		//                     left
dcdd144598 2011-02-23        kinaba: 		int before = gen_state();
dcdd144598 2011-02-23        kinaba: 		int after = gen_state();
dcdd144598 2011-02-23        kinaba: 		add_e_transition( entry, before );
dcdd144598 2011-02-23        kinaba: 		add_e_transition( after, exit );
dcdd144598 2011-02-23        kinaba: 		add_e_transition( after, before );
dcdd144598 2011-02-23        kinaba: 		gen_nfa( before, t->left.get(), after );
dcdd144598 2011-02-23        kinaba: 		if( t->type != N_Closure1 )
dcdd144598 2011-02-23        kinaba: 			add_e_transition( entry, exit );
dcdd144598 2011-02-23        kinaba: 		} break;
dcdd144598 2011-02-23        kinaba: 	case N_01:
dcdd144598 2011-02-23        kinaba: 		//           e
dcdd144598 2011-02-23        kinaba: 		//        ------>
dcdd144598 2011-02-23        kinaba: 		//  entry ------> exit
dcdd144598 2011-02-23        kinaba: 		//         left
dcdd144598 2011-02-23        kinaba: 		add_e_transition( entry, exit );
dcdd144598 2011-02-23        kinaba: 		gen_nfa( entry, t->left.get(), exit );
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	case N_Empty:
dcdd144598 2011-02-23        kinaba: 		//         e
dcdd144598 2011-02-23        kinaba: 		//  entry ---> exit
dcdd144598 2011-02-23        kinaba: 		add_e_transition( entry, exit );
dcdd144598 2011-02-23        kinaba: 		break;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	マッチング
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: void RegNFA::push(storage<st_ele>& stack, int curSt, int pos)
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	// ε無限ループ防止策。同じ状態には戻らないように…
dcdd144598 2011-02-23        kinaba: 	for( int i=stack.size()-1; i>=0; --i )
dcdd144598 2011-02-23        kinaba: 		if( stack[i].ps != pos )
dcdd144598 2011-02-23        kinaba: 			break;
dcdd144598 2011-02-23        kinaba: 		else if( stack[i].st == curSt )
dcdd144598 2011-02-23        kinaba: 			return;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	st_ele nw = {curSt,pos};
dcdd144598 2011-02-23        kinaba: 	stack.Add( nw );
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RegNFA::st_ele RegNFA::pop(storage<st_ele>& stack)
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	st_ele se = stack[stack.size()-1];
dcdd144598 2011-02-23        kinaba: 	stack.ForceSize( stack.size()-1 );
dcdd144598 2011-02-23        kinaba: 	return se;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: int RegNFA::match( const wchar_t* str, int len, bool caseS )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	if( parser.err() )
dcdd144598 2011-02-23        kinaba: 		return -1; // エラー状態なのでmatchとかできません
dcdd144598 2011-02-23        kinaba: 	//if( st.size() <= 31 )
dcdd144598 2011-02-23        kinaba: 	//	return dfa_match(str,len,caseS); // 状態数が少なければDFAを使う、かも
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	int matchpos = -1;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	storage<st_ele> stack;
dcdd144598 2011-02-23        kinaba: 	push(stack, start, 0);
dcdd144598 2011-02-23        kinaba: 	while( stack.size() > 0 )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		// スタックからpop
dcdd144598 2011-02-23        kinaba: 		st_ele se = pop(stack);
dcdd144598 2011-02-23        kinaba: 		int curSt = se.st;
dcdd144598 2011-02-23        kinaba: 		int   pos = se.ps;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 		// マッチ成功してたら記録
dcdd144598 2011-02-23        kinaba: 		if( curSt == final ) // 1==終状態
dcdd144598 2011-02-23        kinaba: 			if( matchpos < pos )
dcdd144598 2011-02-23        kinaba: 				matchpos = pos;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 		// さらに先の遷移を調べる
dcdd144598 2011-02-23        kinaba: 		if( matchpos < len )
dcdd144598 2011-02-23        kinaba: 			for( RegTrans* tr=st[curSt]; tr!=NULL; tr=tr->next.get() )
dcdd144598 2011-02-23        kinaba: 				if( tr->type == RegTrans::Epsilon )
dcdd144598 2011-02-23        kinaba: 					push(stack, tr->to, pos);
dcdd144598 2011-02-23        kinaba: 				else if( pos<len && tr->match( str[pos], caseS ) )
dcdd144598 2011-02-23        kinaba: 					push(stack, tr->to, pos+1);
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	return matchpos;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: int RegNFA::dfa_match( const wchar_t* str, int len, bool caseS )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	int matchpos = -1;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	unsigned int StateSet = (1<<start);
dcdd144598 2011-02-23        kinaba: 	for(int pos=0; StateSet; ++pos)
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		// ε-closure
dcdd144598 2011-02-23        kinaba: 		for(uint DifSS=StateSet; DifSS;)
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			unsigned int NewSS = 0;
dcdd144598 2011-02-23        kinaba: 			for(int s=0; (1u<<s)<=DifSS; ++s)
dcdd144598 2011-02-23        kinaba: 				if( (1u<<s) & DifSS )
dcdd144598 2011-02-23        kinaba: 					for( RegTrans* tr=st[s]; tr!=NULL; tr=tr->next.get() )
dcdd144598 2011-02-23        kinaba: 						if( tr->type == RegTrans::Epsilon )
dcdd144598 2011-02-23        kinaba: 						 NewSS |= 1u << tr->to;
dcdd144598 2011-02-23        kinaba: 			DifSS = (NewSS|StateSet) ^ StateSet;
dcdd144598 2011-02-23        kinaba: 			StateSet |= NewSS;
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 		// 受理状態を含んでるかどうか判定
dcdd144598 2011-02-23        kinaba: 		if( StateSet & (1<<final) )
dcdd144598 2011-02-23        kinaba: 			matchpos = pos;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 		// 文字列の終わりに達した
dcdd144598 2011-02-23        kinaba: 		if( pos == len )
dcdd144598 2011-02-23        kinaba: 			break;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 		// 遷移
dcdd144598 2011-02-23        kinaba: 		unsigned int NewSS = 0;
dcdd144598 2011-02-23        kinaba: 		for(int s=0; (1u<<s)<=StateSet; ++s)
dcdd144598 2011-02-23        kinaba: 			if( (1u<<s) & StateSet )
dcdd144598 2011-02-23        kinaba: 				for( RegTrans* tr=st[s]; tr!=NULL; tr=tr->next.get() )
dcdd144598 2011-02-23        kinaba: 					if( tr->type!=RegTrans::Epsilon && tr->match(str[pos], caseS) )
dcdd144598 2011-02-23        kinaba: 					 NewSS |= 1u << tr->to;
dcdd144598 2011-02-23        kinaba: 		StateSet = NewSS;
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	return matchpos;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //////////////////////////////////////////////////////////////////////
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: bool reg_match( const wchar_t* pat, const wchar_t* str, bool caseS )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	int len = my_lstrlenW(str);
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	RegNFA re( pat );
dcdd144598 2011-02-23        kinaba: 	return len == re.match( str, len, caseS );
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: //@{
dcdd144598 2011-02-23        kinaba: //	GreenPad用検索オブジェクト
dcdd144598 2011-02-23        kinaba: //@}
dcdd144598 2011-02-23        kinaba: //=========================================================================
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: RSearch::RSearch( const unicode* key, bool caseS, bool down )
dcdd144598 2011-02-23        kinaba: 	: re_    ( new RegNFA(key) )
dcdd144598 2011-02-23        kinaba: 	, caseS_ ( caseS )
dcdd144598 2011-02-23        kinaba: 	, down_  ( down )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: bool RSearch::Search(
dcdd144598 2011-02-23        kinaba: 	const unicode* str, ulong len, ulong stt, ulong* mbg, ulong* med )
dcdd144598 2011-02-23        kinaba: {
dcdd144598 2011-02-23        kinaba: 	if( down_ && re_->isHeadType() && stt>0 )
dcdd144598 2011-02-23        kinaba: 		return false;
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	const int d = (down_ ? 1 : -1);
dcdd144598 2011-02-23        kinaba: 	      int s = (!down_ && re_->isHeadType() ? 0 : stt);
dcdd144598 2011-02-23        kinaba: 	const int e = (down_ ? (re_->isHeadType() ? 1 : (long)len) : -1);
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	for( ; s!=e; s+=d )
dcdd144598 2011-02-23        kinaba: 	{
dcdd144598 2011-02-23        kinaba: 		const int L = re_->match( str+s, len-s, caseS_ );
dcdd144598 2011-02-23        kinaba: 		if( L > 0 )
dcdd144598 2011-02-23        kinaba: 		{
dcdd144598 2011-02-23        kinaba: 			if( re_->isTailType() && L!=static_cast<int>(len-s) )
dcdd144598 2011-02-23        kinaba: 				continue;
dcdd144598 2011-02-23        kinaba: 			*mbg = static_cast<ulong>(s);
dcdd144598 2011-02-23        kinaba: 			*med = static_cast<ulong>(s+L);
dcdd144598 2011-02-23        kinaba: 			return true;
dcdd144598 2011-02-23        kinaba: 		}
dcdd144598 2011-02-23        kinaba: 	}
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: 	return false;
dcdd144598 2011-02-23        kinaba: }
dcdd144598 2011-02-23        kinaba: 
dcdd144598 2011-02-23        kinaba: