HNU 软件编译原理实验 4（Go 实现）

编译器、解释器、虚拟机，或许只在杨氏编译原理里面是同义词。

代码已上传至 GitHub，为防止篇幅过长，没有内置所有代码，仅对个人认为值得讲述的地方进行说明，可以对比阅读。

TINY语言编译器的部分到了中间代码生成部分就结束了，生成的是下面这样的TM虚拟机机器码，剩下的部分一直到运行，都由虚拟机来完成。

  0:     LD  6,0(0) 
  1:     ST  0,0(0) 
  2:     IN  0,0,0 
  3:     ST  0,0(5) 
  4:    LDC  0,0(0) 
  5:     ST  0,0(6)

在实验三中完成了词法分析器，实验四包括了语义分析和中间代码生成，至于指导书没提的语法分析，当然只能自己加上了。

TINY编译器的C代码中，大致流程为：词法分析（scan.c）->语法分析（parse.c）->语义分析（analyze.c）->中间代码生成（code.c、cgen.c）。另外还有符号表管理（symtab.c）。本文的之后部分中，将其改写+优化为Go代码进行解释。

该编译器不含有独立的错误处理模块，错误处理在各模块中解决。

语法分析

该编译器的语法分析输出是一个语法树，树节点用以下的结构描述。

type treeNode struct {
	child   [3]*treeNode // 子节点
	sibling *treeNode    // 兄弟节点
	lineNo  int          // 行号
	op      tokenType    // 操作符
	val     int          // 值
	attr    string       // 属性
	stmt    stmtKind     // 语句类型
	expr    exprKind     // 表达式类型
	typ     exprType     // 表达式数值类型
	node    nodeKind     // 节点类型
}

命名很乱是吧，我也是这么想的。

节点类型nodeKind分为表达式节点和语句节点，前者对应一个表达式（如1+1），后者对应一整个或一行语句（如write i）
语句类型stmtKind分为赋值、循环、条件分支、读、写几种
表达式类型exprKind是当前表达式节点的类型，分为运算符、常量、标识符变量
表达式值类型exprType分为整型表达式、布尔表达式和没有值的表达式（真的存在吗）

由于Go孱弱的类型系统，既没有泛型多态有没有类似Rust的Trait（巧了，C也没有），所以每个节点存储完整的信息，不会因表达式或是语句节点而使用不同的结构体。

对于一个treeNode，同一个节点的某个child的sibling和其他child并不是并列的关系。对于某个语句节点，sibling指向的是下一个语句，例如：

fact := fact * x; 
x := x - 1;

第二句作为一个赋值语句节点，就是第一句的sibling。而child可以视为语句中的“槽位”，如：

if 0 < x then
    fact := 1;
end

上面的if-then-end语句有两个槽，分别存放0 < x表达式节点和fact := 1语句节点，也就是这个条件分支语句节点的两个child。因为槽最多的就是if-then-else-end，有三个，所以child最大也仅需要三个。

Parse函数用来启动语法分析，返回语法树根节点。它调用stmtSequence()函数，期望其返回时分析完整个源代码，如果最后识别到的token不为eof，则文件中含有错误。

func Parse() (t *treeNode) {
	currToken= GetToken()
	t = stmtSequence()
	if currToken != eofToken {
		syntaxError("Code ends before file\n")
	}
	return
}

stmtSequence函数用来识别位于同一作用域（如同一if-clause，也就是Python中同一缩进等级）的一串语句，当找到eof、end、else和until这几个代表结束的词语时结束。

t为nil这一个分支我也没看懂为什么在这里。

func stmtSequence() *treeNode {
	t := statement()
	p := t
	for currToken != eofToken && currToken != endToken && currToken != elseToken && currToken != untilToken {
		match(semicolonToken)
		q := statement()
		if q != nil {
			if t == nil {
				p = q
				t = p
			} else {
				p.sibling = q
				p = q
			}
		}
	}
	return t
}

statement函数好理解，一次识别单个语句，根据识别出的token类型进入不同的识别函数。代码略。

