38

从这个维基百科页面：

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

为什么 PEG 的选择算子会短路匹配？是因为尽量减少内存使用（由于记忆）？

我不确定正则表达式中的选择运算符是什么，但让我们假设它是这样的：/[aeiou]/匹配元音。所以这个正则表达式是可交换的，因为我可以用 5 个中的任何一个来写它！（五个阶乘）元音字符的排列？ie/[aeiou]/的行为与/[eiaou]/. 它是可交换的有什么好处？（参见 PEG 的不可交换性）

结果是，如果将 CFG 直接音译为 PEG，则通过从可能的解析中确定性地选择一棵解析树来解决前者中的任何歧义。通过仔细选择指定语法替代方案的顺序，程序员可以很好地控制选择哪个分析树。

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

4

3 回答 3

59

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 解析器会产生 Shift/Reduce 冲突，因为当到达“else”关键字时，它无法决定是否应该转移（读取另一个标记）或减少（完成节点）。当然，有一些方法可以解决这个问题。

PEG 解析器总是会选择第一选择。

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

于 2011-03-31T14:57:46.910 回答
4

我认为您将 CFG 与 LR 和歧义混淆了。语法不是确定性/非确定性的，尽管它们的解析器可能是。如果一个模棱两可的文法符合定义，它仍然是 CFG，并且可以为它构建一个确定性解析器来做 PEG 所做的事情。

于 2012-11-17T14:48:24.527 回答
0

PEG 和 CFG 是指定语言的两种不同方式。如果您手动编写一个解析器，那么您很有可能会编写一个所谓的递归下降解析器。递归下降解析器会自动解决语法中的任何歧义，但会默默地解决，并且可能不会以您想要的方式进行。这样做的问题是你永远不会发现有自动解决的歧义，除非你彻底测试你的解析器。PEG 基本上是递归下降解析器的形式化，因此会出现这个问题。有关此问题的示例，请参阅回溯如何影响解析器识别的语言？和https://cs.stackexchange.com/questions/143480/dragon-book-4-4-5-exercise/143975。

CFG 有很多理论来支持它们，但 PEG 没有那么多。可以通过 CFG 编码的语言集和可以通过 PEG 编码的语言集部分重叠，但两者都不包含另一个。

要对此进行更全面的审查，我推荐优秀的文章Which Parsing Approach？

于 2022-01-18T09:04:19.260 回答