[科普中国]-解析表达文法

解析表达文法，简称PEG，是一种形式文法。这种文法用一个识别字符串的规则的集合来描述某种形式语言。

简介解析表达文法以纯公式的形式的展现递归下降解析器的基础语法，对这个具体的解析器可能会采用的实现方法不做任何限定。解析表达文法看起来与正则表达式和巴科斯范式的上下文无关文法(CFG)很像，但是表达的意思不同。和CFG不同的是，PEG不能有二义性；解析一个字符串的时候，这个字符串只产生一个确定的解析树。这个特性使得PEG更适合计算机语言的解析，对于自然语言就不是很合适。

解析表达文法2004年由布莱恩·福特引入，以纯公式的形式的展现递归下降解析器的基础语法，对这个具体的解析器可能会采用的实现方法不做任何限定。解析表达文法看起来与正则表达式和巴科斯范式的上下文无关文法（CFG）很像，但是表达的意思不同。

和CFG不同的是，PEG不能有二义性；解析一个字符串的时候，这个字符串只产生一个确定的语法分析树。据推测，存在上下文无关语言，不能用PEG处理，但尚未得到证实。这个特性使得PEG更适合计算机语言的解析，对于一般的CFG算法（如依尔利算法）的性能可以与之比拟的自然语言就不是很合适。1

定义语法形式上，一个解析表达文法由以下部分组成：

一个有限的非终结符的集合N

一个有限的终结符的集合 Σ，和N没有交集

一个有限的解析规则的集合P

一个被称作起点表达式的解析表达式eS

P中的每一个解析规则以A←e的形式出现，这里A是一个非终结符，e是一个解析表达式。解析表达式是类似正则表达式的层次表达式：

原子解析表达式由以下组成:

任何的终结符，

任何的非终结符，

空字符串 ε.

给定已经存在的解析表达式e,e1和e2, 一个新的解析表达式可以通过以下操作构成:

序列:e1e2

有序选择:e1/e2

零个或更多:e*

一个或更多:e+

可选:e?

肯定断言: &e

否定断言:!e

语义CFG和PEG的关键不同是PEG的选择操作符是有序的。如果第一个可能成功了，那么第二个可能就忽略。因此PEG的有序选择是不可以互换的，这点和上下文无关文法或者正则表达式在教科书上的定义不同。有序选择类似于某些逻辑编程语言中的软截断操作符。

与上下文无关文法或者其他生成文法不同，在解析表达文法里面，对应某个非终结符，必须且只能有一个的解析规则。这意味着，在PEG里面，解析规则就是定义，每一个非终结符必须有且只能由一个定义。

这导致的区别就是如果一个上下文无关文法被直接转换为解析表达文法，所有的不确定性的地方都会被确定下来，方法是从所有可能的解析树中选择一个分支。通过仔细安排文法可能项的顺序，编程的人就可以自由控制那一个解析分支被选中。1

解析表达式的解释解析表达文法里面的每一个非终结符本质上表示递归下降解析器里面的一个解析函数，其对应的解析表达式展示了这个函数包含的代码内容。概念上，每一个解析函数接受一个输入字符串作为参数，返回以下其中一个结果:

成功，函数可能向前移动或者“消耗”一个或多个输入字符串的字符

失败，不消耗任何字符

一个非终结符有可能成功但是不消耗任何输入字符，这也是一种不同于失败的结果。

只由一个终结符组成的原子解析表达式：成功，如果输入字符串的第一个字符就是定义中的终结符，这种情况下消耗这个输入字符；否之失败。由空字符串组成的原子解析表达式总是成功并且不消耗任何输入。只由一个非终结符A组成的原子解析表达式表示对非终结符A的解析函数的递归调用。

序列操作符e1e2首先调用e1， 如果e1成功， 接着对e1消耗剩下的输入字符串调用e2， 最后返回结果。如果e1或者e2失败，那么序列表达式e1e2失败。

