能否让Menhir生成函子以实现参数化解析器？

问题背景 #

我们有一组结构相似、仅值类型与关键字不同的语言族，已定义如下模块签名：

module type M = sig
  type value_type
  type keyword
end

以及基于该签名的AST函子：

module AST (M : M) = struct
  type t = ...
  ...
end

通过传入不同的M模块可实例化出多种AST变体（如AST1 = AST(M1)、AST2 = AST(M2)等）。目前实现AST(M).t解析器的方式存在局限：要么为每个AST变体单独编写解析器，要么先解析为通用AST再转换（需遍历AST，效率较低）。希望通过Menhir直接生成基于M的参数化解析器，一步完成解析。

可行方案：生成解析器函子 #

Menhir支持生成参数化的解析器函子，具体步骤如下：

1. 编写参数化语法文件 #

在Menhir的.mly语法文件中，通过%parameter声明引入依赖模块，让语法规则绑定到该模块的类型与辅助函数。示例如下：

%parameter (M : sig
  type value_type
  type keyword
  val keyword_of_string : string -> keyword option
  val parse_value : string -> value_type
end)

%start <AST(M).t> main
%%
main:
  expr EOF { $1 }
;

expr:
  | KEYWORD kw { AST.Keyword (M.keyword_of_string kw |> Option.get) }
  | VALUE v { AST.Value (M.parse_value v) }
;

这里的%parameter声明了一个扩展版的M签名，除原有类型外，新增了将字符串转换为关键字、值类型的辅助函数——Menhir需要这些逻辑来完成词法单元到AST节点的映射。

2. 编译生成函子 #

使用Menhir的--functor和--infer选项编译语法文件：

menhir --infer --functor parser.mly

编译后会生成一个Parser函子，其签名大致为：

module Parser (M : sig
  type value_type
  type keyword
  val keyword_of_string : string -> keyword option
  val parse_value : string -> value_type
end) = struct
  type t = AST(M).t
  val main : (Lexing.lexbuf -> token) -> Lexing.lexbuf -> t
  ...
end

3. 实例化解析器 #

针对不同的M模块，直接实例化函子即可得到对应AST的解析器：

module M1 = struct
  type value_type = int
  type keyword = If | Else
  let keyword_of_string s = match s with
    | "if" -> Some If
    | "else" -> Some Else
    | _ -> None
  let parse_value s = int_of_string s
end

module Parser1 = Parser(M1)
(* Parser1.main 即可直接解析生成 AST(M1).t 类型的结果 *)

关键注意事项 #

• %parameter声明的模块必须包含解析所需的全部依赖，仅类型定义不足以支撑Menhir生成解析逻辑；
• 词法分析器需与参数化解析器配合，输出的词法单元（如示例中的KEYWORD、VALUE）要与语法文件中的规则对应；
• 若原有M签名未包含辅助函数，可定义扩展签名（如M_with_parsing），让原M模块实现该扩展签名，或在实例化时补充所需函数。

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