基于带记忆确定有限自动机的正则表达式匹配加速方法

摘要

本发明公开了一种基于带记忆确定有限自动机的正则表达式匹配加速方法。它包括正则表达式规则编译器和模式匹配引擎，正则表达式规则编译器先把正则表达式转换为解析树，再分别把解析树转换为带记忆的非确定有限自动机和带记忆的确定有限自动机，模式匹配引擎使用编译器生成的带记忆确定有限自动机实现对模式匹配的加速。本发明的优点是：1)因为直接支持了重复操作符，编译器可以不对重复表达式进行展开，大大降低了编译器开发难度，也降低了编译器的内存占用和编译时间；2)基于同样的原因，编译器生成的规则数据库大小也可大大减小，降低了模式匹配引擎的成本和复杂度。

主权项

一种基于带记忆确定有限自动机的正则表达式匹配加速方法，其特征在于通过正则表达式规则编译器先把正则表达式转换为解析树，再分别把解析树转换为带记忆的非确定有限自动机和带记忆的确定有限自动机，模式匹配引擎使用编译器生成的带记忆确定有限自动机实现对模式匹配的加速，所述通过正则表达式规则编译器先把正则表达式转换为解析树，再分别把解析树转换为带记忆的非确定有限自动机和带记忆的确定有限自动机是：借助Lex和Yacc软件实现正则表达式上下文无关文法，对正则表达式规则语法进行解析，并在解析过程中根据匹配文法建立相应节点类型的子树，最终形成完整的解析树；在Thompson算法支持操作符的基础上，增加重复操作符({n，m})，其对应的非确定状态机与所重复表达式的非确定状态机相同，但增加了重复范围参数，使用该算法将解析树转换为带记忆的非确定有限自动机；对于不含重复操作符的非确定有限自动机，按ε-闭包算法生成确定有限自动机，而对于含有重复操作符的非确定有限自动机，则先用带有特殊标记的简单字符替换重复操作符，按ε-闭包算法把它转换为确定有限自动机，另外单独把被替换的部分按ε-闭包算法转换为另一个确定有限自动机；解析树由对应的正则表达式经解析生成，为一种每个节点分支不超过2的树，树中非叶节点为操作符，操作符包括连接操作符“·”、选择操作符“|”重复操作符“{n，m}”、Kleen闭包操作符“*”，叶子节点是单个字符、集合、集合的补集、代表集合的字符或代表集合补集的字符，集合与补集的转义字符序列符合IEEE POSIX 1003.2标准；所述的模式匹配引擎使用正则表达式规则编译器生成的带记忆确定有限自动机实现对模式匹配的加速是：模式匹配引擎读入正则表达式规则编译器生成的带记忆确定有限自动机和输入字符串，把输入字符串跟每个有限自动机进行匹配，匹配的位置保存在匹配上下文中；当一个有限自动机匹配完成，则根据该有限自动机类型确定下一步动作：如果该有限自动机不包含重复操作符，且没有后续有限自动机，则报告一个匹配；如果该有限自动机不包含重复操作符，但有后续有限自动机，则根据贪婪模式选项确定是否报告一个匹配，并生成一个后续有限自动机的匹配上下文；如果该有限自动机包含重复操作符，则增加匹配次数，并根据匹配次数决定下一步动作：如果匹配次数小于重复范围下限，则把匹配位置调整到有限自动机初始状态，继续匹配；如果匹配次数大于重复范围上限，则生成后续有限自动机的匹配上下文或报告一个匹配；如果匹配次数位于重复范围内，则把匹配位置调整到有限自动机初始状态，继续匹配；模式匹配引擎可以由现场可编程门阵列或专用集成电路实现，它实现了正则表达式数据库中的带记忆确定有限自动机，可接受输入数据，判断是否存在与库中正则表达式的匹配。