perl、python、java、vim等实现正则表达式解析的基本方法是什么？
不是聪明的形式语言方法(即 NFA、DFA)；也不是解析器组合器(例如 14 line regex engine )。
我看过 java 实现 perl 风格正则表达式的源代码，但它复杂的特性(例如反向引用)和效率(例如 Boyer-Moore 子串匹配)让人很难看清它是如何实现的 < em>基本上 有效。
编辑 各种消息来源称涉及“回溯”(例如 Regular Expression Matching Can Be Simple And Fast ；形式化方法 类(class))，但不清楚回溯的确切内容在上...这是一种方式评估一个NFA？可以直接从正则表达式的 AST 完成吗？
java/perl/python 正则表达式引擎实际上做了什么？
它是不是类似于:“一种生成常规语言中所有可能单词的方法，但一旦与输入字符串不匹配就放弃特定单词”。
请您参考如下方法:
正则表达式引擎有两种通用方法。
正则表达式可以转化为有穷自动机。这种关系在计算机科学中得到了充分研究。然后这些有限的自动化可以高效地执行，甚至倒退运行。它们提供了强有力的保证，例如关于输入字符串在线性时间和恒定空间中运行，但是从正则表达式创建有限自动机可能很昂贵。这种方法还将引擎限制为真正的正则表达式，即排除了反向引用或递归等高级功能。
回溯引擎可以解释正则表达式。如果模式中的备选方案失败，则可以回溯到最后的决策点并尝试不同的方法。这是非常灵活的，并且(具有递归 + 命名子模式等额外功能)可以解析更大类的形式语言(形式上，类似于 LL(*) 语法集)。这与 PEG 解析器非常相似。最大的缺点:由于回溯，运行正则表达式可能会花费指数时间——即使没有任何额外的高级功能也是如此。
最重要的是，正则表达式引擎具有额外的优化功能，例如首先搜索模式中的常量子字符串，因为这比运行任何类型的正则表达式(甚至可以使用矢量化 CPU 指令)都更有效。如果在多个常量字符串之间有一个选择点，那么可以很容易地将它们编译成一个 trie 数据结构(实际上是一个简单的有限自动机)。这可以减少回溯量。
证明有限自动机和回溯之间区别的正则表达式是字符串 aaaaaaaaaaaaaaacb 上的 a*a*a*a*a*b 模式。由于输入中的 c，有限自动机可以很容易地看出此模式将不匹配。但是回溯引擎现在有很多决策点，它可以为每个 a* 子模式尝试不同的长度。在这种情况下，Perl 或 Python 中的 re 模块等正则表达式引擎呈指数增长，即需要很长时间才能完成——向输入添加更多 a 以使其花费更长的时间。如果不受信任的用户可以提供任意正则表达式，这将允许进行有趣的拒绝服务攻击。对于不受信任的输入，只应使用基于有限自动机的正则表达式引擎，例如来自谷歌的 RE2。
