解释器和编译器是否以逐个字符和从左到右的方式比较(并最终匹配)两个字符串是否可能匹配?或者是否有一个底层二进制值(例如,位模式)分配给比较函数中的每个字符串?或者它是否取决于以某种方式(ASCII 或 UTF-32)编码的字符串,或者解释器、编译器、数据库引擎或编程语言?
重新设计数据存储(数据文件或数据库)是一项相当大的工作。 stackoverflow 上类似问题的答案并未明确描述编码问题(是评估位模式还是实际的字母字符)。这个问题的答案对于优化工作可能很重要。
我不想知道如何实现正则表达式(例如,编写我自己的)。我想知道出于教育目的以最佳方式使用现有正则表达式的好处(例如,当需要设计要存储为子字符串组合的数据时,我是否应该注意从左到右的评估)。类似的 StackOverflow 问题answer https://swtch.com/~rsc/regexp/regexp1.html(这是一个具有不受信任的证书的链接,可以查看它)重点关注有限自动机(如何比较字符串的理论)。该答案强调了它的工作原理以及比较字符串的计算复杂性。它确实意味着存在从左到右的角色评估。我认为无论如何这都不是决定性的。这篇文章主要针对 Perl 和与语言无关的 Thomson 非确定性有限自动机算法。我想确切地了解这三种技术组合:1)使用 ASCII 数据文件的 Java 本机函数,2)MySQL(表数据和 SELECT 语句),以及 3)使用 Python 本机函数和 UTF-32 数据文件。
我的问题和方法与旧帖子不同,因为我并不是试图开发一个用于执行正则表达式的解析器。我正在尝试为未来的开发构建数据。我想知道如何以最佳方式利用现有的正则表达式工具。我相信 stackoverflow 是正确的论坛,因为它是正则表达式的核心,并且这个问题以其原始且不那么冗长的形式已被投票通过。
我想知道在CPU级别,位模式是字符串中字符的表示形式吗?是否存在与参与其中锚定一个字符串的比较的字符串的每个字符相对应的位模式的短期索引?我认为技术(例如数据库、编程语言和/或数据编码)会有所不同。
正则表达式引擎有两大系列,称为NFA and DFA(我使用的是 Jeffrey Friedl 书中的术语):
NFA 实施将roughly按以下方式工作:
- 保留一个指向a的指针当前偏移量 in the 输入字符串
- 保留一个指向当前位置 in the pattern(被解释为图形或树)。
然后使用该模式作为recipe如何在输入字符串中前进。如果模式说a
例如,如果当前输入偏移指向一个a
字符,那么该字符将是consumed并且两个指针都会前进到下一个位置。如果字符不匹配,则会回溯(输入指针将转到先前的有效位置,并且模式指针将在输入位置设置为不同的可能替代位置)。
重点是识别是由模式驱动的.
(上面的解释是very粗糙,因为它不包括优化等 - 而且现代模式无论如何都不能用正式的自动机来实现)
DFA 实现的工作原理相反:
还有one输入指针,但有multiple模式指针。输入模式将逐个字符前进,并且模式指针将跟踪给定输入的模式中的有效状态。
The 识别由输入驱动.
这两种方法具有非常不同的属性:
-
NFA引擎可以提供更多的功能,但它们的运行时间取决于输入和模式本身的组合
-
DFA引擎提供的功能较少,但其复杂性O(n), where n是输入字符串的长度。
一些正则表达式引擎(例如PCRE)可以实现这两种识别方法。我建议您阅读PCRE 文档 http://www.pcre.org/current/doc/html/pcre2matching.html关于两种匹配算法,用更专业的术语解释了差异。
至于actual实现,它很大程度上取决于正则表达式引擎本身。 PCRE 有几个:
- 基于树遍历方法的NFA算法
- 基于 JIT 编译的上述优化版本(每个支持的指令集一个版本)
- DFA 实施
因此,您实际上可以看到,仅针对 NFA 就有几种可能的方法。其他引擎具有不同的实现,允许不同的功能集。例如,.NET 的正则表达式可以从左到右或从右到左匹配,因此可以轻松提供可变长度的lookbehind,而 PCRE 的lookbehind 是通过将输入指针临时向左移动lookbehind 的预期输入来实现的长度,并从此偏移量执行从左到右的匹配。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)