error-handling - menhir - 将 AST 节点与源文件中的 token 位置相关联

Question

我正在使用 Menhir 来解析 DSL。我的解析器使用精心设计的嵌套类型集合构建 AST。在稍后的类型检查和为用户生成的错误报告中的其他传递过程中，我想引用它发生的源文件位置。这些不是解析错误，是解析完成后产生的。

一个天真的解决方案是为所有 AST 类型配备额外的位置信息，但这会使使用它们(例如构造或匹配)变得不必要的笨拙。这样做的既定做法是什么？

Answer 1

我不知道这是否是最佳实践，但我喜欢在 Frama-C 系统的抽象语法树中采用的方法；见 https://github.com/Frama-C/Frama-C-snapshot/blob/master/src/kernel_services/ast_data/cil_types.mli

这种方法使用相互嵌套的记录和代数类型的“层”。记录保存元信息，如源位置，以及您可以匹配的代数“节点”。

例如，这里是表达式表示的一部分:

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
...

所以给定一个变量 e类型 exp ，您可以使用 e.eloc 访问其源位置, 并在 e.enode 中对其抽象语法树进行模式匹配.

如此简单，语法上的“顶级”匹配非常简单:

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 的方法在实践中效果很好。