CMPT379编译器Lab4：decafcomp

decafcomp

本作业的目标是为 Decaf 编程语言编写一个完整的工作编译器

Decaf 的结构和代码生成提示在 Decaf 规范中给出：Decaf Programming Language Specification

实验描述

本实验有如下的目标：

• 添加对全局变量（也称为字段变量）的支持，Decaf 仅支持将整数和布尔数组定义为全局变量
• 确保所有变量（包括数组）的初始化均为零
• 添加对控制流（if 语句）和循环（while 和 for 语句）的支持，您需要了解程序控制流图中基本块的静态单一分配 SSA 形式，以及如何使用 LLVM API 实现 SSA 形式
• 实现布尔表达式的短路计算，短路是使用控制流实现的，与 if 语句非常相似
• 实现 Decaf 规范的无咖啡因语义部分中列出的所有语义检查，如果输入的 Decaf 程序未通过任何列出的语义检查，则引发语义错误
• 程序应拒绝任何语法或语义上无效的 Decaf 程序，并提供有用的错误消息，错误报告的质量取决于您，但您至少应该报告引发语法错误的行号和字符号
• 实现以下优化阶段：（可选）
  • 将堆栈分配使用情况 （Alloca） 转换为寄存器使用情况 （mem2reg）
  • 简单的窥视孔优化（指令组合通过）
  • 重新关联表达式
  • 消除公共子表达式 （GVN）
  • 简化控制流图（CFG 简化）
• 使用 DWARF 注释将源代码级调试信息添加到 LLVM 程序集

输出应位于 LLVM 程序集中，可以使用 LLVM 工具编译为 x86 程序集并作为二进制文件运行，我们将在 answer 目录中使用二进制 llvm-run 从测试用例目录中的 Decaf 程序创建和运行二进制文件

LLVM 程序集和工具链输出将转储到 llvm 目录中，应检查输出以调试编译器

如果程序成功解析输入，则应使用 exit(EXIT_SUCCESS) 退出程序，如果您的程序在输入的无咖啡因程序中发现错误，则应使用 exit(EXIT_FAILURE) 退出

实验步骤

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

mv decafexpr.lex decafcomp.lex
mv decafexpr.y decafcomp.y
mv decafexpr.cc decafcomp.cc

• 修改 decafcomp.lex decafcomp.y decafcomp.cc 中的头文件引用
• 将 default.y 中有关 LLVM 的代码拷贝到 decafcomp.y 中
• 将 default.cc 中有关 LLVM 的代码拷贝到 decafcomp.cc 中

直接运行程序就有不错的分数：

➜  decafcomp git:(master) ✗ python3 check.py 
Correct(dev): 129 / 208
Score(dev): 129.00
Total Score: 129.00

接下来的工作就是在上一个实验的基础上进行完善和补充，这里重点介绍一下 bool 短路表达式的实现：

• 要实现布尔表达式的短路，您需要以类似于控制流语句的方式控制基本块
• LLVM 程序集的基础表示形式是静态的单一作业表或 SSA 表格，在 SSA 表单中，每个变量在程序中只分配一次值价值 的变量可以多次使用
• 在复杂的控制流中，图表变量可能从程序中的两个不同路径获取值，为了处理这种复杂性，SSA 表格使用了 φ 功能创建一个新变量，该变量取决于所经过的路径控制流图

