在用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等价使变量唯一,那么这应该在解析完​​成后发生,并且可能涉及某种形式的DeBruijn索引而不是唯一标识符.

无论哪种方式,每次调用时返回新整数标识符的函数是:

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

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

因此,您可以简单地指定{ ... ; s_var_uniqueId = unique () }您的Menhir规则.

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

首先,我将定义一个上下文:它是一组变量,允许您根据其名称轻松检索变量.您可能希望使用哈希表或映射创建它,但为了简单起见,我将在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在当前上下文及其父项中查找变量,并返回绑定数据和找到它的深度.因此,您可以在一个上下文中包含所有全局变量,然后在另一个上下文中将函数的所有参数作为其父级,然后在第三个上下文中将函数中的所有局部变量(当您拥有它们时)将函数的主要上下文作为父级,依此类推.

所以,举例来说,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 *)

但是我确定当你开始在你的interpeter工作时,你会有更多的问题要问;)