【编译原理大作业】Tiny+的三地址码

project Comments

  咕得有点久了
  这是编译原理大作业的第二步：进行语义分析，生成三地址码。

  三地址码是一种平台无关的中间代码（类似汇编，但没到 x86、MIPS 那么具体），特点是：1、变量和 label 无需换成具体的地址，能区分清楚就行（例如嵌套作用域的同名变量要区分开）；2、寄存器无限量，不需要考虑有限的寄存器池；3、没有关于 CPU、操作系统的对接细节。这还是一个比较中间层次的东西，要生成具体的可执行代码时，不同平台可以直接拿三地址码来翻译。
  有了上一步的语法树之后，这一部分就不需要额外的工具了，就在语法树上完成需要的操作。尽管语义分析可以在语法分析的过程中完成，但是建出树以后再操作会好写一点，反正时间复杂度是不变的。
  参考书用龙书即可（Compilers Principles, Techniques, Tools. second version），龙书已经把框架给得很清楚了，虽然略去了一堆坑 b 的细节。。。
  三地址码的格式也用龙书的。

  项目地址

语义分析

  语义分析是比较大的概念，对于不同的程序有不同的语义分析内容，例如，基于我的语言定义，可以进行包括但不限于如下的语义分析：

  • 检查整个程序是否有且仅有一个 MAIN 标识的函数；
  • 检查变量、函数引用前是否声明；
  • 检查变量、函数是否重定义；
  • 类型检查与类型强制转换。目前 Tiny+ 程序可用的类型只有 BOOL,CHAR,INT,REAL，它们之间都可以强制转换，且已按优先级从低到高排好。因此可以不用进行类型检查，只需在类型不匹配时强制类型转换（低优先级转换到高优先级）；
  • 调用函数时检查参数及类型是否匹配；
  • 检查函数是否以 RETURN 结尾，若不是，需提出 warning。

  我们可以在生成三地址码的过程中顺便做这些事情。

符号表

  符号表是一个栈结构，用于记录生成代码中遇到的各种符号，以便在真正的编译中替换成地址。本次的符号表需记录以下内容：

  • 定义的变量；
  • 定义的函数；
  • 控制流跳转用的 label

  具体实现，在基类 node 中定义符号表：(26 行)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
enum Symbol_t{
    SB_VAR,
    SB_FUNC,
    SB_LABEL,
    SB_NOTFOUND
};

class node;
struct Symbol {
    Symbol_t type;
    string label;
    Var_t varType;
    node *ref;        // reference to that symbol

    Symbol(Symbol_t ty,string lb="",Var_t vt=V_BOOL,node *rf=nullptr) {
        type=ty, varType=vt, label=lb, ref=rf;
    }
    Symbol() {}
};

typedef unordered_map<string,Symbol> SymbolTabType;

class node{
    public:
    ...
    static vector<SymbolTabType> symbolTab;         // symbol table. It is a stack
    static int EOCFCnt, elseCnt, loopCnt, varCnt;   // label count
};

  用 std::vector 来模拟符号表的栈（为了可以遍历栈元素而不用 std::stack）；栈的每一项是一个 unordered_map<string,Symbol>，用于映射符号到其信息；信息用 struct Symbol 来记录，内容包括符号类型、符号的 label、符号的运算类型（BOOL,INT 等）、代表该符号的语法树节点。
  在实际编译中，只有跨文件的符号需要记录 label 以用于链接，其余符号可直接记录其内存地址，因为符号最终就是要替换成地址的。
  另使用 EOCFCnt, elseCnt, loopCnt, varCnt 四个计数器来生成控制流跳转 label 标号、else 跳转 label 标号、循环跳转 label 标号、变量及寄存器唯一标号。使用计数器的目的就是使得 label、变量和寄存器标号变得唯一。

从符号表中查找符号

  从符号表中查找一个符号，就从栈顶往栈底依次查找，找到了返回相应的 Symbol 信息，找不到就返回 NOTFOUND。

1
2
3
4
5
Symbol find_symbol(string s) {
    for(int i=node::symbolTab.size()-1; i>=0; i--)
        if (node::symbolTab[i].count(s)) return node::symbolTab[i][s];
    return Symbol(SB_NOTFOUND);
}

