编译正则表达式时会发生什么？

Question

我们都知道你可以将你常用的正则表达式编译成性能非常好的东西.但是这幕巫术背后发生了什么呢？

我想那里有一个有限状态自动机,但你必须比我更清楚.

Answer 1

正则表达式编译的细节因实现而异.例如,Python或re2中的编译只是创建正则表达式对象的实例.该对象的状态机可以被建模为图形或虚拟机.如果没有编译(例如RE.match(expression, input):),每次match调用时都会在幕后创建一个新的正则表达式对象.如果您要多次使用表达式,这是不必要的工作.

在C#中,编译时可能会发生以下三种情况之一:

1. 创建一个类似于Python和re2的正则表达式对象(实现为虚拟机).
2. 创建正则表达式对象,并将其虚拟机操作码即时编译为内存中的IL指令.
3. 创建正则表达式对象,并将其虚拟机操作码作为IL指令编译到磁盘.

你提到了对算法的兴趣.看看Russ Cox关于两种方法的优秀文章:

• 正则表达式匹配可以简单快速 - 描述基于图形的机器
• 正则表达式匹配:虚拟机方法 - 描述虚拟机实现