regex - 零个或多个/一个或多个修饰符和回溯

Question

我在我的 PEG 中添加了零个或多个和一个或多个修饰符解析器，这很简单，因为 PEG 中的回溯很少。早期的迭代永远不会被重新考虑，因此一个简单的 while 循环就足够了。

但是，在其他上下文中，零个或多个和一个或多个修饰符确实需要回溯。例如，采用以下正则表达式:

(aa|aaa)+

这个表达式应该能够贪婪地匹配由七个 a 组成的字符串:有多种方法可以将 2 和 3 相加得到 7。但是要实现这一目标，需要重新考虑早期的迭代。例如，如果表达式第一次匹配三个 a，第二次匹配三个 a，则仅剩下一个 a，即无法匹配。然而，回溯最后三个 a 并匹配两个 a，结果匹配了五个 a。那么最后两个 a 也可以匹配(即 3 + 2 + 2 = 7)。

幸运的是，正则表达式一旦匹配到字符串就会退出搜索。但是 EBNF 怎么样？解析器？如果语法不明确，解析器将使用回溯来查找所有可能的语法树!如果我们有生产

( "aa" | "aaa" )*

和一个由七个 a 组成的字符串，完全回溯解析器将返回用 2 和 3 表示 7 的所有可能方式。这只是七个 a >'s:匹配稍长的字符串，N 可能性树会增长另一个级别。考虑N = 6:

S : ( T )*
  ;

T : A
  | B
  | C
  | D
  | E
  | F
  ;

可怕的组合爆炸!

这真的是这样吗？ EBNF 中对零个或多个和一个或多个修饰符没有限制吗？按照描述实现它们会比 PEG 解析器的普通 while() 循环做更多的工作，所以我不得不想……

Answer 1

是的；回溯可以给你很多结果。我是 lepl 的作者，这是一个递归体面的解析器，它会愉快地回溯并生成所有可能的 AST 的“解析森林”。并且 EBNF 没有任何限制(它只是一种规范语言，不依赖于任何特定的解析器实现)。

但并非所有解析算法都会回溯。正则表达式的许多实现都这样做，但这并不总是必要的。事实上，对于一个“简单”的正则表达式(实际上仅限于正则语法的正则表达式)，完全可以在不回溯的情况下进行匹配 - 从某种意义上说，诀窍是并行运行。

有两种(等效)方法可以做到这一点 - 要么通过“编译”正则表达式(如果并行工作是显式的，则计算出表达式是什么)，或者通过在运行时处理并行匹配。编译方法将正则表达式转换为 DFA(确定性有限自动机)。更准确地说，NFA(非确定性...)有点像正则表达式的图形版本，并且可能就是您想象的正则表达式的工作方式；与 NFA 匹配确实需要回溯，但您可以将 NFA 转换为不需要回溯的 DFA。

但是，在运行时执行此操作更容易理解(并且在实践中往往更有用)，并且在三篇很棒文章中进行了解释，如果您想更好地理解这一点，您应该阅读这些文章: http://swtch.com/~rsc/regexp/regexp3.html以及开头的链接。

这一点我怎么强调都不为过——你需要阅读那些文章......

ps 模糊相关 - 您可以通过缓存稍后可能再次需要的结果(当您最终通过不同的路线到达相同的文本和表达式时)来使回溯更加有效。当应用于递归体面解析时，这被称为“Packrat 解析”(尽管说实话，它不值得单独命名 - 它实际上只是使用缓存)。缓存避免了指数运行时间 - 有一篇由norvig(谷歌的人，但这是之前写的)的论文解释说: http://acl.ldc.upenn.edu/J/J91/J91-1004.pdf