控制流结束跳转 label

  If、For 等控制流需要一个继承属性 label 表示该控制流结束之后跳转到何处。这个继承属性在符号表中实现，用 %EOCF 符号（End Of Control Flow）来表示该语句结束后应跳转到的 label。这样 If、For 等节点具体生成代码的时候，只要从符号表中查找最近的 %EOCF，就知道如何跳转了。

三地址码

  在基类 node 中定义虚函数 generate_3addr_code()，即每个节点类实现自己的三地址码生成过程。

1
2
3
4
5
6
7
8
typedef vector<pair<string,string>> Codes;      // format: pair<label,instruction>

class node{
	public:	
	...
	Codes codes;
	virtual bool generate_3addr_code() {}      // return 0 if compiled successfully
};

  三地址码形如 vector<pair<string,string>>，每条指令代码用两个 string 表示，前一个 string 表示 label，后一个 string 表示指令。
  本次实验中，label 和指令是多对一的关系，即相同名称的 label 一定指向同一条指令，但一条指令可以对应多个 label。这在实际编译中也是可行的，因为 label 的本质是内存地址，如果用内存地址代替 label 的记录，那么 label 和指令就是一一对应的了。
  接下来分不同的节点类来说明 generate_3addr_code() 的实现，以及相应的语法检查。

Program

  Program 是整个语法树的根，它新建一层符号表用于标记全局 label，调用它的子节点（MethodDecls）生成代码，并在整份代码开头补充一句 goto mainFuncLabel 使得程序跳到 MAIN 函数入口。

1
2
3
4
5
6
7
8
bool node_Program::generate_3addr_code() {
    symbolTab.push_back(SymbolTabType());                   // global label
    bool err=son[0]->generate_3addr_code();
    codes.push_back(make_pair("","goto "+mainFuncLabel));   // goto main function
    add_codes(codes,son[0]->codes);
    symbolTab.pop_back();
    return err;
}

  add_codes(a,b) 是把 b 的代码加到 a 的末尾。
1
2
3
4
5
void add_codes(Codes &a,Codes &b) {
	if (a.empty()) a=b;
		else for(auto code:b) a.push_back(code);
	b.clear();
}

MethodDecls

  该节点可以得到整个程序的函数列表。因此先把函数标识符添加到符号表中，生成它们的跳转 label（”__” 加函数名），这样就可以做到函数的调用与声明顺序无关。
  此处顺便找出 MAIN 标识的函数，并检查是否唯一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string node::mainFuncLabel="NO";

bool node_MethodDecls::generate_3addr_code() {
    bool err=0;
    // add function names to symbol table, and find 'main'
    for(auto xp:son) {
        node_MethodDecl *x=(node_MethodDecl*)xp;
        string &funcName=((node_Id*)(x->son[1]))->name;
        symbolTab.back()[funcName]=Symbol(SB_FUNC,"__"+funcName,((node_Type*)(x->son[0]))->varType,xp);
        if (x->isMain) {
            if (mainFuncLabel!="NO") semantic_error("more than one main function")
                else mainFuncLabel="__"+funcName;
        }
    }
    if (mainFuncLabel=="NO") semantic_error("no main function");

    for(auto xp:son) {     // enumerate each method
        // each method generates its codes and add to this->codes
        node_MethodDecl *x=(node_MethodDecl*)xp;
		err|=x->generate_3addr_code();
		add_codes(codes,x->codes);
    }
    return err;
}

这里用到了语义报错操作。简单地在节点类里记录一下当前节点对应的代码的行号（新建节点时保存 flex 的 yylineno 即可），就可以报错时输出行号了。
1
2
3
4
5
6
7
#define semantic_error(message) {\
	cout << lineno << ": semantic error: " << message << endl;\
	err=1;\
}
#define semantic_warning(message) {\
	cout << lineno << ": warning: " << message << endl;\
}

