正则表达式 – PEG和CFG之间有什么区别？

发布时间：2020-12-14 06:36:09 所属栏目：百科来源：网络整理

导读：从这 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 ch

从这 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的选择操作符短路匹配？是因为最小化内存使用(由于memoization)？

我不知道正则表达式中的选择运算符是什么，但是我们假设是这样的：/ [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吗？

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,y1),y2)

CFG解析器会产生移位/减少冲突，因为当达到“else”关键字时，它不能决定是否应该移位(读取另一个令牌)或减少(完成节点)。当然，有办法解决这个问题。

PEG解析器将始终选择第一选择。

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!