各种不同语句的识别函数分为if、repeat、赋值语句、read和write，此处只以ifStatement为例，其他看看代码应该就明白了。if节点的三个域分别存放expression（条件检验表达式）、then-statement（符合执行的语句串）和else-statement（不符合执行的语句串）。

// if 语句的匹配
//
// if <expression> then <stmtSequence> [else <stmtSequence>] end
func ifStatement() *treeNode {
	t := newStatementNode(ifStmt)
	match(ifToken)
	t.child[0] = expression()
	match(thenToken)
	t.child[1] = stmtSequence()
	if currToken == elseToken {
		match(elseToken)
		t.child[2] = stmtSequence()
	}
	match(endToken)
	return t
}

语句的匹配在上面就结束了，而表达式的匹配需要考虑优先级问题。在这个编译器程序中，分为三个优先级：<和=优先级最低，+和-优先级次之，*和/更高，数字、标识符和括号则设为同一最高优先级。在形式化语言表示中，使用不同的符号（Expression、Term、Factor）区分不同的计算优先级。产生式有：

$Expression \to simpleExpression\ |\ simpleExpression \lt simpleExpression\ |\ simpleExpression \lt \simpleExpression$

$simpleExpression \to Term\ |\ Term+Term\ |\ Term-Term$

$Term \to Factor\ |\ Factor \times Factor\ |\ Factor / Factor$

仅贴出Expression的代码，其他类似。

// 表达式的匹配：处理 < 和 = 运算符
// 优先级最低
func expression() *treeNode {
	t := simpleExpression()
	if currToken == ltToken || currToken == eqToken {
		p := newExpressionNode(opExpr)
		p.child[0] = t
		p.op = currToken
		t = p
		match(currToken)
		t.child[1] = simpleExpression()
	}
	return t
}

数字和标识符的处理（factor）如下：

// 表达式的匹配：处理数字、标识符和括号
func factor() (t *treeNode) {
	switch currToken {
	case numToken:
		t = newExpressionNode(constExpr)
		if currToken == numToken {
			var err error
			t.val, err = strconv.Atoi(tokenString)
			if err != nil {
				syntaxError("unexpected token -> %s" + currToken.String())
			}
			match(numToken)
		}
	case idToken:
		t = newExpressionNode(idExpr)
		if currToken == idToken {
			t.attr = tokenString
		}
		match(idToken)
	case lparenToken:
		match(lparenToken)
		t = expression()
		match(rparenToken)
	default:
		syntaxError("unexpected token -> %s" + currToken.String())
		currToken = GetToken()
	}
	return
}

符号表

原来的C版本编译器说白了也就是个自定义哈希函数的哈希表，是一个数组实现，封装了查找和插入，所以既然Go本身就有无序的字典map，当然就用上了。

符号表项的键为符号名，值为内存地址（从0起）和出现的行数列表的引用。

var symtab map[string]*struct {
	refLines []int // 引用行号列表
	memLoc   int   // 内存位置
} = make(map[string]*struct {
	refLines []int
	memLoc   int
})

在原来的符号表实现中，新符号的地址是由词法分析器决定的（而且是简单的递增），此处由符号表模块自行管理。

查找很简单，判断是否存在罢了。

// 查找符号表
// 返回内存位置和是否找到
func lookupSymtab(name string) (location int, ok bool) {
	if item, ok := symtab[name]; ok {
		return item.memLoc, true
	}
	return 0, false
}

插入分两种情况，如果已经存在，则仅更新行数列表；否则，还要分配一个空间。要改变map中某个元素的值，需要将其取出、修改值，然后重新设立对应关系，所以在上面的定义中使用了引用，得以在不修改引用地址的情况下增加引用行列表。

func insertSymtab(name string, lineNo int) {
	if item, ok := symtab[name]; ok {
		item.refLines = append(item.refLines, lineNo)
	} else {
		symtab[name] = &struct {
			refLines []int
			memLoc   int
		}{[]int{lineNo}, memLoc}
		memLoc++
	}
}