处理 bool 短路表达式的代码如下：

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;
        llvm::Value *R;
        list<llvm::BasicBlock *> BL;
        if(this->get_op(Option) == ortmp){
            llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
            llvm::Function* currentFunction = currentBlock->getParent();
            
            L = Exp1->Codegen();
            llvm::BasicBlock* OpValBB = llvm::BasicBlock::Create(Context, "noskct",currentFunction);
            llvm::BasicBlock* CurBB = llvm::BasicBlock::Create(Context, "skctend",currentFunction);
            Builder.CreateCondBr(L,CurBB,OpValBB);

            Builder.SetInsertPoint(OpValBB);
            R = Exp2->Codegen();
            this->des.value = Builder.CreateOr(L, R, "ortmp");
            Builder.CreateBr(CurBB);

            Builder.SetInsertPoint(CurBB);
            llvm::PHINode *val = Builder.CreatePHI(L->getType(), 2, "phival");

            for (llvm::BasicBlock* Pred : llvm::predecessors(CurBB)) {
                BL.push_front(Pred);
            }
            val->addIncoming(L, BL.front());
            BL.pop_front();
            val->addIncoming(this->des.value, BL.front());
            BL.pop_front();
            this->des.value = val;

            return val;
        }
        else if(this->get_op(Option) == andtmp){
            llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
            llvm::Function* currentFunction = currentBlock->getParent();

            L = Exp1->Codegen();
            llvm::BasicBlock* OpValBB = llvm::BasicBlock::Create(Context, "noskct",currentFunction);
            llvm::BasicBlock* CurBB = llvm::BasicBlock::Create(Context, "skctend",currentFunction);
            Builder.CreateCondBr(L,OpValBB,CurBB);

            Builder.SetInsertPoint(OpValBB);
            R = Exp2->Codegen();
            this->des.value = Builder.CreateAnd(L, R, "andtmp");
            Builder.CreateBr(CurBB);

            Builder.SetInsertPoint(CurBB);
            llvm::PHINode *val = Builder.CreatePHI(L->getType(), 2, "phival");

            for (llvm::BasicBlock* Pred : llvm::predecessors(CurBB)) {
                BL.push_front(Pred);
            }
            val->addIncoming(L, BL.front());
            BL.pop_front();
            val->addIncoming(this->des.value, BL.front());
            BL.pop_front();
            this->des.value = val;

            return val;
        }
        else{
            L = Exp1->Codegen();
            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 modtmp:
                this->des.value = Builder.CreateSRem(L, R, "modtmp");
                break;
            case divtmp:
                this->des.value = Builder.CreateSDiv(L, R, "divtmp");
                break;
            case eqtmp:
                this->des.value = Builder.CreateICmpEQ(L, R, "eqtmp");
                break;
            case neqtmp:
                this->des.value = Builder.CreateICmpNE(L, R, "neqtmp");
                break;
            case slttmp:
                this->des.value = Builder.CreateICmpSLT(L, R, "lttmp");
                break;    
            case gttmp:
                this->des.value = Builder.CreateICmpSGT(L, R, "gttmp");
                break;  
            case sletmp:
                this->des.value = Builder.CreateICmpSLE(L, R, "sletmp");
                break;    
            case geqtmp:
                this->des.value = Builder.CreateICmpSGE(L, R, "geqtmp");
                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;
    }
}

接下来的工作和上一个实验无异，完整代码如下：

%{
#include <iostream>
#include <ostream>
#include <string>
#include <cstdlib>
#include "default-defs.h"
#include "decafcomp.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;
list<llvm::BasicBlock*> cg;
list<llvm::BasicBlock*> bg;

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() { 
    get_return = true;
    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 if(this->kind == dif){
        decafIF* s = (decafIF*)this;
        return s->Codegen();
    }
    else if(this->kind == dfor){
        decafFor* s = (decafFor*)this;
        return s->Codegen();
    }
    else if(this->kind == dwhi){
        decafWhile* s = (decafWhile*)this;
        return s->Codegen();
    }
    else if(this->kind == dcb){
        decafCB* s = (decafCB*)this;
        return s->Codegen();
    }
    else{
        return NULL;
    }
}

llvm::Value * decafFunCall::Codegen() { 
    descriptor * des = get_symbol(this->get_name());
    llvm::Function * llvm_func = des->func;
    llvm::Value *ret_value;
    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);
    }

    if(llvm_func->getReturnType()->isVoidTy())
        ret_value = Builder.CreateCall(llvm_func, putsargs);
    else
        ret_value = Builder.CreateCall(llvm_func, putsargs, "calltmp");
    return ret_value;
}

