regex - PEG 和 CFG 之间有什么区别？

Question

从这里 wikipedia页:

The fundamental difference between context-free grammars and parsing expression grammars is that the PEG's choice operator is ordered. If the first alternative succeeds, the second alternative is ignored. Thus ordered choice is not commutative, unlike unordered choice as in context-free grammars and regular expressions. Ordered choice is analogous to soft cut operators available in some logic programming languages.

为什么 PEG 的选择运算符会使匹配短路？是因为要尽量减少内存使用(由于内存)吗？

我不确定正则表达式中的选择运算符是什么，但让我们假设它是这样的: /[aeiou]/匹配一个元音。所以这个正则表达式是可交换的，因为我可以用 5 个中的任何一个来编写它! (五阶乘)元音字符的排列？即 /[aeiou]/行为与 /[eiaou]/ 相同.它是可交换的有什么好处？ (c.f. PEG 的非交换性)

The consequence is that if a CFG is transliterated directly to a PEG, any ambiguity in the former is resolved by deterministically picking one parse tree from the possible parses. By carefully choosing the order in which the grammar alternatives are specified, a programmer has a great deal of control over which parse tree is selected.

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

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

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

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