CMPT379编译器Lab2：decafast

decafast

本作业的目标是为 Decaf 编程语言编写一个语法分析器

Decaf 中词汇元素的详细信息在 Decaf 规范中：Decaf Programming Language Specification

为 Decaf 语言提供解析器，以生成摘要有效 Decaf 程序的语法树

• 抽象语法树（AST）是程序结构，无需在源代码中包含所有详细信息，它可以被认为是一个抽象的表示
• 想要生成的抽象语法树，可以使用 Zehpyr 定义语言（这是一种用于序列化抽象语法树的方法）

实验描述

使用 Decaf 规范作为指导，完成一个 Decaf 语言的语法分析器

请务必遵守以下要求：

• 如果程序成功解析输入，则应使用 exit(EXIT_SUCCESS) 退出程序
• 如果您的程序在输入的无咖啡因程序中发现错误，则应使用 exit(EXIT_FAILURE) 退出
• 程序生成的抽象语法树必须采用上面指定的格式，输出规范在 /compilers-class-hw/decafast/Decaf.asdl 中提供
• 不要在输出中添加空格，这可能会导致将输出与参考输出匹配时出现问题

使用 Python 程序在测试用例上运行 zipout.py 解决方案程序，您的解决方案必须在目录 answer 中编译，并且必须调用 decaflex，针对所有测试用例运行，如下所示：

python3 zipout.py

• 这将创建一个名为 output 的目录和一个可以根据参考输出文件进行检查的文件 output.zip

python3 check.py 

• 这将检查您解决方案的准确性

实验步骤

您需要使用在 HW1 中构建的词法分析器，因此需要将 decaflex 中的词法分析器 decaflex.lex 复制到 /compilers-class-hw/decafast/answer 中

目录 /compilers-class-hw/decafast/answer 中存在这个作业的一个不完整的解决方案，本实验要求构造该方案的副本，因此要执行下列命令：

cp default.cc decafast.cc
cp default.lex decafast.lex
cp default.y decafast.y

• decafast.cc：修改 #include "default.tab.h" 以替换为 #include "decafast.tab.h"
• decafast.y：修改 #include "default.cc" 以替换为 #include "decafast.cc"
• decafast.lex：仅将令牌模式定义从 HW1 中的 decaflex.lex 复制到 decafast.lex，不要从 main 复制任何内容，因为 decafast.y 中有一个新的 main 函数
• PS：T_PACKAGE，T_LCB，T_RCB，T_ID 这4个 token 需使用 default.lex 中的默认值，忽略 T_WHITESPACE

通过运行以下命令构建可执行文件 decafast：

make decafast

该实验提供了一个未完成案例 default.y：

%{
#include <iostream>
#include <ostream>
#include <string>
#include <cstdlib>
#include "default-defs.h"

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

// print AST?
bool printAST = true;

#include "decafast.cc"

using namespace std;

%}

%define parse.error verbose

%union{ // 该样例程序只提供了两个可选类型:树节点,字符串
    class decafAST *ast;
    std::string *sval;
 }

%token T_PACKAGE
%token T_LCB
%token T_RCB
%token <sval> T_ID

%type <ast> extern_list decafpackage

%%

start: program

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

extern_list: /* extern_list can be empty */
    { decafStmtList *slist = new decafStmtList(); $$ = slist; }
    ;

decafpackage: T_PACKAGE T_ID T_LCB T_RCB
    { $$ = new PackageAST(*$2, new decafStmtList(), new decafStmtList()); delete $2; }
    ;

%%

int main() {
  // parse the input and create the abstract syntax tree
  int retval = yyparse();
  return(retval >= 1 ? EXIT_FAILURE : EXIT_SUCCESS);
}

在 decafast.cc 中提供了3个节点的类结构：

class decafAST {
public:
  virtual ~decafAST() {}
  virtual string str() { return string(""); }
};

class decafStmtList : public decafAST { /* 管理decaf语句 */
	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); }
	string str() { return commaList<class decafAST *>(stmts); }
};

