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

Question

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

AST 类型可以递归吗？例如，我有一个生产eprime -> PLUS t eprime | MINUS t eprime | epsilon. 将其翻译为：

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

标签： parsingocamlabstract-syntax-tree

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))