LL(*)与PEG解析器：有什么区别？

Question

14

我在想ANTLR v3是否完全代表了PEG（解析表达式语法）解析器，因为它将其内部解析算法表示为“LL（*）”。

它们有什么区别吗？

- JCLL

4个回答

4

在ANTLR中，您可以在语法中的所有生成规则上启用全局回溯，这样对于k >= 1，您可以实现与PEG相同的解析。当然，由于所有潜在的回溯，解析器的运行时间会降低。通过（一些）内存成本，您还可以启用备忘录功能，使其表现得像Packrat-parser，能够在线性时间内解析输入。

因此，就ANTLR和PEG/Packrat而言，如果启用了正确的选项，它们之间没有太大的区别！

- Bart Kiers

3

ANTLR和PEG并不相同。这是一个非常理论性的问题，我认为最好是参考Terrence Parr写的这篇文章，他在其中精确地指出了ANTLR和PEG之间的区别以及ANTLR LL(*)解析策略的一些优点。我不想随意改述他在那里写的内容，但你最好阅读整篇文章。

- vldmrrdjcc

1

根据这里列出的工具，ANTLR是PEG解析器的完整代表：

ANTLR是由Terence Parr开发的一款成熟的解析器生成器，支持广泛的PEG特性，并将packrat解析与LL解析技术相结合。

- H-Man2

存在一些左递归的Packrat扩展，显然ANTLR不支持。 - SK-logic

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

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

- luikore · Accepted Answer

ANTLR文章关于PEG是错误的。

LL(*)是DCFG（确定性无上下文文法）的子集，其为CFG（上下文无关文法）的子集。

PEG可以表达上下文敏感语法，例如A{n}B{n}C{n}，其中A、B和C都出现了n次。这是定义：

s := &(x C) A+ y / ε
x := A x B / A B
y := B y C / B C

但是在CFG中没有办法定义这样的语法（证明涉及泵引理）。因此，PEG不是CFG的子集。PEG是否是CFG的超集？我不知道。

LL(*)和PEG之间的两个关键区别：

1. LL(*)只能向前查看DFA模式，而PEG可以向前查看递归模式。例如，在PEG中，您可以向前查看嵌套的括号，而LL(*)不能。

2. PEG中的选择运算符“/”是优先级选择（或“占有性”），这意味着如果您有规则“A / AB”，它永远不会到达右侧的“AB”。在LL(*)中，对于规则“A | AB”，可能会匹配“AB”。

如果您有一个没有前瞻的PEG语法，或者您的前瞻模式可以简化为DFA，则可以将其转换为LL(*)。否则，不可能。