Syntactic Specifications

Note

Here is the grammar of the Tiger language for user inputs.

Do not forget that our compiler uses meta-variables internally and must therefore handle the Additional Syntactic Specifications.

We use Extended BNF, with [ and ] for zero or once, and { and } for any number of repetition including zero.

program =
    exp
  | chunks
  ;


(* === Expressions. === *)
exps = [ exp { ";" exp } ] ;
exp =
  (* Literals. *)
    "nil"
  | integer
  | string

  (* Array and record creations. *)
  | type-id "[" exp "]" "of" exp
  | type-id "{" [ id "=" exp { "," id "=" exp } ] "}"

  (* Variables, field, elements of an array. *)
  | lvalue

  (* Function call. *)
  | id "(" [ exp { "," exp }] ")"

  (* Operations. *)
  | "-" exp
  | exp op exp
  | "(" exps ")"

  (* Assignment. *)
  | lvalue ":=" exp

  (* Control structures. *)
  | "if" exp "then" exp ["else" exp]
  | "while" exp "do" exp
  | "for" id ":=" exp "to" exp "do" exp
  | "break"
  | "let" chunks "in" exps "end"
  ;

lvalue =
    id
  (* Record field access. *)
  | lvalue "." id
  (* Array subscript. *)
  | lvalue "[" exp "]"
  ;

op = "+" | "-" | "*" | "/" | "=" | "<>" | ">" | "<" | ">=" | "<=" | "&" | "|" ;


(* === Chunks of declarations. === *)
chunks = { chunk } ;
chunk =
    { tydec }   (* tychunk *)
  | { fundec }  (* funchunk *)
  | vardec      (* varchunk *)

  (* Importing a set of declarations. *)
  | "import" string
  ;

(* Variable declaration. *)
vardec = "var" id [ ":" type-id ] ":=" exp ;

(* Type declaration. *)
tydec = "type" id "=" ty ;

(* Function declaration. *)
fundec =
    "function" id "(" tyfields ")" [ ":" type-id ] "=" exp
  | "primitive" id "(" tyfields ")" [ ":" type-id ]
  ;


(* === Types. === *)
ty =
   (* Type alias. *)
     type-id
   (* Record type definition. *)
   | "{" tyfields  "}"
   (* Array type definition. *)
   | "array" "of" type-id
   ;

tyfields = [ id ":" type-id { "," id ":" type-id } ] ;
type-id = id ;

Precedence of the op operators from high to low:

* /
+ -
>= <= = <> < >
&
|

Comparison operators (<, <=, =, <>, > and >=) are not associative. All the remaining operators are left-associative.

Warning

If you use the exp op exp and op rules as such, Bison will not be able to solve shift/reduce conflicts between operators using their precedences.

This is fixed by expliciting the rule exp op exp for each operator. For example with +, -, * and /, the grammar could look like the following:

exp =
  (* Previous rules ... *)

  (* Operations. *)
  | "-" exp
  | exp "+" exp
  | exp "-" exp
  | exp "*" exp
  | exp "/" exp
  | "(" exps ")"

  (* Next rules ... *)

Tiger’s object-oriented syntax implies additional rules as described below.

exp =
  (* Object creation. *)
  "new" type-id

  (* Method call. *)
  | lvalue "." id "(" [ exp { "," exp }] ")"
  ;


(* Class definition (alternative form). *)
tydec = "class" id [ "extends" type-id ] "{" classfields "}" ;

(* Class definition (canonical form). *)
ty = "class" [ "extends" type-id ] "{" classfields "}" ;

(* Class fields. *)
classfields = { classfield } ;
classfield =
  (* Attribute declaration (varchunk). *)
    vardec
  (* Method declaration (methchunk). *)
  | { "method" id "(" tyfields ")" [ ":" type-id ] "=" exp }
  ;