在计算机科学领域,解析表达文法,简称PEG(英语:Parsing Expression Grammar),是一种分析型形式文法。PEG在2004年由布莱恩·福特(Bryan Ford)推出,它与20世纪70年代初引入的自顶向下的语法分析语言(英语:Top-down parsing language)家族密切相关。
在语法上,PEG很接近上下文无关文法(CFG),但是他们采用了不同的解释:例如PEG中的选择操作符总是会选中第一个匹配项,而在CFG中则是不明确的。这更接近于字符串识别在实际中的应用,例如使用递归下降解析器的情况。另外不像CFG,PEG不能有二义性(英语:Ambiguous grammar):在解析一个字符串的时候,只能有单一确定的语法分析树。据推测,存在上下文无关语言,不能用PEG处理,但尚未得到证实。 这个特性使得PEG更适合计算机语言的解析,对于一般的CFG算法(如依尔利算法(英语:Earley parser))的性能可以与之比拟的自然语言就不是很合适。
形式上,一个解析表达文法由以下部分组成:
中的每一个解析规则以 ← 的形式出现,这里 是一个非终结符, 是一个解析表达式。解析表达式是类似正则表达式的层次表达式:
CFG和PEG的关键不同是PEG的选择操作符是有序的。如果第一个选项成功匹配,则忽略第二个选项。因此PEG的有序选择是不可交换的,这点和上下文无关文法或者正则表达式在教科书上的定义不同。有序选择类似于某些逻辑编程语言中的软截断操作符。
这导致的区别就是如果一个上下文无关文法被直接转换为解析表达文法,所有的不确定性的地方都会被确定下来,方法是从所有可能的解析树中选择一个分支。通过仔细安排文法可能项的顺序,编程的人就可以自由控制哪一个解析分支被选中。
与布尔上下文无关语法一样,解析表达式语法也添加了肯定断言以及否定断言。因为它们可以使用任意复杂的子表达式“向前查看”输入字符串,而不需要实际消耗它,所以它们提供了一个强大的语法向前查找和消歧功能,特别是在重新排序替代方案不能指定所需的准确的解析树时。
解析表达文法里面的每一个非终结符本质上表示递归下降解析器里面的一个解析函数,其对应的解析表达式展示了这个函数包含的代码内容。概念上,每一个解析函数接受一个输入字符串作为参数,返回以下其中一个结果:
一个非终结符有可能成功但是不消耗任何输入字符,这也是一种不同于失败的结果。
只由一个终结符组成的原子解析表达式:成功,如果输入字符串的第一个字符就是定义中的终结符,这种情况下消耗这个输入字符;否之失败。由空字符串组成的原子解析表达式总是成功并且不消耗任何输入。只由一个非终结符A组成的原子解析表达式表示对非终结符A的解析函数的递归调用。
序列操作符 12 首先调用 1, 如果 1成功, 接着对 1 消耗剩下的输入字符串调用 2, 最后返回结果。如果 1 或者 2 失败,那么序列表达式 12 失败。
选择操作符 1 / 2 首先调用 1, 如果 1成功, 立刻返回结果。否则如果 1 失败,选择操作符回溯到输入字符串匹配 1 的原始位置,调用 2, 最后返回 2 结果。
零个或多个,一个或多个,和可选操作符分别消耗零个或多个,一个或多个,或者零个或一个连续重复的子表达式e。与上下文无关文法和正则表达式不同的 是,尽管如此,在PEG里这些操作符总是执行贪婪的行为,那就是消耗尽可能多的输入,而且绝对不回溯。(正则表达式一开始执行贪婪匹配,但是如果整个正则表达式失败后,会回退并尝试短一些的匹配。)例如,解析表达式a*总是尽可能多的消耗输入字符串中连续出现的a,解析表达式(a* a)则必然会失败因为前半部分a*绝对不会留下一丁点a给后半部分去匹配。
最后,肯定断言和否定断言实现了句法断言。&e 表达式调用子表达式e,如果e成功,则返回成功;否则返回失败。无论结果如何都不消耗任何字符。反之,当e失败时!e 表达式成功,e成功时!e 表达式失败, 同样无论结果如何都不消耗任何字符。因为向前判断的子表达式e 可以任意的复杂,所以断言表达式提供了强大的句法向前判断和去除二义性的能力。
这是一个简单的解析表达文法,它识别基本的数学表达式,只使用了基本的四个运算符并且只接受正整数作为操作数.
Expr ← SumSum ← Product (('+' / '-') Product)*Product ← Power (('*' / '/') Power)*Power ← Value ('^' Power)?Value ← + / '(' Expr ')'