Jeff Moser解释.NET正则表达式的工作方式[infoq]

Jeff Moser发表了一篇对.NET中正则表达式工作方式的深入解析。他的文章谈及了微软实现中的一些核心操作原理，如编译正则表达式时使用的机器码。

他首先透露，最近使用的15个正则表达式会被缓存起来。对于那些只使用1到2个正则表达式的小型的应用程序，这意味着没有必要每次都创建一个Regex对象。

在编译正则表达式的时候，首先会通过一个扫描器（scanner）来生成（emit）一个RegexTree。它的叶子节点就好像一种略加扩展的源代码，而下一步便是把它转换为正则表达式引擎所使用的机器码。

这些工作由EmitFragment函数完成，其中包含了大约250行的switch语句。这个函数把RegexTree打散成“碎片”再将它们转化为相对简单的RegexCode。

[…]

这些工作生成一个用于描述RegexCode“操作码”及其参数的整数数组。例如，你可以看到一些例如“Setrep”的指令携带了一些字符串参数。这些参数指向了一个字符串表中的偏移量。这就是为什么说，正如我们之前看到的那样，把所有的东西打包成那些不规则字符串是很重要的原因。这是唯一可以传递指令信息的方法。

把代码数组分解之后，我们可以看到：

索引	指令	操作码/参数	字符串表的引用	描述
0	Lazybranch	23		延迟扩展至偏移量为21的Stop指令。
1		21
2	Setmark	31		把我们当前的状态放入栈中以便稍后进行回溯。
3	Multi	12		对字符串表中的第0项（即“http://”）进行一次多字符匹配。
4		0	"http://"
5	Setmark	31		把我们当前的状态放入栈中以便稍后进行回溯。
6	Setrep	2		对于字符串表中位置为1的集合（即[^\s/]）进行长度为1的反复匹配。
7		1	"\x1\x2\x1\x2F\x30\x64"
8		1
9	Setloop	5		在最多为Int32.MaxValue次的循环中对[^\s/]集合进行匹配。
10		1	"\x1\x2\x1\x2F\x30\x64"
11		2147483647
12	Capturemark	32		捕获组#1，即最近一次Setmark所标记的位置，到当前位置的字符串。
13		1
14		-1
15	Oneloop	3		在最多为1次的循环中匹配Unicode字符47。
16		47
17		1
18	Capturemark	32		捕获组#0，即第一次Setmark所标记的位置，到当前位置的字符串。
19		0
20		-1
21	Stop	40		停止匹配。

可以看到，正则表达式已经被转化为一个稍后可供运行的简单“程序”。

Jeff Moser的博客中描述了有关这个过程的更多信息。他的文章还讨论了：

• 前缀优化
• 解释器
• 回溯
• 已知错误

查看英文原文：Jeff Moser's How .NET Regular Expressions Really Work