MethodDecl

  该节点是具体的一个函数。首先新建一层符号表，表示新一层的局部变量，以及在表里记录当前所在的函数信息（return 要用）；然后处理形参表，将形参加入局部变量；接着生成函数内的 statements 的具体代码；最后检查代码的最后一条指令是否是 return。
  这里需要新建一个 %EOCF 符号，指向最后的 return，即如果该函数最后一条语句是 If 等控制流，那么这个 If 语句就知道它要跳转到最后的 return 了。（如果代码自己生成了 return，那么这个符号也是用不上的。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool node_MethodDecl::generate_3addr_code() {
    bool err=0;
    symbolTab.push_back(SymbolTabType());                            // local label
    symbolTab.back()["%EOCF"]=Symbol(SB_LABEL,"EOCF_"+to_string(EOCFCnt++));    // 'End Of Control Flow' label
    // mark which function we are in
    symbolTab.back()["%FUNC"]=Symbol(SB_LABEL,"",((node_Type*)son[0])->varType,(node*)this);
    err|=((node_FormalParams*)son[2])->add_formal_params();        // formal parameters
    if (son.size()>=4) {
        err|=son[3]->generate_3addr_code();                        // statements
        add_codes(codes,son[3]->codes);
    }
    // check if the last instruction is return
    if (codes.empty() || codes.back().second!="return") {
        semantic_warning("lack of return at the end of function");
        codes.push_back(make_pair("","return"));
    }
    codes.back().first.insert(0,symbolTab.back()["%EOCF"].label+": ");
    codes[0].first.insert(0,"__"+((node_Id*)son[1])->name+": ");    // mark the entrance of function
    symbolTab.pop_back();
    return err;
}

Statements

  该节点表示语句的集合，同时也表示被 BEGIN, END 包起来的一个区块。所以逻辑就是先新建一层符号表表示局部变量，然后每条语句依次生成。
  但是遇到控制流语句的时候，要判断该语句是否是最后一句，如果是，那么 %EOCF 沿用祖先的（即控制流结束后跳转到祖先指定的地方），否则新建一个 %EOCF 指向下一条语句，并在下一条语句的第一个指令加上这个 label。

  听起来很简单

  但实际上。。。细思极恐，所谓“%EOCF指向下一条语句，并在下一条语句的第一个指令加上这个 label”，它可能需要处理这样的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
IF (z==1) BEGIN
	IF (i==1) BEGIN
		IF (y==2) BEGIN
		END
		BEGIN
		END
		BEGIN
			BEGIN
			END
		END
	END
	BEGIN
		BEGIN
		END
	END
	BEGIN
	END
END
BEGIN
	INT a;
END

  这里的三个 if 全部都有“下一条语句”，但由于“下一条语句”为空，因此它们最终全都要使用祖先的 %EOCF，而不能新建 label 然后加到“下一条语句”。
  有同学说，既然这是空语句产生的 bug，那在生成语法树时就把这些空语句规避掉，不建立节点，不就好了？其一，空语句结构可能很复杂（比如这样嵌套的），从语法上处理它是比较麻烦的；其二，空语句不一定是形式上的空语句，还可以是实质空语句（就是写了非平凡的代码但生成的是空语句，例如因代码优化导致的空语句，例如局部变量定义也是不产生代码的），这导致一个不可规避的问题。

  解决方法是，遇到控制流，就把这一段连续的控制流语句抠出来，然后倒着做，相当于先要找到真正的非空的“下一条语句”在哪，然后倒序依次在这条语句的开头新建 %EOCF（或是决定用祖先的）给上一条语句用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
bool isControlFlow(node *x) {
	return (!x->son.empty() && (x->son[0]->nodeType==IFSTMT || x->son[0]->nodeType==FORSTMT));
}

bool node_Statements::generate_3addr_code() {
	bool err=0;
	symbolTab.push_back(SymbolTabType());		// local label
	for(int i=0; i<son.size(); i++) {
		node_Statement *x=(node_Statement*)son[i];
		if (isControlFlow(x)) {
			// for continuous control flows, generate codes in reverse order,
			// to avoid bugs of EOCF label with empty statement
			vector<node*> CFlist;
			int j=i;							// i: the first CF;   j: after the last CF
			for(; ; j++) {
				for(; j<son.size() && isControlFlow(son[j]); j++) CFlist.push_back(son[j]);
				if (j>=son.size()) break;
				err|=son[j]->generate_3addr_code();
				if (!son[j]->codes.empty()) break;
			}
			if (j<son.size()) {
				string eocf="EOCF_"+to_string(EOCFCnt++);
				symbolTab.back()["%EOCF"]=Symbol(SB_LABEL,eocf);
				son[j]->codes[0].first.insert(0,eocf+": ");
			}
			for(int k=CFlist.size()-1; k>=0; k--) {
				err|=CFlist[k]->generate_3addr_code();
				if (k>i) {
					string eocf="EOCF_"+to_string(EOCFCnt++);
					symbolTab.back()["%EOCF"]=Symbol(SB_LABEL,eocf);
					CFlist[k]->codes[0].first.insert(0,eocf+": ");
				}
			}
			symbolTab.back().erase("%EOCF");
			for(; i<=j; i++) if (i<son.size()) add_codes(codes,son[i]->codes);
			i--;
		} else {
			err|=x->generate_3addr_code();		// each statement
			add_codes(codes,x->codes);
		}
		
	}
	symbolTab.pop_back();
	return err;
}

