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

Question

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

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

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

我的问题和方法与较旧的帖子不同，因为我没有尝试开发用于执行正则表达式的解析器。我正在尝试为 future 的发展构建数据。我想知道如何以最佳方式利用现有的正则表达式工具。我相信 stackoverflow 是正确的论坛，因为它是正则表达式的核心，并且这个问题以其原始且不那么冗长的形式已被投票通过。

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

Answer 1

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

非确定性有限自动机

确定性有限自动机

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

在输入字符串中保留一个指向当前偏移量的指针

保持指向模式中当前位置的指针(被解释为图形或树)。

然后使用该模式作为如何在输入字符串中前进的秘诀。如果模式显示 a例如，如果当前输入偏移指向 a字符，则该字符将被消耗并且两个指针都将前进到下一个位置。如果字符不匹配，则会出现回溯(输入指针将转到前一个有效位置，模式指针将设置为输入位置的不同可能替代位置)。

重点是识别是由模式驱动的 .

(上面的解释非常粗略，因为它不包括优化等——无论如何现代模式都不能用正式的自动机实现)

DFA 实现则相反:

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

识别由输入驱动 .

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

NFA 引擎可以提供更多功能，但它们的运行时间取决于输入和模式本身的组合

DFA 引擎提供的功能较少，但它们的复杂度为 O(n)，其中 n 是输入字符串的长度。

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

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

基于树遍历方法的NFA算法

基于JIT编译的上述优化版本(每个支持的指令集一个版本)

DFA 实现

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