1261 lines
46 KiB
C++
1261 lines
46 KiB
C++
#include "stdafx.h"
|
|
#include ".\RexAlgorithm.h"
|
|
#pragma warning(disable:4786)
|
|
#pragma warning(disable:4503)
|
|
|
|
#include <iostream>
|
|
#include <bitset>
|
|
#include <set>
|
|
#include <map>
|
|
#include <string>
|
|
#include <algorithm>
|
|
#include <vector>
|
|
#include <utility>
|
|
#include <fstream>
|
|
using namespace std;
|
|
|
|
typedef bitset<256> REXA_CharSet;
|
|
typedef int REXA_StateId;
|
|
|
|
template<class TSet>
|
|
struct REXA_LessSet{
|
|
bool operator()(const TSet& rTSet1, const TSet& rTSet2)const
|
|
{
|
|
if( rTSet1==rTSet2 ){
|
|
return false;
|
|
}
|
|
for(int i=0;i<rTSet1.size();i++){
|
|
if( rTSet1[i]!=rTSet2[i] )
|
|
return rTSet1[i]<rTSet2[i];
|
|
}
|
|
return false;
|
|
}
|
|
};
|
|
typedef REXA_LessSet<REXA_CharSet> REXA_LessCharSet;
|
|
typedef set<REXA_CharSet,REXA_LessCharSet> REXA_CharSetSet;
|
|
|
|
|
|
// State and Translationtable
|
|
struct REXA_NDFAState;
|
|
|
|
struct REXA_StateSet : public set<const struct REXA_NDFAState*>
|
|
{
|
|
bool IsAccepting ()const;
|
|
};
|
|
|
|
typedef vector<REXA_StateSet> TransitionVector;
|
|
|
|
|
|
|
|
struct REXA_NDFATransition{
|
|
|
|
REXA_NDFATransition(const REXA_CharSet& m_rTransChars,REXA_NDFAState* pStateNext)
|
|
:m_transChars(m_rTransChars),m_nextState(pStateNext)
|
|
{
|
|
}
|
|
REXA_NDFATransition(const char* pcszChars=0,REXA_NDFAState* pNextState=0)
|
|
{
|
|
if(!pcszChars || strlen(pcszChars)==0 ){
|
|
m_bIsMute=true;
|
|
return;
|
|
}
|
|
const unsigned char* pucszChars= (const unsigned char*)pcszChars;
|
|
m_nextState= pNextState;
|
|
while( *pucszChars ){
|
|
m_transChars[*pucszChars++]= true;
|
|
}
|
|
}
|
|
REXA_CharSet m_transChars;
|
|
REXA_NDFAState* m_nextState;
|
|
bool m_bIsMute;
|
|
};
|
|
struct REXA_NDFAState{
|
|
REXA_NDFAState(int id=0,bool isAccepting=false)
|
|
:m_id(id),
|
|
m_nAnswer(REXA_DFAState::eNoAnswer),
|
|
m_isAccepting(isAccepting)
|
|
{
|
|
}
|
|
|
|
static void CollectStates (const REXA_NDFAState* pState,
|
|
set<const REXA_NDFAState*>& rsetStates);
|
|
static void CollectStates (REXA_NDFAState* pState,
|
|
set<REXA_NDFAState*>& rsetStates);
|
|
|
|
static REXA_NDFAState* CopyStates (REXA_NDFAState* pState,
|
|
map<REXA_NDFAState*,REXA_NDFAState*>& rMapStates);
|
|
REXA_NDFAState* Clone ();
|
|
void DeleteAll ();
|
|
|
|
int m_id;
|
|
int m_nAnswer;
|
|
bool m_isAccepting;
|
|
vector<REXA_NDFATransition> m_transitions;
|
|
|
|
};
|
|
struct REXA_TranslatingTable{
|
|
typedef map< REXA_StateSet,TransitionVector > TranslationMap;
|
|
typedef map<const REXA_NDFAState*,int> MapStateOccurrenceCount;
|
|
|
|
REXA_TranslatingTable (const REXA_NDFAState* pStartState);
|
|
|
|
void ComputeOccCounts();
|
|
int GetAnswerCode (const REXA_StateSet& rSet)const;
|
|
|
|
vector<REXA_CharSet> m_vecCharsets;
|
|
const REXA_NDFAState* m_pStartState;
|
|
TranslationMap m_mapTransitions;
|
|
|
|
MapStateOccurrenceCount m_mapStateOccurrenceCount;
|
|
|
|
private:
|
|
vector<REXA_CharSet>
|
|
CharsetToVector (const REXA_CharSetSet& rCharSetSet);
|
|
|
|
set<REXA_CharSet,REXA_LessCharSet>
|
|
ComputeDisjointCharSets (REXA_CharSetSet& rCharSets);
|
|
|
|
void GenerateTranslationTable ( set<const REXA_NDFAState*>& rSetState);
|
|
|
|
void CollectCharSets ( const REXA_NDFAState* pCurState,
|
|
set<int>& rVisitedStates,REXA_CharSetSet& rCharSets);
|
|
};
|
|
|
|
class REXA_NDFAToTable{
|
|
public:
|
|
void NDFA_To_Table (REXA_NDFAState* pStartState,
|
|
REXA_TranslatingTable& rTable);
|
|
|
|
static vector<REXA_CharSet>
|
|
CharsetToVector (const REXA_CharSetSet& rCharSetSet);
|
|
|
|
set<REXA_CharSet,REXA_LessCharSet>
|
|
ComputeDisjointCharSets (REXA_CharSetSet& rCharSets);
|
|
|
|
static void GenerateTranslationTable ( map<int,REXA_NDFAState*>& rMapIdState,
|
|
REXA_TranslatingTable& rTable);
|
|
|
|
|
|
static void CollectCharSets ( REXA_NDFAState* pCurState,
|
|
set<int>& rVisitedStates,
|
|
REXA_CharSetSet& rCharSets);
|
|
};
|
|
|
|
class REXA_NDFAToDfa{
|
|
public:
|
|
typedef map<REXA_NDFAState*,int> MapStateOccurrenceCount;
|
|
|
|
REXA_NDFAToDfa (const REXA_TranslatingTable& rTable,char cEos);
|
|
REXA_DFAState* TableToDfaStates();
|
|
private:
|
|
REXA_DFAState* CreateDfaStates(
|
|
const REXA_StateSet& rStateSet,
|
|
map<REXA_StateSet,REXA_DFAState*>& rMapStateSetDFAState);
|
|
|
|
const REXA_TranslatingTable& m_rTable;
|
|
unsigned char m_cEos;
|
|
};
|
|
|
|
class REXA_Scanner{
|
|
friend class REXA_ParserImpl;
|
|
friend class REXA_Exception;
|
|
public:
|
|
//constructor,desctructor,typedefs
|
|
REXA_Scanner(const char* pcszToParse="") {SetSource(pcszToParse);}
|
|
private:
|
|
void SetSource(const char* pcszSrc){
|
|
m_pcszToParse= pcszSrc;m_pTokBeg= pcszSrc;
|
|
m_pTokEnd= pcszSrc;m_eLastSymbol= eEof;
|
|
}
|
|
//operations
|
|
REXA_ESymbols operator() ();
|
|
|
|
int GetLastSymbol (){return m_eLastSymbol;}
|
|
static string GetSymbolString (REXA_ESymbols eRegexpSymbol);
|
|
void AdvanceAndMatch (REXA_ESymbols eSymbol);
|
|
void Match (REXA_ESymbols eSymbol);
|
|
REXA_BegEnd GetToken (){return make_pair(m_pTokBeg,m_pTokEnd);}
|
|
const char* GetSource (){return m_pcszToParse;}
|
|
REXA_CharSet GetCharSet (){return m_charSet;}
|
|
char GetChar (const char*& rpFrom,bool& rbIsEscape);
|
|
void AddRange ( unsigned char cFirst,
|
|
unsigned char cLast,
|
|
REXA_CharSet& rCharSet);
|
|
const char* SkipWhiteSpace ();
|
|
const char* m_pcszToParse;
|
|
const char* m_pTokBeg;
|
|
const char* m_pTokEnd;
|
|
REXA_CharSet m_charSet;
|
|
string m_strLiteral;
|
|
REXA_ESymbols m_eLastSymbol;
|
|
};
|
|
|
|
class REXA_ParserImpl{
|
|
public:
|
|
REXA_ParserImpl (char cEos=0)
|
|
:m_cEos(cEos),m_eAtomSet(eCharSet|eIdent|eLParen),
|
|
m_nStateIdMax(0)
|
|
{
|
|
}
|
|
~REXA_ParserImpl();
|
|
const REXA_NDFAState* ParseRegExp (string strRegExp);
|
|
bool ParseRegExpDefinition (string strRegExpDefiniton,int nAnswer);
|
|
|
|
char m_cEos;
|
|
map<string,REXA_NDFAState*> m_mapNamedStates;
|
|
private:
|
|
// grammar related functions
|
|
void NamedRegExp (int nAnswer);
|
|
REXA_NDFAState* RegExp ();
|
|
REXA_NDFAState* Term ();
|
|
REXA_NDFAState* Factor ();
|
|
REXA_NDFAState* Atom ();
|
|
REXA_NDFAState* Name (REXA_BegEnd nameToFind);
|
|
REXA_NDFAState* ParseCharSet (REXA_CharSet& rCharSet);
|
|
//NDFA-Automtaton constructors
|
|
REXA_NDFAState* Concat (REXA_NDFAState* pState0,REXA_NDFAState* pState1);
|
|
REXA_NDFAState* Union (REXA_NDFAState* pState0,REXA_NDFAState* pState1);
|
|
REXA_NDFAState* MakeStar (REXA_NDFAState* pState);
|
|
REXA_NDFAState* MakePlus (REXA_NDFAState* pState);
|
|
REXA_NDFAState* MakeOptional (REXA_NDFAState* pState);
|
|
REXA_NDFAState* MakeIgnoreCase (REXA_NDFAState* pState);
|
|
//helper functions for grammar related functions
|
|
void InsertNamedState( REXA_BegEnd name,
|
|
REXA_NDFAState* pState,int nAnwer);
|
|
|
|
vector<pair<REXA_NDFAState*,REXA_NDFATransition> >
|
|
CollectAcceptingTransitions(REXA_NDFAState* pState);
|
|
vector<REXA_NDFAState*> CollectAcceptingStates(REXA_NDFAState* pState);
|
|
void CollectStates(
|
|
REXA_NDFAState* pState,
|
|
set<REXA_NDFAState*>& rsetStates);
|
|
|
|
REXA_NDFAState* CloneNDFA(REXA_NDFAState* pToClone);
|
|
REXA_NDFAState* GetNewNDFAState(int id=0,bool isAccepting=false);
|
|
|
|
int NextStateId ();
|
|
|
|
REXA_Scanner m_scanner;
|
|
const int m_eAtomSet;
|
|
int m_nStateIdMax;
|
|
|
|
vector<REXA_NDFAState*> m_vecAllStates;
|
|
};
|
|
|
|
|
|
static struct SymbolString{
|
|
REXA_ESymbols eSym;
|
|
const char* strSym;
|
|
}g_symbolStrings[]={
|
|
{ eEof, "end of string" },
|
|
{ eIllegal, "illegal character" },
|
|
{ eStar, "*" },
|
|
{ ePlus, "+" },
|
|
{ eAssign, "=" },
|
|
{ eOpt, "?" },
|
|
{ eAlternative,"|" },
|
|
{ eCharSet, "[<characters>]" },
|
|
{ eLParen, "(" },
|
|
{ eRParen, ")" }
|
|
};
|
|
|
|
//-------------------------------------------------------------------------------
|
|
REXA_Exception::REXA_Exception(
|
|
const char* pPos,
|
|
const char* pRegExp,
|
|
string strMsg)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
m_strErrMsg= strMsg;
|
|
m_nErrPos= pPos-pRegExp;
|
|
}
|
|
//-------------------------------------------------------------------------------
|
|
REXA_Exception::REXA_Exception(
|
|
REXA_ESymbols eExpectedSymbol,
|
|
REXA_BegEnd token,
|
|
const char* pRegExp,
|
|
string strMsg)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
|
|
m_strErrMsg= REXA_Scanner::GetSymbolString(eExpectedSymbol)
|
|
+ " expected\r\n ";
|
|
m_nErrPos= token.first - pRegExp;
|
|
}
|
|
//-------------------------------------------------------------------------------
|
|
string REXA_Scanner::GetSymbolString (REXA_ESymbols eRegexpSymbol)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
for(int i=0;i<sizeof(g_symbolStrings)/sizeof(SymbolString);i++){
|
|
if( g_symbolStrings[i].eSym==eRegexpSymbol ){
|
|
return g_symbolStrings[i].strSym;
|
|
}
|
|
}
|
|
return "";
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------
|
|
const char* REXA_Scanner::SkipWhiteSpace ()
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
const char* pCur= m_pTokEnd;
|
|
while(isspace(*pCur))
|
|
pCur++;
|
|
return pCur;
|
|
}
|
|
|
|
//------------------------------------------------------------------------------
|
|
void REXA_Scanner::Match (REXA_ESymbols eSymbol)
|
|
//------------------------------------------------------------------------------
|
|
{
|
|
if( eSymbol!=m_eLastSymbol ){
|
|
throw REXA_Exception(eSymbol,GetToken(),m_pcszToParse);
|
|
}
|
|
}
|
|
//------------------------------------------------------------------------------
|
|
void REXA_Scanner::AdvanceAndMatch (REXA_ESymbols eSymbol)
|
|
//------------------------------------------------------------------------------
|
|
{
|
|
if( eSymbol!=operator()() ){
|
|
throw REXA_Exception(eSymbol,GetToken(),m_pcszToParse);
|
|
}
|
|
}
|
|
//------------------------------------------------------------------------------
|
|
char REXA_Scanner::GetChar(const char*& rpFrom,bool& rbIsEscape)
|
|
//------------------------------------------------------------------------------
|
|
{
|
|
rbIsEscape= false;
|
|
if( *rpFrom=='\0' ) return '\0';
|
|
char c;
|
|
if( *rpFrom=='\\' ){
|
|
rbIsEscape= true;
|
|
rpFrom++;
|
|
switch(*rpFrom){
|
|
case '0': return '\0';
|
|
case 'n': rpFrom++; return '\n';
|
|
case 't': rpFrom++; return '\t';
|
|
case 'v': rpFrom++; return '\v';
|
|
case 'a': rpFrom++; return '\a';
|
|
case 'b': rpFrom++; return '\b';
|
|
case 'r': rpFrom++; return '\r';
|
|
case 'x': c= *rpFrom++;
|
|
if( isxdigit(rpFrom[0]) && isxdigit(rpFrom[1]) ){
|
|
unsigned hexChar=0;
|
|
for(int i=0;i<2;i++){
|
|
hexChar*=16;
|
|
hexChar+= isdigit(rpFrom[i])?(rpFrom[i]-'0'):(toupper(rpFrom[i])-'A'+16);
|
|
}
|
|
c= (char)hexChar;
|
|
rpFrom+= 2;
|
|
}
|
|
return c;
|
|
default: c= *rpFrom++; return c;
|
|
}
|
|
}
|
|
return *rpFrom++;
|
|
}
|
|
//------------------------------------------------------------------------------
|
|
void REXA_Scanner::AddRange(
|
|
unsigned char cFirst,
|
|
unsigned char cLast,
|
|
REXA_CharSet& rCharSet)
|
|
//------------------------------------------------------------------------------
|
|
{
|
|
if( cFirst>cLast ){
|
|
swap(cFirst,cLast);
|
|
}
|
|
for(unsigned char c= cFirst; c<cLast;c++){
|
|
rCharSet[c]= true;
|
|
}
|
|
rCharSet[cLast]= true;
|
|
}
|
|
//------------------------------------------------------------------------------
|
|
REXA_ESymbols REXA_Scanner::operator() ()
|
|
//------------------------------------------------------------------------------
|
|
{
|
|
m_pTokBeg= m_pTokEnd= SkipWhiteSpace();
|
|
switch(*m_pTokEnd){
|
|
case '\0': return m_eLastSymbol=eEof;
|
|
case '+': m_pTokEnd++; return m_eLastSymbol=ePlus;
|
|
case '?': m_pTokEnd++; return m_eLastSymbol=eOpt;
|
|
case '*': m_pTokEnd++; return m_eLastSymbol=eStar;
|
|
case '(': m_pTokEnd++; return m_eLastSymbol=eLParen;
|
|
case ')': m_pTokEnd++; return m_eLastSymbol=eRParen;
|
|
case '=': m_pTokEnd++; return m_eLastSymbol=eAssign;
|
|
case '|': m_pTokEnd++; return m_eLastSymbol=eAlternative;
|
|
case '[': {
|
|
m_pTokEnd++;
|
|
REXA_CharSet cset;
|
|
char c;
|
|
bool bIsEscape;
|
|
bool bIsFirstTime= true;
|
|
bool bPrevWasRangeSeparator= false;
|
|
bool bUseComplement= false;
|
|
char cPrev;
|
|
cPrev=GetChar(m_pTokEnd,bIsEscape);
|
|
if( cPrev=='^' && !bIsEscape ){
|
|
bUseComplement= true;
|
|
cPrev=GetChar(m_pTokEnd,bIsEscape);
|
|
}
|
|
while( cPrev && !(cPrev==']' && !bIsEscape) ){
|
|
c=GetChar(m_pTokEnd,bIsEscape);
|
|
if( !bIsEscape && c=='-' ){
|
|
c=GetChar(m_pTokEnd,bIsEscape);
|
|
if(!c){
|
|
break;
|
|
}
|
|
AddRange(
|
|
(unsigned char)cPrev,(unsigned char)c,cset);
|
|
cPrev= GetChar(m_pTokEnd,bIsEscape);
|
|
}else{
|
|
cset[(unsigned char)cPrev]= true;
|
|
cPrev= c;
|
|
}
|
|
}
|
|
if( !cPrev || !c ){
|
|
throw REXA_Exception(
|
|
m_pTokBeg,m_pcszToParse,"closing ] missing");
|
|
}
|
|
m_charSet= cset;
|
|
if(bUseComplement){
|
|
m_charSet.flip();
|
|
}
|
|
return m_eLastSymbol=eCharSet;
|
|
}
|
|
case '.':{
|
|
m_pTokEnd++;
|
|
m_charSet= REXA_CharSet();
|
|
for(int i=0;i<256;i++){
|
|
m_charSet[i]= true;
|
|
}
|
|
return m_eLastSymbol=eCharSet;
|
|
}
|
|
case '$':{
|
|
if( isalpha(m_pTokEnd[1])||m_pTokEnd[1]=='_' ){
|
|
m_pTokEnd++;
|
|
m_strLiteral="";
|
|
while( isalpha(*m_pTokEnd)||isdigit(*m_pTokEnd)||m_pTokEnd[1]=='_' ){
|
|
m_strLiteral+= *m_pTokEnd++;
|
|
}
|
|
return m_eLastSymbol=eIdent;
|
|
}
|
|
}
|
|
default:
|
|
{
|
|
if( *m_pTokEnd=='\\' && m_pTokEnd[1]=='i' ){
|
|
m_pTokEnd++;
|
|
m_pTokEnd++;
|
|
return m_eLastSymbol=eIgnoreCase;
|
|
}else{
|
|
bool bIsEscape;
|
|
char c=GetChar(m_pTokEnd,bIsEscape);
|
|
m_charSet= REXA_CharSet();
|
|
m_charSet[(unsigned char)c]= true;
|
|
return m_eLastSymbol=eCharSet;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
///////////////////////////////////////////////////////////////////////////////
|
|
// grammar related functions
|
|
///////////////////////////////////////////////////////////////////////////////
|
|
//-----------------------------------------------------------------------------
|
|
REXA_ParserImpl::~REXA_ParserImpl()
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
for(int i=0;i<m_vecAllStates.size();++i){
|
|
delete m_vecAllStates[i];
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_ParserImpl::InsertNamedState(REXA_BegEnd name,
|
|
REXA_NDFAState* pState,int nAnswer)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
vector<REXA_NDFAState*> vecAccepting= CollectAcceptingStates(pState);
|
|
for(int i=0;i<vecAccepting.size();i++){
|
|
vecAccepting[i]->m_nAnswer= nAnswer;
|
|
}
|
|
pair<map<string,REXA_NDFAState*>::iterator,bool> itBool=
|
|
m_mapNamedStates.insert(make_pair(string(name.first,name.second),pState));
|
|
if( !itBool.second ){
|
|
itBool.first->second= pState;
|
|
}
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_ParserImpl::NamedRegExp (int nAnswer)
|
|
//-----------------------------------------------------------------------------
|
|
//$1 NamedRegExp= Ident "=" RegExp.
|
|
{
|
|
m_scanner.Match(eIdent);
|
|
REXA_BegEnd name= m_scanner.GetToken();
|
|
|
|
m_scanner.AdvanceAndMatch(eAssign);
|
|
m_scanner();
|
|
REXA_NDFAState* pState=RegExp();
|
|
if( m_scanner.GetLastSymbol()!=eEof){
|
|
throw REXA_Exception(
|
|
m_scanner.m_pTokBeg,
|
|
m_scanner.m_pcszToParse,
|
|
"unexpected symbol");
|
|
}
|
|
InsertNamedState(name,pState,nAnswer);
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
const REXA_NDFAState* REXA_ParserImpl::ParseRegExp (string strRegExp)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
m_scanner.SetSource(strRegExp.c_str());
|
|
m_scanner();
|
|
const REXA_NDFAState* cRegExp= RegExp();
|
|
if( m_scanner.GetLastSymbol()!=eEof){
|
|
throw REXA_Exception(
|
|
m_scanner.m_pTokBeg,
|
|
m_scanner.m_pcszToParse,
|
|
"unexpected symbol");
|
|
}
|
|
return cRegExp;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
bool REXA_ParserImpl::ParseRegExpDefinition(string strRegExpDefiniton,
|
|
int nAnswer)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
m_scanner.SetSource(strRegExpDefiniton.c_str());
|
|
m_scanner();
|
|
NamedRegExp(nAnswer);
|
|
return true;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::RegExp ()
|
|
//-----------------------------------------------------------------------------
|
|
//$2 RegExp= Term {"|" Term}.
|
|
{
|
|
REXA_NDFAState* pState= Term();
|
|
while( m_scanner.GetLastSymbol()==eAlternative ){
|
|
m_scanner();
|
|
pState= Union(pState,Term());
|
|
}
|
|
return pState;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::Term ()
|
|
//-----------------------------------------------------------------------------
|
|
//$3 Term= Factor {Factor}.
|
|
{
|
|
REXA_NDFAState* pState= Factor();
|
|
while( m_scanner.GetLastSymbol()&m_eAtomSet ){
|
|
pState= Concat(pState,Factor());
|
|
}
|
|
return pState;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::Factor ()
|
|
//-----------------------------------------------------------------------------
|
|
//$4 Factor= Atom ["*"|"+"|"?"|"\i"].
|
|
{
|
|
REXA_NDFAState* pState= Atom();
|
|
switch(m_scanner.GetLastSymbol()){
|
|
case eStar:
|
|
{
|
|
pState= MakeStar(pState);
|
|
m_scanner();
|
|
return pState;
|
|
}
|
|
case ePlus:
|
|
{
|
|
pState= MakePlus(pState);
|
|
m_scanner();
|
|
return pState;
|
|
}
|
|
case eOpt:
|
|
{
|
|
pState= MakeOptional(pState);
|
|
m_scanner();
|
|
return pState;
|
|
}
|
|
case eIgnoreCase:
|
|
{
|
|
pState= MakeIgnoreCase(pState);
|
|
m_scanner();
|
|
return pState;
|
|
}
|
|
default:
|
|
return pState;
|
|
}
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::Atom ()
|
|
//-----------------------------------------------------------------------------
|
|
//$5 Atom= REXA_CharSet | Ident | "(" RegExp ").
|
|
{
|
|
switch(m_scanner.GetLastSymbol()){
|
|
case eCharSet:
|
|
{
|
|
REXA_NDFAState* pState= ParseCharSet(m_scanner.GetCharSet());
|
|
m_scanner();
|
|
return pState;
|
|
}
|
|
|
|
case eIdent:
|
|
{
|
|
REXA_NDFAState* pState= Name(m_scanner.GetToken());
|
|
m_scanner();
|
|
return pState;
|
|
}
|
|
case eLParen:
|
|
{
|
|
m_scanner();
|
|
REXA_NDFAState* pState= RegExp();
|
|
m_scanner.Match(eRParen);
|
|
m_scanner();
|
|
return pState;
|
|
}
|
|
default: throw REXA_Exception(
|
|
m_scanner.m_pTokBeg,
|
|
m_scanner.m_pcszToParse,
|
|
"[,',( or ident expected");
|
|
|
|
}
|
|
return 0;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::Name (REXA_BegEnd nameToFind)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
|
|
map<string,REXA_NDFAState*>::iterator it=
|
|
m_mapNamedStates.find(string(nameToFind.first,nameToFind.second));
|
|
if( it!= m_mapNamedStates.end() ){
|
|
return CloneNDFA(it->second);;
|
|
}
|
|
throw REXA_Exception( m_scanner.m_pTokBeg,
|
|
m_scanner.m_pcszToParse,
|
|
string(nameToFind.first,nameToFind.second-nameToFind.first)
|
|
+ " not found in name dictionary");
|
|
return 0;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::ParseCharSet (REXA_CharSet& rCharSet)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
rCharSet[(unsigned char)m_cEos]=false;
|
|
REXA_NDFAState* pStartState= GetNewNDFAState(NextStateId(),false);
|
|
REXA_NDFAState* pFinalState= GetNewNDFAState(NextStateId(),true);
|
|
pStartState->m_transitions.push_back(REXA_NDFATransition(rCharSet,pFinalState));
|
|
return pStartState;
|
|
}
|
|
|
|
///////////////////////////////////////////////////////////////////////////////
|
|
//NDFA-Automtaton constructors
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::Concat (REXA_NDFAState* pState0,REXA_NDFAState* pState1)
|
|
//-----------------------------------------------------------------------------
|
|
{ //Terms: F0 resp. F1: StateGraph reachable from 'pState0' resp. 'pState1'
|
|
//1. for each transition in F0 leading from state q to an accepting state
|
|
// add a transition leading from q to 'pState1'
|
|
vector<pair<REXA_NDFAState*,REXA_NDFATransition> > vecTrans=
|
|
CollectAcceptingTransitions(pState0);
|
|
vector<REXA_NDFAState*> vecAccepting= CollectAcceptingStates(pState0);
|
|
for(int i=0;i<vecTrans.size();i++){
|
|
vecTrans[i].first->m_transitions.push_back(
|
|
REXA_NDFATransition(vecTrans[i].second.m_transChars,pState1));
|
|
}
|
|
//2. if 'pState0' is accepting
|
|
// add all transitions from 'pState1' to 'pState0'
|
|
if( pState0->m_isAccepting ){
|
|
pState0->m_transitions.insert( pState0->m_transitions.end(),
|
|
pState1->m_transitions.begin(),
|
|
pState1->m_transitions.end());
|
|
}
|
|
//3. accepting states of F1 are accepting states of the catenation
|
|
// accepting states of F0 are no langer accepting
|
|
for(int j=0;j<vecAccepting.size();j++){
|
|
vecAccepting[j]->m_isAccepting= false;
|
|
}
|
|
return pState0;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::Union (REXA_NDFAState* pState0,REXA_NDFAState* pState1)
|
|
//-----------------------------------------------------------------------------
|
|
{ //1. 'pState0' gets also the transitions of 'pState1'
|
|
pState0->m_transitions.insert( pState0->m_transitions.end(),
|
|
pState1->m_transitions.begin(),
|
|
pState1->m_transitions.end());
|
|
//2. if one of the start states is accepting the new start state is also accepting
|
|
if( pState1->m_isAccepting ){
|
|
pState0->m_isAccepting= true;
|
|
}
|
|
return pState0;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::MakeStar (REXA_NDFAState* pState)
|
|
//-----------------------------------------------------------------------------
|
|
{ // //1. for each transition leading from state q to an accepting state
|
|
// add a transition leading from q to 'pState
|
|
vector<pair<REXA_NDFAState*,REXA_NDFATransition> > vecTrans=
|
|
CollectAcceptingTransitions(pState);
|
|
for(int i=0;i<vecTrans.size();i++){
|
|
vecTrans[i].first->m_transitions.push_back(
|
|
REXA_NDFATransition(vecTrans[i].second.m_transChars,pState));
|
|
}
|
|
pState->m_isAccepting=true;
|
|
return pState;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::MakePlus (REXA_NDFAState* pState)
|
|
//-----------------------------------------------------------------------------
|
|
{ //catenate original state graph and its dupplication; then apply MakeStar
|
|
return Concat(pState,MakeStar(CloneNDFA(pState)));
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::MakeOptional (REXA_NDFAState* pState)
|
|
//-----------------------------------------------------------------------------
|
|
{ //start state gets optional
|
|
pState->m_isAccepting= true;
|
|
return pState;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::MakeIgnoreCase (REXA_NDFAState* pState)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
set<REXA_NDFAState*> setStates;
|
|
REXA_NDFAState::CollectStates(pState,setStates);
|
|
set<REXA_NDFAState*>::iterator it;
|
|
for(it= setStates.begin();it!=setStates.end();++it){
|
|
for(int i=0;i<(*it)->m_transitions.size();i++){
|
|
for(int j=0;j<(*it)->m_transitions[i].m_transChars.size();j++){
|
|
if( (*it)->m_transitions[i].m_transChars[j]
|
|
&& isupper(j) ){
|
|
(*it)->m_transitions[i].
|
|
m_transChars[(unsigned char)(tolower(j))]= true;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return pState;
|
|
}
|
|
|
|
//NDFA-Automaton helper functions
|
|
//-----------------------------------------------------------------------------
|
|
vector<REXA_NDFAState*> REXA_ParserImpl::CollectAcceptingStates(REXA_NDFAState* pState)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
set<REXA_NDFAState*> setStates;
|
|
vector<REXA_NDFAState*> vecAcceptingStates;
|
|
REXA_NDFAState::CollectStates(pState,setStates);
|
|
set<REXA_NDFAState*>::iterator it;
|
|
for(it= setStates.begin();it!=setStates.end();++it){
|
|
if( (*it)->m_isAccepting ){
|
|
vecAcceptingStates.push_back(*it);
|
|
}
|
|
}
|
|
return vecAcceptingStates;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
vector<pair<REXA_NDFAState*,REXA_NDFATransition> >
|
|
REXA_ParserImpl::CollectAcceptingTransitions(REXA_NDFAState* pState)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
vector<pair<REXA_NDFAState*,REXA_NDFATransition> > vecStatTrans;
|
|
|
|
set<REXA_NDFAState*> setStates;
|
|
REXA_NDFAState::CollectStates(pState,setStates);
|
|
set<REXA_NDFAState*>::iterator it;
|
|
for(it= setStates.begin();it!=setStates.end();++it){
|
|
for(int i=0;i<(*it)->m_transitions.size();i++){
|
|
if( (*it)->m_transitions[i].m_nextState->m_isAccepting ){
|
|
vecStatTrans.push_back(make_pair(*it,(*it)->m_transitions[i]));
|
|
}
|
|
}
|
|
}
|
|
return vecStatTrans;
|
|
}
|
|
|
|
//-------------------------------------------------------------------------------
|
|
int REXA_ParserImpl::NextStateId ()
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
return m_nStateIdMax++;
|
|
}
|
|
//-------------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::CloneNDFA(REXA_NDFAState* pToClone)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
set<REXA_NDFAState*> setStates;
|
|
REXA_NDFAState* pState= pToClone->Clone();
|
|
REXA_NDFAState::CollectStates(pState,setStates);
|
|
set<REXA_NDFAState*>::const_iterator it;
|
|
for(it= setStates.begin();it!=setStates.end();++it){
|
|
(*it)->m_id= NextStateId();
|
|
m_vecAllStates.push_back(*it);
|
|
}
|
|
return pState;
|
|
}
|
|
//-------------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_ParserImpl::GetNewNDFAState(int id,bool isAccepting)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
REXA_NDFAState* pState= new REXA_NDFAState(id,isAccepting);
|
|
m_vecAllStates.push_back(pState);
|
|
return pState;
|
|
}
|
|
|
|
|
|
///////////////////////////////////////////////////////////////////////////
|
|
// NDFA State
|
|
///////////////////////////////////////////////////////////////////////////
|
|
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_NDFAState::DeleteAll()
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
set<const REXA_NDFAState*> setStates;
|
|
CollectStates(this,setStates);
|
|
set<const REXA_NDFAState*>::iterator it;
|
|
for(it= setStates.begin();it!=setStates.end();++it){
|
|
delete *it;
|
|
}
|
|
}
|
|
//-------------------------------------------------------------------------------
|
|
void REXA_NDFAState::CollectStates(const REXA_NDFAState* pState,set<const REXA_NDFAState*>& rsetStates)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
pair<set<const REXA_NDFAState*>::iterator,bool> itBool= rsetStates.insert(pState);
|
|
if( itBool.second ){
|
|
for(int i=0;i<(*itBool.first)->m_transitions.size();i++){
|
|
CollectStates((*itBool.first)->m_transitions[i].m_nextState,rsetStates);
|
|
}
|
|
}
|
|
}
|
|
//-------------------------------------------------------------------------------
|
|
void REXA_NDFAState::CollectStates (REXA_NDFAState* pState,
|
|
set<REXA_NDFAState*>& rsetStates)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
pair<set<REXA_NDFAState*>::iterator,bool> itBool= rsetStates.insert(pState);
|
|
if( itBool.second ){
|
|
for(int i=0;i<(*itBool.first)->m_transitions.size();i++){
|
|
CollectStates((*itBool.first)->m_transitions[i].m_nextState,rsetStates);
|
|
}
|
|
}
|
|
}
|
|
//-------------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_NDFAState::CopyStates
|
|
(REXA_NDFAState* pState,map<REXA_NDFAState*,REXA_NDFAState*>& rMapStates)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
pair<map<REXA_NDFAState*,REXA_NDFAState*>::iterator,bool> itDone=
|
|
rMapStates.insert(make_pair(pState,(REXA_NDFAState*)0));
|
|
if( itDone.second ){
|
|
REXA_NDFAState* pNewState= new REXA_NDFAState(*pState);
|
|
itDone.first->second= pNewState;
|
|
for(int i=0;i<pNewState->m_transitions.size();i++){
|
|
pNewState->m_transitions[i].m_nextState=
|
|
CopyStates(pNewState->m_transitions[i].m_nextState,rMapStates);
|
|
}
|
|
}
|
|
return itDone.first->second;
|
|
}
|
|
|
|
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAState* REXA_NDFAState::Clone()
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
map<REXA_NDFAState*,REXA_NDFAState*> mapStates;
|
|
return CopyStates(this,mapStates);
|
|
}
|
|
///////////////////////////////////////////////////////////////////////////
|
|
// REXA_StateSet
|
|
///////////////////////////////////////////////////////////////////////////
|
|
//-----------------------------------------------------------------------------
|
|
bool REXA_StateSet::IsAccepting ()const
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
REXA_StateSet::const_iterator it;
|
|
for(it= begin();it!=end();++it){
|
|
if( (*it)->m_isAccepting ){
|
|
return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
|
|
//-----------------------------------------------------------------------------
|
|
void PrintCharSet(ostream& os,const REXA_CharSet& rCharSet)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
os << "\"";
|
|
for(int i=0;i<rCharSet.size();i++){
|
|
if( rCharSet[i] ){
|
|
os << (char)i;
|
|
}
|
|
}
|
|
os << "\"";
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
int REXA_TranslatingTable::GetAnswerCode (const REXA_StateSet& rSet)const
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
REXA_StateSet::const_iterator it;
|
|
int nAnswerCode= REXA_DFAState::eNoAnswer;
|
|
int nMinCount= INT_MAX;
|
|
for(it= rSet.begin();it!=rSet.end();++it){
|
|
MapStateOccurrenceCount::const_iterator itMap=
|
|
m_mapStateOccurrenceCount.find((*it));
|
|
if( itMap!=m_mapStateOccurrenceCount.end() ){
|
|
if( itMap->second<nMinCount ){
|
|
nMinCount= itMap->second;
|
|
nAnswerCode= itMap->first->m_nAnswer;
|
|
}
|
|
}
|
|
}
|
|
return nAnswerCode;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_TranslatingTable::ComputeOccCounts ()
|
|
//-----------------------------------------------------------------------------
|
|
{ //computes the occurrences of all states with an existing answer code
|
|
TranslationMap::const_iterator it;
|
|
for( it= m_mapTransitions.begin();
|
|
it!=m_mapTransitions.end();
|
|
++it){
|
|
REXA_StateSet::const_iterator it1;
|
|
for( it1= it->first.begin();it1!=it->first.end();++it1){
|
|
if( (*it1)->m_isAccepting
|
|
&& (*it1)->m_nAnswer!=REXA_DFAState::eNoAnswer){
|
|
pair<MapStateOccurrenceCount::iterator,bool> pairRes=
|
|
m_mapStateOccurrenceCount.insert(make_pair(*it1,1));
|
|
if( !pairRes.second ){
|
|
pairRes.first->second++;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
set<REXA_CharSet,REXA_LessCharSet>
|
|
REXA_TranslatingTable::ComputeDisjointCharSets(REXA_CharSetSet& rCharSets)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
vector< REXA_CharSetSet > charSets(256);
|
|
vector< REXA_CharSet > unionSets(256);
|
|
REXA_CharSetSet resultSet;
|
|
REXA_CharSetSet::const_iterator it;
|
|
for(it= rCharSets.begin();it!=rCharSets.end();++it){
|
|
charSets[it->count()].insert(*it);
|
|
}
|
|
|
|
//cumulative union
|
|
for(int k= 1;k<256;k++){
|
|
for(int j=0;j<k;j++){
|
|
for(it= charSets[j].begin();it!= charSets[j].end();++it){
|
|
unionSets[k]|= *it;
|
|
}
|
|
}
|
|
}
|
|
|
|
//reduce charset into disjoint charsets
|
|
for(int l=0;l<256;l++){
|
|
for(it= charSets[l].begin();it!= charSets[l].end();++it){
|
|
REXA_CharSet reducedSet= *it;
|
|
REXA_CharSet unionSet= ~unionSets[l];
|
|
reducedSet&= unionSet;
|
|
resultSet.insert(reducedSet);
|
|
}
|
|
}
|
|
|
|
return resultSet;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_TranslatingTable::CollectCharSets(const REXA_NDFAState* pCurState,
|
|
set<int>& rVisitedStates,
|
|
REXA_CharSetSet& rCharSets)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
if( rVisitedStates.find(pCurState->m_id) == rVisitedStates.end() ){
|
|
rVisitedStates.insert(pCurState->m_id);
|
|
for(int i=0;i<pCurState->m_transitions.size();i++){
|
|
if( pCurState->m_transitions[i].m_transChars.count()!=0 ){
|
|
rCharSets.insert(pCurState->m_transitions[i].m_transChars);
|
|
CollectCharSets(
|
|
pCurState->m_transitions[i].m_nextState,
|
|
rVisitedStates,rCharSets);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
|
|
//# Generates a translation table from the NDFA-states present in 'vecpStates'
|
|
//example: NDFA having the States S,A,E. S('a') -> A. S('a') -> E. A('b') -> A. A('b') -> E.
|
|
//TranslationTable:
|
|
// REXA_StateSet 'a' 'b'
|
|
//--------------------------
|
|
// {S} {A,E}
|
|
// {A,E} {A,E}
|
|
// corresponding DFA: {S}('a') -> {A,E}. {A,E}('b') -> {A,E}
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_TranslatingTable::GenerateTranslationTable(set<const REXA_NDFAState*>& rSetState)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
set< REXA_StateSet > setPendingStateSets;
|
|
REXA_StateSet startStateSet;
|
|
|
|
startStateSet.insert(m_pStartState);
|
|
setPendingStateSets.insert(startStateSet);
|
|
|
|
while( setPendingStateSets.size()>0 ){
|
|
REXA_StateSet curStateSet= *setPendingStateSets.begin();
|
|
setPendingStateSets.erase(curStateSet);
|
|
if( m_mapTransitions.find(curStateSet)==m_mapTransitions.end() ){
|
|
TransitionVector transVector(m_vecCharsets.size());
|
|
for(int i=0;i<m_vecCharsets.size();i++){
|
|
REXA_StateSet::const_iterator it;
|
|
for(it= curStateSet.begin();it!=curStateSet.end();++it){
|
|
for(int j=0;j<(*it)->m_transitions.size();j++){
|
|
const REXA_NDFATransition& rTransition= (*it)->m_transitions[j];
|
|
REXA_CharSet charSet= rTransition.m_transChars;
|
|
charSet&= m_vecCharsets[i];
|
|
if( charSet.any() ){
|
|
transVector[i].insert(rTransition.m_nextState);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
m_mapTransitions.insert(make_pair(curStateSet,transVector));
|
|
for(int l=0;l<transVector.size();l++){
|
|
setPendingStateSets.insert(transVector[l]);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
static REXA_DFAState* GetIllegalState()
|
|
{
|
|
static REXA_DFAState illegalState(REXA_DFAState::eNoAnswer,true);
|
|
return &illegalState;
|
|
}
|
|
static REXA_DFAState* GetEosState()
|
|
{
|
|
bool bFirstTime= true;
|
|
static REXA_DFAState eosState(REXA_DFAState::eEos,true);
|
|
if( bFirstTime ){
|
|
bFirstTime= false;
|
|
for(int i=0;i<sizeof(eosState.aNext)/sizeof(eosState.aNext[0]);i++){
|
|
eosState.aNext[i]= &eosState;
|
|
}
|
|
}
|
|
return &eosState;
|
|
}
|
|
|
|
REXA_DFAState* REXA_DFAState::ms_pIllegalState= ::GetIllegalState();
|
|
REXA_DFAState* REXA_DFAState::ms_pEosState= ::GetEosState();
|
|
|
|
//-------------------------------------------------------------------------------
|
|
REXA_DFAState::REXA_DFAState(int nAnwserId,bool bIsFinal)
|
|
:m_nAnwserId(nAnwserId),
|
|
m_bIsFinal(bIsFinal),
|
|
m_bIsAccepting(false)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
for(int i=0;i<256;i++) aNext[i]=0;
|
|
}
|
|
//-------------------------------------------------------------------------------
|
|
void REXA_DFAState::CollectStates(REXA_DFAState* pState,set<REXA_DFAState*>& rsetStates)
|
|
//-------------------------------------------------------------------------------
|
|
{
|
|
if( !pState ) return;
|
|
|
|
pair<set<REXA_DFAState*>::iterator,bool> itBool= rsetStates.insert(pState);
|
|
if( itBool.second ){
|
|
for(int i=0;i<256;i++){
|
|
CollectStates((*itBool.first)->aNext[i],rsetStates);
|
|
}
|
|
}
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_DFAState::DeleteAll()
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
set<REXA_DFAState*> setStates;
|
|
CollectStates(this,setStates);
|
|
set<REXA_DFAState*>::iterator it;
|
|
for(it= setStates.begin();it!=setStates.end();++it){
|
|
if( *it!=ms_pIllegalState && *it!=ms_pEosState ){
|
|
delete *it;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
|
|
//-----------------------------------------------------------------------------
|
|
vector<REXA_CharSet> REXA_NDFAToTable::CharsetToVector(const REXA_CharSetSet& rCharSetSet)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
vector<REXA_CharSet> vecCharSet;
|
|
REXA_CharSetSet::const_iterator it;
|
|
for(it= rCharSetSet.begin();it!=rCharSetSet.end();++it){
|
|
vecCharSet.push_back(*it);
|
|
}
|
|
return vecCharSet;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_TranslatingTable::REXA_TranslatingTable (const REXA_NDFAState* pStartState)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
set<int> setVisitedStates;
|
|
REXA_CharSetSet charSets;
|
|
set<const REXA_NDFAState*> setStates;
|
|
|
|
REXA_NDFAState::CollectStates(pStartState,setStates);
|
|
|
|
CollectCharSets(pStartState,setVisitedStates,charSets);
|
|
m_vecCharsets= REXA_NDFAToTable::CharsetToVector(
|
|
ComputeDisjointCharSets(charSets));
|
|
m_pStartState= pStartState;
|
|
GenerateTranslationTable(setStates);
|
|
ComputeOccCounts();
|
|
}
|
|
|
|
|
|
//-----------------------------------------------------------------------------
|
|
REXA_NDFAToDfa::REXA_NDFAToDfa (const REXA_TranslatingTable& rTable,char cEos)
|
|
:m_rTable(rTable),m_cEos((unsigned char)cEos)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_DFAState* REXA_NDFAToDfa::CreateDfaStates(
|
|
const REXA_StateSet& rStateSet,
|
|
map<REXA_StateSet,REXA_DFAState*>& rMapStateSetDFAState)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
pair<map<REXA_StateSet,REXA_DFAState*>::iterator,bool> pairItBool=
|
|
rMapStateSetDFAState.insert(make_pair(rStateSet,(REXA_DFAState*)0));
|
|
if( pairItBool.second ){
|
|
REXA_DFAState* pDFAState= new REXA_DFAState();
|
|
pairItBool.first->second= pDFAState;
|
|
REXA_TranslatingTable::TranslationMap::const_iterator it=
|
|
m_rTable.m_mapTransitions.find(rStateSet);
|
|
if( it!= m_rTable.m_mapTransitions.end() ){
|
|
const TransitionVector& rvecTrans= it->second;
|
|
for(int i=0;i<rvecTrans.size();i++){
|
|
if( rvecTrans[i].size()>0 ){
|
|
REXA_DFAState* pTransState=
|
|
CreateDfaStates(rvecTrans[i],rMapStateSetDFAState);
|
|
for(int j=0;j<256;j++){
|
|
if( m_rTable.m_vecCharsets[i][j] ){
|
|
pDFAState->aNext[j]= pTransState;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
if( rStateSet.IsAccepting() ){
|
|
int nAnswerCode= m_rTable.GetAnswerCode(rStateSet);
|
|
pDFAState->m_bIsAccepting= true;
|
|
pDFAState->m_nAnwserId= nAnswerCode;
|
|
REXA_DFAState* pAcceptState=
|
|
new REXA_DFAState(nAnswerCode,true);
|
|
pAcceptState->m_bIsAccepting= true;
|
|
for(int j=0;j<256;j++){
|
|
if( !pDFAState->aNext[j] ){
|
|
pDFAState->aNext[j]= pAcceptState;
|
|
}
|
|
}
|
|
}else{
|
|
for(int j=0;j<256;j++){
|
|
if( !pDFAState->aNext[j] ){
|
|
pDFAState->aNext[j]= REXA_DFAState::ms_pIllegalState;
|
|
}
|
|
}
|
|
pDFAState->aNext[m_cEos]= REXA_DFAState::ms_pEosState;
|
|
}
|
|
}
|
|
return pDFAState;
|
|
}
|
|
return pairItBool.first->second;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_DFAState* REXA_NDFAToDfa::TableToDfaStates()
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
REXA_StateSet startStateSet;
|
|
startStateSet.insert(m_rTable.m_pStartState);
|
|
|
|
map<REXA_StateSet,REXA_DFAState*> mapStateSetDFAState;
|
|
|
|
REXA_TranslatingTable::TranslationMap::const_iterator it;
|
|
it= m_rTable.m_mapTransitions.find(startStateSet);
|
|
if( it!=m_rTable.m_mapTransitions.end() ){
|
|
return CreateDfaStates(
|
|
it->first,
|
|
mapStateSetDFAState);
|
|
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
//-----------------------------------------------------------------------------
|
|
REXA_Parser::REXA_Parser (char cEos)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
m_pParserImp= new REXA_ParserImpl(cEos);
|
|
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_Parser::~REXA_Parser ()
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
delete m_pParserImp;
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
REXA_DFAState* REXA_Parser::ParseRegExp (string strRegExp)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
const REXA_NDFAState* pNdfa= m_pParserImp->ParseRegExp(strRegExp);
|
|
REXA_TranslatingTable table(pNdfa);
|
|
REXA_NDFAToDfa ndfaToDfa(table,m_pParserImp->m_cEos);
|
|
return ndfaToDfa.TableToDfaStates();
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_Parser::AddRegDefinition ( string strDefName,
|
|
string strDefExpression,
|
|
int nAnswer)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
string str= strDefName+ "=" + strDefExpression;
|
|
m_pParserImp->ParseRegExpDefinition(str,nAnswer);
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_Parser::RemoveRegDefinition ( string strDefName)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
m_pParserImp->m_mapNamedStates.erase(strDefName);
|
|
}
|
|
//-----------------------------------------------------------------------------
|
|
void REXA_Parser::GetRegDefinitions (vector<string>& vecDefinitions)
|
|
//-----------------------------------------------------------------------------
|
|
{
|
|
map<string,REXA_NDFAState*>::iterator it;
|
|
for(it= m_pParserImp->m_mapNamedStates.begin();
|
|
it!=m_pParserImp->m_mapNamedStates.end();
|
|
++it){
|
|
vecDefinitions.push_back(it->first);
|
|
}
|
|
}
|
|
|
|
|
|
|
|
|