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      //Absyn包 包含抽象语法树的结点

// Vardesc 返回的是一个 元组(g,s)
  // g是类型构造函数，s是变量名
// compose1函数：取出 类型构造子g，用 类型复合机制 构造类型。
// 该文件中的$1表示第一个位置的元素，以此类推，$3表示第三个位置的元素
  // fun x -> g(f(x)) 表示：函数x，它返回的内容是g(f(x))
//  compose1函数是 类型分步构造 的关键

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

let first (x, _, _) = x //取第一个元素
let second (_, y, _) = y //取第二个元素
let third (_, _, z) = z //取第三个元素
%}

//下面这一段是定义段

//%token是词元说明符
%token <int> CSTINT CSTBOOL           // <int> 是词元的语义值类型，布尔类型的值是0 1，故用int类型表示
%token <string> CSTSTRING NAME        // CSTSTRING、NAME都是string类型
%token <char> CSTCHAR
%token <float32> CSTFLOAT
%token MAX MIN

%token FLOAT BOOL BITAND BITOR BITXOR BITNOT CHAR ELSE IF INT NULL PRINT PRINTLN RETURN VOID WHILE FOR IN DO RANGE UNTIL SWITCH CASE BREAK
%token PLUS MINUS TIMES DIV MOD       //加 减 乘 除 取余
%token PLUSASSIGN MINUSASSIGN TIMESASSIGN DIVASSIGN MODASSIGN //复合赋值运算符+= -= *= /= %=
%token BITLEFT BITRIGHT //左移右移
%token SELFINC SELFDEC           //自增 自减
%token EQ NE GT LT GE LE          //相等 不相等 大于 小于 大于等于 小于等于
%token NOT SEQOR SEQAND       //! || &&
%token LPAR RPAR LBRACE RBRACE LBRACK RBRACK SEMI COMMA ASSIGN AMP QUESMARK COLON //QUESMARK是问号 COLON是冒号 SEMI是分号
%token EOF

%right ASSIGN             /* 最低优先级 */  // 最下面的优先级最高
%nonassoc PRINT PRINTLN           //打印
%right MINUSASSIGN PLUSASSIGN MODASSIGN TIMESASSIGN DIVASSIGN //复合赋值运算符-= += %= *= /=
%right QUESMARK COLON     //问号 冒号
%left SEQOR               //逻辑或||
%left SEQAND              //逻辑与&&
%left BITXOR BITOR BITAND
%left EQ NE               //== !=
%nonassoc GT LT GE LE     //大于 小于 大于等于 小于等于
%left BITLEFT BITRIGHT
%left PLUS MINUS          //加 减
%left TIMES DIV MOD       //乘 除 取余
%nonassoc NOT AMP SELFINC SELFDEC BITNOT         //!取反 &取地址 自增 自减
%nonassoc LBRACK          /* 最高优先级  */  //左括号

