parsing - 在用 Ocaml 编写的编译器中，在哪里/如何声明变量的唯一键？

Question

我正在用 Ocaml 编写一个 mini-pascal 编译器。例如，我希望我的编译器接受以下代码:

program test;
var
   a,b : boolean;
   n : integer;
begin
   ...
end.

我在处理变量声明时遇到了困难(var 之后的部分)。目前，变量的类型在 sib_syntax.ml 中是这样定义的。 :

type s_var =
    { s_var_name: string;
      s_var_type: s_type; 
      s_var_uniqueId: s_uniqueId (* key *) }

在哪里 s_var_uniqueId (而不是 s_var_name )是变量的唯一键。我的第一个问题是，每次我有一个新变量时，我可以在哪里以及如何实现生成新 id 的机制(实际上是通过将最大的 id 增加 1)。我想知道我是否应该在 sib_parser.mly 中实现它, 这可能涉及一个静态变量 cur_id以及binding部分的修改，再次不知道如何在 .mly 中实现它们.或者我应该在下一阶段实现该机制 - interpreter.ml ?但在这种情况下，问题是如何制作 .mly与类型s_var一致, 什么 s_var_uniqueId我应该在 binding 的部分中提供吗？ ?

另一个问题是关于 statement 的这一部分在 .mly :

id = IDENT COLONEQ e = expression
  { Sc_assign (Sle_var {s_var_name = id; s_var_type = St_void}, e) }

在这里，我还需要提供下一级( interpreter.ml )一个我只知道 s_var_name 的变量, 那么我能对它的 s_var_type 做些什么呢？和 s_var_uniqueId这里？

有人可以帮忙吗？非常感谢你!

Answer 1

要问自己的第一个问题是您是否真的需要一个唯一的 id。根据我的经验，它们几乎从来没有必要甚至有用。如果您尝试通过 alpha-equivalence 使变量唯一，那么这应该在解析完​​成后发生，并且可能会涉及某种形式的 DeBruijn indices而不是唯一标识符。

无论哪种方式，每次调用都会返回一个新的整数标识符的函数是:

let unique = 
  let last = ref 0 in 
  fun () -> incr last ; !last

let one = unique ()  (* 1 *)
let two = unique ()  (* 2 *)

因此，您可以简单地分配 { ... ; s_var_uniqueId = unique () }在你的 Menhir 规则中。

您在这里尝试解决的更重要的问题是变量绑定(bind) .变量 x在一个位置定义并在另一个位置使用，您需要确定它在两个位置恰好是相同的变量。有很多方法可以做到这一点，其中之一是将绑定(bind)延迟到解释器。我将向您展示如何在解析过程中处理这个问题。

首先，我将定义一个上下文:它是一组变量，允许您根据变量的名称轻松检索变量。你可能想用哈希表或映射来创建它，但为了简单起见，我将使用 List.assoc这里。

type s_context = {
  s_ctx_parent : s_context option ;
  s_ctx_bindings : (string * (int * s_type)) list ;
  s_ctx_size : int ;
}

let empty_context parent = {
  s_ctx_parent = parent ;
  s_ctx_bindings = [] ;
  s_ctx_size = 0
}

let bind v_name v_type ctx = 
  try let _ = List.assoc ctx.s_ctx_bindings v_name in
      failwith "Variable is already defined"
  with Not_found -> 
    { ctx with 
      s_ctx_bindings = (v_name, (ctx.s_ctx_size, v_type)) 
        :: ctx.s_ctx_bindings ;
      s_ctx_size = ctx.s_ctx_size + 1 }

let rec find v_name ctx =       
  try 0, List.assoc ctx.s_ctx_bindings v_name
  with Not_found -> 
    match ctx.s_ctx_parent with 
      | Some parent -> let depth, found = find v_name parent in
                       depth + 1, found
      | None -> failwith "Variable is not defined"

所以，bind在当前上下文中添加一个新变量，find在当前上下文及其父级中查找变量，并返回绑定(bind)数据和找到它的深度。因此，您可以将所有全局变量放在一个上下文中，然后将函数的所有参数放在以全局上下文作为其父上下文的另一个上下文中，然后将函数中的所有局部变量(当您拥有它们时)放在第三种上下文中将函数的主要上下文作为父级，依此类推。

例如，find 'x' ctx将返回类似 0, (3, St_int) 的内容在哪里 0是变量的 DeBruijn 指数，3是变量在 DeBruijn 索引标识的上下文中的位置，St_int是类型。

type s_var = {
  s_var_deBruijn: int;
  s_var_type: s_type;
  s_var_pos: int 
}

let find v_name ctx = 
   let deBruijn, (pos, typ) = find v_name ctx in 
   { s_var_deBruijn = deBruijn ;
     s_var_type = typ ;
     s_var_pos = pos }

当然，您需要您的函数来存储它们的上下文，并确保第一个参数是上下文中位置 0 处的变量:

type s_fun =
{ s_fun_name: string;
  s_fun_type: s_type;
  s_fun_params: context; 
  s_fun_body: s_block; }

let context_of_paramlist parent paramlist = 
  List.fold_left 
    (fun ctx (v_name,v_type) -> bind v_name v_type ctx) 
    (empty_context parent)
    paramlist

然后，您可以更改解析器以考虑上下文。诀窍是，大多数规则不会返回代表 AST 的一部分的对象，而是返回一个函数，该函数将上下文作为参数并返回一个 AST 节点。

例如:

int_expression:
  (* Constant : ignore the context *)
| c = INT { fun _ -> Se_const (Sc_int c) }
  (* Variable : look for the variable inside the contex *)
| id = IDENT { fun ctx -> Se_var (find id ctx) }
  (* Subexpressions : pass the context to both *)
| e1 = int_expression o = operator e2 = int_expression 
  { fun ctx -> Se_binary (o, e1 ctx, e2 ctx) }
;

因此，您只需通过表达式递归地“向下”传播上下文。唯一聪明的部分是创建新上下文时的部分(你还没有这种语法，所以我只是添加一个占位符):

| function_definition_expression (args, body) 
  { fun ctx -> let ctx = context_of_paramlist (Some ctx) args in
               { s_fun_params = ctx ; 
                 s_fun_body = body ctx } }

以及全局上下文(程序规则本身不返回函数，但 block 规则返回，因此从全局变量创建上下文并提供)。

prog:
  PROGRAM IDENT SEMICOLON
  globals = variables
  main = block
  DOT
    { let ctx = context_of_paramlist None globals in 
      { globals = ctx;
        main = main ctx } }

由于 DeBruijn 索引，所有这些都使您的解释器的实现变得更加容易:您可以拥有一个“堆栈”来保存您的值(类型为 value)，定义为:

type stack = value array list 

然后，读写变量x很简单:

let read stack x = 
  (List.nth stack x.s_var_deBruijn).(x.s_var_pos)

let write stack x value = 
  (List.nth stack x.s_var_deBruijn).(x.s_var_pos) <- value

此外，由于我们确保函数参数的顺序与其在函数上下文中的位置相同，如果你想调用函数 f它的参数存储在数组 args 中，那么构建栈就很简单了:

let inner_stack = args :: stack in
(* Evaluate f.s_fun_body with inner_stack here *)

但我敢肯定，当你开始研究你的解释器时，你会有更多的问题要问；)