何时在 Ocaml AST 中使用 "and" 运算符

Question

我正在将我的语法规则翻译成 AST。

是否有必要在定义我们的 AST 时使用 "and" 运算符？

例如，到目前为止我的语法是这样翻译的：

type program =
   |  Decls of typ * identifier * decls_prime

type typ =
   | INT
   | BOOL
   | VOID

type identifier = string

(* decls_prime = vdecl decls | fdecl decls *)
type declsprime =
   | Vdecl of variabledeclaration * decls
   | Fdecl of functiondeclaration * decls

(*“lparen” formals_opt “rparen” “LBRACE” vdecl_list stmt_list “RBRACE”*)
type functiondeclaration =
    | Fdecl of variabledeclarationlist * stmtlist

(*formals_opt = formal_list | epsilon *)
type FormalsOpt =
   |FormalsOpt of formallist

(* typ “ID” formal_list_prime *)
type formalList =
    | FormalList of typ * identifier * formallistprime

type formallistprime =
    | FormalListPrime of formalList

type variabledeclarationlist =
    | VdeclList of variabledeclaration * variabledeclarationlist

(*stmt stmt_list | epsilon*)
type stmtlist =
    | StmtList of stmt * stmtlist
    | StmtlistNil 

(* stmt = “RETURN” stmt_prime| expr SEMI |“LBRACE” stmt_list RBRACE| IF LPAREN expr RPAREN stmt stmt_prime_prime| FOR LPAREN expr_opt SEMI expr SEMI expr_opt RPAREN stmt| WHILE LPAREN expr RPAREN stmt*)
type Stmt
| Return of stmtprime
| Expression of expr
| StmtList of stmtlist
| IF of expr * stmt * stmtprimeprime
| FOR of expropt * expr * expropt * stmt 
| WHILE of expr * stmt

(*stmt_prime = SEMI| expr SEMI*)
type stmtprime
| SEMI 
| Expression of expr 

(*NOELSE | ELSE stmt*)
type stmtprimeprime
| NOELSE 
| ELSE of stmt

(* Expr_opt = expr | epsilon *)
type expropt =
| Expression of expr 
| ExprNil 

type Expr

type ExprPrime

(* Actuals_opt  = actuals_list  | epsilon *)
type ActualsOpt= 
| ActualsList of actualslist 
| ActualsNil

type ActualsList = 
| ActualsList of expr * actualslistprime

(*actualslistprime = COMMA expr actuals_list_prime | epsilon*)
type actualslistprime = 
| ActualsListPrime of expr * actualslistprime
| ALPNil

但看起来这个来自伊利诺伊州的示例使用的结构略有不同：

type program = Program of (class_decl list)
and class_decl = Class of id * id * (var_decl list) * (method_decl list)
and method_decl = Method....

在定义我的 AST 时是否需要使用 "and"？而且，即使我在解析器中正确调用了 AST StmtList 方法，我使用 StmtList 类型而不是 (stmt list) 是错误的吗？

Answer 1

当您的定义相互递归时，您只需要 and。也就是说，如果一个语句可以包含一个表达式，而一个表达式又可以包含一个语句，那么 Expr 和 Stmt 必须与 and 连接。如果您的代码在没有 and 的情况下编译，则不需要 and.

PS：这与您的问题无关，但我认为使用 list 和 option 类型比定义您自己的版本更有意义特定类型（例如 stmntlist、expropt 等）。 stmtprime 是另一种情况：您可以将 Return 定义为 Return of expr option 并删除 stmtprime 类型。与 stmtprimeprime.

相同

何时在 Ocaml AST 中使用 "and" 运算符

When to use "and" operator in Ocaml AST

parsing

ocaml

abstract-syntax-tree