一种构造正则表达式更小ε-NFA的方法  

A Constructing Method of Regular Expression's Smaller ε-NFA

作　　者：敬茂华[1,2] 杨义先[2,3] 于长永[1] 辛阳[3] 

机构地区：[1]东北大学秦皇岛分校计算机与通信工程学院,河北秦皇岛066004 [2]东北大学信息科学与工程学院,辽宁沈阳110819 [3]北京邮电大学信息安全中心,北京100876

出　　处：《东北大学学报（自然科学版）》2013年第9期1240-1243,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(61100021;61121061;61202447);河北省自然科学基金资助项目(F2012501014);教育部高等学校博士学科点专项科研基金资助项目(20120042120009);河北省自然科学青年基金资助项目(F2013501048)

摘　　要：基于有限自动机的正则表达式匹配技术在网络信息领域得到了广泛应用,提出了一种构造正则表达式的更小NFA的方法——基于闭包的分片构造法GREC.GREC方法基于正则表达式中同态运算的封闭性以及闭包运算的层次特性和递归性进行构造.首先对正则表达式进行分片处理,然后构造每个分片的NFA,最后利用栈对各分片NFA进行重组获得最终的NFA.GREC方法在正则表达式层次结构复杂或包含有大量闭包运算的情况下,能够快速地构造出空间效率比传统的Thompson构造法高得多的NFA.Regular expression matching technology based on finite automaton（FA） has been w idely used in the netw ork and information field.A new method w as proposed to construct the smaller nondeterministic FA（NFA） of regular expressions,namely,grouping regular expression based on closure（GREC）.The GREC method w as constructed based on the principle that all kinds of homomorphism computing of regular expression w ere closure and the hierarchy and recursiveness of closure operation w ere in regular set.The regular expression w as cut into pieces,and then the NFA w as constructed for each slice.Finally the stack to the restructuring of the NFA of each slice w as used to obtain the final NFA.It can be concluded that NFA can be quickly constructed by the proposed GREC method,w hich has higher space efficiency compared w ith traditional Thompson structured approach w hen the regular expression is too complex in hierarchical structure or contains too many closure operations.

关 键 词：正则表达式 有限自动机 闭包 同态运算 构造算法 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]