PEG和CFG之间有什么区别？

从这个wikipedia页：PEG和CFG之间有什么区别？

上下文无关文法和解析表达语法的根本区别是，PEG的选择运营商是有序的。如果第一个替代方案成功，则第二个替代方案将被忽略。因此，订购的选择是不可交换的，不像无序的选择，因为在上下文无关语法和正则表达式。有序选择类似于软件削减运算符在一些逻辑可用编程语言。

为什么PEG的选择运算符将匹配短路？是否因为最大限度地减少内存使用（由于记忆）？

我不确定在正则表达式中选择运算符是什么，但我们假设它是这样的：/[aeiou]/以匹配元音。所以这个正则表达式是可交换的，因为我可以把它写在5中的任何一个！（五个阶乘）元音字符的排列？即/[aeiou]/的行为与/[eiaou]/相同。它可交换的优点是什么？（C.F. PEG的不可交换）

的后果是，如果一个CFG是直接音译的PEG，在前任何歧义由确定性挑选一个解析从可能的解析树解决。通过仔细选择指定的文法备选的顺序，程序员对选择哪个解析树有很大的控制权。

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

来源

2011-03-31 Frankie Ribery

“Superior”？你对“上级”的标准是什么？ – Gabe 2011-03-31 14:02:03

对于交换性，想想'（飞机）'试图匹配飞机。 – xanatos 2011-03-31 14:47:35

看起来你很迷惑选择运算符和角色类的概念。在正则表达式中，字符类用方括号'[aeiou]'分隔，而选择操作符是管道字符'|'。在PEG中，选择运算符是斜杠字符'/'。 – hippietrail 2014-08-11 10:56: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解析器将产生移位/减少冲突，因为它不能决定我当它到达“else”关键字时，它应该转移（读取另一个令牌）或减少（完成节点）。当然，有办法解决这个问题。

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

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

来源

2011-03-31 14:57:46

你能提供一个这样的CFG语法的示例（2个解析树）吗？ – 2011-04-04 05:47:00

感谢您悬赏的例子。现在很清楚。 – 2011-04-12 02:50:27

我认为你让CFG和LR混淆并且含糊不清。语法不是确定性/非确定性的，尽管他们的解析器可能是。一个模糊的语法如果符合定义，它仍然是CFG，并且可以为PEG做一个确定性的语法分析器。

来源

2012-11-17 14:48:24 Apalala

不，CFG有时候是不明确的，因为它们的“选择”操作符没有优先级，所以如果给定的字符串与“选择”中的两个选项相匹配，那么你就有一个模糊性。 PEG中的“选择”具有优先匹配优先权，所以不存在歧义，因为最左边的选项*必然*胜出。 – aaronblohowiak 2013-01-15 01:46:54

不可以。否CFG可能不明确，因为所有选项同等有效。当相同的短语可以由不同的制作序列生成时，CFG是不明确的。在LL和LR中，歧义意味着解析器/识别器无法知道哪个产品序列（哪个语法树）对应于给定的短语。 PEG通过按照宣布顺序排列产品来解决歧义问题。它告诉解析器，正确的语法树是第一个语法树。 – Apalala 2013-01-15 10:53:14

PEG和CFG之间有什么区别？

回答

相关问题