如何处理yacc/bison中的变量引用（使用ocaml）

我想知道如何在使用ocamlyacc和ocamllex编写文法时处理语句中的变量引用。如何处理yacc/bison中的变量引用（使用ocaml）

的问题是，形式

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) 
    | _ -> []

来源

2011-12-11 Jack

解析，根本就不是做类型检查的正确的地方。我不明白你为什么坚持要这样做。通过单独的传递，您可以拥有更清晰的代码和更强大的表达能力。

是出于效率的原因吗？我相信你可以在其他地方设计高效的增量打字例程，从语法产品中调用（但我不确定你会赢得多少）。这看起来像不成熟的优化。

作为attribute grammars（它可以被看作是一种声明性的方式来表达键入派生）已经在写作类型系统的工作，但我不认为它是为了混淆分析和打字在一次通过。

如果你真的想在这个方向上走得更远，我建议你在num-typed和bool-typed变量之间使用简单的词汇区分。这听起来很丑，但很简单。

来源

2011-12-11 14:51:52 gasche

我只是分体式检查从分析阶段。我知道，我只是懒惰但利用类型推断+解析强大功能来自动检查的可能性真的很诱人:) – Jack

如果您想将数值表达式和布尔表达式视为不同的语法类别，请考虑如何解析var x = ((y + z))。您不知道要分析哪种类型的表达式，直到您点击+。因此，在知道您是否看到numeric_exp_val或boolean_exp_val之前，您需要先吃掉几个标记：您需要一些无限的前瞻。 Yacc没有提供这样的预测（Yacc只提供了一种限制的预见形式，大致描述为LALR，这对解析时间和内存要求提出了限制）。甚至有一个模棱两可的情况，使得你的文法上下文敏感：像var x = y这样的定义，你需要查找y的类型。

您可以通过将类型信息反馈到词法分析器来解决最后的不确定性，并且可以通过使用支持无界预测的分析器生成器来解决对预测的需求。但是，如果您稍后想要扩展语言（例如区分整数和浮点数字，添加字符串或列表等），这两种技术都会将解析器推向不易发展的地步。）。

如果你想用一个低技术的开销一个简单但制约修正，我将第二gasche's suggestion增加对数字和布尔变量定义一个语法识别器，像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 
    | …

来源

2011-12-11 22:39:19 Gilles

如何处理yacc/bison中的变量引用（使用ocaml）

回答

相关问题