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

Question

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

我猜在那里建立了一个有限状态自动机，但你必须比我更了解。

Answer 1

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

在 C# 中，three things can happen when you compile 之一:

类似于 Python 和 re2 的正则表达式对象被创建(实现为虚拟机)。

创建正则表达式对象，并将其虚拟机操作码即时编译为内存中的 IL 指令。

创建正则表达式对象，并将其虚拟机操作码作为 IL 指令编译到磁盘。

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

Regular Expression Matching Can Be Simple And Fast - 描述基于图的机器

Regular Expression Matching: the Virtual Machine Approach - 描述虚拟机实现