Pwn进你的心
0%

CMPT379编译器Lab3：decafexpr

Posted on In 57k 51 mins.

decafexpr

本作业的目标是为变量编写一个代码生成器，用于处理 Decaf 编程语言的简单表达式和方法

输出将在 LLVM 程序集中，该程序集被编译为x86程序集，然后使用 LLVM 工具 llvm-run 编译为二进制文件（工具 llvm-run 一定要有执行权限）

第一步是为编译器编写符号表，Decaf 的结构和代码生成提示在 Decaf 规范中给出：Decaf Programming Language Specification

在开始此实验之前，建议先完成 LLVM 的练习：SFU Compilers class: LLVM Practice (anoopsarkar.github.io) （这里介绍了一些 llvm api 的使用方式）

实验描述

本实验有两个步骤：

  • 实现可以跟踪变量和方法的符号表
  • 表达式的代码生成

符号表是从标识符到任何信息的映射，需要编译器自动生成

符号表很容易用哈希表或映射实现，例如：cpp stl 的符号表的声明

1
typedef map<string, descriptor* > symbol_table;

其中描述符是包含有用信息的结构或类

在 Decaf 中允许隐藏一个变量声明（在作用域内声明一个变量，但在实际使用之前不对其进行初始化或赋值），这意味着块中标识符的新定义将导致新的描述符与标识符相关联，但一旦块终止必须恢复标识符的先前描述符

实现此本地作用域概念的一种简单方法是指定每个块可以在列表中创建新的符号表：

1
2
typedef list<symbol_table > symbol_table_list;
symbol_table_list symtbl;

如果一个变量的局部定义隐藏了同一变量名称的另一个定义，我们只需扫描从最近的一个开始的符号表列表，就可以获取该变量最近定义的描述符：

1
2
3
4
5
6
7
8
9
descriptor* access_symtbl(string ident) {
    for (auto i : symtbl) {
        auto find_ident = i.find(ident);
        if (find_ident != i.end()) {
            return find_ident->second;
        }
    }
    return NULL;
}

为以下 Decaf 片段提供代码生成器，其中包括：

  • 算术和布尔表达式
  • 函数调用
  • 函数定义（包括递归函数）
  • 外部函数的声明（所有外部函数都在 decaf-stdlib.c 中定义）

LLVM 程序集和工具链输出将转储到目录 llvm 中，应检查输出以调试编译器，请务必遵守以下要求：

  • 如果程序成功解析输入 exit(EXIT_SUCCESS)，则应使用 退出程序
  • 如果您的程序在输入的无咖啡因程序中发现错误，则应使用 exit(EXIT_FAILURE)
  • 您必须通过调用 TheModule->print(errs(),nullptr) 来转储 LLVM 程序集，其中模块的类型为 llvm::Module*

可以使用如下命令对程序进行打分：

1
2
python3 zipout.py -r decafexpr
python3 check.py

实验步骤

首先需要把上一个实验的 decafast.y decafast.lex decafast.cc 放入本实验的 answer 目录，然后修改文件名称：

1
2
3
mv decafast.lex decafexpr.lex
mv decafast.y decafexpr.y  
mv decafast.cc decafexpr.cc
  • 修改 decafexpr.lex decafexpr.y decafexpr.cc 中的头文件引用
  • 将 default.y 中有关 LLVM 的代码拷贝到 decafexpr.y 中
  • 将 default.cc 中有关 LLVM 的代码拷贝到 decafexpr.cc 中

本实验的目标就是将 decaf 代码转化为 llvm ir 代码，并且需要判断程序的语义是否错误，然后用 llvm 工具将 llvm ir 转化为二进制文件

先看一个简单的样例：对于类型提升的处理

