regex - RegEx 引擎的工作原理

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




8年前关闭。




在学习正则表达式时，我想知道底层引擎是如何工作的。可能更具体地说，我想更多地了解它如何评估、确定优先级和解析表达式。我觉得 RegEx 引擎对我来说是一个黑匣子，我真的很喜欢破译它。

所以我想问一下是否有一些很好的资源可以阅读，讨论 RegEx 引擎理论。

*注意:我对构建引擎不感兴趣，只是学习它的内部工作原理。

Answer 1

有两类主要的正则表达式引擎。

那些基于有限状态自动机的。这些通常是最快的。他们通过建立 state machine 来工作, 并从输入字符串中输入字符。在这样的引擎中实现一些更高级的功能是很困难的，如果不是不可能的话。

基于 FSA 的引擎示例:

Posix/GNU ERE/BRE — 用于大多数 unix 实用程序，例如 grep、sed 和 awk。

Re2 — 一个相对较新的项目，试图为基于 Automata 的方法赋予更多功能。

那些基于回溯的。这些通常将模式编译成字节码，类似于机器指令。然后引擎执行代码，从指令跳转到指令。当一条指令失败时，它会回溯以找到另一种匹配输入的方法。

基于回溯的引擎示例:

Perl - 原本的。大多数其他此类引擎都尝试在 Perl 语言中复制正则表达式的功能。

PCRE — 最成功的实现。这个库是使用最广泛的实现。它具有丰富的功能集，其中一些不能被视为"Regular"没有了。

Python , Ruby , Java , .NET — 其他实现我不打算进一步描述。

想要查询更多的信息:

regular-expressions.info - Tutorial

regular-expressions.info - Flavor comparison

swtch.com - Implementing Regular Expressions — 一组关于有效的、基于自动机的正则表达式的好文章。

如果你想让我扩展一些东西，发表评论。