menhir - 将 AST 节点与源文件中的标记位置相关联
menhir - associate AST nodes with token locations in source file
我正在使用 Menhir 来解析 DSL。我的解析器使用精心设计的嵌套类型集合构建 AST。在稍后为用户生成的错误报告中进行类型检查和其他传递时，我想参考它发生的源文件位置。这些不是解析错误，是解析完成后产生的。
一个天真的解决方案是为所有 AST 类型配备额外的位置信息，但这会使使用它们（例如构造或匹配）变得不必要的笨拙。这样做的既定做法是什么？
您需要以某种方式将位置信息附加到您的节点。通常的解决方案是将您的 AST 节点编码为记录，例如
type node =
| Typedef of typdef
| Typeexp of typeexp
| Literal of string
| Constant of int
| ...
type annotated_node = { node : node; loc : loc}
由于您使用的是记录，因此您仍然可以在没有太多句法开销的情况下进行模式匹配，例如，
match node with
| {node=Typedef t} -> pp_typedef t
| ...
根据您的表示，您可以选择单独包装类型的每个分支、包装整个类型或递归，就像@Isabelle Newbie 在 Frama-C 示例中那样。
一种类似但更通用的方法是不使用位置扩展节点，而只使用唯一标识符扩展节点，并使用最终映射将任意数据添加到节点。这种方法的好处是您可以在实际外部化节点属性时使用任意数据扩展节点。缺点是您实际上不能保证属性的完整性，因为有限映射是不完整的。因此，更难保持不变量，例如，所有节点都有一个位置。
由于每个堆分配对象已经有一个隐含的唯一标识符，地址，可以将数据附加到堆分配对象，而无需实际将其包装在另一种类型中。例如，我们仍然可以按原样使用类型 node 并使用有限映射将任意信息附加到它们，只要每个节点都是堆对象，即节点定义不包含常量构造函数（如果有，您可以通过添加一个虚假的单位值来解决它，例如，| End 可以表示为 | End of unit。
当然，我所说的地址，并不是字面上的意思是一个对象的物理或虚拟地址。 OCaml 使用移动 GC，因此 OCaml 对象的实际地址可能会在程序执行期间发生变化。此外，一般来说，地址不是唯一的，因为一旦一个对象被释放，它的地址就可以被一个完全不同的实体获取。
幸运的是，在最新版本的OCaml中添加了ephemera之后，它不再是一个问题。此外，ephemeron 可以很好地与 GC 配合使用，因此如果一个节点不再可达，它的属性（如文件位置）将由 GC 收集。所以，让我们用一个具体的例子来说明这一点。假设我们有两个节点 c1 和 c2:
let c1 = Literal "hello"
let c2 = Constant 42
现在我们可以创建从节点到位置的位置映射（我们将后者表示为字符串）
module Locations = Ephemeron.K1.Make(struct
type t = node
let hash = Hashtbl.hash (* or your own hash if you have one *)
let equal = (=) (* or a specilized equal operator *)
end)
Locations 模块提供了一个典型命令式哈希的接口table。所以让我们使用它。在解析器中，每当你创建一个新节点时，你应该在全局 locations 值中注册它的位置，例如，
let locations = Locations.create 1337
(* somewhere in the semantics actions, where c1 and c2 are created *)
Locations.add c1 "hello.ml:12:32"
Locations.add c2 "hello.ml:13:56"
稍后，您可以提取位置：
# Locations.find locs c1;;
- : string = "hello.ml:12:32"
如您所见，虽然解决方案在某种意义上很好，但它不涉及节点数据类型，因此您的其余代码可以在其上进行模式匹配，非常简单，但它仍然有点脏，因为它需要全局 mutable 状态，很难维护。此外，由于我们使用对象地址作为键，因此每个新创建的对象，即使它在逻辑上是从原始对象派生的，也将具有不同的身份。例如，假设您有一个函数，可以规范化所有文字：
let normalize = function
| Literal str -> Literal (normalize_literal str)
| node -> node
它将从原始节点创建一个新的Literal节点，因此所有位置信息都将丢失。这意味着，每次从一个节点派生出另一个节点时，您都需要更新位置信息。
蜉蝣的另一个问题是它们无法在编组或序列化后继续存在。即，如果您将 AST 存储在文件中的某处，然后恢复它，所有节点都将失去其身份，并且 location table 将变为空。
说到您在评论中提到的"monadic approach"。尽管 monad 很神奇，但它们仍然不能神奇地解决所有问题。它们不是灵丹妙药 :) 为了将某些东西附加到一个节点，我们仍然需要用一个额外的属性来扩展它 - 要么是直接的位置信息，要么是一个身份，通过它我们可以间接附加属性。 monad 对后者很有用，因为我们可以使用状态 monad 来封装我们的 id 生成器，而不是对最后分配的标识符进行全局引用。为了完整起见，不使用状态 monad 或全局引用来生成唯一标识符，您可以使用 UUID 并获取不仅在程序中唯一的标识符 运行，而且在全球范围内也是唯一的，在感觉世界上没有其他对象具有相同的标识符，无论您 运行 您的程序有多频繁（在理智的世界中）。虽然看起来生成 UUID 不使用任何状态，但在引擎盖下它仍然使用命令式随机数生成器，所以它有点作弊，但仍然可以看作是纯函数的，因为它不包含可观察的效果。
我不知道这是否是最佳实践，但我喜欢在 Frama-C 系统的抽象语法树中采用的方法；见 https://github.com/Frama-C/Frama-C-snapshot/blob/master/src/kernel_services/ast_data/cil_types.mli
此方法使用 "layers" 记录和代数类型相互嵌套。这些记录包含源位置等元信息，以及您可以匹配的代数 "node"。
例如，这里是表达式表示的一部分：
type ...
and exp = {
eid: int; (** unique identifier *)
enode: exp_node; (** the expression itself *)
eloc: location; (** location of the expression. *)
}
and exp_node =
| Const of constant (** Constant *)
| Lval of lval (** Lvalue *)
| UnOp of unop * exp * typ
| BinOp of binop * exp * exp * typ
...
因此给定一个 exp 类型的变量 e，您可以使用 e.eloc 访问其源位置，并在 e.enode 中的抽象语法树上进行模式匹配。
如此简单，"top-level"语法匹配非常简单：
let rec is_const_expr e =
match e.enode with
| Const _ -> true
| Lval _ -> false
| UnOp (_op, e', _typ) -> is_const_expr e'
| BinOp (_op, l, r, _typ) -> is_const_expr l && is_const_expr r
要在表达式中进行更深入的匹配，您必须在每一层都遍历一条记录。这增加了一些语法混乱，但不会太多，因为您可以只在您感兴趣的一个记录字段上进行模式匹配：
let optimize_double_negation e =
match e.enode with
| UnOp (Neg, { enode = UnOp (Neg, e', _) }, _) -> e'
| _ -> e
为了比较，在没有元数据的纯 AST 上，这将类似于：
let optimize_double_negation e =
match e.enode with
| UnOp (Neg, UnOp (Neg, e', _), _) -> e'
| _ -> e
我发现 Frama-C 的方法在实践中效果很好。
我正在使用 Menhir 来解析 DSL。我的解析器使用精心设计的嵌套类型集合构建 AST。在稍后为用户生成的错误报告中进行类型检查和其他传递时，我想参考它发生的源文件位置。这些不是解析错误，是解析完成后产生的。
一个天真的解决方案是为所有 AST 类型配备额外的位置信息，但这会使使用它们（例如构造或匹配）变得不必要的笨拙。这样做的既定做法是什么？
您需要以某种方式将位置信息附加到您的节点。通常的解决方案是将您的 AST 节点编码为记录，例如
type node =
| Typedef of typdef
| Typeexp of typeexp
| Literal of string
| Constant of int
| ...
type annotated_node = { node : node; loc : loc}
由于您使用的是记录，因此您仍然可以在没有太多句法开销的情况下进行模式匹配，例如，
match node with
| {node=Typedef t} -> pp_typedef t
| ...
根据您的表示，您可以选择单独包装类型的每个分支、包装整个类型或递归，就像@Isabelle Newbie 在 Frama-C 示例中那样。
一种类似但更通用的方法是不使用位置扩展节点，而只使用唯一标识符扩展节点，并使用最终映射将任意数据添加到节点。这种方法的好处是您可以在实际外部化节点属性时使用任意数据扩展节点。缺点是您实际上不能保证属性的完整性，因为有限映射是不完整的。因此，更难保持不变量，例如，所有节点都有一个位置。
由于每个堆分配对象已经有一个隐含的唯一标识符，地址，可以将数据附加到堆分配对象，而无需实际将其包装在另一种类型中。例如，我们仍然可以按原样使用类型 node 并使用有限映射将任意信息附加到它们，只要每个节点都是堆对象，即节点定义不包含常量构造函数（如果有，您可以通过添加一个虚假的单位值来解决它，例如，| End 可以表示为 | End of unit。
当然，我所说的地址，并不是字面上的意思是一个对象的物理或虚拟地址。 OCaml 使用移动 GC，因此 OCaml 对象的实际地址可能会在程序执行期间发生变化。此外，一般来说，地址不是唯一的，因为一旦一个对象被释放，它的地址就可以被一个完全不同的实体获取。
幸运的是，在最新版本的OCaml中添加了ephemera之后，它不再是一个问题。此外，ephemeron 可以很好地与 GC 配合使用，因此如果一个节点不再可达，它的属性（如文件位置）将由 GC 收集。所以，让我们用一个具体的例子来说明这一点。假设我们有两个节点 c1 和 c2:
let c1 = Literal "hello"
let c2 = Constant 42
现在我们可以创建从节点到位置的位置映射（我们将后者表示为字符串）
module Locations = Ephemeron.K1.Make(struct
type t = node
let hash = Hashtbl.hash (* or your own hash if you have one *)
let equal = (=) (* or a specilized equal operator *)
end)
Locations 模块提供了一个典型命令式哈希的接口table。所以让我们使用它。在解析器中，每当你创建一个新节点时，你应该在全局 locations 值中注册它的位置，例如，
let locations = Locations.create 1337
(* somewhere in the semantics actions, where c1 and c2 are created *)
Locations.add c1 "hello.ml:12:32"
Locations.add c2 "hello.ml:13:56"
稍后，您可以提取位置：
# Locations.find locs c1;;
- : string = "hello.ml:12:32"
如您所见，虽然解决方案在某种意义上很好，但它不涉及节点数据类型，因此您的其余代码可以在其上进行模式匹配，非常简单，但它仍然有点脏，因为它需要全局 mutable 状态，很难维护。此外，由于我们使用对象地址作为键，因此每个新创建的对象，即使它在逻辑上是从原始对象派生的，也将具有不同的身份。例如，假设您有一个函数，可以规范化所有文字：
let normalize = function
| Literal str -> Literal (normalize_literal str)
| node -> node
它将从原始节点创建一个新的Literal节点，因此所有位置信息都将丢失。这意味着，每次从一个节点派生出另一个节点时，您都需要更新位置信息。
蜉蝣的另一个问题是它们无法在编组或序列化后继续存在。即，如果您将 AST 存储在文件中的某处，然后恢复它，所有节点都将失去其身份，并且 location table 将变为空。
说到您在评论中提到的"monadic approach"。尽管 monad 很神奇，但它们仍然不能神奇地解决所有问题。它们不是灵丹妙药 :) 为了将某些东西附加到一个节点，我们仍然需要用一个额外的属性来扩展它 - 要么是直接的位置信息，要么是一个身份，通过它我们可以间接附加属性。 monad 对后者很有用，因为我们可以使用状态 monad 来封装我们的 id 生成器，而不是对最后分配的标识符进行全局引用。为了完整起见，不使用状态 monad 或全局引用来生成唯一标识符，您可以使用 UUID 并获取不仅在程序中唯一的标识符 运行，而且在全球范围内也是唯一的，在感觉世界上没有其他对象具有相同的标识符，无论您 运行 您的程序有多频繁（在理智的世界中）。虽然看起来生成 UUID 不使用任何状态，但在引擎盖下它仍然使用命令式随机数生成器，所以它有点作弊，但仍然可以看作是纯函数的，因为它不包含可观察的效果。
我不知道这是否是最佳实践，但我喜欢在 Frama-C 系统的抽象语法树中采用的方法；见 https://github.com/Frama-C/Frama-C-snapshot/blob/master/src/kernel_services/ast_data/cil_types.mli
此方法使用 "layers" 记录和代数类型相互嵌套。这些记录包含源位置等元信息，以及您可以匹配的代数 "node"。
例如，这里是表达式表示的一部分：
type ...
and exp = {
eid: int; (** unique identifier *)
enode: exp_node; (** the expression itself *)
eloc: location; (** location of the expression. *)
}
and exp_node =
| Const of constant (** Constant *)
| Lval of lval (** Lvalue *)
| UnOp of unop * exp * typ
| BinOp of binop * exp * exp * typ
...
因此给定一个 exp 类型的变量 e，您可以使用 e.eloc 访问其源位置，并在 e.enode 中的抽象语法树上进行模式匹配。
如此简单，"top-level"语法匹配非常简单：
let rec is_const_expr e =
match e.enode with
| Const _ -> true
| Lval _ -> false
| UnOp (_op, e', _typ) -> is_const_expr e'
| BinOp (_op, l, r, _typ) -> is_const_expr l && is_const_expr r
要在表达式中进行更深入的匹配，您必须在每一层都遍历一条记录。这增加了一些语法混乱，但不会太多，因为您可以只在您感兴趣的一个记录字段上进行模式匹配：
let optimize_double_negation e =
match e.enode with
| UnOp (Neg, { enode = UnOp (Neg, e', _) }, _) -> e'
| _ -> e
为了比较，在没有元数据的纯 AST 上，这将类似于：
let optimize_double_negation e =
match e.enode with
| UnOp (Neg, UnOp (Neg, e', _), _) -> e'
| _ -> e
我发现 Frama-C 的方法在实践中效果很好。