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

Question

我想知道将内部解析算法呈现为"LL(*)"的ANTLR v3是否完全代表PEG(解析表达式语法)解析器.

有区别吗？

Answer 1

该ANTLR文章是错的PEG。

LL(*)是DCFG（Deterministic Context Free Grammar）的一个子集，它是CFG（Context Free Grammar）的一个子集。

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 之间的两个主要区别：

LL(*) 只能向前看 DFA 模式，而 PEG 可以向前看递归模式。例如，在 PEG 中，您可以先行嵌套括号，而 LL(*) 则不能。
/PEG 中的选择操作符是优先选择（或“占有”），这意味着如果你有规则A / AB，它永远不会到达右手边AB。在 LL(*) 的规则中A | AB，可以匹配AB.

如果你有一个没有前瞻的 PEG 语法，或者你的前瞻模式可以简化为 DFA，那么它可以被翻译成 LL(*)。如果没有，那是不可能的。