%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) }  // 变量声明。SEMI是分号  fst表示第一个，snd表示第二个
  | Fundec                              { $1 }                       // 函数声明
  | VardecAndAssign SEMI                { VardecAndAssign (first $1,second $1,third $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")        这里Some 10表示值为10，但可以为空
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是左圆括号，RPAR是右圆括号
  | LPAR Vardesc RPAR                   { $2                                      } 
    // ia[]   带方括号，无下标
    // None表示不指定元素个数
    // TypA 数组类型构造子
  | Vardesc LBRACK RBRACK               { compose1 (fun t -> TypA(t, None)) $1    }
    // ia[10]   带方括号，带下标
    // Some $3表示指定元素个数为第三个位置的元素，即CSTINT
    // TypA 数组类型构造子
  | Vardesc LBRACK CSTINT RBRACK        { compose1 (fun t -> TypA(t, Some $3)) $1 }
;

// 函数声明
Fundec:
    // 返回 void 的函数
    // void fun ( 参数列表 ) { 语句块 }
    VOID NAME LPAR Paramdecs RPAR Block { Fundec(None,     $2, $4, $6) }
    // 返回 Type 类型的函数
    // int fun ( 参数列表 ) { 语句块 }
  | 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:                 //最后的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 } //局部变量初始化
                                        //first second third是从第一个位置上的VardecAndAssign取出元素
;

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

StmtM:  /* No unbalanced if-else 数量不匹配的if-else */
    Expr SEMI                           { Expr($1)             }         //表达式
  | RETURN SEMI                         { Return None          }         //返回 空
  | RETURN Expr SEMI                    { Return(Some($2))     }         //返回 表达式
  | Block                               { $1                   }         //语句块
  | IF LPAR Expr RPAR StmtM ELSE StmtM  { If($3, $5, $7)       }         //if语句【包括if-else和if-elseif】
  | WHILE LPAR Expr RPAR StmtM          { While($3, $5)        }         //while循环
  | FOR LPAR Expr SEMI Expr SEMI Expr RPAR StmtM { For($3, $5, $7, $9) } //for循环
//  | FOR LPAR StmtM Expr SEMI Expr RPAR StmtM { ForPrimary($3, $4, $6, $8) } //通常的for循环
  | FOR LPAR Access IN RANGE LPAR Expr COMMA Expr COMMA Expr RPAR RPAR StmtM   { ForInExpr($3, $7, $9, $11, $14) }    //forinrange函数
  | IF LPAR Expr RPAR StmtM             { IfWithoutElse($3, $5)}         //if语句【不带else】
  | DO StmtM WHILE LPAR Expr RPAR SEMI     { DoWhile($2, $5)      }         //dowhile循环
  | DO StmtM UNTIL LPAR Expr RPAR SEMI     { DoUntil($2, $5)      }         //dountil循环
  | SWITCH LPAR Expr RPAR LBRACE CaseStmts RBRACE { Switch($3, $6) }        //switch
  | BREAK SEMI                                          { Break                }
;

//case语句
CaseStmts:
    CASE AtExprNotAccess COLON StmtM       { [Case($2, $4)]       }         //单个case语句
  | CASE AtExprNotAccess COLON StmtM CaseStmts  { [Case($2, $4)] @ $5  }    //多个case语句
;

StmtU:
    IF LPAR Expr RPAR StmtM ELSE StmtU  { If($3, $5, $7)       }     //if语句【包括if-else和if-elseif】
  | IF LPAR Expr RPAR Stmt              { If($3, $5, Block []) }     //if语句【不带else】
  | WHILE LPAR Expr RPAR StmtU          { While($3, $5)        }     //while循环
;

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) } // 打印换行
  | SELFINC Access                      { PreInc $2       }     // 前置自增++a
  | SELFDEC Access                      { PreDec $2       }     // 前置自减--a
  | Access SELFINC                      { NextInc $1      }     // 后置自增a++
  | Access SELFDEC                      { NextDec $1      }     // 后置自减a--
  | 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 BITLEFT  Expr                  { Prim2("<<", $1, $3) }
  | Expr BITRIGHT  Expr                 { Prim2(">>", $1, $3) }
  | Expr AMP Expr                       { Prim2("&", $1, $3)      }
  | Expr BITOR  Expr                    { Prim2("|", $1, $3) }
  | Expr BITXOR  Expr                   { Prim2("^", $1, $3) }
  | BITNOT  Expr                        { Prim1("~", $2) }
  | Access PLUSASSIGN Expr              { Prim3("+=", $1, $3) } // 表达式+=表达式 $1为左值
  | Access MINUSASSIGN Expr             { Prim3("-=", $1, $3) } // 表达式-=表达式 $1为左值
  | Access TIMESASSIGN Expr             { Prim3("*=", $1, $3) } // 表达式*=表达式 $1为左值
  | Access DIVASSIGN Expr               { Prim3("/=", $1, $3) } // 表达式/=表达式 $1为左值
  | Access MODASSIGN Expr               { Prim3("%=", $1, $3) } // 表达式%=表达式 $1为左值
  | PRINT LPAR CSTSTRING COMMA Expr RPAR{ Print($3, $5)       }
  | PRINTLN LPAR  Access RPAR           { Println($3)         }
  | Expr SEQAND Expr                    { Andalso($1, $3)     } // 表达式&&表达式
  | Expr SEQOR  Expr                    { Orelse($1, $3)      } // 表达式||表达式
  | Expr QUESMARK Expr COLON Expr       { TernaryOperator($1, $3, $5)} //三目运算符
  | MAX LPAR Expr COMMA Expr RPAR       { Max($3, $5)         }
  | MIN LPAR Expr COMMA Expr RPAR       { Min($3, $5)         }
;

AtExprNotAccess:
    //不可以为左值的的基本情况，如：
    // Const ,  3
    // (3)
    // AMP Access  , &x
    Const                               { CstI $1             } // 常量
  | ConstChar                           { CstC $1 }
  | ConstFloat                          { CstF $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         } // 指针 不可以为左值的基本情况   如*&x
  | Access LBRACK Expr RBRACK           { AccIndex($1, $3)    } // 左值(表达式)     这个是递归调用
;

Exprs:   //多个表达式
    /* empty */                         { []       }
  | Exprs1                              { $1       }
;

Exprs1:
    Expr                                { [$1]     }  //表达式
  | Expr COMMA Exprs1                   { $1 :: $3 }  //表达式添加到多个表达式中  COMMA是逗号
;

Const:  //常量
    CSTINT                              { $1       }  //int类型常量
  | CSTBOOL                             { $1       }  //布尔类型常量
  | MINUS CSTINT                        { - $2     }  //负数常量
  | NULL                                { -1       }  //null
;

ConstChar:
    CSTCHAR                             { $1       }
;

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

Type:  //变量
    INT                                 { TypI     }  //int类型
  | CHAR                                { TypC     }  //char类型
  | FLOAT                               { TypF     }
  | BOOL                                 { TypB }
;