消除左递归与提取左因子

从一段源程序开始

这一讲不先罗列术语。我们把一个只有变量、表达式和控制流的小程序送入上下文无关文法与LL解析，观察它在本节前后的制品变化。为消除左递归与提取左因子准备最小正常程序、边界程序、非法程序和回归程序，输出逐阶段Token、树、类型或IR证据。你要能指出输入是什么、输出是什么、错误应定位到哪一个源区间，以及下一阶段能相信哪些不变量。最终机器码能运行并不能倒推每个阶段都正确，因为两个错误可能偶然抵消。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

规则、对象与形式化边界

本节核心规则是：消除左递归与提取左因子必须把输入制品、变换规则、输出不变量和诊断位置同时写清；每一步都能由下一阶段独立验证。把规则写成“前提在横线上、结论在横线下”的判断形式，或写成状态机、工作表迭代和图变换。对象可能是Token、产生式、AST节点、符号、类型、基本块、数据流事实或虚拟寄存器；不要在同一张图里悄悄更换对象层级。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

跟我手推一个完整例子

先选最小输入，再逐字符、逐产生式或逐基本块推进。每一步记录当前位置、栈/集合/映射、采用的规则和新制品。对消除左递归与提取左因子至少写出3个中间状态；若出现冲突，不凭经验选择，而是展示导致冲突的两条候选推导或数据流路径，再说明语言定义采用的消歧规则。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

第一步围绕消除左递归与提取左因子写下输入制品和初态；第二步严格按消除左递归与提取左因子必须把输入制品、变换规则、输出不变量和诊断位置同时写清；每一步都能由下一阶段独立验证只执行一次允许变换并保存新状态；第三步用实验为消除左递归与提取左因子准备最小正常程序、边界程序、非法程序和回归程序，输出逐阶段Token、树、类型或IR证据产生可比较的阶段输出；最后针对边界不能以最终程序偶然运行替代阶段正确性；消除左递归与提取左因子遇到二义、未定义行为或目标机限制时必须显式诊断更换输入，从头重放并定位首个分歧。这个课时专属顺序让推导可以暂停、复查和复现，也防止用最终答案倒填中间过程。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

可运行实现

参考实现优先清晰：纯函数接收显式输入并返回显式制品，节点带源位置，诊断与正常结果分离。先让四组内联测试通过：正常、最小边界、非法输入、组合回归；再谈缓存、表压缩或增量更新。代码从标准输入读取并写到标准输出，不依赖第三方包、随机遍历顺序或本机文件。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

复杂度与工程预算

给输入规模写单位。若线性扫描处理每个元素2步、维护制品每个元素1步，长度为30的输入在简化模型中需要30×3=90步。这个预算只有在每个元素常数工作且没有回溯时成立；文法冲突、图迭代次数、哈希退化与目标机约束都可能改变上界。公式用来暴露假设，不是装饰。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

除了时间，还要核对空间和制品规模。针对消除左递归与提取左因子分别记录输入节点数、输出节点数、临时集合峰值和诊断条数；若一个局部变换让输出指数增长，就用共享节点、延迟展开或明确上限控制。优化前后使用同一输入与同一计量口径，不能把解析时间和执行时间混在一起，也不能用小样本偶然更快宣称复杂度已经改善。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

工程实现再加三道护栏：所有集合遍历顺序在测试中稳定；所有源位置经过变换仍能追溯；所有失败返回保留阶段名和最小上下文。这样同伴看到错误时能从目标代码逆查IR、类型、AST和Token，而不是在整个流水线里猜。消除左递归与提取左因子必须把输入制品、变换规则、输出不变量和诊断位置同时写清；每一步都能由下一阶段独立验证，因此验证器不是调试后才补的附件，而是阶段接口的一部分。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

错误、反例与恢复

最危险边界是：不能以最终程序偶然运行替代阶段正确性；消除左递归与提取左因子遇到二义、未定义行为或目标机限制时必须显式诊断。请构造一个最短反例，说明错误实现会生成什么错误制品，验证器应在哪一步拒绝。前端恢复要继续报告而不制造级联假错；优化阶段必须保持可观察语义；后端必须遵守调用约定。对不确定语义，宁可停止优化也不能静默改变程序。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

与流水线前后的联系

向前追问本节输入由谁保证，向后追问输出被谁消费。词法位置影响语法诊断，AST形状影响名字与类型，类型信息影响IR操作，控制流影响数据流与优化，活跃性影响寄存器，调用约定连接运行时。为消除左递归与提取左因子画两条接口箭头，并在箭头上写字段、条件和失败返回。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

再做一次差分验证：同一源程序分别交给未优化解释路径和当前编译路径，比较返回值、输出、错误和可观察副作用。若语言允许未定义行为，先把该输入排除或声明比较范围；不能因为参考系统也给出某个结果，就把未定义结果当作语言保证。对于消除左递归与提取左因子，差分失败时先比较本节输入制品，再比较输出制品，定位首个发生分歧的节点。
（本段编译制品：消除左递归与提取左因子；位置：3-2。）

练习、实验与自检

完成本节单选、多选和计算题；实验课再完成真实代码题的全部测试。闭卷回答：对象是什么，核心规则如何逐步执行，输出不变量是什么，最短反例是什么，下一阶段怎样验证。能从新输入重新推导、运行和诊断，才算学会；只会复述算法名字不合格。