解析表达式文法 PEG

CFG公理库上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。的备选规则表示“存在任意一条生成途径”；PEG的斜杠则是一条决定次序的指令。第一项一旦成功，选择已经完成，即使外层随后失败，也不会回头要求这次选择换用更长的第二项。

这给文法作者明确的消歧方式，也把顺序变成语言定义的一部分。短备选放在前面可能遮住长备选；这不是解析器偶然选错，而是它忠实执行了有序选择。

括号的位置改变回退边界 ​

比较以下两个开始表达式，并都要求输入结束：

在 abc 上，$P$ 的第一项 "a" 成功到位置1，所以选择不再尝试 "ab"。随后 "c" 遇见位置1的 b 而失败，整个 $P$ 拒绝。$Q$ 则先匹配 ab 到位置2，再匹配 c，整串成功。

再看

$R$ 的左备选是完整的 "a" "c"；它在 b 处失败，外层选择因此回到位置0并尝试右备选，最终接受。于是

这里不是只改变了实现效率，而是真正改变了哪些输入被接受。生成式文法中熟悉的代数改写，搬到PEG前必须核对回退边界。

关键字边界与不消费前看 ​

想识别关键字 if，却不把标识符 iffy 的前缀误认成关键字，可定义

在 if( 上，前两字符成功，当前位置是 (，Letter失败，否定前看成功但不吃掉括号。在 iffy 上，前两字符之后还是字母 f，否定前看失败，Keyword整体失败；外围的标识符备选可以从原起点重新识别全部 iffy。

$!e$ 是关于解析成功与否的判断，不是自动生成补语言的字符类。它永不消费；要在“不以某模式开头”的条件下消费一个字符，需另外接点或其他消费表达式。

贪婪重复不会为了后缀退让 ​

表达式 "a"* "a" 在非空全a串上失败：星号先消费所有a，末尾那个a再无输入可读。若希望至少一个a，应写 "a" "a"*。这与某些带回溯的正则表达式引擎会减少重复次数的行为不同。

(ε)* 的重复体每次成功却不前进；A←A "a"/"a" 又在消费之前再次调用A。两者都超出本页良构条件。支持左递归的PEG实现需要额外的种子增长等算法及其复杂度分析，不能仅加一个缓存就宣称问题消失。

对会终止的PEG识别，输入和表达式决定唯一结果。这并不说明它识别的是某个CFG的“唯一正确树”，而是文法已经通过优先选择规定了一个结果。若原任务需要保留自然语言的多种解析，Earley公理库Earley 解析算法Earley parsing · Earley algorithm用带起点的部分产生式及预测、扫描、完成三种规则进行通用CFG识别。或GLR公理库广义 LR 与图结构栈Generalized LR parsing · GLR parsing以图结构栈共享冲突分支，并以打包森林保存多种语法树的LR泛化方法。的森林更符合目标。

直接递归执行仍可能指数重复。Packrat公理库Packrat 记忆化解析Packrat parsing缓存固定PEG每个规则在每个输入位置的结果，避免回溯时重复求值。利用结果唯一性，把每个规则在每个位置的结果缓存起来；良构、无外部可变状态及每表项工作有界等条件满足时，得到固定文法下的线性时间。

单元支线任务及解答 ​

判断 $P,Q,R$ 在 ac、abc、abbc 上是否整串接受，并解释有序选择。解答为：ac 三者都接受；abc 只有 $Q,R$ 接受；abbc 三者都拒绝。最后一个串中，即便匹配了 ab，下一字符仍是 b，后面的 c 无法匹配。

验收要记录每次选择的起点及成功后的位置，特别是 $P$ 在 abc 上不能改用第二分支，而 $R$ 可以。这一差异就是有序选择作用范围的具体证据。