语义分析

语义分析主要干两件事，类型检查和插入符号表。

定义了一个统一的DFS函数，通过传入不同的函数，执行前序和后序遍历的操作。类型检查需要后序遍历，插入符号表则需要前序遍历（看起来TINY是lexical scoping）。

func traverse(t *treeNode, preProc func(*treeNode), postProc func(*treeNode)) {
	if t == nil {
		return
	}
	if preProc != nil {
		preProc(t)
	}
	for i := 0; i < 3; i++ {
		traverse(t.child[i], preProc, postProc)
	}
	if postProc != nil {
		postProc(t)
	}
	traverse(t.sibling, preProc, postProc)
}

构建符号表需要对每个出现变量的地方都进行一次插入操作。因为在之前的符号表操作中已经做到了根据已经插入与否区分不同的行为，所以此处可以省去判断是否已经存在。

// 将某个语法树节点的信息插入符号表
func insertNode(t *treeNode) {
	switch t.node {
	case stmtNode: // 对于语句，只有赋值和读语句需要插入符号表
		if t.stmt == assignStmt || t.stmt == readStmt {
			insertSymtab(t.attr, t.lineNo)
		}
	case exprNode: // 对于表达式，其中的标识符都要记在符号表中
		if t.expr == idExpr {
			insertSymtab(t.attr, t.lineNo)
		}
	}
}

// 遍历，构建符号表
func BuildSymtab(t *treeNode) {
	traverse(t, insertNode, nil)
}

类型检查的思想就是，赋值语句和写语句后面要匹配integer类型，if和repeat则要匹配bool类型。

// 对 t 做类型检查，反正就 bool 和 integer 两种类型
func checkNode(t *treeNode) {
	switch t.node {
	case exprNode:
		switch t.expr {
		case opExpr: // 运算符表达式，两个 child 类型均为 integer
			if t.child[0].typ != intExpr || t.child[1].typ != intExpr {
				typeError(t, "Op applied to non-integer")
			}
			if t.op == eqToken || t.op == ltToken { // 返回的是比较结果
				t.typ = boolExpr
			} else { // 返回的是计算结果
				t.typ = intExpr
			}
		default: // const 或 id，直接返回类型
			t.typ = intExpr
		}
	case stmtNode:
		switch t.stmt {
		case ifStmt: // if 语句，条件表达式类型为 bool
			if t.child[0].typ != boolExpr {
				typeError(t.child[0], "If test is not Boolean")
			}
		case assignStmt: // 赋值语句，表达式类型为 integer
			if t.child[0].typ != intExpr {
				typeError(t.child[0], "Assignment of non-integer value")
			}
		case writeStmt: // 写语句，表达式类型为 integer
			if t.child[0].typ != intExpr {
				typeError(t.child[0], "Write of non-integer value")
			}
		case repeatStmt: // repeat 语句，条件表达式类型为 bool
			if t.child[1].typ != boolExpr {
				typeError(t.child[1], "Repeat test is not Boolean")
			}
		}
	}
}

// 对整个语法树做类型检查
// 在进行完毕类型推导后，再做节点类型检查
func TypeCheck(t *treeNode) {
	traverse(t, nil, checkNode)
}

代码生成

生成代码已经是这个编译器做的最后一步了，没有优化，没有中间代码。TM虚拟机读取的还不完全是三地址码，更别提LLVM IR那样高阶的东西了，而是有点类似于真实计算机的寄存器+内存的组合。寄存器有累加AC1和AC2、程序计数器PC，以及GP和MP寄存器。

在codegen.go中，使用CodeGen()初始化程序运行环境，调用 cGen对AST根节点生成代码，然后挂起虚拟机。在cGen中，根据当前节点的类型调用genStmt或genExp生成语句或表达式，然后再对其兄弟节点调用cGen，生成下一条语句对应的代码。

语句

