gpt4 book ai didi

compiler-construction - OCaml 中 S 表达式树到抽象语法树

转载 作者:行者123 更新时间:2023-12-05 00:26:10 26 4
gpt4 key购买 nike

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

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

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

最佳答案

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

我的猜测是您忘记了类型定义中的案例,例如:

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

一旦完成,这两种类型实际上是相同的,因此转换变得简单。

关于compiler-construction - OCaml 中 S 表达式树到抽象语法树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22746361/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com