yacc/bison（ocamlを使用）で変数参照を処理する方法

Question

ocamlyaccとocamllexを使って文法を書くときに、変数内の文をどのように処理するのかと思いました。

問題は、フォーム

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

のステートメントは両方の正確でなければならないが、第2ケースfにブール変数である第一の場合に変数は数値を意味することです。私はこれを持って書いている文法で

：

両方 var_ref以外の端末が同じに減らすため、明らかに動作しないことができ、（競合を削減/削減）

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 } 
; 

。しかし、私は構文解析フェーズ中に（静的に）（変数参照に関して）ほとんど行われている型チェックをしたいと思います。

だからこそ、私は可変参照を持ち、この構造を保持するのが最善の方法であると思っています。

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

Answer 1

解析が簡単に型チェックを行うには正しい場所ではありません。ただ、追加情報として、私はこの1つのようにバイトコードにそれを翻訳することによって、構文木をコンパイルする機能を持っています。私はあなたがこのパスでこれをすることを主張する理由を理解していません。あなたは、別のパスでそれを行うことにより、はるかに明確なコードとより表現力のあるパワーを得るでしょう。

効率的な理由からですか？私はあなたが効率的なインクリメンタル・タイピング・ルーチンを他のところで考案し、文法の生産から呼び出すことができると確信しています（しかし、それほど勝てるとは思いません）。これは時期尚早の最適化のようです。

attribute grammarsというタイプのシステムを書く作業がありましたが（これは、型定義の派生を表現するための宣言的方法と見ることができます）、パッシングと入力を1回のパスで行うことはできません。

本当にこの方向に進みたい場合は、num-typed変数とbool-typed変数の単純な字句差分を使用することをお勧めします。これは醜いと思うがシンプルです。

Answer 2

数値式とブール式を異なる構文カテゴリとして扱う場合は、どのように解析する必要があるのか​​を検討してください。var x = ((y + z))。あなたは+にヒットするまで、どのタイプの式を解析しているのか分かりません。したがって、numeric_exp_valかboolean_exp_valのいずれかが表示されているかどうかを知る前に、いくつかのトークンを食べる必要があります。無限の先読みが必要です。 Yaccはそのような先読みを提供していません（Yaccは、先読みの制限された形式しか提供しません、おおまかに言えば、構文解析の時間とメモリの必要条件に限界があるLALRと記載されています）。あなたの文法を文脈依存にするあいまいなケースもあります：var x = yのような定義では、yのタイプを調べる必要があります。

型情報をレクサーにフィードバックすることでこの最後のあいまいさを解決できます。無限の先読みをサポートするパーサジェネレータを使用すると、先読みの必要性を解決できます。しかし、これらのテクニックはどちらも、後で言語を拡張したい場合（たとえば、整数と浮動小数点数の区別、文字列やリストの追加など）、容易に進化できないポイントにパーサーを押し込みます。 ）。

あなたは単純だが、低技術のオーバーヘッドで修正を制約したい場合は、私は2番目の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 
    | …