简单语句

  LocalVarDecl, AssignStmt, ReturnStmt, ReadStmt, WriteStmt 都是单条简单语句，它们生成的代码都较为简单，代码不赘述。
  ReturnStmt 需要注意若返回表达式的类型与函数类型不匹配，则要强制类型转换。
  ReadStmt, WriteStmt 当作函数调用处理。

  以 AssignStmt 为例：

1
2
3
4
5
6
7
8
9
10
11
bool node_AssignStmt::generate_3addr_code() {
	bool err=0;
	string &leftName=((node_Id*)son[0])->name;
	Symbol left=find_symbol(leftName);
	if (left.type==SB_NOTFOUND) semantic_error("undeclared identifier '"+leftName+"'")
		else if (left.type!=SB_VAR) semantic_error("identifier '"+leftName+"' is not a variable");
	err|=son[1]->generate_3addr_code();
	add_codes(codes,son[1]->codes);
	codes.push_back(make_pair("",left.label+" = "+((node_Expression*)son[1])->resultLabel));
	return err;
}

IfStmt

  If 是一个控制流，有 else 和没 else 的生成规则分别为：

1
2
3
4
<codes of expression of condition>
ifFalse <condition> goto %EOCF
<codes of ifTrue>
%EOCF: ...

  和
1
2
3
4
5
6
<codes of expression of condition>
ifFalse <condition> goto else
<codes of ifTrue>
goto %EOCF
else: <codes of else>
%EOCF: ...

  注意 ifTrue 和 else 的语句都要新建一层符号表。这里的 else label 要用 elseCnt 计数器来生成唯一标号。具体代码翻译该逻辑即可，不赘述。

ForStmt

  For 语句共 4 个部分：初始化语句 init、循环条件 condition、每次循环结束后执行的操作 afterLoop、循环体 loop。生成规则为：

1
2
3
4
5
6
7
<codes of init>
<codes of condition>
loop: ifFalse <condition> goto %EOCF
<codes of loop>
<codes of afterLoop>
goto loop
%EOCF: ...

Expression

  每个 Expression 类要得到它的代码、返回类型、存放结果的 label。

  • 若为二元算术运算，则先生成左右两个子 Expression 的代码，然后两个返回值取类型优先级较高的作为最终结果类型，接着对两边进行强制类型转换，最后进行左右两个返回值的运算；
  • 若为二元逻辑运算，则同上，但最后结果类型是 BOOL
  • 若为一元运算，则先生成子 Expression 的代码，然后进行运算；
  • 若为立即数，则结果直接赋为该立即数；
  • 若为变量，则从符号表中寻找该变量的 label 作为结果 label；
  • 若为函数调用，则先生成实参的 Expression 的代码（并检查是否与形参匹配），接着用 param 语句传递参数，然后调用函数，最后取出返回值放到一个寄存器。

  这里是把布尔表达式和算数表达式等同对待了，但实际编译器是区别对待的，比如 or 运算，前件成立了是不判断后件的。本来这只是个代码优化，但它已经形成一种编程规范了，如果前件成立仍然判断后件会导致很多程序出错的。

  至此，三地址码的生成就基本说完了。

后续内容

  做一做前端交互，用 -o 选项把代码输出到指定文件啥的，改一下上次的代码不要因为存在语法错误就把整棵树析构了，使其能够同时检查语法错误和语义错误，最好再按行号排个序输出。
  我现在的语言定义里还有很多东西没做，例如数组、指针、break、continue 之类的，因此这个语言还不是很完备。
  再后续，就是代码优化了，平台无关代码优化的部分龙书讲了很多，都挺有趣的。
  但是学期结束了哈哈哈哈哈哈哈哈哈哈

kqpOIACMer / HKU_CS / LLer / TCS

糖少许，盐少许