选择操作符e1/e2首先调用e1， 如果e1成功， 立刻返回结果。否则如果e1失败，选择操作符回溯到输入字符串匹配e1的原始位置，调用e2， 最后返回e2结果。

零个或多个，一个或多个，和可选操作符分别消耗零个或多个，一个或多个，或者零个或一个连续重复的子表达式e。与上下文无关文法和正则表达式不同的 是，尽管如此，在PEG里这些操作符总是执行贪婪的行为，那就是消耗尽可能多的输入，而且绝对不回溯。（正则表达式一开始执行贪婪匹配，但是如果整个正则表达式失败后，会回退并尝试短一些的匹配。）例如，解析表达式a*总是尽可能多的消耗输入字符串中连续出现的a，解析表达式(a* a)则必然会失败因为前半部分a*绝对不会留下一丁点a给后半部分去匹配。

最后，肯定断言和否定断言实现了句法断言。&e 表达式调用子表达式e，如果e成功，则返回成功；否则返回失败。无论结果如何都不消耗任何字符。反之，当e失败时！e 表达式成功，e成功时！e 表达式失败， 同样无论结果如何都不消耗任何字符。因为向前判断的子表达式e 可以任意的复杂，所以断言表达式提供了强大的句法向前判断和去除二义性的能力。1

根据解析表达文法实现解析器所有的解析表达文法都能够被直接转化为递归下降解析器。尽管如此，因为PEG公式提供了理论上不受限制的向前检查的能力，所以最终得到的解析器还是可以避免最坏情况下指数级时间复杂度的。

通过保存增量解析步骤的结果和确保每一个解析函数在同一个输入位置只被调用一次，就可以把任意解析表达文法转化成一个Packrat Parser，可以实现线性的时间复杂度解析，其代价是足够大量的空间占用。

一个Packrat Parser是一种结构上类似于递归下降解析器的语法解析器，区别是在解析过程中，它会记下所有互相递归调用的函数的中间结果。因为保存了这些信息，一个 Packrat Parser就拥有了以线性时间复杂度解析多数上下文无关文法和所有解析表达文法的能力（包括某些表示的不是上下文无关文法语言的文法）。

从解析表达文法建立LL剖析器和LR剖析器也是可行的，但是在这两种情况下，不受限制的向前检查的能力就不能用了。2

优势因为PEG更加严格更加强大，PEG可以成为很好的正则表达式的替代品。例如，一个正则表达式本身是无法匹配嵌套的括号对，因为正则表达式不是递归的，但是PEG却能做到这点。

所有的PEG都能通过使用Parkrat Parser达到线性时间解析，如同上文所述。

CFG表达的解析器，比如LR解析器，需要首先进行一个单独的断词步骤。这个步骤根据空白的位置或者发音等等因素把输入分成词。分词是必要的，因为 这类解析器使用向前检查来判断上下文无关文法是否匹配要求。PEG不需要单独的断词步骤，断词的规则和其他文法规则可以用同样的方式写在一起。

许多CFG固有的存在二义性，即使它们原本要描述的东西并不具有二义性。C, C++, Java里面著名的悬空else问题就是一个例子。这个问题通常都是应用文法之外的一个规则解决。而在PEG里面，因为使用了优先权，所以根本不存在这种问题。2

劣势PEG是新事物，还没有被广泛的应用。相比之下，正则表达式和CFG已经产生了数十年了，用来解析的代码也已经优化的很好，并且很多开发者都熟悉怎么使用他们。

PEG不能表达左递归的解析规则。例如，上面的数学运算文法，通过引入更多的规则，来使得乘法和加法的优先级能够在一行里面表达出来这可是非常的有诱惑力的， 结果可能得到下面的文法：

Value ← [0-9.]+ / '(' Expr ')'Product ← Expr (('*' / '/') Expr)*Sum ← Expr (('+' / '-') Expr)*Expr ← Product / Sum / Value这个文法的问题就是，为了匹配Expr， 你需要首先判断是否某处匹配Product， 而为了匹配Product， 你又必须判断是不是此处匹配Expr。而这个循环定义是不可分析的。2

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所