3

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

然而，在其他情况下，零个或多个和一个或多个修饰符确实需要回溯。例如，采用以下正则表达式：

(aa|aaa)+

这个表达式应该能够贪婪地匹配一个由 7 组成的字符串a：有几种方法可以将 2 和 3 相加得到 7。但要做到这一点，重新考虑早期的迭代是必要的。例如，如果表达式a第一次匹配 3 a，第二次匹配 3，则只剩下一个a，无法匹配。但是，回溯最后三个a并匹配两个a，然后匹配五个a。然后最后两个a也可以匹配（即3 + 2 + 2 = 7）。

幸运的是，正则表达式在匹配字符串后退出搜索。但是EBNF解析器呢？如果语法不明确，解析器将使用回溯查找所有可能的语法树！如果我们有生产

( "aa" | "aaa" )*

和一个由 7 组成的字符串a，一个完全回溯的解析器将返回用 2 和 3 来表达 7 的所有可能方式。这只是针对 7a的：匹配一个稍长的字符串，并且N叉树的可能性会增长另一个层次。考虑N  = 6：

S : ( T )*
  ;

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

恐怖的组合爆炸！

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

4

1 回答 1

7

是的; 回溯可以给你很多结果。我是 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

于 2011-08-28T01:13:39.980 回答