对于repeat <statement> until <expression>，先执行statement，再判断expression，判断结果会存放在AC1寄存器中。当AC1为0时代表条件成立，执行条件跳转指令，到statement之前，再次执行。

	case repeatStmt:
		emitComment("-> repeat")
		p1 := t.child[0]
		p2 := t.child[1]
		// 保存循环前的位置
		savedLoc1 := emitSkip(0)
		emitComment("repeat: jump after body comes back here")
		// 执行语句
		cGen(p1)
		// 判断条件
		cGen(p2)
		// 如果符合，跳转到 savedLoc1，即循环前
		emitAbsRM("JEQ", ACCUMULATOR1, savedLoc1)
		emitComment("<- repeat")

对于 if 语句，依次填入的指令为：

判断 expr
若不符合，跳转到 stmt2
执行 stmt1
跳转到stmt2结束
执行 stmt2

	case ifStmt:
		// if <expr> then <stmt1> else <stmt2> end
		// 或 if <expr> then <stmt1> end
		emitComment("-> if")
		p1 := t.child[0]
		p2 := t.child[1]
		p3 := t.child[2]
		// 生成条件表达式的代码
		cGen(p1)
		// 空一个跳转 stmt1 末尾的位置
		savedLoc1 := emitSkip(1)
		emitComment("if: jump to else belongs here")
		// 生成 stmt1 的代码
		cGen(p2)
		// 空一个指令，供跳转到 stmt2 结束
		savedLoc2 := emitSkip(1)
		emitComment("if: jump to end belongs here")
		// 获得 stmt2 的开始位置
		currLoc := emitSkip(0)
		// 回到 expr 判断结束处，写入条件跳转语句
		emitBackup(savedLoc1)
		emitAbsRM("JEQ", ACCUMULATOR1, currLoc)
		emitComment("if: jmp to else")
		// 回到 stmt2 开始处
		emitRestore()
		// 生成 stmt2 语句的代码
		cGen(p3)
		// 获得 stmt2 结束后的位置
		currLoc = emitSkip(0)
		// 回到 stmt1 结束处，无条件跳转到 stmt2 结束处
		emitBackup(savedLoc2)
		emitAbsRM("LDA", PROGRAM_COUNTER, currLoc)
		emitComment("if: jmp to end")
		// 回到 stmt2 结束处
		emitRestore()
		emitComment("<- if")

对于 assign 语句，就是计算表达式的值，查符号表得到内存地址，然后将值存进去：

	case assignStmt:
		// <id> := <expr>
		emitComment("-> assign")
		// 计算表达式的值，存入 ACCUMULATOR1
		cGen(t.child[0])
		// 找到 id 的内存偏移
		loc, _ := lookupSymtab(t.attr)
		// 将表达式的值存入 id 的内存偏移
		emitRM("ST", ACCUMULATOR1, loc, GLOBAL_POINTER)
		emitComment("<- assign")

read和write语句也会使用AC1作为中转，不同的是write计算表达式的值时会隐式地存入AC1，表现倒是相同的：

	case readStmt:
		// read <id>
		emitComment("-> read")
		// 读取输入，存入 ACCUMULATOR1
		emitRO("IN", ACCUMULATOR1, 0, 0)
		loc, _ := lookupSymtab(t.attr)
		// 将输入的值存入 id 的内存偏移
		emitRM("ST", ACCUMULATOR1, loc, GLOBAL_POINTER)
		emitComment("<- read")
	case writeStmt:
		emitComment("-> write")
		// 计算表达式的值，存入 ACCUMULATOR1
		cGen(t.child[0])
		// 将 ACCUMULATOR1 的值输出
		emitRO("OUT", ACCUMULATOR1, 0, 0)
		emitComment("<- write")

表达式

此处每个表达式的结果最后都会存放在AC1寄存器中，这是一个约定用法。

常量表达式最简单，直接使用加载常量的指令，把值存入AC1：

	case constExpr:
		emitComment("-> Const")
		// 将常量存入 ACCUMULATOR1
		emitRM("LDC", ACCUMULATOR1, t.val, 0)
		emitComment("load const")
		emitComment("<- Const")