class PackageAST : public decafAST { /* 管理decaf类 */
	string Name;
	decafStmtList *FieldDeclList;
	decafStmtList *MethodDeclList;
public:
	PackageAST(string name, decafStmtList *fieldlist, decafStmtList *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) + ")";
	}
};

class ProgramAST : public decafAST { /* 管理decaf程序 */
	decafStmtList *ExternList;
	PackageAST *PackageDef;
public:
	ProgramAST(decafStmtList *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) + ")"; }
};

• 在分析的过程中需要为每一个可能得节点设置对应的类

最开始尝试的时候比较迷茫，不知道从何入手，于是先看一个程序提供的案例来进行分析：

extern func print_int(int) void;
extern func read_int() int;

package Catalan {

    func main() void {
       print_int( cat( read_int() ) );
    }

    // factorial of n
    func fact(n int) int {
       if (n == 1) { return(1); }
       else { return(n*fact(n-1)); }
    }

    // a choose b
    func choose(a int, b int) int { 
       return( fact(a) / (fact(b)*fact(a-b)) ); 
    }

    // catalan number of n
    func cat(n int) int { 
       return( choose(2*n,n)/(n+1) ); 
    }
    
}

Program(ExternFunction(print_int,VoidType,VarDef(IntType)),ExternFunction(read_int,IntType,None),Package(Catalan,None,Method(main,VoidType,None,MethodBlock(None,MethodCall(print_int,MethodCall(cat,MethodCall(read_int,None))))),Method(fact,IntType,VarDef(n,IntType),MethodBlock(None,IfStmt(BinaryExpr(Eq,VariableExpr(n),NumberExpr(1)),Block(None,ReturnStmt(NumberExpr(1))),Block(None,ReturnStmt(BinaryExpr(Mult,VariableExpr(n),MethodCall(fact,BinaryExpr(Minus,VariableExpr(n),NumberExpr(1))))))))),Method(choose,IntType,VarDef(a,IntType),VarDef(b,IntType),MethodBlock(None,ReturnStmt(BinaryExpr(Div,MethodCall(fact,VariableExpr(a)),BinaryExpr(Mult,MethodCall(fact,VariableExpr(b)),MethodCall(fact,BinaryExpr(Minus,VariableExpr(a),VariableExpr(b)))))))),Method(cat,IntType,VarDef(n,IntType),MethodBlock(None,ReturnStmt(BinaryExpr(Div,MethodCall(choose,BinaryExpr(Mult,NumberExpr(2),VariableExpr(n)),VariableExpr(n)),BinaryExpr(Plus,VariableExpr(n),NumberExpr(1))))))))

• 在 Program 中并列了3个节点：ExternFunction，ExternFunction，Package
• 在每个节点中又详细描述了它的基础信息

模仿上述结构，可以写一个初版分析器：

%{
#include <iostream>
#include <ostream>
#include <string>
#include <cstdlib>
#include "default-defs.h"

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

// print AST?
bool printAST = true;

#include "decafast.cc"

using namespace std;

%}

%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 state_for state_break state_continue state_return exp assign 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 extern_def extern_defn extern_typen extern_type func_typen func_type method_type array_type type

%%

start: program

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

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

extern_defn: extern_def extern_defn {
        decafStmtList *slist = (decafStmtList *)$2;
        slist->push_front((decafAST *)$1);
        $$ = slist;
    }
    | {
        decafStmtList *slist = new decafStmtList();
        $$ = 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->get_type());
        func->put_para((decafPara*)para);
        $$ = func;
        delete $3; 
    }
    ;

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: method_call { $$ = $1;}
    | 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;}
    | type { decafType* type = (decafType* )$1; $$ = type;}
    ;

method_type: T_VOID { decafType* type = new decafType("VoidType"); $$ = type;}
    | type { decafType* type = (decafType* )$1; $$ = type;}
    ;

array_type: T_LSB T_INTCONSTANT T_RSB type {

    }
    ;

type: T_INTTYPE { decafType* type = new decafType("IntType"); $$ = type;}
    | T_BOOLTYPE { decafType* type = new decafType("BoolType"); $$ = type;}
    ;

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

