介绍

　　这个篇文章是对我的一个基本功能的正则引擎的实现过程的大致介绍与讨论，实际上在之前的文章中我已经对正则引擎的实现有所涉及，当时是翻译了有关Thompson NFA的文章，文章及其附带的源代码中已经对如何实现一个简单的正则引擎有了详细的说明，但是该文章对正则引擎的介绍并不深入，同时实现方式也过于简单化，虽然最终的结果是高效可靠的，但是这个实现不便于扩展，同时支持的功能也比较有限，因此在这一次的实现中，我采用了更加主流的方法，这样支持了更多的功能，同时也易于扩展。该项目使用的语言为C++，完整项目请移步regexEngine2。

引擎功能介绍

下面简单地介绍一下这一次的正则的一些功能(并联串联功能不再赘述)：

1.’*‘：零个或多个

2.’+’：一个或多个

3.’?’：零个或一个

4.’ . ‘：匹配任意一个字符

5.{a}：重复a次；{a,b}：重复次数大于等于a小于等于b；{a,}：重复次数大于等于a

6.[m-n]：匹配范围内的字符(例如：[a-g]等价于a|b|c|d|e|f|g等价于[abcdefg])

7.[^m-n]：匹配不是范围内的字符

同时还加入了一些特殊的转义字符：

1.\d：等价于[0-9]

2.\D：等价于[^0-9]

3.\s：等价于[\t\n\r\f]

4.\S：等价于[^\t\n\r\f]

5.\w：等价于[a-zA-Z0-9_]

6.\W：等价于[^a-zA-Z0-9_]

构造LR(1)项集族

　　在龙书的P167中为我们提供了为某一个文法G’构造LR(1)项集族的完整算法，照搬如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