llvm::Value * decafAssign::Codegen() {
    decafBinexp* exp = this->get_exp();
    exp->Codegen();
    descriptor * des = get_symbolt(this->get_var());
    if(des == NULL){
        des = get_symbol(this->get_var());
    }

    if(des->kind == arrG){ 
        llvm::Value *ArrayLoc = Builder.CreateStructGEP(des->tyg, des->value, std::stol(this->get_arr()->get_name(),NULL,10), "arrayloc");
        Builder.CreateStore(exp->des.value,ArrayLoc);
    }
    else{
        Builder.CreateStore(exp->des.value,des->alloc);
    }

    return des->value;
}

llvm::Value * decafReturn::Codegen() {
    decafBinexp* exp = this->get_exp();
    llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
    llvm::Function* currentFunction = currentBlock->getParent(); 
    if(exp){
        exp->Codegen();
        Builder.CreateRet(exp->des.value);
        get_return = false;
        return exp->des.value;
    }
    else{
        if(currentFunction->getReturnType()->isVoidTy()){
            Builder.CreateRetVoid();
        }   
        else{
            llvm::Value *zero = llvm::ConstantInt::get(currentFunction->getReturnType(), 0);
            Builder.CreateRet(zero);
        }
        get_return = false;
        return NULL;
    }
}

llvm::Value *decafArrexp::Codegen() {
    descriptor * des = get_symbol(this->get_name());

    llvm::Value *ArrayLoc = Builder.CreateStructGEP(des->tyg, des->value, std::stol(this->get_arr()->get_name(),NULL,10), "arrayloc");
    llvm::Value* load = Builder.CreateLoad(ArrayLoc,"arrayval");
    this->des.value = load;

    return this->des.value;
}


