Как работать со ссылками на переменные в yacc / bison (с ocaml) - PullRequest
Новая
       38

Как работать со ссылками на переменные в yacc / bison (с ocaml)

4 голосов
/ 11 декабря 2011

Мне было интересно, как обращаться с переменными ссылками внутри операторов при написании грамматик с помощью ocamlyacc и ocamllex.

Проблема в том, что утверждения вида 

var x = y + z
var b = true | f;

должно быть и правильным, но в первом случае переменная ссылается на числа, а во втором случае f является логической переменной.

В грамматике, которую я пишу, у меня есть это: 

numeric_exp_val:
  | nint { Syntax.Int $1 }
  | FLOAT { Syntax.Float $1 }
  | LPAREN; ne = numeric_exp; RPAREN { ne }
  | INCR; r = numeric_var_ref { Syntax.VarIncr (r,1) }
  | DECR; r = numeric_var_ref { Syntax.VarIncr (r,-1) }
  | var_ref { $1 }
;

boolean_exp_val:
  | BOOL { Syntax.Bool $1 }
  | LPAREN; be = boolean_exp; RPAREN { be }
  | var_ref { $1 }
;

, который, очевидно, не может работать, поскольку оба терминала var_ref не терминалы сводятся к одному и тому же (конфликт уменьшения / уменьшения). Но я бы хотел, чтобы проверка типов выполнялась в основном статически (в отношении ссылок на переменные) во время самой фазы синтаксического анализа.

Вот почему мне интересно, как лучше всего иметь переменные ссылки и сохранять эту структуру. В качестве дополнительной информации у меня есть функции, которые компилируют синтаксическое дерево, переводя его в байт-код, похожий на этот: 

let rec compile_numeric_exp exp =
  match exp with
    Int i -> [Push (Types.I.Int i)]
    | Float f -> [Push (Types.I.Float f)]
    | Bop (BNSum,e1,e2) -> (compile_numeric_exp e1) @ (compile_numeric_exp e2) @ [Types.I.Plus]
    | Bop (BNSub,e1,e2) -> (compile_numeric_exp e1) @ (compile_numeric_exp e2) @ [Types.I.Minus]
    | Bop (BNMul,e1,e2) -> (compile_numeric_exp e1) @ (compile_numeric_exp e2) @ [Types.I.Times]
    | Bop (BNDiv,e1,e2) -> (compile_numeric_exp e1) @ (compile_numeric_exp e2) @ [Types.I.Div]
    | Bop (BNOr,e1,e2) -> (compile_numeric_exp e1) @ (compile_numeric_exp e2) @ [Types.I.Or]
    | VarRef n -> [Types.I.MemoryGet (Memory.index_for_name n)]
    | VarIncr ((VarRef n) as vr,i) -> (compile_numeric_exp vr) @ [Push (Types.I.Int i);Types.I.Plus;Types.I.Dupe] @ (compile_assignment_to n) 
    | _ -> []

Ответы [ 2 ]

9 голосов
/ 11 декабря 2011

Синтаксический анализ просто не подходит для проверки типов.Я не понимаю, почему вы настаиваете на этом.Вы бы получили намного более четкий код и большую выразительную силу, выполнив его в отдельном проходе.

Это из соображений эффективности?Я уверен, что вы могли бы разработать эффективные процедуры инкрементной типизации в другом месте, чтобы вызывать их из грамматического производства (но я не уверен, что вы так много выиграете).Это выглядит как преждевременная оптимизация.

Была работа по написанию систем типов как атрибутных грамматик (которые можно рассматривать как декларативный способ выражения дериваций типирования), но я не думаю, чтоон предназначен для совмещения разбора и ввода за один проход.

Если вы действительно хотите пойти дальше в этом направлении, я бы посоветовал вам использовать простое лексическое различие между переменными с типом num и типом bool.Это звучит некрасиво, но просто.

4 голосов
/ 12 декабря 2011

Если вы хотите рассматривать числовые выражения и логические выражения как разные синтаксические категории, то подумайте, как вы должны проанализировать var x = ( ( y + z ) ). Вы не знаете, какой тип выражения вы анализируете, пока не нажмете +. Поэтому вам нужно съесть несколько жетонов, прежде чем вы узнаете, видите ли вы numeric_exp_val или boolean_exp_val: вам нужен какой-то неограниченный взгляд вперед. Yacc не предоставляет такой возможности просмотра (Yacc предоставляет только ограниченную форму просмотра, грубо описанную как LALR , которая ограничивает время анализа и требования к памяти). Есть даже неоднозначный случай, который делает вашу грамматику контекстно-зависимой: с определением типа var x = y вам нужно найти тип y.

Вы можете решить эту последнюю двусмысленность, передав информацию о типе в лексер, и вы можете решить необходимость просмотра с помощью генератора синтаксических анализаторов, который поддерживает неограниченный просмотр. Тем не менее, оба эти метода будут подталкивать ваш синтаксический анализатор к точке, в которой он не может легко эволюционировать, если вы захотите расширить язык позже (например, чтобы различать целые числа и числа с плавающей запятой, добавлять строки или списки и т. Д. ).

Если вам нужно простое, но ограничивающее исправление с низкими технологическими затратами, я подкреплю предложением Гаше о добавлении синтаксического различителя для определений числовых и логических переменных, что-то вроде bvar b = … и nvar x = … , Здесь снова будет сложно поддерживать другие типы позже.

В целом вам будет легче, если вы отделите проверку типа от анализа. После того как вы построили абстрактное синтаксическое дерево, выполните проверку типа (в которой вы получите тип переменных. 

type numeric_expression = Nconst of float | Nplus of numeric_expression * numeric_expression | …
 and boolean_expression = Bconst of bool | Bor of boolean_expression * boolean_expression | …
type typed_expression = Tnum of numeric_expression | Tbool of boolean_expression
type typed_statement = Tvar of string * typed_expression
let rec type_expression : Syntax.expression -> typed_expression = function
  | Syntax.Float x -> Tnum (Nconst x)
  | Syntax.Plus (e1, e2) ->
      begin match type_expression e1, type_expression e2 with
        | Tnum n1, Tnum n2 -> Tnum (Nplus (n1, n2))
        | _, (Tbool _ as t2) -> raise (Invalid_argument_type ("+", t2))
        | (Tbool _ as t1), _ -> raise (Invalid_argument_type ("+", t1))
      end
  | …
...