Первый вопрос, который нужно задать себе, - действительно ли вам нужен уникальный идентификатор. По моему опыту, они почти никогда не нужны или даже полезны. Если вы пытаетесь сделать переменные уникальными через альфа-эквивалентность , то это должно произойти после завершения синтаксического анализа и, вероятно, будет включать некоторую форму индексов Дебрюйна вместо уникальных идентификаторы.
В любом случае, функция, которая возвращает новый целочисленный идентификатор каждый раз, когда она вызывается:
let unique =
let last = ref 0 in
fun () -> incr last ; !last
let one = unique () (* 1 *)
let two = unique () (* 2 *)
Итак, вы можете просто назначить { ... ; s_var_uniqueId = unique () } в своих правилах Менгира.
Более важной проблемой, которую вы пытаетесь решить, является проблема привязки переменных . Переменная 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 } }
Все это значительно упрощает реализацию вашего интерпретатора благодаря индексам Дебрюйна: у вас может быть «стек», в котором хранятся ваши значения (типа 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 *)
Но я уверен, что у вас будет гораздо больше вопросов, когда вы начнете работать с вашим интерпретатором;)