简单的正则表达式引擎

前端之家收集整理的这篇文章主要介绍了简单的正则表达式引擎前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

1、基础理论

非确定有限自动机(NFA),是计算理论中抽象出来的状态机计算模型。它拥有有限个状态,当前状态根据不同的输入可以迁移到其他的状态,它的下一个状态不是唯一确定的。

正则表达式本身是有限长度的字符串,在这里可以看做NFA上输入状态组成的序列。于是,NFA可以用来作为一种识别装置识别正则表达式。

Thompson构造法:将正则表达式转换为NFA。这里的NFA包括ε状态及其转换,即不需要输入就可以进行状态转换。

两个状态之间的转换图如下:

(注:以下图片为使用在线绘图工具画图后截图所得)


正则表达式中包括一些子表达式的组合关系,可以概括如下:




对于NFA上的每个状态,我们可以概括为如下三种:


对于第一种状态,只有一个箭头,代表唯一的输出状态,c代表输入的字符(我们在此算法上进行改进,程序里的c是一个代表功能边的字符串);对于第二种状态,我们定义为‘|’所代表的状态,它有两个输出状态;对于第三种状态,不需要输入信息而且也没有输出状态,代表了“终极状态”,也就是我们最后匹配成功的状态。

Thompson算法理论上只能实现基本的正则表达式的匹配,而不能实现扩展正则表达式以及后向引用等。我们在此算法的基础上,改进了数据结构,用一个功能边字符串来代替c,并在State中加了另一个字符变量ch来判定此状态属于哪一个后向引用。例如:字符串“[a-zA-Z]”被当做一个功能边来判定某个字符是否符合这里的规则,ch=‘2’代表此状态在第二个后向引用中。

根据以上状态和状态转换的分类,我们就可以将正则表达式构造出NFA了。

2、数据结构和算法思想

(1)首先,由于正则表达式是前缀表达式,而构造NFA的过程需要的是由后缀表达式代表的语法树。比如,“(ab)|c”的语法树如下:


其中的○即为两个子表达式的连接符号,在这是(),我们在后缀表达式中用两个点’..’来替换小括号起连接作用,所以后缀表达式为”ab..c|”。在程序中,我们通过函数std::vector<std::string>regexpToPostfix(void); 将语法树中每个节点中上的内容当做一个字符串(有的节点上的字符长度大于1,比如 “..”,此外,为了识别 “\w” 等转义符,我们提前处理成了 “\\w”,长度也大于1),后续遍历然后加入一个vector容器中。

(2)为了模拟状态和状态转换的关系,我们定义一个结构体State。成员变量c代表跳转到下一状态时携带的字符串信息。前文提到的三种状态中,对于第一种普通状态,c为原文信息;对于第二种,我们称之为Split状态,我们定义c的值为 “Split”;对于第三种,我们称之为Match状态,c值为“Match”;而变量ch即为第ch-‘0’个后向引用。结构体State定义如下:

struct State { //NFA状态
        std::string c; //每条边上代表匹配功能的字符串
        State *out; //指向下一个状态的指针,
        State *out1;//当本状态为split时,out1表示分支
        char ch; //后向引用时,ch为数字字符,否则为空格字符
        int listIndex; //状态编号
        State():c(""),out(NULL),out1(NULL),ch(' '),listIndex(-1) {}
        State(std::string _c,State* p1,State* p2,char ct=' ',int listIndex=-1)
        :c(_c),out(p1),out1(p2),ch(ct) {}
    };

对于单个状态,有些状态可能存在多个输出状态,在此我们将这些输出状态连接成一个链表,然后就有了结构体PtrList,定义如下:

struct Ptrlist { //指向State指针的指针链表
        Ptrlist *next;
        State **outp;
        Ptrlist(State **ptr):next(NULL),outp(ptr) {}
    };

在NFA状态机构造过程中,我们将已经构造好成State,但是还没有加入到状态栈里的状态称为Frag,定义如下:

struct Frag {
        State *start;	//开始节点
        Ptrlist* out;	//out是一组指向未链接到任何东西的状态指针的列表的指针
        Frag():start(NULL),out(NULL) {}
        Frag(State *s,Ptrlist *list):start(s),out(list) {}
    };

