PEG和CFG之间有什么区别？

Question

从这个维基百科页面:

无上下文语法和解析表达式语法之间的根本区别在于PEG的选择运算符是有序的.如果第一个替代方案成功,则忽略第二个替代方案.因此,有序选择不是可交换的,不像无上下文选择,如无上下文语法和正则表达式.有序选择类似于某些逻辑编程语言中可用的软切算子.

为什么PEG的选择算子会使匹配短路？是因为最小化内存使用量(由于记忆)？

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

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

这说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-conflict,因为在到达"else"关键字时,它无法决定是应该移位(读取另一个令牌)还是减少(完成节点).当然,有办法解决这个问题.

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

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