RegEx引擎如何工作

在学习正则表达式时，它让我想知道底层引擎是如何工作的。也许更具体一点，我想知道更多关于它如何评估，优先考虑和解析表达。我觉得RegEx引擎对我来说是一个黑盒子，我真的很喜欢破译它。RegEx引擎如何工作

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

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

2010-09-01 Robb

掌握正则表达式是一本很棒的书，虽然它没有关注这个主题，但它有几章讨论每个正则表达式引擎的行为。（尽管它更实用一些，而不是分析引擎本身的细节） – NorthGuard 2010-09-01 22:56:22

我实际上一直在探索那本书，但并不了解这些章节。谢谢！ – Robb 2010-09-02 00:26:01

一个优秀的artile是：[如何RegEx工程]（http://perl.plover.com/Regex/article.html） – PHPst 2012-11-14 17:02:21

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

那些基于有限状态自动。这些通常是最快的。他们通过构建state machine并从输入字符串中提供字符来工作。即使不是不可能，在这样的引擎中实现一些更高级的功能也是困难的。基于FSA引擎

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

例子：
- Perl —原。这种类型的大多数其他引擎都试图在Perl语言中复制正则表达式的功能。
- PCRE —最成功的实施。这个库是使用最广泛的实现。它具有丰富的功能，其中一些功能不再被视为"Regular"。
- Python,Ruby,Java,.NET —其他实现我不打算进一步描述。

欲了解更多信息：

如果您希望我在某些方面有所扩展，请发表评论。

2010-09-02 11:17:15

它看起来像我有一些工作为我贴出链接，但我相信这是更多的东西我正在寻找。更进一步的，如果你知道一本可以购买的实际书籍，那就太棒了。 – Robb 2010-09-02 15:24:28

我还没有读过关于这个主题的很多书，但我喜欢的是Michael Sipser的“计算理论导论”。它不仅仅是正则表达式，而是一直到图灵机和NP完整性等。 – 2010-09-02 16:52:29

回答