4

我正在 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 表达式树节点转换为抽象语法树节点。

在理想情况下，我可以评估列表头部并在一个表达式中递归尾部。我尝试使用排序来模拟这种理想状态。但这当然会忽略左侧的值，并且只会在打印已解析的标记流时输出最后一个值。

任何人都可以建议一种评估列表头的方法，而不忽略 value，并更深入地递归到 s 表达式树中吗？我什至愿意阅读更好的解决方案来在两棵树之间进行翻译。

4

2 回答 2

4

Ast.expr类型定义看起来不对：它不代表抽象语法树，而只是原子表达式的语法。这是因为该类型根本不是递归的，所以它几乎不能称为树。相比之下，Sexp.expr是递归类型。

我的猜测是您在类型定义中忘记了一个案例，例如：

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

一旦这样做了，这两种类型实际上是相同的，因此转换变得简单。

于 2014-03-30T17:26:29.833 回答
2

非常一般地，这里是如何计算一些值“而不忽略它们”：

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

我不确定这是您要问的，但对于从 OCaml（恕我直言）开始的人们来说，这是一个概念上的困难。

于 2014-03-30T16:55:48.033 回答