llvm::Value *decafBinexp::Codegen() {
    if(this->des.kind == valueK || this->des.kind == valueG){
        decafAllexp * exp = (decafAllexp *)this; 
        return exp->Codegen();
    }
    else if(this->des.kind == arrG){
        decafArrexp * exp = (decafArrexp *)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;
        llvm::Value *R;
        list<llvm::BasicBlock *> BL;
        if(this->get_op(Option) == ortmp){
            llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
            llvm::Function* currentFunction = currentBlock->getParent();
            
            L = Exp1->Codegen();
            llvm::BasicBlock* OpValBB = llvm::BasicBlock::Create(Context, "noskct",currentFunction);
            llvm::BasicBlock* CurBB = llvm::BasicBlock::Create(Context, "skctend",currentFunction);
            Builder.CreateCondBr(L,CurBB,OpValBB);

            Builder.SetInsertPoint(OpValBB);
            R = Exp2->Codegen();
            this->des.value = Builder.CreateOr(L, R, "ortmp");
            Builder.CreateBr(CurBB);

            Builder.SetInsertPoint(CurBB);
            llvm::PHINode *val = Builder.CreatePHI(L->getType(), 2, "phival");

            for (llvm::BasicBlock* Pred : llvm::predecessors(CurBB)) {
                BL.push_front(Pred);
            }
            val->addIncoming(L, BL.front());
            BL.pop_front();
            val->addIncoming(this->des.value, BL.front());
            BL.pop_front();
            this->des.value = val;

            return val;
        }
        else if(this->get_op(Option) == andtmp){
            llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
            llvm::Function* currentFunction = currentBlock->getParent();

            L = Exp1->Codegen();
            llvm::BasicBlock* OpValBB = llvm::BasicBlock::Create(Context, "noskct",currentFunction);
            llvm::BasicBlock* CurBB = llvm::BasicBlock::Create(Context, "skctend",currentFunction);
            Builder.CreateCondBr(L,OpValBB,CurBB);

            Builder.SetInsertPoint(OpValBB);
            R = Exp2->Codegen();
            this->des.value = Builder.CreateAnd(L, R, "andtmp");
            Builder.CreateBr(CurBB);

            Builder.SetInsertPoint(CurBB);
            llvm::PHINode *val = Builder.CreatePHI(L->getType(), 2, "phival");

            for (llvm::BasicBlock* Pred : llvm::predecessors(CurBB)) {
                BL.push_front(Pred);
            }
            val->addIncoming(L, BL.front());
            BL.pop_front();
            val->addIncoming(this->des.value, BL.front());
            BL.pop_front();
            this->des.value = val;

            return val;
        }
        else{
            L = Exp1->Codegen();
            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 modtmp:
                this->des.value = Builder.CreateSRem(L, R, "modtmp");
                break;
            case divtmp:
                this->des.value = Builder.CreateSDiv(L, R, "divtmp");
                break;
            case eqtmp:
                this->des.value = Builder.CreateICmpEQ(L, R, "eqtmp");
                break;
            case neqtmp:
                this->des.value = Builder.CreateICmpNE(L, R, "neqtmp");
                break;
            case slttmp:
                this->des.value = Builder.CreateICmpSLT(L, R, "lttmp");
                break;    
            case gttmp:
                this->des.value = Builder.CreateICmpSGT(L, R, "gttmp");
                break;  
            case sletmp:
                this->des.value = Builder.CreateICmpSLE(L, R, "sletmp");
                break;    
            case geqtmp:
                this->des.value = Builder.CreateICmpSGE(L, R, "geqtmp");
                break;  
            case shltmp:
                this->des.value = Builder.CreateShl(L, R, "shltmp");
                break; 
            case lshrtmp:
                this->des.value = Builder.CreateLShr(L, R, "lshrtmp");
                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());
        if(des == NULL){
            des = get_symbol(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::stol(this->get_name(),NULL,16));
        }
        else{
            arg = llvm::ConstantInt::get(llvm::Type::getInt32Ty(Context), std::stol(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(this->Kind == "Array"){
        if(put_symbol(this->get_name(),des)){
            llvm::ArrayType *arrayi32 = llvm::ArrayType::get(this->lType, std::stol(this->get_arr()->get_name(),NULL,10));
            llvm::Constant *zeroInit = llvm::Constant::getNullValue(arrayi32);
            llvm::GlobalVariable *Foo = new llvm::GlobalVariable(*TheModule, arrayi32, false, llvm::GlobalValue::ExternalLinkage, zeroInit, this->get_name());
            des->value = Foo;
            des->tyg = arrayi32;
            des->kind = arrG;
        }
    }
    else if(this->Kind == "Scalar"){
        if(put_symbol(this->get_name(),des)){
            decafAllexp *exp = this->get_exp();
            llvm::Constant *Init;
            if(exp == NULL){
                Init = llvm::Constant::getNullValue(lType);
            } 
            else {
                Init = (llvm::Constant *)exp->Codegen();
            }

            llvm::GlobalVariable *Foo = new llvm::GlobalVariable(*TheModule, this->lType, false, llvm::GlobalValue::ExternalLinkage, Init, this->get_name());
            des->value = Foo;
            des->kind = valueG;
        }
    }
    else{
        if(put_symbolt(this->get_name(),des)){
            this->Alloca = Builder.CreateAlloca(this->lType, 0, this->get_name());
            llvm::Value *zero = llvm::ConstantInt::get(this->lType, 0);
            llvm::Value *val = Builder.CreateStore(zero, this->Alloca);
            des->alloc = this->Alloca;
        }
    }
    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, "func", 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());
            }
            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;
}

llvm::Value *decafIF::Codegen(){
    llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
    llvm::Function* currentFunction = currentBlock->getParent(); 
    decafBinexp * exp = (decafBinexp*)this->get_exp();
    decafBlock *Block = this->get_block();
    decafBlock *Block2 = this->get_block2();

    llvm::BasicBlock *conditionBlock = llvm::BasicBlock::Create(Context, "if",currentFunction);

    Builder.CreateBr(conditionBlock);
    Builder.SetInsertPoint(conditionBlock);
    llvm::Value *condition = exp->Codegen();

    llvm::BasicBlock *trueBlock = llvm::BasicBlock::Create(Context, "true",currentFunction);
    llvm::BasicBlock *falseBlock = llvm::BasicBlock::Create(Context, "false",currentFunction);
    llvm::BasicBlock *elseBlock = NULL;
    if(Block2){
        elseBlock = llvm::BasicBlock::Create(Context, "else",currentFunction);
    }

    if(Block2){
        Builder.CreateCondBr(condition, trueBlock, elseBlock);
    }
    else{
        Builder.CreateCondBr(condition, trueBlock, falseBlock);
    }

    if(Block){
        Builder.SetInsertPoint(trueBlock);
        Block->Codegen();
        Builder.CreateBr(falseBlock);
        get_return = true;
    }

    if(Block2){
        Builder.SetInsertPoint(elseBlock);
        Block2->Codegen();
        Builder.CreateBr(falseBlock);
        get_return = true;
    }

    Builder.SetInsertPoint(falseBlock);
    return NULL;
}

llvm::Value *decafFor::Codegen(){
    llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
    llvm::Function* currentFunction = currentBlock->getParent(); 
    decafBinexp * exp = (decafBinexp*)this->get_exp();
    decafBlock* Block = this->get_block();
    decafAssignList *Alist = this->get_list();
    decafAssignList *Alist2 = this->get_list2();

    llvm::BasicBlock *conditionBlock = llvm::BasicBlock::Create(Context, "loop",currentFunction);

    if(Alist){
        Alist->Codegen();
    }
    Builder.CreateBr(conditionBlock);
    Builder.SetInsertPoint(conditionBlock);
    llvm::Value *condition = exp->Codegen();
    llvm::BasicBlock *bodyBlock = llvm::BasicBlock::Create(Context, "body",currentFunction);
    llvm::BasicBlock *nextBlock = llvm::BasicBlock::Create(Context, "next",currentFunction);
    llvm::BasicBlock *endBlock = llvm::BasicBlock::Create(Context, "end",currentFunction);

    Builder.CreateCondBr(condition, bodyBlock, endBlock);

    Builder.SetInsertPoint(bodyBlock);
    if(Block){
        cg.push_back(nextBlock);
        bg.push_back(endBlock);
        Block->Codegen();
        cg.pop_back();
        bg.pop_back();
    }
    Builder.CreateBr(nextBlock);

    Builder.SetInsertPoint(nextBlock);
    if(Alist2){
        Alist2->Codegen();
    }
    Builder.CreateBr(conditionBlock);

    Builder.SetInsertPoint(endBlock);
    return NULL;
}

llvm::Value *decafWhile::Codegen(){
    llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
    llvm::Function* currentFunction = currentBlock->getParent(); 
    decafBinexp * exp = (decafBinexp*)this->get_exp();
    decafBlock* Block = this->get_block();

    llvm::BasicBlock *conditionBlock = llvm::BasicBlock::Create(Context, "loop",currentFunction);

    Builder.CreateBr(conditionBlock);
    Builder.SetInsertPoint(conditionBlock);
    llvm::Value *condition = exp->Codegen();
    llvm::BasicBlock *bodyBlock = llvm::BasicBlock::Create(Context, "body",currentFunction);
    llvm::BasicBlock *endBlock = llvm::BasicBlock::Create(Context, "end",currentFunction);
    Builder.CreateCondBr(condition, bodyBlock, endBlock);

    Builder.SetInsertPoint(bodyBlock);
    if(Block){
        cg.push_back(conditionBlock);
        bg.push_back(endBlock);
        Block->Codegen();
        cg.pop_back();
        bg.pop_back();
    }
    Builder.CreateBr(conditionBlock);

    Builder.SetInsertPoint(endBlock);;
    return NULL;
}


llvm::Value *decafCB::Codegen(){
    llvm::BasicBlock* currentBlock = Builder.GetInsertBlock(); 
    llvm::Function* currentFunction = currentBlock->getParent(); 

    llvm::BasicBlock* endBlock = NULL;
    llvm::BasicBlock *loopBlock = NULL;
    llvm::BasicBlock *nextBlock = NULL;

    if(this->Data == "BreakStmt"){
        Builder.CreateBr(bg.back());
    }
    else if(this->Data == "ContinueStmt"){
        Builder.CreateBr(cg.back());
    }

    return NULL;
}

// 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, "func", 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");
        $$ = 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 {
        decafBinexp *exp = (decafBinexp *)$3; 
        decafBlock *if_block = (decafBlock *)$5;
        decafBlock *else_block = (decafBlock *)$7;
        decafIF *ifs = new decafIF(exp,if_block,else_block);
        $$ = ifs;

        ifs->kind = dif;
    }
    | T_IF T_LPAREN exp T_RPAREN blockt {
        decafBinexp *exp = (decafBinexp *)$3; 
        decafBlock *if_block = (decafBlock *)$5;
        decafIF *ifs = new decafIF(exp,if_block,NULL);
        $$ = ifs;

        ifs->kind = dif;
    }
    ;

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

        whiles->kind = dwhi;
    }
    ;

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

        fors->kind = dfor;
    }
    ;

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

        data->kind = dcb;
    }
    ;

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

        data->kind = dcb;
    }
    ;

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 = "DecafComp";
    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);
}

