首页 > 代码库 > 正则表达式引擎

正则表达式引擎

2024-08-02 22:01:12   219人阅读

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 left, 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,List *next_list,State *s)

/***
* 对一个字符c进行匹配状态操作
*/
void RegexpToNfa::nextState(List *cur_list, List *next_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)

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

正则表达式引擎


联系
我们