CPar.fsy

%{
(*	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

// Vardesc 返回的是一个 元组 (g,s)
// g是类型构造函数，s是变量名
// compose1 函数 取出 类型构造子 g，用类型复合机制构造类型。

let compose1 f (g, s) = ((fun x -> g(f(x))), s)
let nl = CstI 10 //  \n 的 ASCII 码

let first  (a, _, _) = a
let second (_, b, _) = b
let third  (_, _, c) = c
%}

%token <int> CSTINT CSTBOOL  // <int> 是词元的语义值类型
%token <float32> CSTFLOAT
%token <string> CSTSTRING NAME
%token <char> CSTCHAR

%token INT FLOAT CHAR ELSE IF NULL PRINT PRINTLN RETURN VOID WHILE FOR DO SWITCH CASE
%token PLUS MINUS TIMES DIV MOD SELFPLUS SELFMINUS
%token EQ NE GT LT GE LE
%token NOT SEQOR SEQAND
%token LPAR RPAR LBRACE RBRACE LBRACK RBRACK SEMI COMMA ASSIGN AMP COLON QUEST BREAK CONTINUE
%token EOF

%right ASSIGN             /* lowest precedence */  // 最下面的优先级最高
%nonassoc PRINT
%right QUEST COLON
%left SEQOR
%left SEQAND
%left EQ NE 
%nonassoc GT LT GE LE
%left PLUS MINUS
%left TIMES DIV MOD 
%right NOT AMP SELFPLUS SELFMINUS
%nonassoc LBRACK          /* highest precedence  */

%start Main            // 语法开始符号
%type <Absyn.program> Main   // 开始符号，对应抽象语法树节点类型, program

%%

Main:
    Topdecs EOF                         { Prog $1 }  // { }内是合法的F#代码
                                        // $1 是 Topdecs的语义值， Prog $1 返回抽象语法树根节点，也就是整个程序
;                                       // 规则结束符

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

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

/*                                               
变量声明  由于C 类型声明的复杂性，这里用了函数式编程的技巧来辅助类型构造

利用变量描述中的构造函数，构造类型
 { ((fst $2) $1, snd $2) }

int i;  // int  (TypI, "i")            fst (fun t->t , "i") TypI , snd (fun t->t , "i") 
int *p;   // pointer to int   (TypP TypI, "p")
int ia[10];  // array of 10 ints   (TypA (TypI, Some 10), "ia")
int* ia2;  // pointer to int   (TypP TypI, "ia2")
int *ipa[10];  // array of 10 pointers to int   (TypA (TypP TypI, Some 10), "ipa")
int (*iap)[10];  // pointer to array of 10 int    (TypP (TypA (TypI, Some 10))
*/

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

VardecAndAssign:
    Type Vardesc ASSIGN Expr    { ((fst $2) $1, snd $2 , $4) }
;

/*
 变量描述
NAME  "n"   (fun t->t, "n") 返回一个元组，第一个元素，是类型构造函数，在Vardec 规则中使用
*/ 

// 变量描述
Vardesc:                         
    // "i"    标识符                        fun t->t  id 函数
    NAME                                { ((fun t -> t), $1)                      }
    // "*p"   指针标识符
    // let compose1 f (g, s) = ((fun x -> g(f(x))), s)
    //      compose1  (fun t -> TypP t) $2 ===  compose1 TypP $2 
    //       TypP 指针类型构造子 
  | TIMES Vardesc                       { compose1 TypP $2                        }  
    // (*p)   带括号的标识符                                 
  | LPAR Vardesc RPAR                   { $2                                      } 
    // ia[]   带方括号，无下标
  | Vardesc LBRACK RBRACK               { compose1 (fun t -> TypA(t, None)) $1    }
    // ia[10]   带方括号，带下标
  | Vardesc LBRACK CSTINT RBRACK        { compose1 (fun t -> TypA(t, Some $3)) $1 }
;

Fundec:
    // 返回 void 的函数
    VOID NAME LPAR Paramdecs RPAR Block { Fundec(None,     $2, $4, $6) }
    // 返回 Type 类型的函数
  | 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 }
  | VardecAndAssign SEMI StmtOrDecSeq   { DecAndAssign ( first $1, second $1, third $1)::$3 }
;

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

StmtM:  /* No unbalanced if-else */
    Expr SEMI                           { Expr($1)             }
  | RETURN SEMI                         { Return None          }
  | BREAK SEMI                          { Break                }
  | CONTINUE SEMI                       { Continue             }
  | RETURN Expr SEMI                    { Return(Some($2))     }
  | Block                               { $1                   }
  | FOR LPAR Expr SEMI Expr SEMI Expr RPAR StmtM { For($3,$5,$7,$9) }
  | IF LPAR Expr RPAR StmtM ELSE StmtM  { If($3, $5, $7)       }
  | WHILE LPAR Expr RPAR StmtM          { While($3, $5)        }
  | DO StmtM WHILE LPAR Expr RPAR SEMI  { DoWhile($2, $5)      }
  | SWITCH LPAR Expr RPAR LBRACE StmtCase RBRACE { Switch($3,$6)  }
;

StmtCase:
    CASE AtExprNotAccess COLON StmtM               { [Case($2,$4)]    }  
  | CASE AtExprNotAccess COLON StmtM StmtCase      { Case($2,$4)::$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)        }
  | DO StmtM WHILE LPAR Expr RPAR SEMI  { DoWhile($2, $5)      }
;

Expr: 
    Access                              { Access $1           } //取$1的右值
  | ExprNotAccess                       { $1                  } 
;
  //非左值的情况
ExprNotAccess:
    AtExprNotAccess                     { $1                  }
  | Access ASSIGN Expr                  { Assign($1, $3)      } // $1为左值
  | NAME LPAR Exprs RPAR                { Call($1, $3)        }  
  | NOT Expr                            { Prim1("!", $2)      }
  | PRINT Expr                          { Prim1("printi", $2) }
  | PRINTLN                             { Prim1("printc", nl) }
  | Expr SELFPLUS                       { Prim1("I++", $1)    }
  | Expr SELFMINUS                      { Prim1("I--", $1)    }
  | SELFPLUS Expr                       { Prim1("++I", $2)    }
  | SELFMINUS Expr                      { Prim1("--I", $2)    }
  | 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 QUEST Expr COLON Expr          { Prim3($1, $3, $5)   }
  | Expr SEQAND Expr                    { Andalso($1, $3)     }
  | Expr SEQOR  Expr                    { Orelse($1, $3)      }
;

AtExprNotAccess:
    //不可以为左值的的基本情况 
    // Const ,  3
    // AMP Access  , &x
    // (3)   
    Const                               { CstI $1             }
  | ConstFloat                          { CstF($1)            }
  | ConstChar                           { CstC($1)            }
  | LPAR ExprNotAccess RPAR             { $2                  } 
  | AMP Access                          { Addr $2             } // 取地址
;

Access:    //可以为左值的情况
    NAME                                { AccVar $1           }  // 变量 x
  | LPAR Access RPAR                    { $2                  }  // 括号中的变量 (x)
  | TIMES Access                        { AccDeref (Access $2)}  // 指针  *x 
  | 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       }
;

ConstFloat:
    CSTFLOAT                            { $1       }
  | MINUS CSTFLOAT                      { - $2     }
;

ConstChar:
  CSTCHAR                               { $1       }
;

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