PEG和CFG有什么区别? [英] What are the differences between PEGs and CFGs?

问题描述

从此维基百科页面:

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

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的选择运算符会使匹配短路?是因为要尽量减少内存使用(由于记忆)?

Why does PEG's choice operator short circuits the matching? Is it because to minimize memory usage (due to memoization)?

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

I'm not sure what the choice operator is in regular expressions but let's suppose it is this: /[aeiou]/ to match a vowel. So this regex is commutative because I could have written it in any of the 5! (five factorial) permutations of the vowel characters? i.e. /[aeiou]/ behaves the same as /[eiaou]/. What is the advantage of it being commutative? (c.f. PEG's non-commutativity)

结果是，如果CFG为 直接音译为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的语法?

Is this saying that PEG's grammar is superior to CFG's?

推荐答案

CFG语法是不确定的，这意味着某些输入可能会导致两个或更多个可能的解析树.尽管大多数基于CFG的解析器生成器都对语法的可确定性有所限制.如果有两个或多个选择，它将给出警告或错误.

A CFG grammar is non-deterministic, meaning that some input could result in two or more possible parse-trees. Though most CFG-based parser-generators have restrictions on the determinability of the grammar. It will give a warning or error if it has two or more choices.

PEG语法是确定性的，这意味着任何输入只能以一种方式进行解析.

A PEG grammar is deterministic, meaning that any input can only be parsed one way.

举一个经典的例子；语法

To take a classic example; The grammar

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"关键字时，它无法决定是否应该移位(读取另一个令牌)或减少(完成节点).当然，有一些方法可以解决此问题.

A CFG-parser would generate a Shift/Reduce-conflict, since it can't decide if it should shift (read another token), or reduce (complete the node), when reaching the "else" keyword. Of course, there are ways to get around this problem.

PEG分析器将始终选择第一选择.

A PEG-parser would always pick the first choice.

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

Which one is better is for you to decide. My opinion is that often PEG-grammars is easier to write, and CFG grammars easier to analyze.

这篇关于PEG和CFG有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！