(3)全局变量
const char *str;  //待匹配的字符串
    std::string regexp; //构造NFA的正则表达式
    int listid;
    List currentList;		//当前状态链表
    List nextList;		//下一个状态链表
    State *matchState;  //匹配状态
    std::vector<std::string> edge; //从regexp中分离出的token字符串
    Pos pos[10]; //各个后向引用的开始与结束位置
    int reference[10];
    std::map<char,std::string> result_reference; //每个后向引用对应的必须匹配的字符串
    bool no_addstate;
    int iteratorTimes; //防止死循环的迭代次数
int isEmpty; //判断某个后向引用是否为空字符串,
(4)匹配结果必须是从左到右匹配到的第一个结果,且满足贪婪原则。为此,对于一行待匹配的字符串,我们设置一个两个下标left、right,分别作为子字符串两端的下标,两个for语句循环,外面一层是left从0开始自增,里面一层是right从右边界开始自减。然后用函数intmatchString(State *start,int left,int right)匹配子字符串,一旦成功即退出循环并成功返回。

3、程序模块

(1)构造NFA

函数:State*postfixToNfa(std::vector<std::string> postfix);

经过前面处理后得到的后缀表达式,可以用来构造NFA。举个例子,对于上文出现的后缀表达式 “ab..c|”(实际上是包含 “a”,“b”,“..”,“c”,“|” 的字符串容器),大概实现过程如下:

对于 “a”,首先生成一个State变量,然后构造出该状态State的碎片Frag,然后加入到一个存放Frag栈,即stack<Frag>;然后到 “b”,同上,Frag入栈;对于 “..”,即我们定义的连接符,这时从栈顶取出两个碎片Frag e1,e2,通过函数voiddanglingPointLinkToState(e1.out,e2.start); 将两个状态连接起来,然后把连接后两个状态构成的Frag入栈。对于 “c”,同“a”;对于 “|”,这里代表分支,取出栈顶两个元素,然后新生成一个Split状态,将取出的两个状态作为Split的输出状态,Split状态构造Frag然后入栈;最后,也是判断正则表达式匹配是否成功的关键,需要生成一个Match状态,将其连接到栈顶元素的状态后面。函数执行完后返回栈底元素的state。最终生成状态图如下:


(2)匹配字符串

函数:intmatchString(State *start,int right);

NFA工作过程是从左到右逐个去匹配字符。实现过程如下:首先初始化当前状态列表,然后进入循环,一步一步去匹配。循环结束后检查是否成功匹配整个字符串。在这个过程中涉及到两个重要子函数

单步匹配函数voidnextState(List *cur_list,List *next_list,const char* str,char end);状态匹配成功后,调用函数addStateToList将其添加一个新状态到列表中。在这个函数中,需要根据当前状态输入信息,即state->c,做不同的处理。state->c如果是占位符,比如 “a”,“\w”,则调用isEqual函数判断该占位符是否能匹配字符串的指定位置;如果不是占位符, “^”,“\b”,“\B”,“$”,则需要调用isWBoudary等函数判断字符串当前位置是否合法,如果合法,字符串指定当前位置不变,状态机的下一个状态去匹配字符串该位置。

检查匹配成功函数intisMatch(List *l); 根据列表中的状态集是否包含Match状态判断是否匹配成功。

匹配过程中的相关操作函数
/***
* 判断字符c与NFA的状态是否匹配
*/
bool RegexpToNfa::isEqual(string edgeStr,char c,State *s)

/***
* 对一个字符c进行匹配状态操作
*/
void RegexpToNfa::nextState(List *cur_list,const char* testStr,char end)
(3)其他字符串处理的函数
/***
*   将输入的字符串按token分开为字符串
*/
void RegexpToNfa::getToken(string re)

/****
* 将字符串中的大括号里的重复次数
* 换成代表重复的*,+,?等等
*/
void RegexpToNfa::dealBrace(string re)

/***
*  获取中括号[]的位置
*  通过指针pStart,pEnd返回左括号[和右括号]的位置信息
*/
void RegexpToNfa::FindBracket(const char* pStart,const char*& pEnd)

/***
* 根据中括号里第一个字符位置指针pStart和最后一个字符地位置指针pEnd
* 返回其中所有可能取值的字符串的集合,作为一个字符串
*/
string RegexpToNfa::GetBracketContent(const char* pStart,const char* pEnd)


/***
* 判断字符c是否是中括号取值集合里面的一个
*/
int RegexpToNfa::MatchBracket(char c,string str)

/**
* 判断当前指针位置是否为行结尾
*/
bool RegexpToNfa::isLEnd(const char* pStr)

代码在这里:点击打开链接

原文链接:https://www.f2er.com/regex/361059.html

猜你在找的正则表达式相关文章