Может ли тип 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

Да, тип AST может быть рекурсивным и часто таковым является. Однако правильный синтаксис будет Add of t * eprime. Без * t будет рассматриваться как аргумент типа для eprime, который не принимает ничего.

PS: Вам не нужно (и, вероятно, не следует) моделировать АСТ после грамматики так же тщательно, как и вы. Совершенно нормально иметь «левую рекурсию» в AST, даже если вы удалили ее из своей грамматики. Точно так же вам не нужно кодировать приоритет оператора в ваших типах 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

Answer 2

Краткий ответ - да.Это более или менее точно, как вы определяете древовидную структуру данных.

Синтаксически правильное определение выглядит примерно так:

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

Если вы предполагаете, t равно int(для простоты) вы можете создать значение этого типа следующим образом:

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