背景

当前正则表达式NFA（非确定有穷自动机，Non-deterministic finite automaton）构造方法，通常需要先借助“堆栈（Stack）”构造“语法树（SyntaxTree）”，然后，将语法树转换为NFA。由于正则语义的嵌套层级未知，导致堆栈的大小不可控，容易导致内存溢出错误，并且，构造语法树也需要一定的消耗CPU。同时，传统的NFA在复杂字符集的情况下，采用邻接矩阵（全量数组）或邻接表的方式存储状态跳转，存在空间存储较大或者匹配性能较差的问题。

本文，消除构造“语法树（SyntaxTree）”环节，采用有序邻接区间表的存储方式，实现了一种无需申请额外的“堆栈（Stack）”空间且存储空间压缩率较高的正则表达式NFA高效构造方法。

怎么实现的？

本文提出一种支持复杂字符集的NFA高效构造方法，无需开辟额外的“堆栈（Stack）”空间，进而避免出现内存溢出错误，无需创建“语法树（SyntaxTree）”，进而加快了构造速度，采用有序邻接区间表，较好的实现了复杂字符集功能。系统模块设计分为三部分：正则预处理、NFA构造。

   A）正则预处理，用于判定是否需要在头部增加“前缀.*”。

正则匹配模式包含两种：搜索和匹配。“搜索”表示字符串是否包含符合正则表达式的子串，“匹配”表示整个字符串是否符合正则表达式。

如果正则匹配为“搜索”模式，并且正则第一个字符不是“^”（字符^用于限定开头）,则需要为此正则表达式增加“前缀.*”。例如：搜索模式的正则表达式“abc”，在头部增加“前缀.*”得到的正则表达式为“.*abc”。

   B）NFA构造。遍历正则表达式，同步构造NFA，无需创建“语法树（SyntaxTree）”。

1.创建“当前自动机nowNfa”。

2.遍历正则表达式，根据“当前字符currentCharacter”所属的字符类型（字符转换、量词、或、小括号），分别执行对应操作。

（1）字符转换

如果“当前字符currentCharacter”为“转义字符”，则解析“转义字符”、“16进制”、“8进制”得到“结果字符集resultCharSet”。

如果“当前字符currentCharacter”为“非元字符”，则解析为只包含“非元字符”的“结果字符集resultCharSet”。

如果“当前字符currentCharacter”为“任意字符.”，则解析为包含“所有字符”的“结果字符集resultCharSet”。

如果“当前字符currentCharacter”为“区间值[]”，则解析为包含“所有区间值”的“结果字符集resultCharSet”。

默认情况，解析为只包含“一个字符”的“结果字符集resultCharSet”。

如果“下一个字符nextChar”为“量词”，则将当前结果转化为“下一个自动机nextNfa”。否则，为“当前自动机nowNfa”根据“结果字符集resultCharSet”添加跳转操作。

如果“结果字符集resultCharSet”包含了汉语，例如：“.*中国.*”、“ [\u4e00-\u9fa5]”、[^abc]，此时跳转表仅采用包含256个元素的数组不能表达上述语义，需要在后面采用“有序区间邻接表”表示超出常见字符集的复杂字符集部分。小于256的常见字符集通过数组索引能够直接定位，超过255的部分需要采用二分查找模式判定匹配结果。

（2）量词

如果“当前字符currentCharacter”为“*”，则解析值为“{0，+∞}”的“量词区间countInterval”。

如果“当前字符currentCharacter”为“？”，则解析值为“{0，1}”的“量词区间countInterval”。

如果“当前字符currentCharacter”为“+”，则解析值为“{1，+∞}”的“量词区间countInterval”。

如果“当前字符currentCharacter”为“{”，则解析值为“{m，n}”的“量词区间countInterval”。

量词复制操作repeat会造成状态膨胀，比如形如{10000}的量词会repeat10000次，由此也会创建10000个NFA状态，这种情形极易造成内存超限。为此本文在量词操作repeat前做了次数阈值限定，如果repeat次数超过阈值（比如：10），则转换为量词节点自转换操作nodeSelfConvert，此操作采用“标记位Tag”和“计数器Counter”的方式表示此量词。在匹配过程中遇到此类型的“标记位Tag”，需要比较当前“计数器Counter”是否符合量词限定，如果符合则继续执行匹配操作，同时将当前“计数器Counter”加1。

首先，判断根据量词是否超过阈值，然后，确定针对“下一个自动机nextNfa”执行量词复制操作repeat还是量词节点自转换操作nodeSelfConvert，最后，针对“当前自动机nowNfa”和“下一个自动机nextNfa”执行连接操作connact。

（3）或

如果“当前字符currentCharacter”为“|”，则针对“后续的正则表达式子串”构造“单独的自动机newNfa”。

针对“当前自动机nowNfa”和“单独的自动机newNfa”执行或操作or。

（4）小括号

如果“当前字符currentCharacter”为“（”，则针对 “处于小括号内正则表达式子串”构造“单独的自动机newNfa”。

针对“当前自动机nowNfa”和“单独的自动机newNfa”执行连接操作connact。

    支持复杂字符集的NFA高效构造算法执行参照：

有哪些实际价值？

1）构造时间短：遍历正则表达式的同时，直接构造了NFA，无需中间结果“语法树（SyntaxTree）”，效率较高，程序具体较短的执行时间。                                             

2）内存可控：程序执行过程中无需额外申请与“正则串长度成正比”的“堆栈（Stack）”内存空间，避免内存溢出风险，保障程序正常运行。

3）匹配效率高：高频使用的前256个字符采用数组方式存储可以直接定位，其他复杂字符集采用有序邻接区间表采用二分查找定位，上述两种类型的匹配效率均较高。