Pfthb

I am translating the rules of my grammar into an AST.

Is it necessary to use the "and" operator in defining our AST?

For instance, I have translated my grammar thus far like so:

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

But it looks as though this example from Illinois uses a slightly different structure:

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

Is it necessary to use "and" when defining my AST? And moreover, is it wrong for me to use a StmtList type rather than (stmt list) even though I call the AST StmtList method correctly in my parser?

You only need and when your definitions are mutually recursive. That is, if a statement could contain an expression and an expression could in turn contain a statement, then Expr and Stmt would have to be connected with an and. If your code compiles without and, you don't need the and.

PS: This is unrelated to your question, but I think it would make a lot more sense to use the list and option types than to define your own versions for specific types (such as stmntlist, expropt etc.). stmtprime is another such case: You could just define Return as Return of expr option and get rid of the stmtprime type. Same with stmtprimeprime.