要问自己的第一个问题是您是否真的需要一个唯一的 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 索引标识的上下文中的位置以及类型。0
3
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 *)
但我敢肯定,当你开始研究你的解释器时,你会有更多的问题要问;)