5

我正在用 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另一个问题是关于in 的这一部分.mly

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

在这里,我还需要提供下一级 (the interpreter.ml) 一个我只知道的变量s_var_name,那么对于它s_var_types_var_uniqueId这里我能做些什么呢?

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

4

2 回答 2

5

要问自己的第一个问题是您是否真的需要一个唯一的 id。根据我的经验,它们几乎从来没有必要甚至有用。如果您要做的是通过alpha-equivalence使变量唯一,那么这应该在解析完​​成后发生,并且可能涉及某种形式的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将返回变量的 DeBruijn 索引在0, (3, St_int)哪里,变量在由 DeBruijn 索引标识的上下文中的位置以及类型。03St_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 *)

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

于 2011-06-29T10:19:11.613 回答
2

如何创建全局 id 生成器:

let unique =
  let counter = ref (-1) in
  fun () -> incr counter; !counter

测试:

# unique ();;
- : int = 0
# unique ();;
- : int = 1

关于您更一般的设计问题:您的数据表示似乎没有忠实地表示编译器阶段。如果s_var_type在解析阶段之后必须返回一个类型感知的数据类型(带有这个字段),那就有问题了。你有两个选择:

  • 为解析后的 AST 设计更精确的数据表示,这将不同于后键入的 AST,并且没有这些s_var_type字段。键入将是从无类型到有类型 AST 的转换。这是我推荐的一个干净的解决方案。

  • 承认你必须打破数据表示语义,因为你在这个阶段没有足够的信息,并尝试在St_void解析阶段之后对返回垃圾的想法保持冷静,以便稍后重建正确的信息。这是较少类型的(因为您对数据有一个隐含的假设,这在类型中并不明显),更务实,丑陋但有时是必要的。在这种情况下,我认为这不是正确的决定,但是您会遇到最好少打字的情况。

我认为独特的 id 处理设计的具体选择取决于你在这个更一般的问题上的立场,以及你对类型的具体决定。如果您选择解析后 AST 的更精细类型表示,则由您决定是否包含唯一 ID(我会,因为生成唯一 ID 非常简单,不需要单独的传递,我会而不是稍微复杂化语法产生而不是打字阶段)。如果您选择使用虚拟值破解类型字段,如果您愿意,也可以对变量 id 执行此操作,将0其作为虚拟值并稍后定义;但我个人仍然会在解析阶段这样做。

于 2011-06-29T09:50:56.673 回答