-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathCPar.fsy
244 lines (207 loc) · 9.23 KB
/
CPar.fsy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
%{
(* File MicroC/CPar.fsy
Parser specification for micro-C, a small imperative language
[email protected] * 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 码
%}
%token <int> CSTINT CSTBOOL // <int> 是词元的语义值类型
%token <string> CSTSTRING NAME
%token CHAR ELSE IF INT NULL PRINT PRINTLN RETURN VOID WHILE FOR DOWHILE DO UNTIL DOUNTIL HEXCHANGE SWITCH CASE DEFAULT BREAK CONTINUE
%token BOOL PLUS MINUS TIMES DIV MOD INC SUB PLUSASSIGN MINUSASSIGN TIMESASSIGN DIVASSIGN MODASSIGN
%token EQ NE GT LT GE LE
%token NOT SEQOR SEQAND
%token LPAR RPAR LBRACE RBRACE LBRACK RBRACK SEMI COMMA ASSIGN AMP COLON QUE
%token EOF
%right ASSIGN /* lowest precedence */ // 最下面的优先级最高
%nonassoc PRINT
%right COLON QUE
%left SEQOR
%left SEQAND
%left EQ NE
%nonassoc GT LT GE LE
%left PLUS MINUS PLUSASSIGN MINUSASSIGN TIMESASSIGN DIVASSIGN MODASSIGN
%left TIMES DIV MOD
%nonassoc NOT AMP
%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) }
| 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) }
;
/*
变量描述
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 }
;
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 }
| 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) }
| DO StmtM UNTIL LPAR Expr RPAR SEMI { DoUntil($2, $5) }
| FOR LPAR Expr SEMI Expr SEMI Expr RPAR StmtM { For($3, $5, $7, $9)}
| SWITCH LPAR Expr RPAR LBRACE CaseList RBRACE { Switch($3,$6) }
| BREAK SEMI { Break }
| CONTINUE SEMI { Continue }
;
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 } //取$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 PLUS Expr { Prim2("+", $1, $3) }
| Expr MINUS Expr { Prim2("-", $1, $3) }
| Expr TIMES Expr { Prim2("*", $1, $3) }
| INC Access { Inc($2) }
| Access INC { Inc($1) }
| SUB Access { Sub($2) }
| Access SUB { Sub($1) }
| Access PLUSASSIGN Expr { Self($1,"+",$3) }
| Access MINUSASSIGN Expr { Self($1,"-",$3) }
| Access TIMESASSIGN Expr { Self($1,"*",$3) }
| Access DIVASSIGN Expr { Self($1,"/",$3) }
| Access MODASSIGN Expr { Self($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 QUE Expr COLON Expr { Prim3($1,$3,$5) }
| Expr SEQAND Expr { Andalso($1, $3) }
| Expr SEQOR Expr { Orelse($1, $3) }
| HEXCHANGE LPAR CSTSTRING COMMA CSTINT RPAR {HexChange($3,$5) }
;
AtExprNotAccess:
//不可以为左值的的基本情况
// Const , 3
// AMP Access , &x
// (3)
Const { CstI $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 }
;
CaseList:
{ [] }
| CaseDec { [$1] }
| CaseDec CaseList { $1 :: $2 }
| DEFAULT COLON StmtM { [Default($3)] }
CaseDec:
CASE Expr COLON Stmt { Case($2,$4) }
Const:
CSTINT { $1 }
| CSTBOOL { $1 }
| MINUS CSTINT { - $2 }
| NULL { -1 }
;
Type:
INT { TypI }
| CHAR { TypC }
| BOOL { TypB }
;