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

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

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

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

在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 – 描述虚拟机实现

相关文章
相关标签/搜索