Micro C Parser

%{
(*  File MicroC/CPar.fsy
    Parser specification for micro-C, a small imperative language
    sestoft@itu.dk * 2009-09-29
    No (real) shift/reduce conflicts thanks to Niels Kokholm.
*)

open Absyn

let compose1 f (g, s) = ((fun x -> g(f(x))), s)
let nl = CstI 10
%}

%token <int> CSTINT CSTBOOL
%token <string> CSTSTRING NAME

%token CHAR FOR ELSE IF INT NULL PRINT PRINTLN RETURN VOID WHILE
%token PLUS MINUS TIMES DIV MOD
%token EQ NE GT LT GE LE
%token NOT SEQOR SEQAND
%token LPAR RPAR LBRACE RBRACE LBRACK RBRACK SEMI COMMA ASSIGN AMP
%token EOF

%right ASSIGN             /* lowest precedence */
%nonassoc PRINT
%left SEQOR
%left SEQAND
%left EQ NE
%nonassoc GT LT GE LE
%left PLUS MINUS
%left TIMES DIV MOD
%nonassoc NOT AMP
%nonassoc LBRACK          /* highest precedence  */

%start Main
%type <Absyn.program> Main

%%

Main:
    Topdecs EOF                         { Prog $1 }
;

Topdecs:
    /* empty */                         { [] }
  | Topdec Topdecs                      { $1 :: $2 }
;

Topdec:
    Vardec SEMI                         { Vardec (fst $1, snd $1) }
  | Fundec                              { $1 }
;

Vardec:
    Type Vardesc                        { ((fst $2) $1, snd $2) }
;

Vardesc:
    NAME                                { ((fun t -> t), $1)                      }
  | TIMES Vardesc                       { compose1 TypP $2                        }
  | LPAR Vardesc RPAR                   { $2                                      }
  | Vardesc LBRACK RBRACK               { compose1 (fun t -> TypA(t, None)) $1    }
  | Vardesc LBRACK CSTINT RBRACK        { compose1 (fun t -> TypA(t, Some $3)) $1 }
;

Fundec:
    VOID NAME LPAR Paramdecs RPAR Block { Fundec(None,     $2, $4, $6) }
  | Type NAME LPAR Paramdecs RPAR Block { Fundec(Some($1), $2, $4, $6) }
;

Paramdecs:
    /* empty */                         { [] }
  | Paramdecs1                          { $1 }
;

Paramdecs1:
    Vardec                              { [$1]     }
  | Vardec COMMA Paramdecs1             { $1 :: $3 }
;

Block:
    LBRACE StmtOrDecSeq RBRACE          { Block $2 }
;

StmtOrDecSeq:
    /* empty */                         { [] }
  | Stmt StmtOrDecSeq                   { Stmt $1 :: $2 }
  | Vardec SEMI StmtOrDecSeq            { Dec (fst $1, snd $1) :: $3 }
;

Stmt:
    StmtM                               { $1 }
  | StmtU                               { $1 }
;

StmtM:  /* No unbalanced if-else */
    Expr SEMI                           { Expr($1)             }
  | RETURN SEMI                         { Return None          }
  | RETURN Expr SEMI                    { Return(Some($2))     }
  | Block                               { $1                   }
  | FOR LPAR Expr SEMI Expr SEMI Expr RPAR StmtU {Block[Stmt(Expr($3)); While($5, Block[Stmt($9); Stmt(Expr($7))])]}
  | IF LPAR Expr RPAR StmtM ELSE StmtM  { If($3, $5, $7)       }
  | WHILE LPAR Expr RPAR StmtM          { While($3, $5)        }
;

StmtU:
    IF LPAR Expr RPAR StmtM ELSE StmtU  { If($3, $5, $7)       }
  | IF LPAR Expr RPAR Stmt              { If($3, $5, Block []) }
  | WHILE LPAR Expr RPAR StmtU          { While($3, $5)        }
;

Expr:
    Access                              { Access $1           }
  | ExprNotAccess                       { $1                  }
;

ExprNotAccess:
    AtExprNotAccess                     { $1                  }
  | Access ASSIGN Expr                  { Assign($1, $3)      }
  | NAME LPAR Exprs RPAR                { Call($1, $3)        }
  | NOT Expr                            { Prim1("!", $2)      }
  | PRINT Expr                          { Prim1("printi", $2) }
  | PRINTLN                             { Prim1("printc", nl) }
  | Expr PLUS  Expr                     { Prim2("+",  $1, $3) }
  | Expr MINUS Expr                     { Prim2("-",  $1, $3) }
  | Expr TIMES Expr                     { Prim2("*",  $1, $3) }
  | Expr DIV   Expr                     { Prim2("/",  $1, $3) }
  | Expr MOD   Expr                     { Prim2("%",  $1, $3) }
  | Expr EQ    Expr                     { Prim2("==", $1, $3) }
  | Expr NE    Expr                     { Prim2("!=", $1, $3) }
  | Expr GT    Expr                     { Prim2(">",  $1, $3) }
  | Expr LT    Expr                     { Prim2("<",  $1, $3) }
  | Expr GE    Expr                     { Prim2(">=", $1, $3) }
  | Expr LE    Expr                     { Prim2("<=", $1, $3) }
  | Expr SEQAND Expr                    { Andalso($1, $3)     }
  | Expr SEQOR  Expr                    { Orelse($1, $3)      }
;

AtExprNotAccess:
    Const                               { CstI $1             }
  | LPAR ExprNotAccess RPAR             { $2                  }
  | AMP Access                          { Addr $2             }
;

Access:
    NAME                                { AccVar $1           }
  | LPAR Access RPAR                    { $2                  }
  | TIMES Access                        { AccDeref (Access $2)}
  | TIMES AtExprNotAccess               { AccDeref $2         }
  | Access LBRACK Expr RBRACK           { AccIndex($1, $3)    }
;

Exprs:
    /* empty */                         { []       }
  | Exprs1                              { $1       }
;

Exprs1:
    Expr                                { [$1]     }
  | Expr COMMA Exprs1                   { $1 :: $3 }
;

Const:
    CSTINT                              { $1       }
  | CSTBOOL                             { $1       }
  | MINUS CSTINT                        { - $2     }
  | NULL                                { -1       }
;

Type:
    INT                                 { TypI     }
  | CHAR                                { TypC     }
;