正则表达式灵活、高效,具有极其强大的表达能力,在众多领域被广泛应用。在基于正则表达式为模式描述工具的应用中,需要将正则表达式转换成与之等价的有限状态自动机,运行自动机来实现应用。将给定的正则表达式转换成等价的有限状态自动机称为自动机构造。通常从两个方面来评价构造理论的有效性:一是其所获得的自动机的规模,其规模越小越好:另一个是构造算法本身的算法复杂性,其复杂性越低越好。论文提出了一种新的自动机构造理论和方法,并将其命名为PFA:Postfix Automata。PFA理论包含了最基本的定义及概念,确保理论完备性和正确性的各种定理和定律。论文给出了定理和定律正确性和有效性的证明,分析了 PFA构造算法计算复杂性;提出了利用PFA构造正则引擎的一套方法和算法;研究了将NFA转换成DFA的算法,提出了一种优化的NFA确定化为DFA的算法;并将PFA方法在FPGA硬件正则引擎上进行仿真。理论计算科学是计算机科学的根本和基石,形式语言与自动机理论在理论计算科学中占据着极其重要的地位,尤其是有限状态自动机和正则表达式,在自然语言理解、模式识别、交换理论、自动控制、编译器构造、蛋白质序列比对、光学字符识别、数据压缩及加密处理、通信协议分析等各种领域得到了广泛的应用。有限自动机理论所研究的内容包括正则文法及正则集、有限自动机的性质及其可判定性原理、正则表达式与有限自动机的等价性、正则表达式与有限自动机之间的等价互转换、不确定的有限自动机的确定化以及确定的有限自动机的最小化处理、构造有限自动机的算法及其复杂性分析等。这里的等价是指它们所表示或识别的是相同的正规语言。这些基础理论的研究及成果对正则表达式和有限自动机在各个领域的应用都有着重要的理论指导意义。执行模式匹配的有限自动机称为正则引擎。正则引擎的效率低下,是正则表达式和有穷自动机技术和应用中亟需解决的迫切问题。国内外大量专家和学者都在研究如何有效提高正则引擎匹配效率的问题,提出了规则改写、分组匹配、状态合并、混合自动机等多种能在一定程度上改善大规模正则表达式应用效率的方法和措施。在众多针对正则引擎效率的研究方法中,从有限自动机本身的理论入手,通过有效地减少有限自动机的规模的途径来提升正则引擎的效率,是一种能够从根本上解决正则引擎瓶颈问题的研究方法和途径。本文提出了一套新的自动机构造理论和算法,从基础理论着手,从根本上解决各种基于正则表达式的模式匹配技术和应用中的效率低下问题。本文首先给出了 PFA理论所包含的基本概念和定义,然后提出了一套完备的定律,包括规模最小性定理、恒等元定理、幂等律和吸收律,这些定理和定律保证了 PFA理论中运算的封闭性和正则性,也就保障了理论的正确性和完备性。基于上述基本概念和定理,本文提出了一系列的构造算法,论证了算法的正确性和有效性,对比分析了算法的计算复杂度。正则表达式和有限自动机技术在各个领域都得到了广泛的应用,本文所提出的PFA理论及其系列算法和方法,适用于任何采用正则表达式作为模式描述工具运行其等价自动机实现应用的各种领域。本文从有限自动机构造算法本身的理论和原理出发,围绕如何能够采用更加简单的方法来构造出更小规模的有限自动机的核心问题展开一系列的研究,最终达到从根本上简化正则引擎的实现、提升正则引擎匹配效率的最终目的。本文的研究工作和贡献主要体现在如下几个方面:(1)深入研究了已有的4大类自动机构造算法的原理及优缺点,提出了一种全新的自动机构造理论——PFA理论。PFA是一套完备、有效的有限自动机构造理论,规模最小性定理、恒等元定理、幂等律和吸收律这四个定理或定律从数学理论上证明了 PFA在将正则表达式转换成NFA的过程中所有操作的封闭性、正则性和同态性,从而也就证明了理论的正确性和完备性,以及这套理论在等价同态转换过程中对自动机规模压缩的有效性。(2)由于自动机的规模直接影响到正则引擎的效率。针对有效地减少自动机规模的问题,提出了一种基于后缀解析树的优化编码算法。该算法能够在保证同态性和封闭性的前提下,有效地缩减自动机的状态数目,并且能够非常简单地实现对状态的标识。状态标识的处理尽管简单并且看似与状态合并和空间压缩无关,实际上却直接实现了等价状态的合并和冗余转换弧的消除。由于自动机构造算法本身的难易程度影响了 IDS、IPS、DPI等众多系统中正则引擎的实现。针对算法本身尽可能简单易于实现的问题,提出了基于后缀编码树遍历操作来构造规模更小的有限状态自动机的算法。该算法不但算法本身的时间空间复杂度较现有的各种自动机构造算法要小,并且能够获得比当前实践中最常用的Thompson构造法和Glushkov构造法规模更小的自动机,一般情况下,该算法能够获得接近当前规模最小的后跟自动机构造法的自动机的规模。(3)折中NFA引擎和DFA引擎的优缺点,采用混合正则引擎是当今用于提升系统效率的一个有效而常用的手段。PFA理论使得构造一组正则表达式的单一 NFA能够很简单地实现。而子表达式和自动机分片的识别和处理,使得构造NFA/DFA混合引擎能够简单而有效的实现。同时,能够基于识别子表达式构造出规模更小的自动机,就能有效地提升混合引擎的效率。针对子表达式的嵌入式自动机构造问题,提出了一个基于分片和重组的构造更小NFA的算法。(4)将NFA转换成等价DFA的过程称为自动机的确定化。自动机的确定化算法的难易程度同样也直接影响着DFA和NFA/DFA混合引擎的匹配效率。针对自定价确定化问题,提出了一个优化的有限状态自动机确定化算法,该算法实现起来简单,相较于传统的自动机确定化算法子集法来说,其算法本身的复杂度都下降了 一个数量级。(5)硬件具有天然的并发性和高速性,基于硬件实现的正则引擎在大规模模式集下仍能够获得较高吞吐率的匹配性能,因此近年来基于FPGA的硬件正则引擎设计成为一大研究热点。评价FPGA引擎效率主要有“速度”和“面积”两个性能指标。速度通常用吞吐量来衡量,即每秒能处理的最大比特位数;面积则是指实现相同正则表达式集所占用的逻辑资源数。将给定的正则表达式集转换成等价的NFAs的规模在很大程度上决定“速度”和“面积”这两个指标。针对如何有效提升硬件FPGANFA引擎效率的问题,将本文提出的PFA理论和算法应用于FPGA NFA引擎的设计上,利用PFA规模小的优势,使得能够利用相同的FPGA资源实现更多条正则表达式的匹配,从而有效地提升了 FPGA NFA引擎的性能。Testbench模拟仿真的结果表明,这种方法能够完全实现预期匹配要求,而其支持的正则表达式的数量和匹配速度都因有效的规模压缩而得到了很大的提升。