正则表达式如何在幕后工作(在CPU级别)？

Question

解释器和编译器是否比较(并最终匹配)两个字符串,以逐个字符和从左到右的方式进行潜在匹配？或者是否在比较函数中为每个字符串分配了基础二进制值(例如,位模式)？或者它取决于以某种方式编码的字符串(ASCII或UTF-32),还是解释器,编译器,数据库引擎或编程语言？

重新设计数据存储(数据文件或数据库)是一项相当大的工作.stackoverflow上类似问题的答案并没有明确地描述编码问题(是否正在评估位模式或实际的字母字符).这个问题的答案对于优化工作可能很重要.

我不想知道如何实现正则表达式(例如,写我自己的).出于教育目的,我想知道以最佳方式使用现有正则表达式的好处(例如,当设计数据作为子串的组合存储时,我是否应该注意从左到右的评估).类似的StackOverflow问题的答案(这是一个具有不受信任的证书来查看它的链接)侧重于有限自动机(如何比较字符串的理论).这个答案强调它如何工作以及比较字符串的计算复杂性.它确实意味着存在从左到右的角色评估.我认为无论如何都不是决定性的.这篇文章主要针对Perl和语言无关的Thomson非确定性有限自动机算法.我想知道这三种技术组合:1)使用ASCII数据文件的Java本机函数,2)MySQL(表数据和SELECT语句),以及3)使用Python本机函数和UTF-32数据文件.

我的问题和方法与旧帖不同,因为我不是在尝试使用正则表达式开发解析器.我正在尝试构建数据以供将来开发.我想知道如何以最佳方式利用现有的正则表达式工具.我相信stackoverflow是正确的论坛,因为它是正则表达式的核心,并且这个问题以其原始且不那么冗长的形式进行了投票.

我想知道在CPU级别,字符串模式是字符串中字符的表示吗？是否存在与参与比较的字符串的每个字符相对应的位模式的短寿命索引,其中一个字符串被锚定？我认为技术(例如,数据库,编程语言和/或数据的编码)会有所不同.

Answer 1

有两大类正则表达式引擎,称为NFA和DFA(我使用的是Jeffrey Friedl的书中的术语):

• 非确定性有限自动机
• 确定性有限自动机

NFA实现将大致按以下方式工作:

• 保持一个指向电流偏移的输入字符串
• 保持的指针的当前位置的图案(其被解释为图形或树).

然后使用该模式作为如何在输入字符串中前进的配方.a例如,如果模式说明,并且当前输入偏移指向一个a字符,那么该字符将被消耗,并且两个指针将前进到下一个位置.如果字符不匹配,则会有回溯(输入指针将转到先前的有效位置,并且模式指针将在输入位置设置为不同的可能替代).

关键是识别是由模式驱动的.

(上面的解释非常粗糙,因为它不包括优化等等 - 现代模式无法用正式的自动机实现)

DFA实现以相反的方式工作:

仍然有一个输入指针,但有多个模式指针.输入模式将逐个字符地前进,并且模式指针将跟踪给定输入的模式中的有效状态.

该识别是通过输入驱动.

这两种方法都有非常不同的属性:

• NFA引擎可以提供更多功能,但它们的运行时间取决于输入和模式本身的组合
• DFA引擎提供的功能较少,但其复杂度为O(n),其中n是输入字符串的长度.

一些正则表达式引擎(例如PCRE)可以实现两种识别方法.我建议您阅读关于两种匹配算法的PCRE文档,它们解释了更多技术术语的差异.

至于实际的实现,它高度依赖于正则表达式引擎本身.PCRE有几个:

• 一种基于树遍历方法的NFA算法
• 基于JIT编译的上述优化版本(每个支持的指令集一个版本)
• DFA实施

所以你实际上可以看到NFA有几种可能的方法.其他引擎具有允许不同功能集的不同实现.例如,.NET的正则表达式可以从左到右或从右到左匹配,因此可以很容易地提供可变长度的后视,而PCRE的后观是通过将后端的预期输入临时移位到左侧的输入指针来实现的.长度,并从此偏移量执行从左到右的匹配.

Answer 2

正则表达式的工作方式是一个实现细节。它们可以通过一种方式或第二种方式实现。

事实上，有些语言的实现效率很低。

如果你想了解更多，我可以参考这篇文章： https: //swtch.com/~rsc/regexp/regexp1.html