如何處理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）

回答

相關問題