如何在Menhir Incremental的on_fail中推送合成令牌？及方案合理性探讨

一、on_fail函数推送DEDENT合成令牌的实现示例 #

首先需在.mly文件中声明DEDENT为令牌（无需在.mll中定义对应的词法规则）：

%token DEDENT

以下是在错误恢复函数on_fail中动态推送DEDENT的OCaml实现：

open MenhirLib.General
open MenhirLib.ErrorReports
module Parser = Parser
module Lexer = Lexer

let rec on_fail (env : _ Parser.env) (pos : Lexing.position) =
  match Parser.top env with
  | Some (Parser.Element (state, _, _, _)) ->
      (* 检查当前解析状态是否期望DEDENT令牌 *)
      if List.mem Parser.DEDENT (Parser.expecting state) then
        (* 推送合成DEDENT令牌，位置复用当前游标位置 *)
        Parser.offer env (Parser.DEDENT, pos, pos)
      else
        (* 其他错误恢复逻辑：如跳过当前令牌或终止解析 *)
        failwith "Unrecoverable syntax error"
  | None ->
      failwith "No active parser state for recovery"

核心要点： #

• 利用Parser.expecting获取当前状态的期望令牌列表，精准判断是否需要插入DEDENT。
• Parser.offer将合成令牌注入解析输入流，让解析器继续尝试匹配case语句的闭合规则。

二、无符号关联合成令牌方案的合理性 #

这种方案是可行且符合解析器设计实践的，原因如下：

• 解决上下文依赖的缩进问题：BNF无法表达嵌套结构的缩进层级约束，合成DEDENT令牌可以在解析冲突时动态补充缺失的闭合标记，弥补BNF的局限性。
• 分离词法与解析职责：无需在词法分析器中维护复杂的缩进状态机（如跟踪层级、生成INDENT/DEDENT），将缩进相关逻辑转移到解析阶段的错误恢复中，保持.mll文件简洁。
• 适配Menhir特性：Menhir的错误恢复机制支持动态推送令牌，该方案充分利用这一特性，无需大幅修改核心语法规则结构。

潜在风险与优化方向： #

• 错误恢复准确性：需避免盲目推送DEDENT，必须结合当前解析状态的期望令牌判断，否则可能生成错误的语法树。
• 调试复杂度：合成令牌不在原始词法流中，调试时需额外日志跟踪DEDENT的插入时机。
• 性能影响：频繁的错误恢复操作可能小幅降低解析性能，但对多数场景可忽略。

内容的提问来源于stack exchange，提问作者Bleg Bleg