解析表达文法

在计算机科学中解析表达文法，简称PEG，是一种解析形式文法。这种文法用一个识别字符串的规则的集合来描述某种形式语言。解析表达文法2004年由布莱恩·福特引入， 以纯公式的形式的展现递归下降解析器的基础语法，对这个具体的解析器可能会采用的实现方法不做任何限定。解析表达文法看起来与正则表达式和巴科斯范式的上下文无关文法（CFG）很像，但是表达的意思不同。
和CFG不同的是，PEG不能有二义性；解析一个字符串的时候，这个字符串只产生一个确定的语法分析树。据推测，存在上下文无关语言，不能用PEG处理，但尚未得到证实。 这个特性使得PEG更适合计算机语言的解析，对于一般的CFG算法（如依尔利算法）的性能可以与之比拟的自然语言就不是很合适。

语义

CFG和PEG的关键不同是PEG的选择操作符是有序的。如果第一个可能成功了，那么第二个可能就忽略。因此PEG的有序选择是不可以互换的，这点和上下文无关文法或者正则表达式在教科书上的定义不同。有序选择类似于某些逻辑编程语言中的软截断操作符。
与上下文无关文法或者其他生成文法不同，在解析表达文法里面，对应某个非终结符，必须且只能有一个的解析规则。这意味着，在PEG里面，解析规则就是定义，每一个非终结符必须有且只能由一个定义。
这导致的区别就是如果一个上下文无关文法被直接转换为解析表达文法，所有的不确定性的地方都会被确定下来，方法是从所有可能的解析树中选择一个分支。通过仔细安排文法可能项的顺序，编程的人就可以自由控制那一个解析分支被选中。

示例

这是一个简单的解析表达文法，它识别基本的数学表达式，只使用了基本的四个运算符并且只接受正整数作为操作数.

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Value (('*' / '/') Value)*
Value   ← [0-9]+ / '(' Expr ')'
在上面这个例子里面，终结符就是字符文本，用单引号括起来表示。比如'('和')'。[0-9]这个区间是10个字符的缩写，表示数字0到数字9里面的任意一个。（这里区间的语义和正则表达式里面的一样。）非终结符就是被定义成其他表达式的符号：Value, Product, Sum, 以及 Expr。
下面的例子去掉引用标记以便阅读。小写字母表示终结符，大写字母是非终结符。真实的PEG语法要求所有的小写字母都在引号里面。
解析表达式('a'/'b')*匹配任意长度的a和b序列。解析规则S ← 'a' S? 'b' 描述了. 这样一个简单的上下文无关匹配语言。而下面的这个解析表达文法则可以描述经典的非上下文无关文法：

S ← &(A 'c') 'a'+ B !('a'/'b'/'c')
A ← 'a' A? 'b'
B ← 'b' B? 'c'
接下来的递归规则匹配了标准C风格的if/then/else语句。因为/操作符的隐式优先级安排，可选的else语句总是会被绑定到最内层的if语句。（在上下文无关文法里，这种结构的文法会导致悬空的else语句这种二义性错误。

S ← 'if' C 'then' S 'else' S / 'if' C 'then' S
解析表达式foo &(bar) 只有当foo 后面紧跟着字符串bar 的时候，才会匹配并消耗foo。而解析表达式foo !(bar) 只有当foo 后面没有紧跟着字符串bar 的时候，才会匹配。表达式!(a+ b) a 只有当a 不是一连串a后面连着一个b的情况下出现的时候，才能匹配一个单独的字母a。
下面的这个递归规则匹配Pascal格式的注释语法，(*和*)括号，其内部可以有嵌套的(*和*)对。注释符号放在双引号内内是为了与其他PEG操作符区分开来。

Begin ← '(*'
End   ← '*)'
C     ← Begin N* End
N     ← C / (!Begin !End Z)
Z     ← any single character

根据解析表达文法实现解析器

所有的解析表达文法都能够被直接转化为递归下降解析器。 尽管如此，因为PEG公式提供了理论上不受限制的向前检查的能力，所以最终得到的解析器还是可以避免最坏情况下指数级时间复杂度的。
通过保存增量解析步骤的结果和确保每一个解析函数在同一个输入位置只被调用一次，就可以把任意解析表达文法转化成一个Packrat Parser，可以实现线性的时间复杂度解析，其代价是足够大量的空间占用。
一个Packrat Parser是一种结构上类似于递归下降解析器的语法解析器，区别是在解析过程中，它会记下所有互相递归调用的函数的中间结果。因为保存了这些信息，一个 Packrat Parser就拥有了以线性时间复杂度解析多数上下文无关文法和所有解析表达文法的能力（包括某些表示的不是上下文无关文法语言的文法）。
从解析表达文法建立LL剖析器和LR剖析器也是可行的，但是在这两种情况下，不受限制的向前检查的能力就不能用了。

优势

因为PEG更加严格更加强大，PEG可以成为很好的正则表达式的替代品。例如，一个正则表达式本身是无法匹配嵌套的括号对，因为正则表达式不是递归的，但是PEG却能做到这点。
所有的PEG都能通过使用Parkrat Parser达到线性时间解析，如同上文所述。
CFG表达的解析器，比如LR解析器，需要首先进行一个单独的断词步骤。这个步骤根据空白的位置或者发音等等因素把输入分成词。分词是必要的，因为 这类解析器使用向前检查来判断上下文无关文法是否匹配要求。PEG不需要单独的断词步骤，断词的规则和其他文法规则可以用同样的方式写在一起。
许多CFG固有的存在二义性，即使它们原本要描述的东西并不具有二义性。C, C++, Java里面著名的悬空else问题就是一个例子。这个问题通常都是应用文法之外的一个规则解决。而在PEG里面，因为使用了优先权，所以根本不存在这种问题。

劣势

PEG是新事物，还没有被广泛的应用。相比之下，正则表达式和CFG已经产生了数十年了，用来解析的代码也已经优化的很好，并且很多开发者都熟悉怎么使用他们。
PEG不能表达左递归的解析规则。例如，上面的数学运算文法，通过引入更多的规则，来使得乘法和加法的优先级能够在一行里面表达出来这可是非常的有诱惑力的， 结果可能得到下面的文法：

Value ← [0-9.]+ / '(' Expr ')'
Product ← Expr (('*' / '/') Expr)*
Sum ← Expr (('+' / '-') Expr)*
Expr ← Product / Sum / Value
这个文法的问题就是，为了匹配Expr， 你需要首先判断是否某处匹配Product， 而为了匹配Product， 你又必须判断是不是此处匹配Expr。而这个循环定义是不可分析的。
尽管如此，我们总是可以通过重写左递归规则把左递归消除掉。 例如，一个左递归可能无限的重复一个规则，就像在CFG里面的：

string-of-a ← string-of-a 'a' | 'a'
在PEG里面，可以用加号操作符重写为：

string-of-a ← 'a'+
PEG还涉及到Packrat Parsing， 一种通过占用更多的存储空间来消除不必要解析步骤的方法。Packrat Parsing需要的存储空间与总的输入文件的大小成正比，而不是LR解析器的与解析树的深度成正比。如果稍作修改，传统的Packrat Parser也可以支持左递归。