1
2
3
4
5
6
7
8
9
10
11
extern func print_int(int) void;
package Test {
    func main() int
    {
        var x int;
        print_int(true && true);
        print_int(true && false);
        print_int(false && true);
        print_int(false && false);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
; ModuleID = 'Test'
source_filename = "DecafExpr"

declare void @print_int(i32)

define i32 @main() {
entry:
  %x = alloca i32
  call void @print_int(i32 1)
  call void @print_int(i32 0)
  call void @print_int(i32 0)
  call void @print_int(i32 0)
  ret i32 0
}
  • 这里的实际传参类型和该函数定义的传参类型不同

编译修改好的实验初始文件，尝试将该样例作为输入，输出的结果如下：

1
2
3
4
5
6
7
; ModuleID = 'Test'
source_filename = "Test"

define i32 @main() {
entry:
  ret i32 0
}

现在的目标就是用 llvm api 去识别 decaf 的语法分析树，将其转化为 llvm ir

核心步骤就是在上一个实验的基础上进行修改，在合适的位置为其添加 llvm api，并在上一个实验的类中添加对应的 llvm 类指针和 Codegen 函数

  • 本实验采用从下往上分析法，和 llvm api 需要的执行顺序不同
  • 因此只能把 llvm 相关操作写入 Codegen，当从下往上的分析结束时，就从上往下调用 Codegen 来构建 llvm ir

接下来的实验目标就是为各个类补充 llvm api 指针和 Codegen 函数，我会依照几个实验案例来展示一些我认为比较棘手的问题（包括遇到的问题和解决思路）

首先是上述案例，需要解决的问题就是对传参类型不同的处理：

  • 一开始我打算直接修改 true 的类型，但后来发现直接修改类型会对后续 true 的使用产生影响（具体而言是影响了 llvm::Value）
  • 然后选择将函数参数的 llvm::Value 提取出来，根据函数定义所规定的传参类型新定义一个 llvm::Value，并使用该 llvm::Value 调用 CreateCall
  • 最后在查看实验文档时发现了零扩展函数 CreateZExt
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
llvm::Value * decafFunCall::Codegen() { 
    descriptor * des = get_symbol(this->get_name());
    llvm::Function * llvm_func = des->func;
    std::vector<llvm::Value *> putsargs;
    std::vector<llvm::Type *> putstypes;

    for (auto& arg : llvm_func->args()) {
        llvm::Type* func_type = arg.getType();
        putstypes.push_back(func_type);
    }
    int i = 0;
    for(auto p:this->get_para()){
        decafBinexp * exp = (decafBinexp *)p;
        llvm::Value* vt = exp->Codegen();
        llvm::Type* func_type = putstypes[i++];
      
        vt = Builder.CreateZExt(vt, func_type, "zexttmp");
        /*
        if(exp->get_kind() != "VariableExpr"){
            llvm::ConstantInt* constantInt = llvm::dyn_cast<llvm::ConstantInt>(vt);
            if (constantInt) {
                llvm::APInt apIntValue = constantInt->getValue();
                int intValue = apIntValue.getZExtValue();
                vt = llvm::ConstantInt::get(func_type, intValue);
            }
        } 
        */

        putsargs.push_back(vt);
    }

    llvm::Value *ret_value = Builder.CreateCall(llvm_func, putsargs);
    return ret_value;
}
  • PS：对返回类型的处理同理

接着分析下一个样例：对于表达式的处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
extern func print_int(int) void;

package foo {
    func main() int {
        var flag bool;
        var a, b, c bool;
        var size int;
        a = true;
        b = false;
        c = true;
        flag = a || b && !c;
        size = 1 >> 3 + 1 / -2 % 10 - 5 * 2 / 20 << 2;
        print_int(size);
    }
}
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
; ModuleID = 'foo'
source_filename = "DecafExpr"

declare void @print_int(i32)

define i32 @main() {
entry:
  %flag = alloca i1
  %a = alloca i1
  %b = alloca i1
  %c = alloca i1
  %size = alloca i32
  store i1 true, i1* %a
  store i1 false, i1* %b
  store i1 true, i1* %c
  %a1 = load i1, i1* %a
  %b2 = load i1, i1* %b
  %c3 = load i1, i1* %c
  %nottmp = xor i1 %c3, true
  %andtmp = and i1 %b2, %nottmp
  %ortmp = or i1 %a1, %andtmp
  store i1 %ortmp, i1* %flag
  store i32 0, i32* %size
  %size4 = load i32, i32* %size
  call void @print_int(i32 %size4)
  ret i32 0
}
  • 这个案例主要展示了如何处理表达式

其中最困难的地方就是区别：一元运算类，二元运算类，常量类，变量类

我的做法是令二元运算类 decafBinexp 继承常量/变量类 decafAllexp，然后将一元运算类 decafUnaryexp 当成特殊的 decafBinexp

最后在 decafBinexp::Codegen 中分情况讨论，对于不同的类进行不同的处理：

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
llvm::Value *decafBinexp::Codegen() {
    if(this->des.kind == valueK){
        decafAllexp * exp = (decafAllexp *)this; 
        return exp->Codegen();
    }
    else if(this->des.kind == expuK){
        llvm::Value *L = Exp1->Codegen();
        if (L == 0) {
            return 0;
        }
        switch (this->get_op(Option)) {
            case nottmp:
                this->des.value = Builder.CreateNot(L, "nottmp");
                break;     
            case negtmp:
                this->des.value = Builder.CreateNeg(L , "negtmp");
                break;
        }
        return this->des.value;
    }
    else if(this->des.kind == expbK){
        llvm::Value *L = Exp1->Codegen();
        llvm::Value *R = Exp2->Codegen();
        if (L == 0 || R == 0) {
            return 0;
        }

        switch (this->get_op(Option)) {
            case addtmp:
                this->des.value = Builder.CreateAdd(L, R, "addtmp"); 
                break;
            case subtmp:
                this->des.value = Builder.CreateSub(L, R, "subtmp");
                break;
            case multmp:
                this->des.value = Builder.CreateMul(L, R, "multmp");
                break;
            case remtmp:
                this->des.value = Builder.CreateSRem(L, R, "remtmp");
                break;
            case divtmp:
                this->des.value = Builder.CreateSDiv(L, R, "divtmp");
                break;
            case ortmp:
                this->des.value = Builder.CreateOr(L, R, "ortmp");
                break;
            case andtmp:
                this->des.value = Builder.CreateAnd(L, R, "andtmp");
                break;
            case eqtmp:
                this->des.value = Builder.CreateICmpEQ(L, R, "eqtmp");
                break;
            case netmp:
                this->des.value = Builder.CreateICmpNE(L, R, "netmp");
                break;
            case slttmp:
                this->des.value = Builder.CreateICmpSLT(L, R, "slttmp");
                break;    
            case sgttmp:
                this->des.value = Builder.CreateICmpSGT(L, R, "sgttmp");
                break;  
            case sletmp:
                this->des.value = Builder.CreateICmpSLE(L, R, "sletmp");
                break;    
            case sgetmp:
                this->des.value = Builder.CreateICmpSGE(L, R, "sgetmp");
                break;  
            case shltmp:
                this->des.value = Builder.CreateShl(L, R, "shltmp");
                break; 
            case shrtmp:
                this->des.value = Builder.CreateLShr(L, R, "shrtmp");
                break;                          
            default: 
                this->des.value = NULL;
                break;
        }
        return this->des.value;
    }
    else if(this->des.kind == funcK){
        decafFunCall * call = (decafFunCall *)this; 
        this->des.value = call->Codegen();
        return this->des.value;
    }
}
  • 其实就是把对 decafAllexp decafBinexp decafUnaryexp 的处理都整合到了 decafBinexp::Codegen 上
  • 最后一个函数调用的处理其实是特殊情况，我为了方便就直接把它放到这个地方了
  • 对于 “语句Stmt” 的处理也可以使用上述思路（本实验没有要求处理 “语句Stmt”）

参考以下案例：对于函数定义和函数调用的处理

1
2
3
4
5
6
7
8
9
10
11
extern func print_int(int) void;

package Test {
    func main() int {
        test(10, 13);
    }
    func test(a int, b int) void {
        print_int(a);
        print_int(b);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
; ModuleID = 'Test'
source_filename = "DecafExpr"

declare void @print_int(i32)

define i32 @main() {
entry:
  call void @test(i32 10, i32 13)
  ret i32 0
}

define void @test(i32 %a, i32 %b) {
entry:
  %a1 = alloca i32
  store i32 %a, i32* %a1
  %b2 = alloca i32
  store i32 %b, i32* %b2
  %a3 = load i32, i32* %a1
  call void @print_int(i32 %a3)
  %b4 = load i32, i32* %b2
  call void @print_int(i32 %b4)
  ret void
}
  • 这个案例有一个特点：在定义 test 前，先在 main 中调用了 test
  • 为了实现这个效果，我将 “函数定义” 的相关操作拆为两部分，分别放入 decafFuncDef::Codegen 和 method_decl 中
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
llvm::Value *decafFuncDef::Codegen() { 
    descriptor* des = get_symbol(this->get_name());
    if(check_symbol( this->get_name(), funcK)){
        get_return = true;

        llvm::BasicBlock *BB = llvm::BasicBlock::Create(TheContext, "entry", this->lfunc);
        Builder.SetInsertPoint(BB);

        int i = 0;
        for(auto p:this->get_para()->get_para()){
            this->lfunc->getArg(i)->setName(p->get_name());

            descriptor * des2 = new descriptor();
            if(put_symbol(p->get_name(),des2)){
                des2->alloc = Builder.CreateAlloca(p->lType, 0, p->get_name());
                des2->kind = valueK;
            }
            Builder.CreateStore(this->lfunc->getArg(i),des2->alloc);
            i++;
        }
        
        decafBlock * B = this->get_block();
        B->Codegen();

        if(get_return){
            if(this->lType->isVoidTy())
                Builder.CreateRetVoid();
            else
                Builder.CreateRet(llvm::ConstantInt::get(TheContext, llvm::APInt(32, 0)));
        }
    }
    return this->lfunc;
}
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
method_decl: T_FUNC T_ID T_LPAREN para_list_def T_RPAREN method_type block {
        decafFuncDef *func = new decafFuncDef();
        decafPara* para = (decafPara*)$4;
        decafBlock * block = (decafBlock*)$7;
        decafType * type = (decafType *)$6;
        func->put_name($2);
        func->put_type(type);
        func->put_para(para);
        func->put_block(block);
        $$ = func;
        delete $2;

        descriptor* des = new descriptor();
        if(put_symbol( func->get_name(), des)){
            llvm::Type *returnTy = func->lType;
            std::vector<llvm::Type *> functionArgs;
            for(auto p:func->get_para()->get_para()){
                functionArgs.push_back(p->lType);
            }

            func->lfunc = llvm::Function::Create(
                llvm::FunctionType::get(returnTy, functionArgs ,false),
                llvm::Function::ExternalLinkage, 
                func->get_name(), 
                TheModule);
            if (func->lfunc == 0) {
                throw runtime_error("empty function block"); 
            }

            des->func = func->lfunc;
            des->kind = funcK;
        }
    }
    ;

完整代码如下：

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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
%{
#include <iostream>
#include <ostream>
#include <string>
#include <cstdlib>
#include "default-defs.h"
#include "decafexpr.cc"

int yylex(void);
int yyerror(char *); 

// print AST?
bool printAST = false;

using namespace std;

// this global variable contains all the generated code
llvm::Module *TheModule;

typedef map<string, descriptor* > symbol_table;
typedef list<symbol_table > symbol_table_list;
symbol_table symtbl;
symbol_table_list symtblt;

// this is the method used to construct the LLVM intermediate code (IR)
llvm::LLVMContext TheContext;
llvm::LLVMContext &Context = TheContext;
llvm::IRBuilder<> Builder(TheContext);
// the calls to TheContext in the init above and in the
// following code ensures that we are incrementally generating
// instructions in the right order

// dummy main function
// WARNING: this is not how you should implement code generation
// for the main function!
// You should write the codegen for the main method as 
// part of the codegen for method declarations (MethodDecl)
static llvm::Function *TheFunction = 0;
static bool get_return;

descriptor *get_symbolt(string name){
    for(auto s:symtblt){
        map<string, descriptor* >::iterator it;
        for (it = s.begin(); it != s.end(); it++) {
            string s = it->first;
            if(name == s)
                return it->second;
        }
    }
    return NULL;
}

descriptor *get_symbol(string name){
    map<string, descriptor* >::iterator it;
    for (it = symtbl.begin(); it != symtbl.end(); it++) {
        string s = it->first;
        if(name == s)
            return it->second;
    }
    return NULL;
}

int put_symbolt(string name, descriptor * des){
    if(symtblt.front()[name] != NULL){
        return 0;
    }
    else{
        symtblt.front()[name] = des;
        return 1;
    }
}

int put_symbol(string name, descriptor * des){
    if(symtbl[name] != NULL){
        return 0;
    }
    else{
        symtbl[name] = des;
        return 1;
    }
}

bool check_symbol(string name, llvmValue k){
    map<string, descriptor* >::iterator it;
    for (it = symtbl.begin(); it != symtbl.end(); it++) {
        string s = it->first;
        if(name == s && it->second->kind == k){
            return true;
        }
    }
    return false;
}

llvm::Value * decafBlock::Codegen() { 
    symbol_table s;
    symtblt.push_front(s);
    llvm::Value *val = NULL;
    if (NULL != FieldDeclList) {
        val = FieldDeclList->Codegen();
    }
    if (NULL != StateDeclList) {
        val = StateDeclList->Codegen();
    } 
    symtblt.pop_front();
    return val; 
}

llvm::Value * decafStmt::Codegen() { 
    if(this->kind == dass){
        decafAssign* s = (decafAssign*)this;
        return s->Codegen();
    }
    else if(this->kind == dcall){
        decafFunCall* s = (decafFunCall*)this;
        return s->Codegen();
    }
    else if(this->kind == dblo){
        decafBlock* s = (decafBlock*)this;
        return s->Codegen();
    }
    else if(this->kind == dret){
        decafReturn* s = (decafReturn*)this;
        return s->Codegen();
    }
    else{
        return NULL;
    }
}

llvm::Value * decafFunCall::Codegen() { 
    descriptor * des = get_symbol(this->get_name());
    llvm::Function * llvm_func = des->func;
    std::vector<llvm::Value *> putsargs;
    std::vector<llvm::Type *> putstypes;

    for (auto& arg : llvm_func->args()) {
        llvm::Type* func_type = arg.getType();
        putstypes.push_back(func_type);
    }
    int i = 0;
    for(auto p:this->get_para()){
        decafBinexp * exp = (decafBinexp *)p;
        llvm::Value* vt = exp->Codegen();
        llvm::Type* func_type = putstypes[i++];
      
        vt = Builder.CreateZExt(vt, func_type, "zexttmp");
        /*
        if(exp->get_kind() != "VariableExpr"){
            llvm::ConstantInt* constantInt = llvm::dyn_cast<llvm::ConstantInt>(vt);
            if (constantInt) {
                llvm::APInt apIntValue = constantInt->getValue();
                int intValue = apIntValue.getZExtValue();
                vt = llvm::ConstantInt::get(func_type, intValue);
            }
        } 
        */

        putsargs.push_back(vt);
    }

    llvm::Value *ret_value = Builder.CreateCall(llvm_func, putsargs);
    return ret_value;
}

llvm::Value * decafAssign::Codegen() {
    decafBinexp* exp = this->get_exp();
    exp->Codegen();
    descriptor * des = get_symbolt(this->get_var());
    Builder.CreateStore(exp->des.value,des->alloc);
    return des->value;
}

llvm::Value * decafReturn::Codegen() {
    decafBinexp* exp = this->get_exp();
    if(exp){
        exp->Codegen();
        Builder.CreateRet(exp->des.value);
        get_return = 0;
        return exp->des.value;
    }
    else{
        Builder.CreateRetVoid();
        get_return = 0;
        return NULL;
    }
}

llvm::Value *decafBinexp::Codegen() {
    if(this->des.kind == valueK){
        decafAllexp * exp = (decafAllexp *)this; 
        return exp->Codegen();
    }
    else if(this->des.kind == expuK){
        llvm::Value *L = Exp1->Codegen();
        if (L == 0) {
            return 0;
        }
        switch (this->get_op(Option)) {
            case nottmp:
                this->des.value = Builder.CreateNot(L, "nottmp");
                break;     
            case negtmp:
                this->des.value = Builder.CreateNeg(L , "negtmp");
                break;
        }
        return this->des.value;
    }
    else if(this->des.kind == expbK){
        llvm::Value *L = Exp1->Codegen();
        llvm::Value *R = Exp2->Codegen();
        if (L == 0 || R == 0) {
            return 0;
        }

        switch (this->get_op(Option)) {
            case addtmp:
                this->des.value = Builder.CreateAdd(L, R, "addtmp"); 
                break;
            case subtmp:
                this->des.value = Builder.CreateSub(L, R, "subtmp");
                break;
            case multmp:
                this->des.value = Builder.CreateMul(L, R, "multmp");
                break;
            case remtmp:
                this->des.value = Builder.CreateSRem(L, R, "remtmp");
                break;
            case divtmp:
                this->des.value = Builder.CreateSDiv(L, R, "divtmp");
                break;
            case ortmp:
                this->des.value = Builder.CreateOr(L, R, "ortmp");
                break;
            case andtmp:
                this->des.value = Builder.CreateAnd(L, R, "andtmp");
                break;
            case eqtmp:
                this->des.value = Builder.CreateICmpEQ(L, R, "eqtmp");
                break;
            case netmp:
                this->des.value = Builder.CreateICmpNE(L, R, "netmp");
                break;
            case slttmp:
                this->des.value = Builder.CreateICmpSLT(L, R, "slttmp");
                break;    
            case sgttmp:
                this->des.value = Builder.CreateICmpSGT(L, R, "sgttmp");
                break;  
            case sletmp:
                this->des.value = Builder.CreateICmpSLE(L, R, "sletmp");
                break;    
            case sgetmp:
                this->des.value = Builder.CreateICmpSGE(L, R, "sgetmp");
                break;  
            case shltmp:
                this->des.value = Builder.CreateShl(L, R, "shltmp");
                break; 
            case shrtmp:
                this->des.value = Builder.CreateLShr(L, R, "shrtmp");
                break;                          
            default: 
                this->des.value = NULL;
                break;
        }
        return this->des.value;
    }
    else if(this->des.kind == funcK){
        decafFunCall * call = (decafFunCall *)this; 
        this->des.value = call->Codegen();
        return this->des.value;
    }
}

llvm::Value *decafAllexp::Codegen() {
    if(this->get_kind() == "VariableExpr"){
        descriptor * des = get_symbolt(this->get_name());
        llvm::Value* load = Builder.CreateLoad(des->alloc,this->get_name());
        this->des.value = load;
    }
    else if(this->get_kind() == "NumberExpr"){
        string s = this->get_name().substr(0, 2);
        llvm::Value* arg;
        if(s == "0x"){
            arg = llvm::ConstantInt::get(llvm::Type::getInt32Ty(Context), std::stoi(this->get_name(),NULL,16));
        }
        else{
            arg = llvm::ConstantInt::get(llvm::Type::getInt32Ty(Context), std::stoi(this->get_name(),NULL,10));
        }
        this->des.value = arg;
    }
    else if(this->get_kind() == "BoolExpr"){
        if(this->get_name() == "True"){
            llvm::Type* boolType = llvm::Type::getInt1Ty(Context);
            llvm::Constant* trueValue = llvm::ConstantInt::get(boolType, 1);
            this->des.value = trueValue;
        }else if(this->get_name() == "False"){
            llvm::Type* boolType = llvm::Type::getInt1Ty(Context);
            llvm::Constant* falseValue = llvm::ConstantInt::get(boolType, 0);
            this->des.value = falseValue;
        }
    }
    else if(this->get_kind() == "StringConstant"){
        llvm::GlobalVariable *GS = Builder.CreateGlobalString(this->get_name() ,"globalstring");
        llvm::Value *stringConst = Builder.CreateConstGEP2_32(GS->getValueType(), GS, 0, 0, "cast");
        this->des.value = stringConst;
    }
    return this->des.value;
}

llvm::Value *decafVar::Codegen() { 
    descriptor * des = new descriptor();
    if(put_symbolt(this->get_name(),des)){
        this->Alloca = Builder.CreateAlloca(this->lType, 0, this->get_name());
        des->alloc = this->Alloca;
        des->kind = valueK;
    }
    return this->Alloca;
}

llvm::Value *decafEXFuncDef::Codegen() { 
    descriptor* des = get_symbol(this->get_name());
    if(check_symbol( this->get_name(), funcK)){
        return this->lfunc;
    }
    else{
        return 0;
    }
}

llvm::Value *decafFuncDef::Codegen() { 
    descriptor* des = get_symbol(this->get_name());
    if(check_symbol( this->get_name(), funcK)){
        symbol_table s;
        symtblt.push_front(s);
        get_return = true;
        llvm::BasicBlock *BB = llvm::BasicBlock::Create(TheContext, "entry", this->lfunc);
        Builder.SetInsertPoint(BB);

        int i = 0;
        for(auto p:this->get_para()->get_para()){
            this->lfunc->getArg(i)->setName(p->get_name());

            descriptor * des2 = new descriptor();
            if(put_symbolt(p->get_name(),des2)){
                des2->alloc = Builder.CreateAlloca(p->lType, 0, p->get_name());
                des2->kind = valueK;
            }
            Builder.CreateStore(this->lfunc->getArg(i),des2->alloc);
            i++;
        }
        
        decafBlock * B = this->get_block();
        B->Codegen();

        if(get_return){
            if(this->lType->isVoidTy())
                Builder.CreateRetVoid();
            else
                Builder.CreateRet(llvm::ConstantInt::get(TheContext, llvm::APInt(32, 0)));
        }
        symtblt.pop_front();
        symtblt.clear();
    }
    return this->lfunc;
}

// we have to create a main function 
llvm::Function *gen_main_def() {
    // create the top-level definition for main
    llvm::FunctionType *FT = llvm::FunctionType::get(llvm::IntegerType::get(TheContext, 32), false);
    llvm::Function *TheFunction = llvm::Function::Create(FT, llvm::Function::ExternalLinkage, "main", TheModule);
    if (TheFunction == 0) {
        throw runtime_error("empty function block"); 
    }
    // Create a new basic block which contains a sequence of LLVM instructions
    llvm::BasicBlock *BB = llvm::BasicBlock::Create(TheContext, "entry", TheFunction);
    // All subsequent calls to IRBuilder will place instructions in this location
    Builder.SetInsertPoint(BB);

    descriptor* des = new descriptor();
    des->func = TheFunction;
    des->kind = funcK;
    put_symbol("main",des);

    return TheFunction;
}

%}

%define parse.error verbose

%union{
    class decafAST *ast;
    std::string *sval;
 }

%token T_PACKAGE T_EXTERN T_FUNC T_SEMICOLON T_COMMA T_CONTINUE T_FALSE T_TRUE T_VAR T_FOR T_NULL T_RETURN T_WHITESPACE
%token T_AND T_ASSIGN T_DIV T_DOT T_EQ T_RIGHTSHIFT T_GEQ T_GT T_LEFTSHIFT T_LEQ T_LT T_MINUS T_MOD T_MULT T_NEQ T_NOT T_OR T_PLUS
%token T_VOID T_INTTYPE T_BOOLTYPE T_STRINGTYPE
%token T_LCB T_RCB T_LPAREN T_RPAREN T_LSB T_RSB 
%token T_COMMENT
%token T_BREAK T_ELSE T_IF T_WHILE
%token <sval> T_ID T_INTCONSTANT T_CHARCONSTANT T_STRINGCONSTANT

%type <ast> state_if state_while lvalues state_for state_break state_continue state_return exp assign assigns assignss method_call lvalue statements statement extern_list para_list_use para_usen para_use para_list_def block blockt var_decls var_decl method_decls method_decl decafpackage var_declp var_declps extern_def extern_defn extern_typen extern_type func_typen func_type method_type type

%right T_ASSIGN 
%left T_OR
%left T_AND
%left T_EQ T_NEQ T_LT T_GT T_GEQ T_LEQ
%left T_PLUS T_MINUS 
%left T_MULT T_DIV T_MOD T_RIGHTSHIFT T_LEFTSHIFT
%right T_NOT 
%right T_UMINUS
%right T_LPAREN
%left T_RPAREN
%nonassoc T_IF
%nonassoc T_ELSE

%%

start: program

program: extern_list decafpackage{ 
        ProgramAST *prog = new ProgramAST((decafEXFuncDefList *)$1, (PackageAST *)$2); 
        prog->Codegen();
		if (printAST) {
			cout << getString(prog) << endl;
		}
        delete prog;
    }
    ;

extern_list: extern_defn { 
        $$ = $1;
    }
    | {
        decafEXFuncDefList *slist = new decafEXFuncDefList();
        $$ = slist;
    }
    ;

extern_defn: extern_def extern_defn {
        decafEXFuncDefList *slist = (decafEXFuncDefList *)$2;
        slist->push_front((decafEXFuncDef *)$1);
        $$ = slist;
    }
    | {
        decafEXFuncDefList *slist = new decafEXFuncDefList();
        $$ = slist;
    }
    ;

extern_def: T_EXTERN T_FUNC T_ID T_LPAREN para_list_def T_RPAREN method_type T_SEMICOLON {
        decafEXFuncDef *func = new decafEXFuncDef();
        decafPara* para = (decafPara*)$5;
        decafType * type = (decafType *)$7;
        func->put_name($3);
        func->put_type(type);
        func->put_para((decafPara*)para);
        $$ = func;
        delete $3; 
    
        descriptor* des = new descriptor();
        if(put_symbol( func->get_name(), des)){
            llvm::Type *returnTy = func->lType;
            string Name = func->get_name();
            llvm::SmallVector<llvm::Type *,0> functionArgs;

            for(auto p:func->get_para()->get_para()){
                functionArgs.push_back(p->lType);
            }
            func->lfunc = llvm::Function::Create(
                llvm::FunctionType::get(returnTy, functionArgs, false),
                llvm::Function::ExternalLinkage,
                Name,
                TheModule
            );
            des->func = func->lfunc;
            des->kind = funcK;
        }
    }
    ;

para_list_use: para_usen {
        $$ = $1;
    } 
    | {
        decafStmtList *slist = new decafStmtList();
        $$ = slist;
    }
    ;

para_usen: para_use T_COMMA para_usen {
        decafStmtList * para = (decafStmtList *)$3;
        para->push_front($1);
        $$ = para;
    }
    | para_use {
        decafStmtList * para = new decafStmtList();
        para->push_front($1);
        $$ = para;
    }
    ;

para_use: exp { $$ = $1;}
    ;

para_list_def: extern_typen {
        $$ = $1;
    }
    | func_typen {
        $$ = $1;
    }
    | {
        decafStmtList *slist = new decafStmtList();
        $$ = slist;
    }
    ;

func_typen: func_type T_COMMA func_typen {
        decafPara * para = (decafPara *)$3;
        para->push_front((decafType *)$1);
        $$ = para;     
    }
    | func_type {
        decafPara * para = new decafPara();
        para->push_front((decafType*)$1);
        $$ = para;   
    }
    ;

func_type: T_ID extern_type {
        decafType* type = (decafType*)$2;
        type->put_name(*$1);
        $$ = type;
        delete $1; 
    }
    ;

extern_typen: extern_type T_COMMA extern_typen {
        decafPara * para = (decafPara *)$3;
        para->push_front((decafType *)$1);
        $$ = para;
    }
    | extern_type {
        decafPara * para = new decafPara();
        para->push_front((decafType*)$1);
        $$ = para;
    }
    ;

extern_type: T_STRINGTYPE { 
        decafType* type = new decafType("StringType");
        type->Ty = stringTy; 
        $$ = type;

        type->lType = getLLVMType(type->Ty,Context);
    }
    | type { 
        decafType* type = (decafType* )$1; 
        $$ = type;
    }
    ;

method_type: T_VOID { 
        decafType* type = new decafType("VoidType"); 
        type->Ty = voidTy;
        $$ = type;

        type->lType = getLLVMType(type->Ty,Context);
    }
    | type { 
        decafType* type = (decafType* )$1;
        $$ = type;
    }
    ;

type: T_INTTYPE { 
        decafType* type = new decafType("IntType"); 
        type->Ty = intTy;
        $$ = type;

        type->lType = getLLVMType(type->Ty,Context);
    }   
    | T_BOOLTYPE { 
        decafType* type = new decafType("BoolType"); 
        type->Ty = boolTy;
        $$ = type;

        type->lType = getLLVMType(type->Ty,Context);
    }
    ;

decafpackage: T_PACKAGE T_ID T_LCB var_declps method_decls T_RCB {
        decafVarList *field = (decafVarList *)$4;
        decafFuncDefList *method = (decafFuncDefList *)$5;
        $$ = new PackageAST(*$2, field, method); 
        delete $2; 
    }
    | T_PACKAGE T_ID T_LCB T_RCB { 
        $$ = new PackageAST(*$2, new decafVarList(), new decafFuncDefList()); 
        delete $2; 
    }
    ;

var_declps: var_declp var_declps {
        decafVarList *slist = (decafVarList *)$2;
        slist->cat_front((decafVarList *)$1);
        $$ = slist;
    }
    | {
        decafVarList *slist = new decafVarList(); 
        $$ = slist;
    }
    ;

var_declp: T_VAR lvalues type T_SEMICOLON {
        decafType * type = (decafType *)$3;
        decafVarList * list = (decafVarList *)$2;
        list->put_types(type);
        list->put_kinds("Scalar");
        $$ = list;
    }
    | T_VAR lvalue type T_ASSIGN exp T_SEMICOLON {
        decafVarList * list = new decafVarList();
        decafType * type = (decafType *)$3;
        decafVar * var = (decafVar *)$2;
        decafAllexp * exp = (decafAllexp *)$5;
        var->put_kind("Scalar");
        var->put_type(type);
        var->put_exp(exp);
        list->push_front(var);
        $$ = list;
    }
    | T_VAR lvalue type T_SEMICOLON {
        decafVarList * list = new decafVarList();
        decafType * type = (decafType *)$3;
        decafVar * var = (decafVar *)$2;
        var->put_kind("Scalar");
        var->put_type(type);
        list->push_front(var);
        $$ = list;
    }
    ;

var_decls: var_decl var_decls {
        decafVarList *slist = (decafVarList *)$2;
        slist->cat_front((decafVarList *)$1);
        $$ = slist;
    }
    | {
        decafVarList *slist = new decafVarList(); 
        $$ = slist;
    }
    ;

var_decl: T_VAR lvalues type T_SEMICOLON {
        decafType * type = (decafType *)$3;
        decafVarList * list = (decafVarList *)$2;
        list->put_types(type);
        $$ = list;
    }
    | T_VAR lvalue type T_ASSIGN exp T_SEMICOLON {
        decafVarList * list = new decafVarList();
        decafType * type = (decafType *)$3;
        decafVar * var = (decafVar *)$2;
        decafAllexp * exp = (decafAllexp *)$5;
        var->put_type(type);
        var->put_exp(exp);
        list->push_front(var);
        $$ = list;
    }
    | T_VAR lvalue type T_SEMICOLON {
        decafVarList * list = new decafVarList();
        decafType * type = (decafType *)$3;
        decafVar * var = (decafVar *)$2;
        var->put_type(type);
        list->push_front(var);
        $$ = list;
    }
    ;

lvalues: lvalue T_COMMA lvalues {
        decafVar* var = (decafVar*)$1;
        decafVarList * list = (decafVarList*)$3;
        list->push_back(var);
        $$ = list;
    }
    | lvalue {
        decafVar* var = (decafVar*)$1;
        decafVarList * list = new decafVarList();
        list->push_back(var);
        $$ = list;
    }
    ;

lvalue: T_ID { 
        decafVar* var = new decafVar(*$1) ;
        $$ = var; 
        delete $1;
    }
    | T_ID T_LSB exp T_RSB { 
        decafVar* var = new decafVar(*$1) ; 
        decafAllexp* arr = (decafAllexp *)$3;
        var->put_arr(arr);
        var->put_kind("Array("+arr->get_name()+")");
        $$ = var; 
        delete $1;
    }
    ;

CONSTANT : T_INTCONSTANT | T_CHARCONSTANT | T_STRINGCONSTANT { };

method_decls: method_decl method_decls{
        decafFuncDefList *slist = (decafFuncDefList *)$2;
        slist->push_front((decafFuncDef *)$1);
        $$ = slist;
    }
    | {
        decafFuncDefList *slist = new decafFuncDefList(); 
        $$ = slist;
    }
    ;

method_decl: T_FUNC T_ID T_LPAREN para_list_def T_RPAREN method_type block {
        decafFuncDef *func = new decafFuncDef();
        decafPara* para = (decafPara*)$4;
        decafBlock * block = (decafBlock*)$7;
        decafType * type = (decafType *)$6;
        func->put_name($2);
        func->put_type(type);
        func->put_para(para);
        func->put_block(block);
        $$ = func;
        delete $2;

        descriptor* des = new descriptor();
        if(put_symbol( func->get_name(), des)){
            llvm::Type *returnTy = func->lType;
            std::vector<llvm::Type *> functionArgs;
            for(auto p:func->get_para()->get_para()){
                functionArgs.push_back(p->lType);
            }

            func->lfunc = llvm::Function::Create(
                llvm::FunctionType::get(returnTy, functionArgs ,false),
                llvm::Function::ExternalLinkage, 
                func->get_name(), 
                TheModule);
            if (func->lfunc == 0) {
                throw runtime_error("empty function block"); 
            }

            des->func = func->lfunc;
            des->kind = funcK;
        }
    }
    ;

blockt: T_LCB var_decls statements T_RCB {
        decafVarList *field = (decafVarList *)$2;
        decafStmts *state = (decafStmts *)$3;
        decafBlock *block = new decafBlock("Block",field,state);
        $$ = block;
    }
    | T_LCB T_RCB {
        decafVarList *field = new decafVarList(); 
        decafStmts *state = new decafStmts(); 
        decafBlock *block = new decafBlock("Block",field,state);
        $$ = block;
    }
    ;

block: T_LCB var_decls statements T_RCB {
        decafVarList *field = (decafVarList *)$2;
        decafStmts *state = (decafStmts *)$3;
        decafBlock *block = new decafBlock("MethodBlock",field,state);
        $$ = block;
    }
    | T_LCB T_RCB {
        decafVarList *field = new decafVarList(); 
        decafStmts *state = new decafStmts(); 
        decafBlock *block = new decafBlock("MethodBlock",field,state);
        $$ = block;
    }
    ;

statements: statement statements {
        decafStmts *slist = (decafStmts *)$2;
        slist->push_front((decafStmt *)$1);
        $$ = slist;
    }
    | {
        decafStmts *slist = new decafStmts(); 
        $$ = slist;
    }
    ;

statement: blockt { $$ = $1; }
    | assign T_SEMICOLON { $$ = $1; }
    | method_call T_SEMICOLON { $$ = $1; }
    | state_return T_SEMICOLON { $$ = $1; }
    | state_if { $$ = $1; }
    | state_while { $$ = $1; }
    | state_for { $$ = $1; }
    | state_break T_SEMICOLON { $$ = $1; }
    | state_continue T_SEMICOLON { $$ = $1; }
    ;

state_if: T_IF T_LPAREN exp T_RPAREN blockt T_ELSE blockt {
        decafAllexp *exp = (decafAllexp *)$3; 
        decafBlock *if_block = (decafBlock *)$5;
        decafBlock *else_block = (decafBlock *)$7;
        decafIF *ifs = new decafIF(exp,if_block,else_block);
        $$ = ifs;
    }
    | T_IF T_LPAREN exp T_RPAREN blockt {
        decafAllexp *exp = (decafAllexp *)$3; 
        decafBlock *if_block = (decafBlock *)$5;
        decafIF *ifs = new decafIF(exp,if_block,NULL);
        $$ = ifs;
    }
    ;

state_while: T_WHILE T_LPAREN exp T_RPAREN blockt {
        decafAllexp *exp = (decafAllexp *)$3; 
        decafBlock *block = (decafBlock *)$5;
        decafWhile *whiles = new decafWhile(exp,block);
        $$ = whiles;
    }
    ;

state_for: T_FOR T_LPAREN assignss T_SEMICOLON exp T_SEMICOLON assignss T_RPAREN blockt{
        decafAllexp *exp = (decafAllexp *)$5; 
        decafBlock *block = (decafBlock *)$9;
        decafAssignList *aslist = (decafAssignList *)$3; 
        decafAssignList *aslist2 = (decafAssignList *)$7; 
        decafFor * fors = new decafFor(exp,block,aslist,aslist2);
        $$ = fors;
    }
    ;

state_break: T_BREAK {
        decafOutput * data = new decafOutput("BreakStmt");
        $$ = data;
    }
    ;

state_continue: T_CONTINUE {
        decafOutput * data = new decafOutput("ContinueStmt");
        $$ = data;
    }
    ;

state_return: T_RETURN T_LPAREN exp T_RPAREN {
        decafBinexp *exp = (decafBinexp *)$3; 
        decafReturn *ret = new decafReturn(exp);
        $$ = ret;
    }
    | T_RETURN T_LPAREN T_RPAREN {
        decafReturn *ret = new decafReturn(NULL);
        $$ = ret;
    }
    | T_RETURN {
        decafReturn *ret = new decafReturn(NULL);
        $$ = ret;
    }
    ;

assignss : assigns {
        $$ = $1;
    }
    | {
        decafAssignList *aslist = new decafAssignList(); 
        $$ = aslist;
    }
    ;

assigns: assign T_COMMA assigns {
        decafAssignList *aslist = (decafAssignList *)$3; 
        decafAssign *ass = (decafAssign *)$1; 
        aslist->push_front(ass);
        $$ = aslist;
    }
    | assign {
        decafAssignList *aslist = new decafAssignList(); 
        decafAssign *ass = (decafAssign *)$1; 
        aslist->push_front(ass);
        $$ = aslist;
    }
    ;

assign: lvalue T_ASSIGN exp {
        decafVar* var = (decafVar *)$1;
        decafBinexp* exp = (decafBinexp *)$3;
        decafAssign* ass = new decafAssign(var->get_name(),exp);
        ass->kind = dass;
        ass->put_arr(var->get_arr());
        $$ = ass;
    }
    ;

exp : T_NOT exp { 
        decafUnaryexp * exp = new decafUnaryexp("Not", (decafBinexp*)$2); 
        $$ = exp; 
    }
    | T_MINUS exp %prec T_UMINUS { 
        decafUnaryexp * exp = new decafUnaryexp("UnaryMinus", (decafBinexp*)$2); 
        $$ = exp; 
    }
    | exp T_PLUS exp { 
        decafBinexp * exp = new decafBinexp("Plus", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_MINUS exp { 
        decafBinexp * exp = new decafBinexp("Minus", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_MULT exp { 
        decafBinexp * exp = new decafBinexp("Mult", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_DIV exp { 
        decafBinexp * exp = new decafBinexp("Div", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_MOD exp { 
        decafBinexp * exp = new decafBinexp("Mod", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_LEFTSHIFT exp { 
        decafBinexp * exp = new decafBinexp("Leftshift", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_RIGHTSHIFT exp { 
        decafBinexp * exp = new decafBinexp("Rightshift", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_LEQ exp { 
        decafBinexp * exp = new decafBinexp("Leq", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_GEQ exp { 
        decafBinexp * exp = new decafBinexp("Geq", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_LT exp { 
        decafBinexp * exp = new decafBinexp("Lt", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_GT exp { 
        decafBinexp * exp = new decafBinexp("Gt", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_EQ exp { 
        decafBinexp * exp = new decafBinexp("Eq", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_NEQ exp { 
        decafBinexp * exp = new decafBinexp("Neq", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_AND exp { 
        decafBinexp * exp = new decafBinexp("And", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp; 
    }
    | exp T_OR exp { 
        decafBinexp * exp = new decafBinexp("Or", (decafBinexp*)$1, (decafBinexp*)$3); 
        $$ = exp;
    }
    | T_LPAREN exp T_RPAREN { $$ = $2; }
    | T_ID { 
        decafAllexp * exp = new decafAllexp(*$1,"VariableExpr"); 
        $$ = exp; 
        delete $1;
    }
    | T_ID T_LSB exp T_RSB { 
        decafAllexp * exp = (decafAllexp *)$3;
        decafArrexp * arr = new decafArrexp(*$1,exp); 
        $$ = arr; 
        delete $1;
    }
    | T_INTCONSTANT { 
        decafAllexp * exp = new decafAllexp(*$1,"NumberExpr"); 
        $$ = exp; 
        delete $1;
    }  
    | T_CHARCONSTANT { 
        decafAllexp * exp = new decafAllexp(*$1,"NumberExpr"); 
        $$ = exp; 
    }  
    | T_STRINGCONSTANT { 
        decafAllexp * exp = new decafAllexp(*$1,"StringConstant");
        $$ = exp; 
    }  
    | T_TRUE { 
        decafAllexp * exp = new decafAllexp("True","BoolExpr"); 
        $$ = exp; 
    }
    | T_FALSE { 
        decafAllexp * exp = new decafAllexp("False","BoolExpr"); 
        $$ = exp; 
    }
    | method_call { $$ = $1; }
    ;

method_call: T_ID T_LPAREN para_list_use T_RPAREN {
        decafFunCall *call = new decafFunCall();
        decafStmtList* para = (decafStmtList*)$3;
        call->put_name($1);
        call->put_para(para->get_para());
        $$ = call;
        delete $1; 
    }
    ;

%%

int main() {
    // initialize LLVM
    // Make the module, which holds all the code.
    TheModule = new llvm::Module("Test", Context);
    // set up symbol table
    // set up dummy main function
    llvm::StringRef newFilename = "DecafExpr";
    TheModule->setSourceFileName(newFilename);
    // parse the input and create the abstract syntax tree
    int retval = yyparse();
    // remove symbol table
    // Finish off the main function. (see the WARNING above)
    // return 0 from main, which is EXIT_SUCCESS
    // Validate the generated code, checking for consistency.
    // Print out all of the generated code to stderr
    TheModule->print(llvm::errs(), nullptr);
    return(retval >= 1 ? EXIT_FAILURE : EXIT_SUCCESS);
}
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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
#include "default-defs.h"
#include <list>
#include <ostream>
#include <iostream>
#include <sstream>
#include <map>
#include <regex>

#ifndef YYTOKENTYPE
#include "decafexpr.tab.h"
#endif

using namespace std;
extern llvm::Module *TheModule;

class descriptor {
	public:
	union 
	{
		llvm::AllocaInst * alloc;
		llvm::Function* func;
		llvm::Value* value;
		llvm::Type* type;
	};
	llvmValue kind;
};

// decafAST - Base class for all abstract syntax tree nodes.
class decafAST {
public:
	descriptor des = {0,nullK};
	virtual ~decafAST() {}
	virtual string str() { return string(""); }
	llvm::Value *Codegen(){
		return des.value;
	};
};

llvm::Type *getLLVMType(llvmType ty, llvm::LLVMContext &Context ) { 
    switch (ty) {
        case voidTy: return llvm::Type::getVoidTy(Context);
        case intTy: return llvm::Type::getInt32Ty(Context);
        case boolTy: return llvm::Type::getInt1Ty(Context);
        case stringTy: return llvm::Type::getInt8PtrTy(Context); 
		default: throw runtime_error("unknown type");
    } 
}

template <class T>
llvm::Value *listCodegen(list<T> vec) {
	llvm::Value *val = NULL;
	for (typename list<T>::iterator i = vec.begin(); i != vec.end(); i++) { 
		llvm::Value *j = (*i)->Codegen();
		if (j != NULL) { val = j; }
	}	
	return val;
}

string getString(decafAST *d) {
	if (d != NULL) {
		return d->str();
	} else {
		return string("None");
	}
}

template <class T>
string commaList(list<T> vec) {
    string s("");
    for (typename list<T>::iterator i = vec.begin(); i != vec.end(); i++) { 
        s = s + (s.empty() ? string("") : string(",")) + (*i)->str(); 
    }   
    if (s.empty()) {
        s = string("None");
    }   
    return s;
}

// decafStmtList - List of Decaf statements
class decafStmtList : public decafAST {
	list<decafAST *> stmts;
public:
	decafStmtList() {}
	~decafStmtList() {
		for (list<decafAST *>::iterator i = stmts.begin(); i != stmts.end(); i++) { 
			delete *i;
		}
	}
	int size() { return stmts.size(); }
	void push_front(decafAST *e) { stmts.push_front(e); }
	void push_back(decafAST *e) { stmts.push_back(e); }
	list<decafAST *> get_para(){return stmts; }
	string str() { return commaList<class decafAST *>(stmts); }
	llvm::Value * Codegen() { 
		return listCodegen<decafAST *>(stmts); 
	}
};

class decafAllexp : public decafAST {
	string Kind;
	string Name;
public:
	string get_name(){return this->Name; }
	string get_kind(){return this->Kind; }
	decafAllexp(){}
	decafAllexp(string name,string kind) : Name(name),Kind(kind){
		this->des.kind = valueK;
		map<string,int> tab = {
			{"'\\t'",'\t'},
			{"'\\r'",'\r'},
			{"'\\n'",'\n'},
			{"'\\a'",'\a'},
			{"'\\v'",'\v'},
			{"'\\b'",'\b'},
			{"'\\f'",'\f'},
			{"'\\\\'",'\\'},
			{"'\\\''",'\''},
			{"'\\\"'",'\"'},
		};
		if( kind == "NumberExpr"){
			if(tab.count(this->Name)){
				this->Name = to_string(tab[this->Name]);
			}
			else if(this->Name.size() == 1){
				this->Name = to_string(Name[0]-48);
			}
			else if(this->Name.size() == 3 && ( this->Name[0]=='\'' || this->Name[0]=='\"' )){
				this->Name = to_string(Name[1]);
			}
		}
		if( kind == "StringConstant"){
			string s = this->get_name().erase(0,1);
			s.pop_back();
			for(int i=0;i<s.length();i++){
				if(s[i] == '\\'){
					char t[0x8];
					sprintf(t,"'\\%c'",s[i+1]);
					s[i+1] = tab[t];
					for(int j=i;j<s.length()-1;j++){
						s[j] = s[j+1];
					}
					s.pop_back();
				}
			}
			this->Name = s;
		}
	}
	string str() { return Kind + "(" + Name + ")"; }
	llvm::Value *Codegen();
};

class decafArrexp : public decafAllexp {
	string Name;
	decafAllexp * Exp;
public:
	decafArrexp(string Name, decafAllexp *Exp) 
		: Name(Name), Exp(Exp) {}
	string str() { return string("ArrayLocExpr") + "(" + Name + "," + getString(Exp) + ")"; }
};

class decafBinexp : public decafAllexp {
public:
	string Option;
	decafBinexp * Exp1;
	decafBinexp * Exp2;
	decafBinexp(){}
	decafBinexp(string op, decafBinexp *exp1, decafBinexp *exp2) 
		: Option(op), Exp1(exp1), Exp2(exp2) {
			this->des.kind = expbK;
		}
	virtual int get_op(string Option);
	string str() { return string("BinaryExpr") + "(" + Option + "," + getString(Exp1) + "," + getString(Exp2) + ")"; }
	llvm::Value *Codegen();
};

int decafBinexp::get_op(string Option){
	if(Option == "Plus")
		return addtmp;
	else if(Option == "Minus")
		return subtmp;
	else if(Option == "Mult")
		return multmp;
	else if(Option == "UnaryMinus")
		return negtmp;
	else if(Option == "Div")
		return divtmp;
	else if(Option == "Mod")
		return remtmp;
	else if(Option == "Or")
		return ortmp;
	else if(Option == "And")
		return andtmp;
	else if(Option == "Eq")
		return eqtmp;
	else if(Option == "Neq")
		return netmp;
	else if(Option == "Not")
		return nottmp;
	else if(Option == "Lt")
		return slttmp;
	else if(Option == "Gt")
		return sgttmp;
	else if(Option == "Leq")
		return sletmp;
	else if(Option == "Geq")
		return sgetmp;
	else if(Option == "Leftshift")
		return shltmp;
	else if(Option == "Rightshift")
		return shrtmp;
	else 
		return 0;
}

class decafUnaryexp : public decafBinexp {
public:
	decafUnaryexp(){}
	decafUnaryexp(string op, decafBinexp *exp1){
		decafBinexp::Option = op;
		decafBinexp::Exp1 = exp1;
		decafBinexp::Exp2 = NULL;
		this->des.kind = expuK;
	}
	string str() { 
		return string("UnaryExpr") + "(" + Option + "," + getString(Exp1) + ")"; 
	}
};

class decafType : public decafAST {
	string Type;
	string Name;
public:
	llvm::Type* lType;
	llvmType Ty;
	string get_type(){return this->Type; }
	string get_name(){return this->Name; }
	void put_name(string Name){ this->Name = Name;}
	decafType(string Type){this->Type = Type;}
	string str() {
		if(Name != ""){
			return "VarDef("+Name+","+Type+")"; 
		}
		else{
			return "VarDef("+Type+")"; 
		}
	}
	llvm::Value *Codegen();
};

class decafVar : public decafAST {
	string Type;
	string Name;
	string Kind;
	decafAllexp* Exp;
	decafAllexp* Arr;
public:
	llvm::AllocaInst *Alloca;
	llvm::Type* lType;
	decafVar(string Name) {this->Name = Name;}
	string get_type(){return this->Type;}
	string get_name(){return this->Name;}
	string get_kind(){return this->Kind;}
	decafAllexp* get_arr(){return this->Arr;}
	decafAllexp* get_exp(){return this->Exp;}
	void put_type(decafType* type){
		this->Type = type->get_type();
		this->lType = type->lType;
	}
	void put_name(string Name){this->Name = Name;}
	void put_kind(string Kind){
		if(this->Kind == "")
			this->Kind = Kind;
	}
	void put_arr(decafAllexp* Arr){this->Arr = Arr;}
	void put_exp(decafAllexp* Exp){this->Exp = Exp;}
	string str() { 
		if(Exp != NULL){
			return "AssignGlobalVar("+Name+","+Type+","+getString(Exp)+")"; 
		}
		else if(Kind != "" && Name != ""){
			return "FieldDecl("+Name+","+Type+","+Kind+")"; 
		}	
		else if(Name != ""){
			return "VarDef("+Name+","+Type+")"; 
		}
		else{
			return "VarDef("+Type+")"; 
		}
	}
	llvm::Value *Codegen();
};

class decafVarList : public decafAST {
	list<decafVar*> List;
public:
	list<decafVar*> get_list(){return this->List; }
	int size() { return List.size(); }
	void push_front(decafVar *e) { List.push_front(e); }
	void push_back(decafVar *e) { List.push_back(e); }
	void cat_front(decafVarList* List) {
		list<decafVar*> l = List->get_list();
		for(auto e:l){
			this->List.push_front(e); 
		}
	}
	void put_types(decafType* Type){
		for(auto e:this->List){
			e->put_type(Type); 
		}
	}
	void put_kinds(string Kind){
		for(auto e:this->List){
			e->put_kind(Kind); 
		}
	}
	string str() {return commaList<class decafVar *>(List);}
	llvm::Value * Codegen() { 
		return listCodegen<decafVar *>(List); 
	}
};

class decafOutput : public decafAST {
	string Data;
public:
	decafOutput(string Data){this->Data = Data;}
	string str() { return Data; }
};

class decafPara : public decafAST {
	list<decafType *> Para;
public:
	int size() { return Para.size(); }
	void push_front(decafType *e) { Para.push_front(e); }
	void push_back(decafType *e) { Para.push_back(e); }
	list<decafType *> get_para(){return Para; }
	string str() { return commaList<class decafType *>(Para); }
	llvm::Value *Codegen();
};

class decafStmt : public decafAST {
public:
	llvmStmt kind;
	decafStmt(){}
	llvm::Value * Codegen();
};

class decafStmts : public decafAST {
	list<decafStmt *> stmts;
public:
	decafStmts() {}
	int size() { return stmts.size(); }
	void push_front(decafStmt *e) { stmts.push_front(e); }
	void push_back(decafStmt *e) { stmts.push_back(e); }
	list<decafStmt *> get_para(){return stmts; }
	string str() { return commaList<class decafStmt *>(stmts); }
	llvm::Value * Codegen() { 
		llvm::Value* v = listCodegen<decafStmt *>(stmts); 
		return v;
	}
};

class decafFunCall : public decafStmt {
	string Name;
	list<decafAST *> Para;
public:
	decafFunCall(){
		this->kind = dcall; 
		this->des.kind = funcK;
	}
	void put_para(list<decafAST *>  Para){ this->Para = Para; }
	void put_name(string *Name){ this->Name = *Name; }
	int size() { return Para.size(); }
	string get_name(){ return this->Name; }
	list<decafAST *> get_para(){ return this->Para; }
	string str() { 
		return string("MethodCall") + "(" + Name + "," + commaList<class decafAST *>(Para) + ")";
	}
	llvm::Value *Codegen();
};

class decafAssign : public decafStmt {
	string Var;
	bool key;
	decafAllexp* Arr;
	decafBinexp* Exp;
public:
	void put_arr(decafAllexp* Arr){this->Arr = Arr;}
	void put_key(bool key){this->key = key;}
	string get_var(){ return this->Var; }
	decafBinexp* get_exp(){ return this->Exp; }
	decafAssign(string Var, decafBinexp* Exp):Var(Var),Exp(Exp){}
	string str() { 
		if(Arr == NULL)
			return string("AssignVar") + "(" + Var + "," + getString(Exp) + ")";
		else
			return string("AssignArrayLoc") + "(" + Var + "," + getString(Arr)+","+ getString(Exp) + ")";
	}
	llvm::Value *Codegen(); 
};

class decafAssignList : public decafAST {
	list<decafAssign *>List;
public:
	int size() { return List.size(); }
	void push_front(decafAssign *e) { List.push_front(e); }
	void push_back(decafAssign *e) { List.push_back(e); }
	void put_keys(bool key){
		for(auto ass:List){
			ass->put_key(key);
		}
	}
	string str() { 
		return commaList<class decafAssign *>(List);
	}
	llvm::Value *Codegen() { 
		return listCodegen<decafAssign *>(List); 
	}
};

class decafBlock : public decafStmt {
	string BloKind;
	decafVarList *FieldDeclList;
	decafStmts *StateDeclList;
public:
	decafBlock(string blokind,decafVarList *fieldlist, decafStmts *methodlist) 
		: BloKind(blokind), FieldDeclList(fieldlist), StateDeclList(methodlist) { this->kind = dblo; }
	~decafBlock() { 
		if (FieldDeclList != NULL) { delete FieldDeclList; }
		if (StateDeclList != NULL) { delete StateDeclList; }
	}
	string str() { 
		return BloKind + "(" + getString(FieldDeclList) + "," + getString(StateDeclList) + ")";
	}
	llvm::Value *Codegen();
};

class decafFuncDef : public decafAST {
	string Name;
	string Type;
	decafPara * Para;
	decafBlock * Block;
public:
	llvm::Type *lType;
	llvm::Function *lfunc;
	void put_para(decafPara * Para){ this->Para = Para;}
	void put_name(string *Name){ this->Name = *Name; }
	void put_type(decafType* type){
		this->Type = type->get_type();
		this->lType = type->lType;
	}
	void put_block(decafBlock *Block){ this->Block = Block; }
	decafBlock *get_block(){ return this->Block; }
	decafPara *get_para(){ return this->Para; }
	string get_name(){ return this->Name; }
	string str() { 
		return string("Method") + "(" + Name + "," + Type + "," + getString(Para) + "," + getString(Block) + ")";
	}
	llvm::Value *Codegen();
};

class decafFuncDefList : public decafAST {
	list<decafFuncDef*> List;
public:
	list<decafFuncDef*> get_list(){return this->List; }
	int size() { return List.size(); }
	void push_front(decafFuncDef *e) { List.push_front(e); }
	void push_back(decafFuncDef *e) { List.push_back(e); }
	void cat_front(decafFuncDefList* List) {
		list<decafFuncDef*> l = List->get_list();
		for(auto e:l){
			this->List.push_front(e); 
		}
	}
	void put_types(decafType* Type){
		for(auto e:this->List){
			e->put_type(Type); 
		}
	}
	string str() {return commaList<class decafFuncDef *>(List);}
	llvm::Value *Codegen() { 
		return listCodegen<decafFuncDef *>(List); 
	}
};

class decafEXFuncDef : public decafAST {
	string Name;
	string Type;
	decafPara* Para;
public:
	llvm::Type *lType;
	llvm::Function *lfunc;
	void put_para(decafPara* Para){ this->Para = Para;}
	void put_name(string *Name){ this->Name = *Name; }
	void put_type(decafType* type){
		this->Type = type->get_type();
		this->lType = type->lType;
	}
	string get_name(){return this->Name; }
	string get_type(){return this->Type; }
	decafPara* get_para(){ return this->Para; }
	string str() { 
		return string("ExternFunction") + "(" + Name + "," + Type + "," + getString(Para) + ")";
	}
	llvm::Value *Codegen();
};

class decafEXFuncDefList : public decafAST {
	list<decafEXFuncDef*> List;
public:
	list<decafEXFuncDef*> get_list(){return this->List; }
	int size() { return List.size(); }
	void push_front(decafEXFuncDef *e) { List.push_front(e); }
	void push_back(decafEXFuncDef *e) { List.push_back(e); }
	void cat_front(decafEXFuncDefList* List) {
		list<decafEXFuncDef*> l = List->get_list();
		for(auto e:l){
			this->List.push_front(e); 
		}
	}
	void put_types(decafType* Type){
		for(auto e:this->List){
			e->put_type(Type); 
		}
	}
	string str() {return commaList<class decafEXFuncDef *>(List);}
	llvm::Value *Codegen() { 
		return listCodegen<decafEXFuncDef *>(List); 
	}
};

class PackageAST : public decafAST {
	string Name;
	decafVarList *FieldDeclList;
	decafFuncDefList *MethodDeclList;
public:
	PackageAST(string name, decafVarList *fieldlist, decafFuncDefList *methodlist) 
		: Name(name), FieldDeclList(fieldlist), MethodDeclList(methodlist) {}
	~PackageAST() { 
		if (FieldDeclList != NULL) { delete FieldDeclList; }
		if (MethodDeclList != NULL) { delete MethodDeclList; }
	}
	string str() { 
		return string("Package") + "(" + Name + "," + getString(FieldDeclList) + "," + getString(MethodDeclList) + ")";
	}
	llvm::Value *Codegen() { 
		llvm::Value *val = NULL;
		TheModule->setModuleIdentifier(llvm::StringRef(Name)); 
		if (NULL != FieldDeclList) {
			val = FieldDeclList->Codegen();
		}
		if (NULL != MethodDeclList) {
			val = MethodDeclList->Codegen();
		} 
		// Q: should we enter the class name into the symbol table?
		return val; 
	}
};

class decafIF : public decafStmt {
	decafAllexp * Exp;
	decafBlock * Block;
	decafBlock * Block2;
public:
	decafIF(decafAllexp * Exp,decafBlock * Block,decafBlock * Block2): Exp(Exp),Block(Block),Block2(Block2){}
	string str() { 
		return string("IfStmt") + "(" + getString(Exp) +"," + getString(Block) + "," + getString(Block2) + ")"; 
	}
	llvm::Value *Codegen();
};

class decafWhile : public decafStmt {
	decafAllexp * Exp;
	decafBlock * Block;
public:
	decafWhile(decafAllexp * Exp,decafBlock * Block): Exp(Exp),Block(Block){}
	string str() { 
		return string("WhileStmt") + "(" + getString(Exp) +"," + getString(Block) + ")"; 
	}
	llvm::Value *Codegen();
};

class decafFor : public decafStmt {
	decafAllexp * Exp;
	decafBlock * Block;
	decafAssignList *List;
	decafAssignList *List2;
public:
	decafFor(decafAllexp * Exp,decafBlock * Block,decafAssignList *List,decafAssignList *List2): Exp(Exp),Block(Block),List(List),List2(List2){}
	string str() { 
		return string("ForStmt") + "(" + getString(List)+","+getString(Exp) +","+getString(List2)+","+getString(Block) + ")"; 
	}
	llvm::Value *Codegen();
};

class decafReturn : public decafStmt {
	decafBinexp * Exp;
public:
	decafReturn(){
		this->kind = dret;
	}
	decafReturn(decafBinexp * Exp){ 
		this->Exp = Exp;
		this->kind = dret;
	}
	decafBinexp* get_exp(){ return this->Exp; }
	string str() { return string("ReturnStmt") + "(" + getString(Exp) + ")"; }
	llvm::Value *Codegen();
};

// ProgramAST - the decaf program
class ProgramAST : public decafAST {
	decafEXFuncDefList *ExternList;
	PackageAST *PackageDef;
public:
	ProgramAST(decafEXFuncDefList *externs, PackageAST *c) : ExternList(externs), PackageDef(c) {}
	~ProgramAST() { 
		if (ExternList != NULL) { delete ExternList; } 
		if (PackageDef != NULL) { delete PackageDef; }
	}
	string str() { return string("Program") + "(" + getString(ExternList) + "," + getString(PackageDef) + ")"; }
	llvm::Value *Codegen() { 
		llvm::Value *val = NULL;
		if (NULL != ExternList) {
			val = ExternList->Codegen();
		}
		if (NULL != PackageDef) {
			val = PackageDef->Codegen();
		} else {
			throw runtime_error("no package definition in decaf program");
		}
		return val; 
	}
};

最终拿到了满分：

1
2
3
Correct(dev): 100 / 100
Score(dev): 100.00
Total Score: 100.00