Packrat 记忆化解析

回溯并不一定浪费；浪费来自“回到同一位置，又把同一规则从头做一遍”。PEG恰好给每个这样的请求一个唯一答案，所以第一次算完后就可以重复使用。

表中保存终点位置尤其重要。规则可以一次匹配很长的片段，调用者直接跳到它的终点继续；不必为了解这段长度而重新扫描。表空间为线性，换来远距离前看与回退仍不重复内部解析。

一个确实指数重复的坏输入 ​

用字符文法

递归调用前已经消费a，所以没有左递归。对输入 $a^{n}d$，任一位置的两个非空备选都最终找不到所需的b或c，于是 $A(i)$ 以空备选成功并返回同一位置 $i$。$S$ 最后检查输入结束时失败，正确拒绝。

但朴素执行会为两个备选各调用一次 $A(i+1)$，重复整个后缀工作。令 $T(n)$ 为A的调用次数，则

缓存后只有 $n+1$ 个不同的A表项需要计算。第一次备选算过 $A(i+1)$，第二次直接复用；仍有 $2n+1$ 次请求，但其中 $n$ 次是命中缓存，不是重新执行。

上述递推给出表中数字，缓存结果均为 $M[A,i]=\mathrm{success}(i)$。表项成功而整串失败并不矛盾：A允许空串，开始规则S另外要求消耗全部输入。

失败结果也值得保存 ​

若把最后的空备选去掉，改成 $A\leftarrow \mathtt{\text{"a"}}A\mathtt{\text{"b"}}/\mathtt{\text{"a"}}A\mathtt{\text{"c"}}/\mathtt{\text{"z"}}$，同样的 $a^{n}d$ 会让所有A调用失败。只缓存成功结果时，这个输入仍会重复指数工作；保存failure才真正消除了重复。

缓存键漏掉状态会产生错误答案 ​

假设规则 TypeName 会查询一个可变符号表，判断当前位置的名字是否已被声明为类型。第一次在位置 $i$ 失败，后来某条语义动作往符号表加入同名类型。再次请求 TypeName(i) 时，正确结果已经改变；仍返回旧failure就不可靠。

可以禁止这类外部状态，把相关状态纳入缓存键，或采用专门的状态化解析方案。后一种选择可能让同一位置对应许多状态，原来的 $g(n+1)$ 表项上界随之失效。不能同时更改语义依赖，又保留未经证明的线性界。

对满足条件的规范化PEG，最多有 $g(n+1)$ 个表项。每格首次求值做 $O(1)$ 本地工作并访问常数个表格；重复请求只查表，因此识别总时间 $O(g(n+1))$，存储 $O(g(n+1))$。固定文法时两者均为 $O(n+1)$，也计入空输入位置上的求值。每个表项的正确性与直接PEG求值一致，因为缓存保存的是同一确定子问题的完整结果；良构性确保首次计算不会在同一未完成键上无限递归。

若语义动作构造长度 $k$ 的新字符串，单格成本就可能为 $O(k)$；若许多格各复制长后缀，总成本可能二次。共享AST节点、保存输入切片索引并把后处理另算，才能让识别复杂度与交付物大小相配。

空间是重要代价。LL或LR可以在适当语法下流式前进并丢弃旧输入；Packrat通常保留大量早期位置的结果，因为后续回溯还可能需要它们。只有证明某个前缀不再被访问，才能安全回收对应缓存；“已经读过”本身不够。

单元终局检查 ​

现在可把本单元三种处理选择的方式分开：LL/LR用预先计算的信息唯一决定动作；Earley/GLR保存多种生成式推导；PEG先用有序选择规定唯一识别，再由Packrat消除重复计算。

任务是为一份需要保留全部歧义分析的文法和一份按规则优先级定义的配置语法分别选方案。解答：前者应选带森林的Earley/GLR，不能用“缓存后更快”来掩盖PEG只返回一个结果的语义改变；后者若满足良构和无外部状态条件，可用Packrat，验收要计表项而不只测某个顺利输入的耗时。

再对上面的指数例子说明：缓存为何不改变拒绝结果、为何只需 $n+1$ 次实际A计算、为什么failure也要保存。能够写出键、值和递推式，才说明读者真正掌握了算法，而不仅知道“加一个字典”。