SetOfItems CLOSURE(I) {
	repeat
		for(I中的每个项[A->α·Bβ,a])
			for(G'中的每个产生式B->γ)
				for(FIRST(βa)每个终结符号b)
					将[B->·γ,b]加入到集合I中;
	until 不能向I中加入更多的项;
	return I;
}

SetOfItems GOTO(I,X) {
	将J初始化为空集;
	for(I中的每个项[A->α·Xβ,a])
		将项[A->αX·β,a]加入到集合J中;
	return CLOSURE(J);
}

void items(G') {
	将C初始化为{CLOSURE}({[S'->·S,$]});
	repeat
		for(C中的每个项集I)
			for(每个文法符号X)
				if(GOTO(I,X)非空且不在C中)
					将GOTO(I,X)加入C中;
	until 不再有新的项集加入到C中;
}

　　上述的代码只是从理论角度提供的可行的算法，而具体怎么写还要根据我们的实现来进行修改。上边的item便是计算LR(1)项集族的主要函数，它会分别调用CLOSURE函数计算一个内核项所产生的项集，之后调用GOTO函数计算一个项集在遇到一个终结符或者非终结符时所产生的内核项。(内核项的概念十分重要，内核项是指包括初始项S'->·S以及点不在最左端的所有项，一个项集其实只用内核项表示就足够了，两个项集如果内核项一样，那这两个项集一定是相同的。)

前言

　　该项目是我在学习编译原理的时候所完成的一个项目，不同于成熟的yacc语法分析器，我的语法检查器通过和一个词法分析器相互配合，启动之前读入由BNF范式和正则表达式所描述的文法与词法，之后根据给定的文法对给出的代码文件进行检查，并指出文件中的错误。整个文法的解析以LR(1)为基础，总共的代码量为800左右（不包括词法分析器），完整的代码请移步Configurable-syntactic-analyzer。

正文

理论介绍

　　一般说来，常用的语法分析技术有两种，一种是自顶向下的，另一种是自底向上的，对于LL(1)型的文法来说，我们一般使用自顶向下的分析方式例如递归下降或者构造预测分析器的方式进行文法的解析，而其中递归下降分析法经常在手写的语法分析器中用到，这种方式对于大部分比较简单的文法是十分实用的，递归下降写起来也十分的方便。虽然LL(1)的文法足以描述大部分程序设计的构造，但是却无法描述左递归的文法以及二义性的文法，而在程序设计中，左递归的文法是经常出现的，例如S->Sab这样的产生式便是左递归的，因此递归下降的方式在此时并不适用，因此我们需要将左递归的文法经过某些变换，使它变为非递归的文法，但这种变换常常使得文法面目全非，而且实现起来也比较困难，因此我们提出了基于LR(k)的语法分析的概念。

前言

　　整篇文章是对作者Russ Cox的文章Regular Expression Matching: the Virtual Machine Approach的翻译，在我看来，该文章是入门正则引擎的较好的文章之一，读者在阅读之前，最好有一定的正则表达式的基础。翻译内容仅代表作者观点。侵删
　　该作者所有的文章的网址在此：https://swtch.com/~rsc/regexp/

正文

Pike实现

　　在“线程化”的实现，如thompsonvm中，我们简单地将保存后的指针加入到线程的状态中。Rob Pike首先于文本编辑器sam中使用了这种实现方式。

前言

　　整篇文章是对作者Russ Cox的文章Regular Expression Matching: the Virtual Machine Approach的翻译，在我看来，该文章是入门正则引擎的较好的文章之一，读者在阅读之前，最好有一定的正则表达式的基础。翻译内容仅代表作者观点。侵删
　　该作者所有的文章的网址在此：https://swtch.com/~rsc/regexp/

正文

非递归回溯实现

　　递归的回溯实现形式会持续运行一个线程直到它终止，并且以颠倒的顺序运行被创建的线程（新的最先运行）。等待运行得线程并没有被明确的编码，相反的，它们被间接地以pc和sp的值的方式存储在了C的调用栈中。如果同一时刻有过多的线程等待运行，C的调用栈可能会溢出，造成难以调试的错误。这种问题最常出现在处理重复如 .* 的时候，它会在每一个字符之后都创建一个新的线程（正如上边的例子中的a+所做的那样）。这会在多线程的程序中造成很大的困扰，因为它们常常对栈的大小有所限制，同时也没有对于栈溢出的硬件检查。

前言

　　整篇文章是对作者Russ Cox的文章Regular Expression Matching: the Virtual Machine Approach的翻译，在我看来，该文章是入门正则引擎的较好的文章之一，读者在阅读之前，最好有一定的正则表达式的基础。翻译内容仅代表作者观点。侵删
　　该作者所有的文章的网址在此：https://swtch.com/~rsc/regexp/

正文

介绍

　　说出几个如今被广泛应用的字节码解释器或者虚拟机：Sun公司的JVM？Adobe公司的Flash？.NET或者Mono？Perl？Python？PHP？这些的确都很流行，但是还有一个比上述这些加起来都还要广泛使用的，那便是Henry Spencer的正则表达式库的字节码解释器以及它的众多衍生。
　　该系列的第一篇文章介绍了实现正则匹配的两种主要的方法：一个是在awk和egrep中使用的，最坏情况为线性时间复杂度的基于NFA或DFA的策略，另一个是广泛使用的，包括sed，Perl，PCRE和Python，最坏情况为指数级时间复杂度的基于回溯的策略。
　　这篇文章介绍两种实现虚拟机的方法，该虚拟机执行已经被编译成为字节码的正则表达式，正如.NET和Mono是两种不同的方法去实现执行已经被编译成为CLI字节码的程序的虚拟机一样。

前言

　　整篇文章是对作者Russ Cox的文章Regular Expression Matching Can Be Simple And Fast的翻译，在我看来，该文章是入门正则引擎的较好的文章之一，读者在阅读之前，最好有一定的正则表达式的基础。翻译内容仅代表作者观点。侵删
　　该作者所有的文章的网址在此：https://swtch.com/~rsc/regexp/

正文

性能表现

　　前文中我们所提到的C语言的实现并未按照效率优先的方式编写，但即便如此，当我们的输入足够巨大的时候，一个线性时间复杂度的实现算法要远快与拥有指数时间复杂度的实现方法。我们用被称为病态的正则表达式去测试如今几个比较流行的正则引擎后得到的结果证明了上边的观点。
　　考虑一下a?ⁿaⁿ这一正则表达式。它可以匹配aⁿ。当a?选择不去匹配任何的字符的时候，整个字符串都会被后边的aⁿ所匹配。拥有回溯功能的正则引擎会在遇到零个或一个的符号 ? 时优先去匹配一个，之后才是零个。对于a?ⁿaⁿ来说，便有n个选择，一共就会产生2ⁿ种可能性。而只有最后一种可能性——为所有的 ? 均选择为不匹配才可以最终匹配成功。因此采用回溯的正则引擎会需要O(2ⁿ)的时间，所以当n大于25的时候，匹配所需的时间就相当可观了。
　　相反的，Thompson的算法在匹配长度为n的字符串，并在同时维护一个长度为n的状态列表所需要的匹配时间为O(n²)（整个的时间复杂度是超线性的，因为在输入增加的情况下，正则表达式不一定是恒定的，因此当我们使用长度为m的正则表达式去匹配长度为n的文本的时候，Thompson算法的时间复杂度为O(mn)）
　　下图展示了在不同的正则引擎下使用a?ⁿaⁿ去匹配aⁿ所需的时间：

前言

　　整篇文章是对作者Russ Cox的文章Regular Expression Matching Can Be Simple And Fast的翻译，在我看来，该文章是入门正则引擎的较好的文章之一，读者在阅读之前，最好有一定的正则表达式的基础。翻译内容仅代表作者观点。侵删
　　该作者所有的文章的网址在此：https://swtch.com/~rsc/regexp/

正文

正则表达式搜索算法

　　现在我们已经有了确定一个正则表达式是否匹配一个字符串的方法，将正则表达式转换为NFA之后以字符串为输入运行该NFA。记住NFA在面对多个选择的下一状态时能够很好地选择下一状态。而使用普通的计算机运行NFA时我们必须找到一个能够模拟这一能力的方法。
　　一种模拟猜测多种选择的方法是首先选择一个方向进行匹配，如果匹配失败，就选择余下方向中的一个。举个例子，考虑用abab|abbb的NFA去匹配字符串abbb：

前言

　　整篇文章是对作者Russ Cox的文章Regular Expression Matching Can Be Simple And Fast的翻译，在我看来，该文章是入门正则引擎的较好的文章之一，读者在阅读之前，最好有一定的正则表达式的基础。翻译内容仅代表作者观点。侵删
　　该作者所有的文章的网址在此：https://swtch.com/~rsc/regexp/

正文

正则表达式

　　正则表达式是一个用来表示一系列字符的字符串的符号，当一个确定的字符串处于一个正则表达式所描述的字符串系列时，我们通常说这一正则表达式匹配了这一字符串。
　　最简单的正则表达式是一个字面上的字符，除了一些特殊的元字符：*+？（）| 以外，字符匹配的是它们自身。而为了匹配特殊的元字符，我们在这些元字符之前加上一个斜线 \ ，例如\+ 则可以匹配加号。
　　两个正则表达式相并联或串联可以形成新的正则表达式：如果e₁可以匹配s,而e₂匹配t,那么e₁|e₂匹配s或者t，e₁e₂匹配st。
　　元字符*，+，？代表重复操作符，e₁*匹配一系列零个或多个元素的字符串，其中的每一个元素均匹配e₁；e₁+匹配一个或多个；e₁？匹配零个或一个。
　　操作符的优先级，由弱到强排列，首先是并联 |，之后是串联，最后是重复操作符。括号可以用来改变结合的顺序，就像书写算术表达式一样。例如：ab|cd与（ab）|（cd）含义相同，ab*与a（b*）含义相同。

前言

　　整篇文章是对作者Russ Cox的文章Regular Expression Matching Can Be Simple And Fast的翻译，在我看来，该文章是入门正则引擎的较好的文章之一，读者在阅读之前，最好有一定的正则表达式的基础。翻译内容仅代表作者观点。侵删
　　该作者所有的文章的网址在此：https://swtch.com/~rsc/regexp/

正文

介绍

　　下图是两种不同的正则引擎的匹配时间图。一个是被广泛应用于许多语言的标准解释器中，其中包括Perl。而另外一个则只被用到了少数的几个地方，比较出名的是awk和grep。这两种匹配方式有着相当不同的性能表现。