%{
(* 補助的な変数、関数、型などの定義 *)
let make_fun vars expr =
  List.fold_right (fun v e -> Syntax.Fun (v, e)) vars expr
%}
/* 以降、どういうわけかコメントが C 式になることに注意 */
/* トークンの定義 */
%token LPAREN RPAREN
%token <int> NUMBER
%token <string> VAR
%token PLUS MINUS TIMES DIVIDE
%token FUN ARROW
%token CONTROL PROMPT
%token EOF
/* End of File: 入力の終わりを示す */

/* 非終端記号の型をここで宣言する */
%type <Syntax.e> expr

/* 開始記号の定義 */
%start expr

/* 演算子の優先順位を指定する */
/* 下に行くほど強く結合する */
%nonassoc ARROW
%left PLUS MINUS
%left TIMES DIVIDE
/* nonassoc は結合なし（毎回、かっこを書かなくてはならない）、
   left は左結合、right は右結合 */

/* 以下の %% は省略不可。それ以降に文法規則を書く */
%%

simple_expr:
| NUMBER
{ Syntax.Num ($1) }
| VAR
{ Syntax.Var ($1) }
| LPAREN expr RPAREN
{ $2 }

expr:
| simple_expr
{ $1 }
| expr PLUS expr
        { Syntax.Op ($1, Syntax.Plus, $3) }
| expr MINUS expr
        { Syntax.Op ($1, Syntax.Minus, $3) }
| expr TIMES expr
        { Syntax.Op ($1, Syntax.Times, $3) }
| expr DIVIDE expr
        { Syntax.Op ($1, Syntax.Divide, $3) }
| FUN VAR vars ARROW expr
{ Syntax.Fun ($2, make_fun $3 $5) }
| app
{ $1 }
| CONTROL VAR ARROW expr
{ Syntax.Control ($2, $4) }
| PROMPT simple_expr
{ Syntax.Prompt ($2) }

vars:
|
  { [] }
| VAR vars
{ $1 :: $2 }

app:
| simple_expr simple_expr
{ Syntax.App ($1, $2) }
| app simple_expr
{ Syntax.App ($1, $2) }