%%
%term
    EOF
  | ID of string
  | INT of int | STRING of string  (*literals*)
  | COMMA | COLON | SEMICOLON | LPAREN | RPAREN | LBRACK | RBRACK (*punctuation*)
  | LBRACE | RBRACE | DOT (*record operators*)
  | UNARY | PLUS | MINUS | TIMES | DIVIDE | EQ | NEQ | LT | LE | GT | GE (*arithmetic operators*)
  | AND | OR | ASSIGN
  | ARRAY | IF | THEN | ELSE | NO_ELSE | WHILE | FOR | TO | DO | LET | IN | END | OF (*control flow*)
  | BREAK | NIL (*more control flow*)
  | FUNCTION | VAR | TYPE

%nonterm  exp | program | decs | dec | tydec | vardec | fundec | ty | tyfields | tyfield
    | lvalue | lval | exp_sequence | sequence | seq | fun_args | args | recs | rec | rec_tail | rec_node | record | control_flow | function_call | boolean | arithmetic | comparison | assign | array

%pos int
%verbose
%start program
%eop EOF
%noshift EOF

%name Tiger

%keyword WHILE FOR TO BREAK LET IN END FUNCTION VAR TYPE ARRAY IF THEN ELSE
    DO OF NIL

%prefer THEN ELSE LPAREN

%value ID ("bogus")
%value INT (1)
%value STRING ("")

(*Setting explicit precedence follows*)

(* We want to shift when there is an exp of the following form
 * if e1 then if e2 then s1 else s2
 * shifting is preferred to reducing to avoid
 * the dangling else problem.
 * Hence THEN has lower precedence than ELSE => shift will happen, not reduce.
 * idea borrowed from :
 * https://www.gnu.org/software/bison/manual/html_node/Precedence-Only.html#Precedence-Only
 *)
%nonassoc NO_ELSE
%nonassoc ELSE

%right OF (*OF is right associative in array OF*)
%nonassoc DO
%nonassoc ASSIGN
%nonassoc EQ NEQ LT GT LE GE

(*A&B|C&D should reduce to ((A&B|(C&D), and not (A&(B|C)&D)*)
%left OR
%left AND

%left PLUS MINUS
%left TIMES DIVIDE
%left UNARY (*unary minus, highest precedence*)

%%

program : exp               ()


(*Declarations*)
decs : (*epsilon*) ()
     | dec decs    ()

dec : tydec    ()
    | vardec   ()
    | fundec   ()

(*Data types*)
tydec : TYPE ID EQ ty () (*type type-id = ty*)
(*ID : ID               ()    *)

ty : ID ()
   | LBRACE tyfields RBRACE     ()
   | ARRAY OF ID            ()

tyfield : COMMA ID COLON ID     () (*{,id : type-id}*)

tyfields : (*epsilon*)              ()
     | ID COLON ID tyfield      ()

(*Variables*)
vardec : VAR ID ASSIGN exp              () (*var id := exp*)
       | VAR ID COLON ID ASSIGN exp     () (*var id:type-id := exp*)

(*Functions*)
fundec : FUNCTION ID LPAREN tyfields RPAREN EQ exp              ()
       | FUNCTION ID LPAREN tyfields RPAREN COLON ID EQ exp     ()

    (*lvalue with 'apparently redundant' production as in textbook*)
lvalue: ID  ()
      | lvalue DOT ID  ()
      | lvalue LBRACK exp RBRACK ()
      | ID LBRACK exp RBRACK ()


(*Expressions*)

        (*Some useful production shorthands*)
sequence : LPAREN exp_sequence RPAREN ()
exp_sequence : (*epsilon*) ()
         | exp seq     ()

seq : (*epsilon*)                () (*an exp sequence can be empty*)
    | SEMICOLON exp exp_sequence () (*exps separated by semicolon - to be used below*)


(* Productions for exp *)
exp : lvalue                () (*lval*)
    | sequence              () (*sequence of expressions*)
    | INT               () (*integer literal*)
    | STRING                () (*string literal *)
    | function_call         ()
    | arithmetic            ()
    | comparison            ()
    | boolean               ()
    | control_flow          ()
    | array             ()
    | assign                ()
    | record                ()
    | NIL               () (*nil - reserved keyword *)
    (*| LPAREN exp RPAREN           () paren*)

assign: lvalue ASSIGN exp           () (*assignment*)

comparison : exp EQ exp         ()
    | exp NEQ exp           ()
    | exp GT exp            ()
    | exp LT exp            ()
    | exp LE exp            ()
    | exp GE exp            ()

arithmetic : MINUS exp %prec UNARY  ()(* negation - highest precedence! *)
    | exp PLUS exp          ()
    | exp MINUS exp         ()
    | exp DIVIDE exp            ()
    | exp TIMES exp         ()

boolean : exp AND exp           ()
    | exp OR exp            ()


function_call : ID LPAREN fun_args RPAREN       ()
(* Helper production for function arguments.
 * Function arguments can be empty,
 * or of the form (exp{, exp}
*)
fun_args: (*epsilon*) ()
    | exp args    ()
(*production for args -> {,exp}*)
args : (*empty*)      ()
     | COMMA exp args ()


control_flow : IF exp THEN exp ELSE exp     () (*if-then-else*)
    | IF exp THEN exp %prec NO_ELSE     () (*if-then*)
    | WHILE exp DO exp          () (*while*)
    | FOR ID ASSIGN exp TO exp DO exp   ()(*for*)
    | BREAK                 () (*break*)
    | LET decs IN sequence END  () (*let-in-end*)

record : ID LBRACE rec_node rec_tail RBRACE     () (*record creation*)

(* Helper production for record creation:
 * type-id {id=exp{, id=exp}}
 *
 *)
rec_node : ID EQ exp  ()
rec_tail   : (*empty*) ()
       | COMMA rec_node rec_tail ()

array : ID LBRACK exp RBRACK OF exp () (*array creation*)