在 OCaml 中向我的 AST 添加行信息

Question

我正在 OCaml 中创建一个编译器，语法如下：

type expr =
| Cons of const
| Var of string
| List of ( expr list )
| Sum of ( expr * expr )
| Less_than of ( expr * expr ) 
| Conditional of ( expr * expr * expr )
| Array_literal of ( expr )
| Array_read of ( expr * expr )

AST 的节点如下所示：

type 'a astNode = 
{
data: 'a;
metadata: Metadata;
}

元数据模块如下所示：

module Metadata = struct
    type loc = Lexing.position
    type loc_range = loc * loc

    and metadata = ?
end

元数据的语法应该是什么？在行 and metadata = ? 之后我的代码会是什么样子基本上，我什么时候需要用元数据信息更新 AST。我应该如何构建我的 AST 以包含元数据信息？对我来说，元数据目前意味着它的位置，例如行号、文件名等。这包含在 Lexing.position 模块中。

Answer 1

这更像是一个软件设计问题，有一些常见的解决方案。我将尝试涵盖所有内容。

最常见的解决方案是将您的表达式类型包装到一个记录中，该记录除了表达式有效负载外，还有一些元数据。元数据的类型可以抽象或具体，这也是一个品味问题。元数据的抽象类型使以后更容易扩展它。经典的方法是在 OCaml 编译器本身实现的，参考 Locations 模块，它会告诉你如何在经典的 OCaml Yacc/Menhir 解析器中获取位置信息。

一种略有不同的方法是索引树并将标识符附加到每个 AST 节点。然后您可以使用外部映射（如任何关联容器）将任意元数据添加到您的 AST。 BAP Primus Lisp Parser 中使用了这种方法。这种方法的好处是它可以很容易地与 hash-consing 结合使用。它还使您可以轻松扩展与节点相关联的属性集，而成本映射现在是部分的。（或记录映射之间的常见选择）。

您可以选择一些特定的方法来为节点编号（例如，DFS 编号），而不是直接在节点中存储索引。使用这种方法，您不需要修改您的 AST 类型，如果您不控制它，那将特别好。这种方法的一个例子是来自 Janestreet 的 parsexp 库的 Positions 模块，它基于一些遍历（不是 DFS 编号）实现了位置的紧凑集。不幸的是，它们的实现不够通用，无法与不同的 AST 重用，但该方法是通用的。

在 OCaml 中向我的 AST 添加行信息

Adding line information to my AST in OCaml

compiler-construction

ocaml

metadata

abstract-syntax-tree