加载一个变量也只需根据指针将其从内存中读出：

	case idExpr:
		emitComment("-> Id")
		// 找到 id 的内存偏移
		loc, _ := lookupSymtab(t.attr)
		// 将该地址对应的值存入 ACCUMULATOR1
		emitRM("LD", ACCUMULATOR1, loc, GLOBAL_POINTER)
		emitComment("load id value")
		emitComment("<- Id")

在计算一个带运算符（算术运算和比较）的表达式的值时，需要先求出左右子表达式的值。tmpOffset的设置是为了让嵌套执行此处代码时，每一个genExpr的tmpOffset值都是不同的，从而在多层opExpr下能够将左子表达式的临时值存放在不同的位置；否则每次执行都会向同一个位置（即MP）读写内容，从而覆盖外层求出的结果。

	case opExpr:
		emitComment("-> Op")
		// 求左子表达式的值，存入 ACCUMULATOR1
		cGen(t.child[0])
		// 将 ACCUMULATOR1 的值存入内存偏移 tmpOffset
		emitRM("ST", ACCUMULATOR1, tmpOffset, MEMORY_POINTER)
		// 将 tmpOffset 加 1，即指向下一个内存偏移（当然后面存的不能重合了）
		tmpOffset--
		emitComment("op: push left")
		// 求右子表达式的值，存入 ACCUMULATOR1
		cGen(t.child[1])
		tmpOffset++
		// 将左子表达式的值存入 ACCUMULATOR2
		emitRM("LD", ACCUMULATOR2, tmpOffset, MEMORY_POINTER)
		emitComment("op: load left")

算术表达式的求解很简单，惟需注意上面执行完毕后左边对应AC2，右边对应AC1：

		switch t.op {
		case plusToken:
			// AC1 = AC2 + AC1
			emitRO("ADD", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
			emitComment("op +")
		case minusToken:
			// AC1 = AC2 - AC1
			emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
			emitComment("op -")
		case timesToken:
			// AC1 = AC2 * AC1
			emitRO("MUL", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
			emitComment("op *")
		case overToken:
			// AC1 = AC2 / AC1
			emitRO("DIV", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
			emitComment("op /")

小于运算符的情况，如果AC1<AC2，则AC1=0；否则AC1=1。

		case ltToken:
			// AC1 = AC2 - AC1
			emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
			emitComment("op <")
			// 若 AC1<AC2（新 AC1<0），则往后跳两个指令
			emitRM("JLT", ACCUMULATOR1, 2, PROGRAM_COUNTER)
			emitComment("br if true")
			// 若 AC1>=AC2，则 AC1=0
			emitRM("LDC", ACCUMULATOR1, 0, ACCUMULATOR1)
			emitComment("false case")
			// 无条件跳一条指令
			emitRM("LDA", PROGRAM_COUNTER, 1, PROGRAM_COUNTER)
			emitComment("unconditional jmp")
			// 若 AC1<AC2，则 AC1=1
			emitRM("LDC", ACCUMULATOR1, 1, ACCUMULATOR1)
			emitComment("true case")

等于的情况类似，仅当AC1=AC2时AC1=0：

		case eqToken:
			emitRO("SUB", ACCUMULATOR1, ACCUMULATOR2, ACCUMULATOR1)
			emitComment("op ==")
			emitRM("JEQ", ACCUMULATOR1, 2, PROGRAM_COUNTER)
			emitComment("br if true")
			emitRM("LDC", ACCUMULATOR1, 0, ACCUMULATOR1)
			emitComment("false case")
			emitRM("LDA", PROGRAM_COUNTER, 1, PROGRAM_COUNTER)
			emitComment("unconditional jmp")
			emitRM("LDC", ACCUMULATOR1, 1, ACCUMULATOR1)
			emitComment("true case")

This content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.

语法分析

符号表

语义分析

代码生成

语句

表达式

发送评论 编辑评论

推荐文章

发送评论编辑评论