在OCaml中抽象語法樹的S-表達式樹

我在OCaml中實現了一種符號語言，並且一直在努力將我的s表達式樹翻譯成抽象語法樹。在OCaml中抽象語法樹的S-表達式樹

的s表達式樹是

(* sexpr.mli *) 
type atom = 
    | Atom_unit 
    | Atom_int of int 
    | Atom_sym of string 

type expr = 
    | Expr_atom of atom 
    | Expr_list of expr list

抽象語法樹是

(* ast.ml *) 
open Sexpr 

type sym = string 

(* abstract syntax tree nodes *) 
type expr = 
    | Expr_unit 
    | Expr_int of int 
    | Expr_sym of sym 

(* Sexp.atom -> Ast.expr *) 
let ast_of_atom a = 
    match a with 
     | Atom_unit -> Expr_unit 
     | Atom_int n -> Expr_int n 
     | Atom_sym s -> Expr_sym s 

(* Sexp.expr -> Ast.expr *) 
let rec ast_of_sexpr sx = match sx with 
    | Expr_atom a -> ast_of_atom a 
    | Expr_list l -> 
    match l with 
     | [] -> ast_of_atom Atom_unit 
     | [x] -> ast_of_sexpr x 
     | h::t -> ignore (ast_of_sexpr h); ast_of_sexpr (Expr_list t)

ast_of_sexpr需要與類型簽名

val ast_of_sexpr : Sexpr.expr -> expr順應函數。

這是我的挑戰;我找不到一種符合類型簽名的方法來遞歸到s表達式樹中（即嵌套列表）並將s表達式樹節點轉換爲抽象語法樹節點。

在一個理想的世界裏，我可以評估列表頭，並在一個表達式中對尾部遞歸。我試圖用測序來模擬這種理想。但是，這當然會忽略左側值，並且只會在打印解析的標記流時輸出最後一個值。

任何人都可以提出一個方法來評估列表頭，而不忽略價值，並遞歸到s表達式樹更深？我甚至開放閱讀更好的解決方案來翻譯兩棵樹。

來源

2014-03-30 jdmartin86

Ast.expr類型定義看起來不正確：它不代表抽象語法樹，而只是原子表達式的語法。這是因爲這個類型根本不是遞歸的，所以它很難被稱爲樹。比較而言，Sexp.expr是遞歸類型。

我的猜測是，你的類型定義忘了的情況下，例如：

type expr = 
    | Expr_unit 
    | Expr_int of int 
    | Expr_sym of sym 
    | Expr_call of expr list

一旦做到這一點，這兩種類型實際上是相同的，因此轉換變得簡單。

來源

2014-03-30 17:26:29 chi

這是一個有趣的觀察。我認爲這也可能是解決這個問題的方法。在接受答案之前，我想清楚地理解你。實質上，你的建議是在兩棵樹之間創建一個一對一的映射關係？看起來很合理。但是爲什麼定義一個樹結構對於反覆的AST是非常必要的？我的印象是，對於符號語法來說，AST節點都是原子。我認爲s表達式列表類型只是作爲指令來深入到AST中。我誤解了這一點？ – jdmartin86

定義節點與定義樹不同。因爲需要在語法樹中存儲無限量的信息，並且非遞歸類型只能存儲有限數量，所以需要遞歸。當然，你可以單獨定義一個參數化的'tree'類型，然後使用'node tree'，其中'node'不是遞歸的，''tree''是。這就是'Sexp.expr'正在做兩個不同類型的聲明。 – chi

非常普遍，這裏是如何計算的一些值「不忽視他們」：

let v = <calculate> in 
let w = <calculate> in 
<expression using v and w>

我不知道這是你在問什麼，但這是人們開始OCaml的一個概念上的困難（恕我直言）。

來源

2014-03-30 16:55:48

在OCaml中抽象語法樹的S-表達式樹

回答

相關問題