var_decls: var_decl var_decls{
        decafStmtList *slist = (decafStmtList *)$2;
        slist->push_front((decafAST *)$1);
        $$ = slist;
    }
    | {
        decafStmtList *slist = new decafStmtList(); 
        $$ = slist;
    }
    ;

var_decl: T_VAR T_ID type T_SEMICOLON {

    }
    | T_VAR T_ID array_type T_SEMICOLON {

    }
    | T_VAR T_ID type T_ASSIGN CONSTANT T_SEMICOLON {

    }
    ;

CONSTANT : T_INTCONSTANT | T_CHARCONSTANT | T_STRINGCONSTANT { };

method_decls: method_decl method_decls{
        decafStmtList *slist = (decafStmtList *)$2;
        slist->push_front((decafAST *)$1);
        $$ = slist;
    }
    | {
        decafStmtList *slist = new decafStmtList(); 
        $$ = 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;
        decafStmtList * block = (decafStmtList*)$7;
        decafType * type = (decafType *)$6;
        func->put_name($2);
        func->put_type(type->get_type());
        func->put_para(para);
        func->put_block(block);
        $$ = func;
        delete $2; 
    }
    ;

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

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

statements: statement statements {
        decafStmtList *slist = (decafStmtList *)$2;
        slist->push_front((decafAST *)$1);
        $$ = slist;
    }
    | {
        decafStmtList *slist = new decafStmtList(); 
        $$ = 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: {}
    ;

state_for: {}
    ;

state_break: {}
    ;

state_continue: {}
    ;

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

assign: lvalue T_ASSIGN exp {

    }
    ;

lvalue: T_ID {  }
    | T_ID T_LSB exp T_RSB { }
    ;

exp : T_ID { decafAllexp * exp = new decafAllexp(*$1,"VariableExpr"); $$ = exp; }
    | T_INTCONSTANT { decafAllexp * exp = new decafAllexp(*$1,"NumberExpr"); $$ = exp; }  
    | T_CHARCONSTANT { decafAllexp * exp = new decafAllexp(*$1,"NumberExpr"); $$ = exp; }  
    | T_STRINGCONSTANT { decafAllexp * exp = new decafAllexp(*$1,"NumberExpr"); $$ = exp; }  
    | method_call { $$ = $1; }
    | T_NOT exp { decafBinexp * exp = new decafBinexp("Not", (decafAllexp*)$2, NULL); $$ = exp; }
    | T_MINUS exp { decafBinexp * exp = new decafBinexp("Minus", (decafAllexp*)$2, NULL); $$ = exp; }
    | exp T_PLUS exp { decafBinexp * exp = new decafBinexp("Plus", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_MINUS exp { decafBinexp * exp = new decafBinexp("Minus", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_MULT exp { decafBinexp * exp = new decafBinexp("Mult", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_DIV exp { decafBinexp * exp = new decafBinexp("Div", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_MOD exp { decafBinexp * exp = new decafBinexp("Mod", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_LEFTSHIFT exp { decafBinexp * exp = new decafBinexp("Leftshift", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_RIGHTSHIFT exp { decafBinexp * exp = new decafBinexp("Rightshift", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_LEQ exp { decafBinexp * exp = new decafBinexp("Leq", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_GEQ exp { decafBinexp * exp = new decafBinexp("Geq", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_LT exp { decafBinexp * exp = new decafBinexp("Lt", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_GT exp { decafBinexp * exp = new decafBinexp("Gt", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_EQ exp { decafBinexp * exp = new decafBinexp("Eq", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_NEQ exp { decafBinexp * exp = new decafBinexp("Neq", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_AND exp { decafBinexp * exp = new decafBinexp("And", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_OR exp { decafBinexp * exp = new decafBinexp("Or", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | T_LPAREN exp T_RPAREN { $$ = $2; }
    | {}
    ;

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() {
  // parse the input and create the abstract syntax tree
  int retval = yyparse();
  return(retval >= 1 ? EXIT_FAILURE : EXIT_SUCCESS);
}

上述语法分析器可以完美完成第一个样例，大体包含了对以下部分的处理：

• 类定义，函数定义，函数调用，函数声明，表达式，IF语句，语句块

我这里说明几点需要注意的地方

函数参数列表的问题：我们不能提前确定传入函数的参数个数，因此需要利用循环（FOR 语句的处理也是同理）

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_list_use 时，会有2种情况：
  • 无参数，不需要处理
  • 有参数，进入 para_usen，对于每一个 para_usen 有2种情况：
    • 剩余多个参数：将 para_use 压栈，继续匹配 para_usen 循环处理
    • 剩余一个参数：将 para_use 压栈

常量取值问题：对于常量需要再词法分析时将其字符串拷贝进来

{all_char}                 { yylval.sval = new string(yytext);return T_CHARCONSTANT; }
{all_str}                  { yylval.sval = new string(yytext);return T_STRINGCONSTANT; }
{decimal_num}|{hex_num}    { yylval.sval = new string(yytext);return T_INTCONSTANT; }

注释处理问题：注释需要在词法分析时进行匹配（最好不要返回 token）

"//"[^\n]*  	             { }
"/*"([^\*]|(\*)*[^\*/])*(\*)*"*/" { }       

得分结果：

➜  decafast git:(master) ✗ python3 check.py  
Correct(dev): 42 / 134
Score(dev): 42.00
Total Score: 42.00

已经匹配了部分样例，剩下的就是完善加调整，最后写一个完整分析器：

%{
#include <iostream>
#include <ostream>
#include <string>
#include <cstdlib>
#include "default-defs.h"

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

// print AST?
bool printAST = true;

#include "decafast.cc"

using namespace std;

%}

%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((decafStmtList *)$1, (PackageAST *)$2); 
		if (printAST) {
			cout << getString(prog) << endl;
		}
        delete prog;
    }
    ;

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

extern_defn: extern_def extern_defn {
        decafStmtList *slist = (decafStmtList *)$2;
        slist->push_front((decafAST *)$1);
        $$ = slist;
    }
    | {
        decafStmtList *slist = new decafStmtList();
        $$ = 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->get_type());
        func->put_para((decafPara*)para);
        $$ = func;
        delete $3; 
    }
    ;

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: method_call { $$ = $1;}
    | 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;}
    | type { decafType* type = (decafType* )$1; $$ = type;}
    ;

method_type: T_VOID { decafType* type = new decafType("VoidType"); $$ = type;}
    | type { decafType* type = (decafType* )$1; $$ = type;}
    ;

type: T_INTTYPE { decafType* type = new decafType("IntType"); $$ = type;}
    | T_BOOLTYPE { decafType* type = new decafType("BoolType"); $$ = type;}
    ;

decafpackage: T_PACKAGE T_ID T_LCB var_declps method_decls T_RCB {
        decafVarList *field = (decafVarList *)$4;
        decafStmtList *method = (decafStmtList *)$5;
        $$ = new PackageAST(*$2, field, method); 
        delete $2; 
    }
    | T_PACKAGE T_ID T_LCB T_RCB { 
        $$ = new PackageAST(*$2, new decafVarList(), new decafStmtList()); 
        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->get_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->get_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->get_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 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->get_type());
        var->put_exp(exp);
        list->push_front(var);
        $$ = list;
    }
    | T_VAR lvalues type T_SEMICOLON {
        decafType * type = (decafType *)$3;
        decafVarList * list = (decafVarList *)$2;
        list->put_types(type->get_type());
        $$ = list;
    }
    | T_VAR lvalue type T_SEMICOLON {
        decafVarList * list = new decafVarList();
        decafType * type = (decafType *)$3;
        decafVar * var = (decafVar *)$2;
        var->put_type(type->get_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{
        decafStmtList *slist = (decafStmtList *)$2;
        slist->push_front((decafAST *)$1);
        $$ = slist;
    }
    | {
        decafStmtList *slist = new decafStmtList(); 
        $$ = 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;
        decafStmtList * block = (decafStmtList*)$7;
        decafType * type = (decafType *)$6;
        func->put_name($2);
        func->put_type(type->get_type());
        func->put_para(para);
        func->put_block(block);
        $$ = func;
        delete $2; 
    }
    ;

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

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

statements: statement statements {
        decafStmtList *slist = (decafStmtList *)$2;
        slist->push_front((decafAST *)$1);
        $$ = slist;
    }
    | {
        decafStmtList *slist = new decafStmtList(); 
        $$ = 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 {
        decafAllexp *exp = (decafAllexp *)$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;
        decafAllexp* exp = (decafAllexp *)$3;
        decafAssign* ass = new decafAssign(var->get_name(),exp,NULL);
        ass->put_arr(var->get_arr());
        $$ = ass;
    }
    ;

exp : 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; }  
    | 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; }
    | T_NOT exp { decafUnaryexp * exp = new decafUnaryexp("Not", (decafAllexp*)$2); $$ = exp; }
    | T_MINUS exp %prec T_UMINUS { decafUnaryexp * exp = new decafUnaryexp("UnaryMinus", (decafAllexp*)$2); $$ = exp; }
    | exp T_PLUS exp { decafBinexp * exp = new decafBinexp("Plus", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_MINUS exp { decafBinexp * exp = new decafBinexp("Minus", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_MULT exp { decafBinexp * exp = new decafBinexp("Mult", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_DIV exp { decafBinexp * exp = new decafBinexp("Div", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_MOD exp { decafBinexp * exp = new decafBinexp("Mod", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_LEFTSHIFT exp { decafBinexp * exp = new decafBinexp("Leftshift", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_RIGHTSHIFT exp { decafBinexp * exp = new decafBinexp("Rightshift", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_LEQ exp { decafBinexp * exp = new decafBinexp("Leq", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_GEQ exp { decafBinexp * exp = new decafBinexp("Geq", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_LT exp { decafBinexp * exp = new decafBinexp("Lt", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_GT exp { decafBinexp * exp = new decafBinexp("Gt", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_EQ exp { decafBinexp * exp = new decafBinexp("Eq", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_NEQ exp { decafBinexp * exp = new decafBinexp("Neq", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_AND exp { decafBinexp * exp = new decafBinexp("And", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | exp T_OR exp { decafBinexp * exp = new decafBinexp("Or", (decafAllexp*)$1, (decafAllexp*)$3); $$ = exp; }
    | T_LPAREN exp T_RPAREN { $$ = $2; }
    ;

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() {
  // parse the input and create the abstract syntax tree
  int retval = yyparse();
  return(retval >= 1 ? EXIT_FAILURE : EXIT_SUCCESS);
}

其中用到的类与函数如下：

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

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

using namespace std;

/// decafAST - Base class for all abstract syntax tree nodes.
class decafAST {
public:
  virtual ~decafAST() {}
  virtual string str() { return string(""); }
};

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;
}

class decafAllexp : public decafAST {
	string Kind;
	string Name;
public:
	string get_name(){return this->Name; }
	decafAllexp(string name,string kind) : Name(name),Kind(kind){
		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]);
			}
		}
	}
	string str() { return Kind + "(" + Name + ")"; }
};

class decafArrexp : public decafAST {
	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 decafAST {
	string Option;
	decafAllexp * Exp1;
	decafAllexp * Exp2;
public:
	decafBinexp(string op, decafAllexp *exp1, decafAllexp *exp2) 
		: Option(op), Exp1(exp1), Exp2(exp2) {}
	string str() { return string("BinaryExpr") + "(" + Option + "," + getString(Exp1) + "," + getString(Exp2) + ")"; }
};

class decafUnaryexp : public decafAST {
	string Option;
	decafAllexp * Exp1;
public:
	decafUnaryexp(string op, decafAllexp *exp1) 
		: Option(op), Exp1(exp1) {}
	string str() { return string("UnaryExpr") + "(" + Option + "," + getString(Exp1) + ")"; }
};

class decafType : public decafAST {
	string Type;
	string Name;
public:
	string get_type(){return this->Type; }
	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+")"; 
		}
	}
};

class decafVar : public decafAST {
	string Type;
	string Name;
	string Kind;
	decafAllexp* Exp;
	decafAllexp* Arr;
public:
	decafVar(string Name) {this->Name = Name;}
	string get_type(){return this->Type;}
	string get_name(){return this->Name;}
	decafAllexp* get_arr(){return this->Arr;}
	decafAllexp* get_exp(){return this->Exp;}
	void put_type(string Type){this->Type = Type;}
	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+")"; 
		}
	}
};

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(string 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);}
};


/// 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); }
};

class decafAssign : public decafAST {
	string Var;
	bool key;
	decafAllexp* Arr;
	decafAllexp* Exp;
	decafAllexp* Exp2;
public:
	void put_arr(decafAllexp* Arr){this->Arr = Arr;}
	void put_key(bool key){this->key = key;}
	decafAssign(string Var,decafAllexp* Exp,decafAllexp* Exp2):Var(Var),Exp(Exp),Exp2(Exp2){}
	string str() { 
		if(Arr == NULL)
			return string("AssignVar") + "(" + Var + "," + getString(Exp) + ")";
		else
			return string("AssignArrayLoc") + "(" + Var + "," + getString(Arr)+","+ getString(Exp) + ")";
	}
};

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);
	}
};

class decafFunCall : public decafAST {
	string Name;
	list<decafAST *> Para;
public:
	void put_para(list<decafAST *>  Para){ this->Para = Para; }
	void put_name(string *Name){ this->Name = *Name; }
	string str() { 
		return string("MethodCall") + "(" + Name + "," + commaList<class decafAST *>(Para) + ")";
	}
};

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); }
};

class PackageAST : public decafAST {
	string Name;
	decafVarList *FieldDeclList;
	decafStmtList *MethodDeclList;
public:
	PackageAST(string name, decafVarList *fieldlist, decafStmtList *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) + ")";
	}
};

class decafFuncDef : public decafAST {
	string Name;
	string Type;
	decafPara * Para;
	decafStmtList * Block;
public:
	void put_para(decafPara * Para){ this->Para = Para;}
	void put_name(string *Name){ this->Name = *Name; }
	void put_type(string Type){ this->Type = Type; }
	void put_block(decafStmtList *Block){ this->Block = Block; }
	string str() { 
		return string("Method") + "(" + Name + "," + Type + "," + getString(Para) + "," + getString(Block) + ")";
	}
};

class decafEXFuncDef : public decafAST {
	string Name;
	string Type;
	decafPara* Para;
public:
	void put_para(decafPara* Para){ this->Para = Para;}
	void put_name(string *Name){ this->Name = *Name; }
	void put_type(string Type){ this->Type = Type; }
	string str() { 
		return string("ExternFunction") + "(" + Name + "," + Type + "," + getString(Para) + ")";
	}
};

class decafBlock : public decafAST {
	string Kind;
	decafStmtList *FieldDeclList;
	decafStmtList *StateDeclList;
public:
	decafBlock(string kind,decafStmtList *fieldlist, decafStmtList *methodlist) 
		: Kind(kind), FieldDeclList(fieldlist), StateDeclList(methodlist) {}
	~decafBlock() { 
		if (FieldDeclList != NULL) { delete FieldDeclList; }
		if (StateDeclList != NULL) { delete StateDeclList; }
	}
	string str() { 
		return Kind + "(" + getString(FieldDeclList) + "," + getString(StateDeclList) + ")";
	}
};

class decafIF : public decafAST {
	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) + ")"; 
	}
};

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

class decafFor : public decafAST {
	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) + ")"; 
	}
};

class decafReturn : public decafAST {
	decafAllexp * Exp;
public:
	decafReturn(decafAllexp * Exp){ this->Exp = Exp; }
	string str() { return string("ReturnStmt") + "(" + getString(Exp) + ")"; }
};

/// ProgramAST - the decaf program
class ProgramAST : public decafAST {
	decafStmtList *ExternList;
	PackageAST *PackageDef;
public:
	ProgramAST(decafStmtList *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) + ")"; }
};

最终拿到了满分：

➜  decafast git:(master) ✗ python3 check.py 
Correct(dev): 134 / 134
Score(dev): 134.00
Total Score: 134.00