题干与适用场景
请设计一个解析算术表达式和变量声明的小型解析器。输入可能包含多个语法错误，但解析器仍需报告位置、继续解析后续语句，并为 IDE 提供部分 AST。
题目考察词法、语法、错误恢复和数据结构边界。Bison 文档建议在同步点丢弃输入并继续解析；IDE 场景还要求错误节点、稳定范围和不因首个错误终止整份输入。
面试官考察点
候选人应先定义 token 和语法，再说明递归下降或 LR 方案；能否区分语法错误与词法错误；能否选择安全同步点、抑制级联错误、保留部分 AST，并测试嵌套括号、缺失分隔符和未闭字符串。
30 秒回答框架
“我把输入分成 lexer、parser 和诊断层。Parser 维护 token 游标和源范围，遇到错误先记录期望与实际 token，再跳到分号、右括号或文件尾等同步点，插入 ErrorNode 后继续。恢复期间抑制重复诊断，成功消费若干 token 后恢复报告。AST 节点保留缺失范围，调用方可选择严格模式或容错模式。”
分步骤深入解答
第一步：定义 token 和语法
词法器输出种类、文本、起止偏移和行列号；识别标识符、数字、运算符、括号、分号和非法字符。语法明确优先级与结合性，避免把错误恢复逻辑散落到每个表达式函数。
第二步：选择解析器结构
递归下降易读，适合小语法；使用 precedence climbing 处理表达式优先级。若语法复杂，可用生成器和明确的 error strategy。无论实现方式，都要让 parser 能查询 lookahead、回退有限 token，并携带源范围。
第三步：分离词法错误与语法错误
非法字符或未闭字符串属于词法错误，lexer 应产生错误 token 并继续扫描；缺少操作数、右括号或分号属于语法错误，由 parser 按上下文报告。不要把所有问题都包装成“Unexpected token”。
第四步：选择同步点
语句级同步点通常是分号、右大括号或文件尾；表达式内部可同步到逗号、右括号或运算符边界。跳过 token 时必须保证游标前进，否则同一错误会无限循环。
第五步：构造部分 AST
错误位置保留在节点范围内；缺失子节点用 MissingNode，无法恢复的片段用 ErrorNode 包住原 token。下游格式化、语法高亮和补全应能处理这些节点，而不能假设树永远完整。
第六步：抑制级联诊断
一次恢复可能引发多个表面错误。记录最近同步点和成功消费计数，在恢复后至少消费若干 token 再输出下一条诊断；同时限制单个文件的错误数量，避免日志和 UI 被淹没。
第七步：支持增量解析
编辑器输入变化时，只重解析受影响的 token 区间和相邻语法上下文，复用未变子树。节点范围和 token ID 要稳定，缓存失效必须以父节点边界和语法状态为准，不能只按字符位置猜测。
第八步：测试与性能
测试正确输入、单个错误、多个错误、嵌套错误、长字符串和极大表达式。断言错误位置、数量、AST 错误节点和终止条件；对长输入测量线性扫描、递归深度、内存和最坏恢复开销。
设计取舍与边界
严格失败还是继续解析
编译器批处理可在诊断后继续以提升反馈；配置校验可能在首个错误后立即拒绝。用模式开关控制，但共享 lexer、token 和诊断结构，避免两套实现漂移。
同步点多还是少
同步点多能缩短错误影响范围，却可能跳过本可恢复的 token；同步点少能保留更多上下文，却容易产生级联错误。按语句和分隔符设计，并用语料测试。
递归下降还是生成器
递归下降便于解释和定制错误信息；生成器适合大型、稳定语法。错误恢复策略应是显式接口，不能依赖生成器默认行为而缺少测试。
失败演练与演进计划
缺少右括号
输入下一条语句，确认 parser 在分号或文件尾同步，输出一条缺失括号错误并保留后续语句。
非法字符和未闭字符串
确认 lexer 产生错误 token 后继续到行尾或字符串结束，parser 不因单个字符卡住。
连续错误风暴
构造每个 token 都非法的输入，确认游标始终前进、错误数量受限且 CPU 不呈平方增长。
常见误区与追问
误区一：遇到第一个错误就返回 null
追问：IDE 如何继续高亮和补全？应返回带范围的 ErrorNode 或 MissingNode。
误区二：恢复时不推进游标
追问：如何证明不会在同一 token 无限循环？
误区三：所有错误都在 parser 报告
追问：未闭字符串和非法字符的诊断责任属于 lexer 还是 parser？
误区四：忽略级联错误抑制
追问：一个缺分号为什么不能打印十条重复错误？
误区五：增量解析只按字符偏移缓存
追问：插入一个括号后，哪些父节点和语法状态必须失效？
延伸追问与参考答案
为什么要保留错误节点？
格式化、补全和高亮仍需要结构与范围；错误节点让下游显式处理不完整输入，而不是崩溃。
如何保证恢复终止？
每次恢复必须消费 token 或到达 EOF，并设置最大错误数和最大递归深度。
如何验证错误质量？
用包含多个独立错误的语料断言位置、数量、后续 AST 和运行时间，而非只测试第一个错误。