正则表达式引擎是如何工作的

Question

44

在学习正则表达式时，我想知道其底层引擎是如何工作的，具体来说，我想了解更多关于它如何评估、优先处理和解析表达式的信息。我感觉正则表达式引擎对我来说是一个黑匣子，我真的很想揭开它的神秘面纱。

因此，我想问一下是否有一些优秀的资源可以让我学习正则表达式引擎的原理。

*注意：我不想构建引擎，只是想学习其内部工作原理。

- Robb

1

正则表达式引擎基于有限状态机。有关正则表达式匹配速度如何的详细文章可参见http://swtch.com/~rsc/regexp/regexp1.html。 - Giuseppe Cardone

拿一些关于自动机理论的书。这里也可以找到好的文章：http://swtch.com/~rsc/regexp/ - Vadim Shender

1

精通正则表达式是一本非常好的书，尽管它不仅专注于该主题，但它确实有几章涉及每个正则表达式引擎的行为方式。（虽然更多地是实践性而非分析引擎本身的细节） - NorthGuard

我实际上一直在翻阅那本书，但不知道有这些章节。谢谢！ - Robb

1

一篇优秀的文章是：正则表达式是如何工作的。 - Handsome Nerd

为什么这个问题不适合我们的问答格式？（目前的状态下） - Nur

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Markus Jarderot · Accepted Answer

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

基于有限状态自动机的引擎。这些通常是最快的。它们通过构建状态机并从输入字符串中提取字符来工作。在这样的引擎中，实现一些更高级的功能可能很困难，甚至不可能。

基于FSA的引擎示例：
- Posix/GNU ERE/BRE - 用于大多数Unix实用程序，如grep、sed和awk。
- Re2 - 一个相对较新的项目，旨在为基于自动机的方法提供更多的功能。
基于回溯的引擎。这些引擎通常将模式编译成类似于机器指令的字节码。然后引擎执行代码，从指令跳转到指令。当某个指令失败时，它会回溯以找到另一种匹配输入的方法。

基于回溯的引擎示例：
- Perl - 最初的版本。这种类型的大多数其他引擎都试图复制Perl语言中正则表达式的功能。
- PCRE - 最成功的实现。这个库是使用最广泛的实现。它具有丰富的功能集，其中一些不能再被认为是“正则表达式”。
- Python、Ruby、Java、.NET - 我不打算进一步描述的其他实现。

更多信息请参考：

如果您需要我对某些内容进行扩展，请发表评论。