解析表达式语法

在计算机科学中，解析表达式语法（PEG）是一种分析形式语法，即它用一套识别语言中的字符串的规则来描述一种形式语言。

这种形式主义是由BryanFord在2004年提出的，与1970年代初提出的自上而下的解析语言家族密切相关。

从语法上看，PEG也与无语境语法（CFG）相似，但它们有不同的解释：选择运算符在PEG中选择xxx个匹配，而在CFG中是模糊的。这更接近于实践中的字符串识别方式，例如由递归下降分析器完成。

与CFG不同的是，PEG不能是模棱两可的；如果一个字符串可以解析，它就有一个有效的解析树。

据猜测，存在着不能被PEG识别的无语境语言，但这一点尚未被证明。

PEG非常适合解析计算机语言（和人工人类语言，如Lojban），但不适合解析自然语言，因为PEG算法的性能与一般的CFG算法（如Earley算法）相当。

从形式上看，一个解析表达式语法由以下部分组成。一个由非终端符号组成的有限集合N；一个由终端符号组成的有限集合Σ，该集合与N不相连；一个由解析规则组成的有限集合P；一个表达式eS，称为起始表达式；P中的每个解析规则都有A←e的形式，其中A是一个非终端符号，e是一个解析表达。

解析表达式是一个类似于正则表达式的分层表达式，它的构造方式如下。

一个原子解析表达式包括：任何终端符号、任何非终端符号或空字符串ε。给定任何现有的解析表达式e、e1和e2，可以使用以下运算符构建一个新的解析表达式：序列：e1e2有序选择：e1/e2零或多：e*一或多：e+可选：e？和-谓语：&e不-谓语：！e语义上下文自由语法和解析表达式语法的根本区别在于，PEG的选择运算符是有序的。如果xxx个选择成功了，第二个选择就会被忽略。

因此，有序选择不是换元的，与无语境语法中的无序选择不同。有序选择类似于某些逻辑编程语言中的软切割运算符。其结果是，如果CFG被直接翻译成PEG，那么前者的任何歧义都可以通过从可能的解析中确定地挑选一个解析树来解决。

通过仔细选择指定语法选项的顺序，程序员对选择哪种解析树有很大的控制权。像布尔上下文自由语法一样，解析表达式语法也增加了and-和not-的句法谓词。因为它们可以使用任意复杂的子表达式来提前查看输入字符串，而不实际消耗它，所以它们提供了强大的句法提前查看和消歧义设施，特别是当重新排序的替代物不能指定所需的确切解析树时。

解析表达式的操作解释解析表达式语法中的每个非终端基本上都代表递归解析器中的一个解析函数，而相应的解析表达式则代表构成该函数的代码。

每个解析函数在概念上以一个输入字符串为参数，并产生以下结果之一。成功，在这种情况下，函数可以选择向前移动或消耗提供给它的输入字符串中的一个或多个字符，或者失败，在这种情况下不消耗任何输入。

如果输入字符串的xxx个字符与一个终端（即字面意思）相匹配，则由一个原子解析表达式成功，在这种情况下消耗输入字符；否则表达式产生一个失败结果。

由空字符串组成的原子解析表达式总是在不消耗任何输入的情况下成功。由非终端A组成的原子解析表达式表示对非终端函数A的递归调用。非终端可以在不消耗任何输入的情况下成功，这被认为是不同于失败的结果。

序列运算符e1e2首先调用e1，如果e1成功，随后对e1未消耗的输入字符串的剩余部分调用e2，并返回结果。如果e1或e2失败，那么序列表达式e1e2失败（不消耗输入）。

选择运算符e1/e2首先调用e1，如果e1成功，立即返回其结果。否则，如果e1失败了，那么选择运算符回溯到它调用e1的原始输入位置，但随后调用e2，返回e2的结果。零或多、一或多和可选运算符分别消耗其子表达式e的零或多、一或多、零或一的连续重复。