PEG和CFG之间有什么区别？

Question

从这个维基百科页面中可以了解到：

上下文无关文法和解析表达式文法的根本区别在于PEG的选择运算符是有序的。如果第一个备选成功，那么第二个备选将被忽略。因此，与上下文无关文法和正则表达式中的无序选择不同，有序选择是不可交换的。有序选择类似于某些逻辑编程语言中可用的软剪切运算符。

PEG的选择运算符为什么会短路匹配呢？这是为了减少内存使用（由于备忘录机制）吗？

我不确定正则表达式中的选择运算符是什么，但假设它是这样的：/[aeiou]/以匹配元音字母。那么这个正则表达式是否是可交换的，因为我可以将它写成五个元音字符的5！（五的阶乘）排列之一？即/[aeiou]/与/[eiaou]/表现相同。它可交换的优点是什么？（与 PEG 的非交换性相比）

从下面的引用中可以了解到：

其结果是，如果一个CFG直接被转换为PEG，那么前者中的任何歧义都将通过确定性地从可能的解析树中选择一棵来解决。通过仔细选择语法备选项的顺序，程序员可以对选择哪个解析树有很大的控制权。

这是在说PEG的语法优于CFG吗？

- Frankie Ribery

---

“优秀”？你对“优秀”的标准是什么？ - Gabe

对于可交换性，可以想象(air|airplane)试图匹配单词airplane。 - xanatos

看起来你混淆了选择运算符和字符类的概念。在正则表达式中，字符类用方括号 [aeiou] 分隔，而选择运算符是管道字符 |，而在 PEG 中，选择运算符是斜杠字符 /。 - hippietrail

Answer 1

一个CFG语法是非确定性的，意味着某些输入可能会导致两个或多个可能的解析树。虽然大多数基于CFG的解析器生成器对语法的确定性有限制。如果它具有两个或更多选择，则会发出警告或错误。

一个PEG语法是确定性的，意味着任何输入只能被一种方式解析。

以经典示例为例；语法

if_statement := "if" "(" expr ")" statement "else" statement
              | "if" "(" expr ")" statement;

应用于输入

if (x1) if (x2) y1 else y2

可能被解析为

if_statement(x1, if_statement(x2, y1, y2))

或者

if_statement(x1, if_statement(x2, y1), y2)

使用CFG解析器会生成一种移进/规约冲突，因为当到达 "else" 关键字时，它无法确定是应该移进（读取另一个标记）还是规约（完成节点）。当然，有方法可以解决这个问题。

使用PEG解析器将总是选择第一个选项。

哪一个更好由您来决定。我的观点是，通常编写PEG语法比较容易，而分析CFG语法更容易。

- Markus Jarderot

---

你能提供一个这样的CFG语法的例子吗（带有2个解析树）？ - Frankie Ribery

Answer 2

我觉得你把CFG和LR以及二义性混淆了。语法不是确定性/非确定性的，尽管它们的解析器可能是。如果符合定义，即使是一个有歧义的语法仍然是CFG，可以构建一个确定性解析器来执行像PEG一样的操作。

- Apalala

---

不，上下文无关文法有时是模糊的，因为它们的“选择”运算符没有优先级，所以如果给定字符串匹配“选择”中的两个选项，则存在歧义。在解析表达式语法中，每个“选择”操作只尝试一次，因此具有首次匹配优先级，因此不存在歧义，因为最左边的选项必然获胜。 - aaronblohowiak

不。CFG可能存在歧义，因为所有选项都是同样有效的。当相同短语可以通过不同的产生式序列生成时，CFG就存在歧义。在LL和LR中，歧义意味着解析器/识别器无法知道哪个产生式序列（哪个语法树）对应于给定的短语。PEG通过按照它们被声明的顺序排列产生式来解决歧义问题。它告诉解析器正确的语法树是第一个语法树。 - Apalala

Answer 3

PEG和CFG是指定语言的两种不同方式。如果您手动编写解析器，那么很有可能会编写所谓的递归下降解析器。递归下降解析器将自动解决语法中的任何歧义，但是这样做是静默的，并且可能不是您想要的方式。问题在于，除非您彻底测试解析器，否则您永远不会发现已经自动解决了歧义。 PEG基本上是递归下降解析器的形式化，因此具有此问题。有关此问题的示例，请参见How does backtracking affect the language recognized by a parser?和https://cs.stackexchange.com/questions/143480/dragon-book-4-4-5-exercise/143975。

CFG具有大量理论支持，但PEG并没有。可以通过CFG编码的语言集合与可以通过PEG编码的语言集合部分重叠，但两者都不包含对方。

如果您想进行更全面的审查，我建议阅读优秀的文章哪种解析方法更好？

- hkBst