AST类型可以在ocaml中递归吗？

Question

我试图将我的语法翻译成 AST。

AST 类型可以递归吗？例如，我有一个作品 eprime -> PLUS t eprime | MINUS t eprime | epsilon。将其翻译成以下内容是否正确：

type eprime = 
| Add of t eprime 
| Minus of t eprime 
| Eempty

Answer 1

简短的回答是肯定的。这或多或少正是您定义树形数据结构的方式。

句法上正确的定义看起来更像这样：

type eprime = 
| Add of t * eprime 
| Minus of t * eprime 
| Empty

如果您假设 t 是 int（为简单起见），您可以像这样创建一个这种类型的值：

# Add (3, Add (4, Empty));;
- : eprime = Add (3, Add (4, Empty))

Answer 2

是的，AST 类型可以递归并且经常是。然而，正确的语法应该是 Add of t * eprime。如果没有 *，t 将被视为 eprime 的类型参数，它不带任何参数。

PS：您不必（而且可能不应该）像您一样严格地按照语法对 AST 进行建模。在 AST 中使用 "left recursion" 是完全可以的，即使您已将其从语法中删除。同样，您不必像在语法中那样在 AST 类型中对运算符优先级进行编码，因此例如在同一类型中使用 Add 和 Mult 是没有问题的。考虑到这一点，表达式的 AST 的通常定义看起来更像这样：

type exp =
  | Add of exp * exp
  | Sub of exp * exp
  | Mult of exp * exp
  | Div of exp * exp
  | FunctionCall of ident * exp list
  | Var of ident
  | Const of value

AST类型可以在ocaml中递归吗？

Can AST type be recursive in ocaml?

parsing

ocaml

abstract-syntax-tree