#include "default-defs.h"
#include <list>
#include <ostream>
#include <iostream>
#include <sstream>
#include <map>
#include <regex>

#ifndef YYTOKENTYPE
#include "decafcomp.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;
	};
	llvm::ArrayType *tyg;
	llvmValue kind;
};

// decafAST - Base class for all abstract syntax tree nodes.
class decafAST {
public:
	descriptor des = {0};
	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 * Arr;
public:
	decafArrexp(string Name, decafAllexp *Arr) : Name(Name), Arr(Arr) {
		this->des.kind = arrG;
	}
	string get_name(){ return this->Name; }
	decafAllexp* get_arr() {return this->Arr;}  
	string str() { return string("ArrayLocExpr") + "(" + Name + "," + getString(Arr) + ")"; }
	llvm::Value *Codegen();
};

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 modtmp;
	else if(Option == "Or")
		return ortmp;
	else if(Option == "And")
		return andtmp;
	else if(Option == "Eq")
		return eqtmp;
	else if(Option == "Neq")
		return neqtmp;
	else if(Option == "Not")
		return nottmp;
	else if(Option == "Lt")
		return slttmp;
	else if(Option == "Gt")
		return gttmp;
	else if(Option == "Leq")
		return sletmp;
	else if(Option == "Geq")
		return geqtmp;
	else if(Option == "Leftshift")
		return shltmp;
	else if(Option == "Rightshift")
		return lshrtmp;
	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 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 decafCB : public decafStmt {
	string Data;
public:
	decafCB(string Data){this->Data = Data;}
	string str() { return Data; }
	llvm::Value * Codegen();
};

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; }
	decafAllexp* get_arr(){return this->Arr;}
	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 {
	decafBinexp * Exp;
	decafBlock * Block;
	decafBlock * Block2;
public:
	decafIF(decafBinexp * Exp,decafBlock * Block,decafBlock * Block2): Exp(Exp),Block(Block),Block2(Block2){}
	decafBinexp * get_exp(){return this->Exp; } 
	decafBlock * get_block(){return this->Block; } 
	decafBlock * get_block2(){return this->Block2; } 
	string str() { 
		return string("IfStmt") + "(" + getString(Exp) +"," + getString(Block) + "," + getString(Block2) + ")"; 
	}
	llvm::Value *Codegen();
};

class decafWhile : public decafStmt {
	decafBinexp * Exp;
	decafBlock * Block;
public:
	decafBinexp *get_exp(){return this->Exp; }
	decafBlock *get_block(){return this->Block; }
	decafWhile(decafBinexp * Exp,decafBlock * Block): Exp(Exp),Block(Block){}
	string str() { 
		return string("WhileStmt") + "(" + getString(Exp) +"," + getString(Block) + ")"; 
	}
	llvm::Value *Codegen();
};

class decafFor : public decafStmt {
	decafBinexp * Exp;
	decafBlock * Block;
	decafAssignList *List;
	decafAssignList *List2;
public:
	decafFor(decafBinexp * Exp,decafBlock * Block,decafAssignList *List,decafAssignList *List2): Exp(Exp),Block(Block),List(List),List2(List2){}
	decafBinexp *get_exp(){return this->Exp; }
	decafBlock *get_block(){return this->Block; }
	decafAssignList *get_list(){return this->List; }
	decafAssignList *get_list2(){return this->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; 
	}
};

最终结果如下：

Correct(dev): 208 / 208
Score(dev): 208.00
Total Score: 208.00