编译器手册.md

编译器手册

文件夹目录说明及编译器使用

这里是这个编译器如何使用的简单说明.

主程序为compiler.py, (目录中compiler_alpha.py为alpha版, 现在已经不能使用.)

输入为工作目录(windows下就是同目录)下的input.c,输入文件的对应目标语言为MiniC,简单来说是阉割版C语言,具体需要看最新版文档. (控制语句必须用大括号括起来)

编译器首先读入代码并格式化(包括去单行/多行注释, 加{}号, 去;号, 分行, 替换变量格式标识符,替换一元右结合运算符号), 格式化的结果输出为code1.txt

之后利用格式化过的代码进行翻译成汇编代码, 输出为code.asm. 中间检测到的错误会被抛出, 即error.txt记录了所有格式化过的错误代码行.(不保证能够正确处理及抛出) 所以如果要定位错误行, 需要将 源代码 — 格式化后的代码 — 错误代码行 三者匹配.

编译器编程思路

说在最前面.. 这次编译器整体的设计思路为: 抛弃lex和yacc, python直接翻译

MiniC简介

这次的编译器的目标语言是MiniC, 与C区别在于精简了大量功能并规定了一些格式. (这也是敢用python硬解的底子) 于是再看一下我们需要处理的语言是什么模样. 这里是MiniC的一个示例代码:

int a;
void delay(int i, int j) {
	int a[10];
	short s;
	char c;
	unsigned char uc;
	unsigned short us;
	unsigned int ui;
	char q;
	short w;
	int e;
	int *p;
	a[1] = 1000;
	while(c>0){ c=c - 1;}
	i = a[5] + 3;
}
int main(void)
{
	int i,j,k[3];
	int key;
	int *LED;
	key=0;
	LED = 0xfffffc60;
	while(1)
	{
		key=key+1;
		*LED=key;
		if(key>100) key=0;
		else if(key>10)key = 1;
		else key=key-3;
		delay(a+5, k[2]);
	}
}

大概就是这种样式. 重点在于它比C更注重规则化: 全局变量定义在所有函数前, 函数内部变量定义必须在代码之前; 定义和赋值必须分开. 另外MiniC支持(unsigned) byte/short/int.

自底向上: asm输出文件分析

首先, 看一下编译出的汇编语言中有哪几个部分:

.stack
.data
.code

.stack

.stack默认为空, 为满足汇编器需求, 需要在.code中生成一句初始化$sp的代码即可:

outputln('addi $29,$0,4000H')

(outputln函数为自定义的文件写入函数, 具体代码为:

outputcode = open('code.asm','w')
def outputln(s):
	outputcode.write(str(s))
	outputcode.write('\n')
	outputcode.flush()

之后不再说明.)

.data

.data需要存放非寄存器类型数据, 分为全局变量和局部变量(函数内定义的变量).

1. 全局变量, 毫无疑问是定义在.data区. 所以只要扫描提取出变量名并列在.data就好. 首先定义一个名为Global的word类型数, 值为之后全局变量占用了多少字节(8位). 之后是全局变量, 为了和之后函数里的变量名区分, 全局变量在汇编.data里的名称定义都是 "Global_ + 原本的变量名". 另外为了支持对齐, 假设不足32位的变量, 会被强制补齐至足够32位的个数.

   举例, 上面的实例代码中, 全局变量为 int a , 最后生成的全局变量在.data中的代码是这个样子:

   .data
   Global .word 4
   Global_a .word 0

2. 函数的局部变量, 与全局变量不同的是, 前8个使用最频繁的局部变量需要分配的是寄存器, 其它才会分配到.data区. 所以先要提取出函数形参和最开始定义的变量, 并扫描整个函数记录变量出现的次数, 选取前8个分配寄存器, 之后的分配到.data区. 比如这个函数:

   int delay(int n){
   	int a[10];
   	char b[3];
   	return 0;
   }  

   实际编译出的效果应为:

   delay .word 44
   delay_a .word 0 0 0 0 0 0 0 0 0 0
   delay_b .byte 0 0 0 0

   有一个叫delay(void)的函数, 里面定义了一个

   int a[10]; char b[3]; 的数组. 注意虽然b[3]定义里长度是3, 但为了32位对齐, 实际会补足32位长度, 即4个.

   ​

.code

.code是程序代码. MiniC代码大致可以分类为三种:

1. 变量定义
2. 普通运算, 包括函数调用
3. 控制语句, 包括if , while (未支持for)

赋值之类思路很简单, 关键是while 循环和if else条件控制. 这里, 编译器和汇编器之间做了一个约定: 编译器中绝不出现实际地址, 全部由标号(Label)代替. 在这里, while循环比较简单, 只要在while语句开始时加一个while_begin_number的Label, 最后加一个j while_begin_number的跳转语句和一个while_end_number 的结束Label, 内部开头加一个判断跳转语句即可. 但if else循环相当不好写. 大致的处理步骤如下:

1. 首先, 不一定有{}号把if-else的语句括起来, 需要你自行处理. 所以第一步就是规则化, 把所有的if else语句变成if() {} else{ if-else }的形式, 这实际变成了一个递归的问题.
2. 递归地生成Label. 这里我无法用语言去描述代码. 总之是根据第一步生成好了的左右{}号来生成Label, 较1.而言应该说是简单多了.

具体请看下面的 编译器的顺序处理流程

类定义

为了方便处理及OOP(Object-oriented programming), 定义了两种类:

Variable类

顾名思义, 该类为函数中变量对应的类.

class Variable(object):
	"""docstring for Variable
		type: 0 : register;   1 : RAM,单独变量,占1单元  n(>1):数组,占n单元
	"""
	def __init__(self, name, vartp):
		super(Variable, self).__init__()
		self.name = name #name in function
		self.vtype = vartp  #variable_types = ['sint08','sint16','sint32','uint08','uint16','uint32']
		self.sizeof = int(vartp[4:6])  # 8, 16, 32

		self.corname = '' # name in .code or register name
		self.type = 0    # 0 : register;   1 : RAM单独变量  n(>1):数组,占n单元

	def generatecode(self):
		if self.type == 1:
			tmp = 32/self.sizeof
			ret = self.corname + ' ' + sizetotype[self.sizeof]
			for i in range(tmp):
				ret += ' 0'   #32对齐
			return 1,ret
		elif self.type > 1:
			cursize = self.sizeof * self.type
			while cursize % 32 != 0:
				cursize += self.sizeof
			num = cursize / 32
			tmp = cursize / self.sizeof
			ret = self.corname + ' ' + sizetotype[self.sizeof]
			for i in range(tmp):
				ret += ' 0'   #32对齐
			return num,ret
		else:
			return 0,''

类的有如下几个属性:

属性	含义
name	实际变量名
vtype	变量类型. 包括sint08,sint16,sint32,uint08,uint16,uint32
sizeof	类型所占空间大小. 包括8,16,32
corname	对应在.data区的名称或对应的寄存器的名称
type	0: 寄存器型变量 1: .data区单独变量 n(n>1): .data区数组型变量

Function类

除去全局变量, MiniC的代码是有一个或多个Funciton组成的. Main函数同样为Function. 故定义Function类将其规范化.

class Function(object):
	def __init__(self, codes):
		super(Function, self).__init__()
		self.codes = []
		for i in codes:
			i = i.strip()
			if i != '':
				self.codes.append(i)

		tmp = self.codes[0]
		name = tmp[tmp.find(' ')+1:tmp.find('(')].strip()
		if name == '':
			throw_error(get_cur_info() + codes[0])
		varstring = tmp[tmp.find('(')+1:tmp.rfind(')')].strip()

		self.name = name
		self.prefix = name + '_'
		self.vtype = self.codes[0][:6]  #variable_types = ['void00','sint08','sint16','sint32','uint08','uint16','uint32']
		self.sizeof = int(self.vtype[4:6])  # 8, 16, 32
		self.params = []

		self.vardict = {}	# varname -> varclass

		if varstring != '' and varstring not in types:
			for x in varstring.split(','):
				x = x.strip()
				tp = x[:6].strip()
				name = x[6:].strip()
				if name.find('[') != -1:
					name = name[:name.find('[')].strip()
				self.params.append((name,tp))

		self.head = codes[0]
		self.vardeclaration = []
		self.realcode = []
		for i in range(2,len(codes)):
			s = self.codes[i]
			if len(s) >= 8 and s[:6] in variable_types and s[6] == ' ':
				continue
			else:
				self.vardeclaration = codes[2:i]
				self.realcode = codes[i:-1]
				break
	def printcode(self):
		outputln('\n\n' + self.name + '_begin:')
		availableVars = self.vardict.copy()
		for i,j in globalVarDict.items():
			if i not in self.vardict:
				availableVars[i] = j

		print '\nBegin##################################### ' + self.name
		print 'self.name = ',self.name
		print 'self.vtype = ',self.codes[0][:6]  #variable_types = ['void00','sint08','sint16','sint32','uint08','uint16','uint32']
		print 'self.params = ',self.params
		self.sizeof = int(self.vtype[4:6])  # 8, 16, 32
		print '%s vardict len:%d'%(self.name,len(self.vardict))
		print '%s availableVars num: %d'%(self.name,len(availableVars))
		for i,j in availableVars.items():
			print 'vars %s -- %s'%(i,j.corname)
		dealCodes(self.name, self.realcode, availableVars, 0)
		rassignr('$v0', '$zero')
		outputln('jr $ra')
		print '\nEnd##################################### ' + self.name

Function类中有如下属性:

属性	含义
name	函数名
codes	全部代码行
prefix	对应的.data区变量定义时加的前缀. 一般为 "函数名_"
vtype	函数返回类型
sizeof	函数返回类型所占空间大小. 包括8,16,32
params	函数参数列表. 存放的是 (参数名,类型) 的二元组
vardict	{参数名->参数类} 的字典
head	函数定义行
vardeclaration	参数定义行列表
realcode	实际执行代码列表

函数通过传给__init__全部的代码行进行初始化, 通过printcode输出全部函数对应的汇编代码.

编译器的顺序处理流程

上面把编译器的约定大致说完了, 这里是具体的工作流程.

1460行之前的代码都是各种定义和函数, 之后才是main函数体. 其实应该用一个__main__函数括起来的, 不过当时还没有用那种代码风格.

读入数据并格式化

""""""""""""""""""""" 读入数据并格式化 """""""""""""""""""""
codes = init_input()
sys.stdout = open('code1.txt', 'w')
for i in codes:
	print i

def init_input():
	sys.stdin = open('input.c', 'r')
	ret = []
	global raw
	ss = ''
	while True:
		try:
			s = raw_input().strip()
			raw.append(s)
			loc = s.find('//')
			if loc != -1:
				s = s[:loc].strip()
			ss += s
		except EOFError:
			break

	while True:
		loc = ss.find('/*')
		if loc == -1:
			break
		pre = ss[:loc]
		aft = ss[loc + 2:]
		loc = aft.find('*/')
		if loc != -1:
			aft = aft[loc + 2:]
		else:
			aft = []
		ss = pre + aft

	tmp = re.search('\\bvoid\\b',ss)
	while tmp:
		i,j = tmp.span()
		ss = ss[:i] + 'void00' + ss[j:]
		tmp = re.search('\\bvoid\\b',ss)

	tmp = re.search('\\bunsigned char\\b',ss)
	while tmp:
		i,j = tmp.span()
		ss = ss[:i] + 'uint08' + ss[j:]
		tmp = re.search('\\bunsigned char\\b',ss)

	tmp = re.search('\\bunsigned short\\b',ss)
	while tmp:
		i,j = tmp.span()
		ss = ss[:i] + 'uint16' + ss[j:]
		tmp = re.search('\\bunsigned short\\b',ss)

	tmp = re.search('\\bunsigned int\\b',ss)
	while tmp:
		i,j = tmp.span()
		ss = ss[:i] + 'uint32' + ss[j:]
		tmp = re.search('\\bunsigned int\\b',ss)

	tmp = re.search('\\bchar\\b',ss)
	while tmp:
		i,j = tmp.span()
		ss = ss[:i] + 'sint08' + ss[j:]
		tmp = re.search('\\bchar\\b',ss)

	tmp = re.search('\\bshort\\b',ss)
	while tmp:
		i,j = tmp.span()
		ss = ss[:i] + 'sint16' + ss[j:]
		tmp = re.search('\\bshort\\b',ss)

	tmp = re.search('\\bint\\b',ss)
	while tmp:
		i,j = tmp.span()
		ss = ss[:i] + 'sint32' + ss[j:]
		tmp = re.search('\\bint\\b',ss)

	while len(ss) > 0:
		# for while if else
		ss = extract_a_part(ss, ret)
	return ret

具体内容包括:

1. 分行, 是以 ; 号和 \n来分行, 并删除;号. 即, 这之后的数据, 只有两种形式: 具体的运算/定义代码, 否则就是 {或} 号.

2. 单行注释直接在读入每行时消除.

3. 多行注释方面, 我犯了一个极其愚蠢的错误, 而且这个错误几乎无法修正: 为了支持多行注释的格式/* xxx */, 我采用了一个蠢办法: 将所有读入行合成一整行, 之后扫描寻找/*子串, 找到后继续向后寻找*/子串. 这种方法虽然可行, 但却严重破坏了代码的行信息, 以至于在之后的错误定位上越改越乱. (姑且, 现在错误定位是这样实现的: 存了一份原始的代码, 之后在代码处理过程中发现错误的时候, 直接将错误行抛出, 最后对所有抛出的代码行, 查找其在原始代码中的位置. 愚蠢的方法, 但别无选择了. )

4. 类型名替换. 这是被坑过一次的事: 初版MiniC手册只要求支持int,所以alpha版代码也就只支持了int; 而后序更新的MiniC手册要求增加对各种长度类型的支持. 为了便利的处理不同类型, 将原本的名称(unsigned) char, short, int 统一替换为swift语言风格的int08, int16, int32. 并根据是否为unsigned类型而添加u和s. 最后类型会被编译器替换为

   ['sint08','sint16','sint32','uint08','uint16','uint32']

   这个6种格式. 当然这些都是编译器做的, 对用户透明. 用户写的时候仍然是标准C风格的定义即可.

5. 运算符替换. 关于指针类型, 直接按照*作为一种右结合的运算, 数据本身作为sint32处理. 同时为了不与乘运算混淆, 所有的指针运算符号* 都被替换为了 $号; 作为单元运算符的负号 - 也被替换为了 `号(以便和二元运算符减号区分).

6. if控制语句的标准化. 因为if else的处理相当麻烦, 所以要统一处理为

   if(){
     //xxx
   }else{
     if(){}
     else{}
   }

   的形式. 其中, else if的处理是递归的, 具体是在这个函数里:

   def extract_a_part(s, ret):
   	if s[0] == '{' or s[0] == '}':
   		ret.append(s[0])
   		s = s[1:].strip()
   		return s
   	if s == '':
   		return ''
   	if re.match('(unsigned )?char |(unsigned )?short |(unsigned )?int ',s):
   		replace = ''
   		if s[0] == 'u':
   			replace += 'u'
   			s = s[9:]
   		else:
   			replace += 's'
   		replace += 'int'
   		if s[:4] == 'char':
   			replace += '08'
   			s = s[4:]
   		elif s[:5] == 'short':
   			replace += '16'
   			s = s[5:]
   		elif s[:3] == 'int':
   			replace += '32'
   			s = s[3:]
   		s = replace + s
   	if re.match('\\bvoid\\b',s):
   		s = 'void00' + s[4:]
   
   	if len(s)>=8 and s[:6] in types:
   		i = 6
   		while i < len(s) and ( s[i] == ' ' or s[i] == '\t' ):
   			i += 1
   		if i < len(s) and s[i] == '*':
   			s = s[:i] + s[i+1:]
   
   	if s[:3] == 'for':
   		s = s[3:].strip()
   		tmp = get_parenthesis_content(s)
   		ret.append('for' + tmp[0])
   		s = tmp[1]
   		if s[0] != '{':
   			ret.append('{')
   			s = extract_a_part(s, ret)
   			ret.append('}')
   		return s
   	if s[:5] == 'while':
   		s = s[5:].strip()
   		tmp = get_parenthesis_content(s)
   		ret.append('while' + tmp[0])
   		s = tmp[1]
   		if s[0] != '{':
   			ret.append('{')
   			s = extract_a_part(s, ret)
   			ret.append('}')
   		return s
   	elif s[:2] == 'if':
   		s = s[2:].strip()
   		tmp = get_parenthesis_content(s)
   		ret.append('if' + tmp[0])
   		s = tmp[1]
   		if s[0] != '{':
   			ret.append('{')
   			s = extract_a_part(s, ret)
   			ret.append('}')
   
   		if re.match('else[ \\t]+if',s):
   			tmp = s.find('if')
   			s = s[tmp:]
   			ret.append('else')
   			ret.append('{')
   			s = extract_a_part(s,ret)
   			ret.append('}')
   		elif s[:4] == 'else':
   			s = s[4:].strip()
   			ret.append('else')
   			if s[0] != '{':
   				ret.append('{')
   				s = extract_a_part(s, ret)
   				ret.append('}')
   		return s
   
   	i = 0
   	for c in s:
   		if c == ';':
   			if i:
   				ret.append(s[:i])
   			s = s[i + 1:]
   			break
   		elif c == '{' or c == '}':
   			if i:
   				ret.append(s[:i])
   			ret.append(s[i])
   			s = s[i + 1:]
   			break
   		i += 1
   	return s

   该函数递归处理一段程序代码, 将其分块并适当添加{}号, 参数ret存放所有处理过的代码.

代码分块, 初始化Function类

""""""""""""""""""""""""""""""""" 分块,初始化function类 开始 """""""""""""""""""""""""""""""""
i = 0
for i in range(len(codes)):
	if codes[i].find('(') != -1:
		globalCodes = codes[:i]
		codes = codes[i:]
		break

while len(codes) > 0:
	block = codes[0:2]
	codes = codes[2:]
	num = 1
	while num != 0 and len(codes)>=1:
		tmp = codes[0].strip()
		if tmp == '':
			continue
		block.append(tmp)
		if tmp == '{':
			num += 1
		elif tmp == '}':
			num -= 1
		codes = codes[1:]
	func = Function(block)
	functions.append(func)
	while len(codes)>0 and codes[0].strip == '':
		codes = codes[1:]

for i in range(len(functions)):
	if functions[i].name == '':
		functions[i],functions[len(functions)-1] = swap(functions[i],functions[len(functions)-1])
		functions = functions[:-1]
	else:
		functionDict[functions[i].name] = functions[i]
	if i >= len(functions)-1:
		break

if functions[len(functions)-1].name != 'main':
	for i in range(len(functions)):
		if functions[i].name == 'name':
			functions[i],functions[len(functions)-1] = swap(functions[i],functions[len(functions)-1])
			break
for f in functions:
	functionNameList.append(f.name)
	functionReturnType[f.name] = f.vtype

for f in functions:
	print f.name
	for i,j in f.vardict.items():
		print '\t',j.name

""""""""""""""""""""""""""""""""" 分块,初始化function类 结束 """""""""""""""""""""""""""""""""
##此时var还未填充

通过 ( 号来判断第一个函数行位置, 并认定之前的代码为全局变量定义. 之后通过左右大括号来确定每一个函数的函数体, 并将main函数放到所有函数的末尾. (只是强迫症) 类的初始化参数为类的全部代码行, 初始化时函数抽取出函数头, 参数列表和实际代码等数据. 至此输入和初始化完毕, 接下来是输出.

.DATA输出

.data区数据, 包括全局变量和函数的临时变量. 全局变量的处理如之前所述, 为方便识别全体在.data区加上了前缀 Global_ .

函数的临时变量同样如之前所述, 计算了之后变量出现的次数并排序, 前8个分配给寄存器, 之后的再.data中开辟空间. 不过需要注意的是如果是数组类型则必定放在.data区, 无论数组大小是多少. 另外函数的形参同样是它自己 定义的 参数, 不能落下.

""""""""""""""""""""""""""""""""" .DATA输出开始 """""""""""""""""""""""""""""""""
outputln('.stack')
outputln('.data')

globalVarList,nouse,globalArray = scanVarible(globalCodes, globalCodes)
for name,tp in globalVarList:
	tmp = Variable(name,tp)
	tmp.corname = prefix_global + name
	tmp.type = 1
	globalVarDict[name] = tmp
for array,tp in globalArray:
	name = array[:array.find('[')].strip()
	num = int(array[ array.find('[') + 1 : array.rfind(']') ].strip())
	tmp = Variable(name, tp)
	tmp.corname = prefix_global + name
	tmp.type = num
	globalVarDict[name] = tmp
tmp = []
num = 0
for i,j in globalVarDict.items():
	print '\t',j.name,j.vtype,j.sizeof,j.type
	tmpnum,tmps = j.generatecode()
	if tmpnum == 0:
		continue
	num += tmpnum
	tmp.append(tmps)
outputln('Global .word ' + str(num * 4))
for s in tmp:
	outputln(s)

""""""""""""""""""""" 全局变量输出完毕 """""""""""""""""""""

for f in functions:
	print 'init functino %s'%(f.name)
	f.varlist,numdict,arraylist = scanVarible([f.head] + f.vardeclaration, f.realcode)
	print 'f.varlist size:%d, numdict size:%d'%(len(f.varlist),len(numdict))

	for array,tp in arraylist:
		name = array[:array.find('[')].strip()
		num = int(array[array.find('[') + 1:array.rfind(']')].strip())
		tmp = Variable(name, tp)
		tmp.corname = f.prefix + name
		tmp.type = num
		f.vardict[name] = tmp

	numlist = sorted(numdict.items(), key = lambda x:x[1], reverse = True)
	if len(numlist)<= 8:
		for i in range(len(numlist)):
			name,tp = numlist[i][0]
			tmp = Variable(name,tp)
			tmp.corname = '$s' + str(i)
			tmp.type = 0
			f.vardict[name] = tmp
	else:
		for i in range(8):
			name,tp = numlist[i][0]
			tmp = Variable(name, tp)
			tmp.corname = '$s' + str(i)
			tmp.type = 0
			f.vardict[name] = tmp
		for (name,tp),num in numlist[8:]:
			tmp = Variable(name, tp)
			tmp.corname = f.prefix + name
			tmp.type = 1
			f.vardict[name] = tmp
	tmp = []
	num = 0
	for i,j in f.vardict.items():
		tmpnum,tmps = j.generatecode()
		if tmpnum == 0:
			continue
		num += tmpnum
		tmp.append(tmps)
	outputln(f.name + ' .word ' + str(num * 4))
	for s in tmp:
		outputln(s)
	outputln('')

	print 'f.vardict size:%d\n'%(len(f.vardict))

""""""""""""""""""""""""""""""""" .DATA输出结束 """""""""""""""""""""""""""""""""

.CODE输出

首先是对$ra和$sp(即$29)的初始化, 之后要求直接跳到main_begin, 即main函数开始标号处. 之后依序输出各个函数翻译过的代码, 结束.

""""""""""""""""""""""""""""""""" .CODE输出开始 """""""""""""""""""""""""""""""""
outputln('\n.code')
outputln('START:')
outputln('addi $ra,$zero,END')
outputln('addi $29,$0,4000H')
outputln('j main_begin\n')

for f in functions:
	f.printcode()

outputln('\nEND:')
outputln('END START')

""""""""""""""""""""""""""""""""" .CODE输出结束 """""""""""""""""""""""""""""""""

printcode()函数做了什么?

其实printcode函数的具体代码核心部分如下:

def printcode(self):
    outputln('\n\n' + self.name + '_begin:')
    availableVars = self.vardict.copy()
    for i,j in globalVarDict.items():
        if i not in self.vardict:
            availableVars[i] = j
    self.sizeof = int(self.vtype[4:6])  # 8, 16, 32
    dealCodes(self.name, self.realcode, availableVars, 0)
    rassignr('$v0', '$zero')
    outputln('jr $ra')

即, 首先输出 函数名_begin 标号, 之后初始化变量词典. 这个词典包括全部内部定义的变量+全局变量中变量名不重复的变量. (这里要注意必须用python的.copy()生成新的dict, 我就因为传指针搞得很惨.) 最后添加的

rassignr('$v0', '$zero')

outputln('jr $ra')

是为了防止函数本身没有写return函数而不跳回之前的调用位置, 这时候默认返回0.

中间所有的代码生成是由dealCodes函数完成.

dealCodes()函数做了什么?

dealCodes具体的工作就是判断下每条语句的类型, 是if while控制语句, 还是return语句, 还是普通的计算语句. 对于if/while这样的准函数 , 即本身也有一个 '体' 的控制语句, 同样是递归处理.

def dealCodes(funcname, codes, corvar, loopnum):
	for i,j in corvar.items():
		print i + ':' + j.corname
	print ''

	dealedLineNum = -1
	for linenum in range(len(codes)):
		outputln('')
		if linenum <= dealedLineNum:
			continue
		s = codes[linenum].strip()
		if s == '{' or s == '}' or s == '':
			continue

		if re.match('^return\\b',s):
			tmp = s[6:].strip()
			if tmp != '':
				dealExpression(tmp, '$v0', funcname, corvar)
				#throw_error(get_cur_info() + 'tmp:'+tmp)
			outputln('jr $ra')
			pass
		elif re.match('^while(.+)$',s):
			beginLabel = funcname + '_while_start_' + str(loopnum)
			endLabel = funcname + '_while_end_' + str(loopnum)
			loopnum += 1
			state = s[s.find('(')+1:s.rfind(')')].strip()
			body,curnum = findCurlyContent(codes[linenum:])
			dealedLineNum = linenum + curnum
			if state == '':
				throw_error(get_cur_info() + s)
				continue

			outputln(beginLabel + ':')
			dealExpression(state,'$t0', funcname, corvar)
			outputln('beq $t0,$zero,' + endLabel)

			dealCodes(funcname, body, corvar, loopnum)

			outputln('j ' + beginLabel)
			outputln(endLabel + ':')
			outputln('')
			pass
		elif re.match('^if(.+)$',s):
			ifbeginLabel = funcname + '_if_start_' + str(loopnum)
			ifendLabel = funcname + '_if_end_' + str(loopnum)
			allendLabel = funcname + '_ifelse_end_' + str(loopnum)
			state = s[s.find('(')+1:s.rfind(')')].strip()
			body,curnum = findCurlyContent(codes[linenum:])
			dealedLineNum = linenum + curnum
			if state == '':
				throw_error(get_cur_info() + s)
				continue

			outputln(ifbeginLabel + ':')
			dealExpression(state,'$t0', funcname, corvar)
			outputln('beq $t0,$zero,' + ifendLabel)

			dealCodes(funcname, body, corvar, loopnum)
			outputln('j ' + allendLabel)
			outputln(ifendLabel + ':')
			outputln('')

			if dealedLineNum + 1 < len(codes) and codes[dealedLineNum + 1].strip() == 'else':
				elsebeginLabel = funcname + '_else_start_' + str(loopnum)
				elseendLabel = funcname + '_else_end_' + str(loopnum)
				body,curnum = findCurlyContent(codes[dealedLineNum + 1:])
				dealedLineNum += curnum
				if state == '':
					throw_error(get_cur_info() + s)
					continue

				outputln(elsebeginLabel + ':')

				dealCodes(funcname, body, corvar, loopnum + 1)

				outputln(elseendLabel + ':')

			outputln(allendLabel + ':')
			outputln('')
			loopnum += 1
			pass
		elif re.match('^for(.*;.*;.*)$',s):
			pass
		else:# 赋值语句或单条表达式或函数
			dealExpression(s,'$v1', funcname, corvar)
			pass

打个比方的话, dealCodes函数就是一台电脑的BIOS, 真正的大头, 也就是操作系统是之后调用的dealExpression函数.

编译器的核心——dealExpression()函数

dealExpression函数是整个编译器的准核心. 一切bug都产生与此并消灭于此. 现在这里的代码连作者本人都很难看懂.

整个代码的大意是根据其所在的函数 prefuncname, 及对应的变量表corvar, 处理运算代码exp, 并将值保存到saveto寄存器里. 注意, 即使是 a = b + 1这样的语句也是有返回值的, 返回值就是a的值. 所以本质上a = b + 1 和 b+1 是没有任何区别的. 等号也只是一个普通的二元运算符而已. (虽然处理的时候分开处理了)

具体代码如下:

def dealExpression(exp, saveto, prefuncname, corvar):
	parts = toParts(exp, prefuncname, corvar)
	suffix = midToSuffix(parts)
	ansvtype = ''

	if len(suffix) == 0:
		print 'NoSuffix'
	for i in suffix:
		print 'suffix:'
		print i[0],'#',i[1],'#',i[2]
	print '\n'

	##calc mid and save to saveto

	stack = []
	failFlag = 0
	print 'dealE begin: ' + exp
	for i,tp,vtype in suffix:
		print 'i,tp,vtype:',i,tp,vtype
		if tp == 'function' or tp == 'array' or tp == 'const' or tp == 'variable' or tp == 'port':
			stack.append((i,tp,vtype))
		elif tp == 'symbol' and operation_units[i] == 2:
			r = stack.pop()
			l = stack.pop()
			print 'r:',r
			print 'l:',l

			rs = '$a3'
			if r[1] == 'register': ##if the tp is register, it must be a value calculated and pushed before
									##but the value in reg may be replaced, so we must pop from stack to get the value
				outputln('POP ' + rs)
			else:
				if not assignr(r,rs,prefuncname, corvar):
					print 'error: if not assignr(r,rs,prefuncname, corvar):'
					failFlag = throw_error(get_cur_info() + exp)
					break


			if i in assign_operation:
				ansvtype = rassign((rs, r[2]), l, prefuncname, corvar)
				if ansvtype == '':
					failFlag = throw_error(get_cur_info() + exp)
					break
				if not rassignrWithStyle(saveto, rs, l[2], r[2]):
					failFlag = throw_error(get_cur_info() + exp)
					break
			else:
				ls = '$a2'
				if l[1] == 'register':
					outputln('POP ' + ls)
				else:
					if not assignr(l,ls,prefuncname, corvar):
						failFlag = throw_error(get_cur_info() + exp)
						break
				ansvtype = calc2((ls,l[2]),i,(rs,r[2]),saveto) ##这样是无法写回数据的. 只能把右值assign给寄存器. 左值不行

			stack.append((saveto,'register',ansvtype))
			outputln('PUSH ' + saveto)
		elif i == '$':
			#需要把所有指针类型转成对register的解析
			l = stack.pop()
			print '$l:',l
			if l[1] == 'const':
				if not assignr(l,saveto,prefuncname,corvar):
					failFlag = throw_error(get_cur_info() + exp)
					print get_cur_info() + 'pointer: const to reg failed'
				pass
			outputln('PUSH ' + saveto)
			stack.append((saveto,'port','sint32'))
			pass
		elif tp == 'symbol' and operation_units[i] == 1:
			l = stack.pop()
			ls = '$a2'
			if l[1] == 'register':
				outputln('POP ' + ls)
			else:
				assignr(l,ls,prefuncname, corvar)
			print 'calc1:',ls,l[2],i,saveto	
			ansvtype = calc1((ls,l[2]),i,saveto)
			stack.append((saveto,'register',ansvtype))
			outputln('PUSH ' + saveto)
		else:
			failFlag = throw_error(get_cur_info() + exp)
			break


	print 'dealE end len:%d'%(len(stack))

	if not failFlag:
		if len(stack) == 0:
			for i,j in corvar.items():
				print 'i,j:',i,j.corname
			print 'exp:',exp
		print 'stack[0]:',stack[0]
		i,tp,vtype = stack[0]

		if tp == 'register':
			outputln('POP ' + saveto)
		else:
			assignr(stack[0], saveto, prefuncname, corvar)
		return stack[0][2]
	else:
		for i in stack:
			if i[1] == 'register':
				outputln('POP $t0')
		return 'NoVtype'

函数的工作流程为:

1. 将exp分块. 利用了toParts函数

   #@call  string, prefuncname, corvar
   #@return  [(a_part, left_string, part_type,  part_vtype)]
   def toParts(s, prefuncname, corvar):
   	ret = []
   	while len(s) > 0:
   		tmp = readapart(s, prefuncname, corvar)
   		if tmp[0] != '':
   			ret.append((tmp[0],tmp[2],tmp[3]))
   		s = tmp[1].strip()
   	for i in range(len(ret)):
   		if ret[i][0] == '-':
   			if i == 0 or ret[i-1][0] == '(' or ret[i-1][1] == 'symbol':
   				ret[i] = ('`',ret[i][1],ret[i][2])
   		if ret[i][0] == '+':
   			if i == 0 or ret[i-1][0] == '(' or ret[i-1][1] == 'symbol':
   				ret = ret[:i] + ret[i+1:]
   		if ret[i][0] == '*':
   			if i == 0 or ret[i-1][0] == '(' or ret[i-1][1] == 'symbol':
   				ret[i] = ('$',ret[i][1],ret[i][2])
   	return ret

   返回值类型为list, 内部是每一部分的( 代码, 类型, 值类型 ), 类型包括 function/array/const/variable/port, 值类型为[u/s]int[08|16|32].

2. 中缀转后缀. 为了处理中缀运算, 利用逆波兰表达式, 转成后缀之后顺序处理.

   逆波兰算法:

   将中缀表达式转换成后缀表达式算法：

   1. 从左至右扫描一中缀表达式。
   2. 若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
   3. 若读取的是运算符
      1. 该运算符为左括号"("，则直接存入运算符堆栈。
      2. 该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
      3. 该运算符为非括号运算符：
         1. 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
         2. 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
         3. 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。
      4. 当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。

    逆波兰表达式求值算法：

   1. 循环扫描语法单元的项目。
   2. 如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
   3. 如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
   4. 如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
   5. 将运算结果重新压入堆栈。
   6. 重复步骤2-5，堆栈中即为结果值。

   ​

   中缀转后缀代码如下:

   def midToSuffix(l):
   	ret = []
   	symbols = [('#','NoType','NoVtype')]
   	for i,tp,vtype in l:
   		if tp == 'function' or tp == 'array' or tp == 'const' or tp == 'variable' or tp == 'port':
   			ret.append((i,tp,vtype))
   		elif i == '(':
   			symbols.append((i,tp,vtype))
   		elif i == ')':
   			tmp = symbols.pop()
   			while tmp[0] != '(':
   				ret.append(tmp)
   				tmp = symbols.pop()
   		else:
   			if symbols[-1][0] == '(':
   				symbols.append((i,tp,vtype))
   			elif priority[i] <= priority[symbols[-1][0]]:
   				symbols.append((i,tp,vtype))
   			else:
   				while priority[i] > priority[symbols[-1][0]]:
   					ret.append(symbols.pop())
   				symbols.append((i,tp,vtype))
   	for tmp in reversed(symbols[1:]):
   		ret.append(tmp)
   	return ret

   后面的部分是对后缀表达式的计算. 真正的计算只有碰到1元或2元运算符时才会出现. 运算的处理思路为: 将运算用到的 元 通过assignr()赋给临时寄存器, 临时寄存器运算并将结果写回saveto寄存器. 具体请看代码旁边的注释. 解释太麻烦.

   ​

函数(包括递归)的处理

关于函数的处理, 虽然它本身也是属于上面的那部分, 但因为很重要单独提出来另说. 函数的调用, 其实就是将一个函数的返回值赋给一个寄存器, 所以核心部分在assignr这么一个方法里.

#assign the value in x to reg
#@return  successful
def assignr(x , reg, prefuncname, corvar):
	# x[0] : name x[1] : type   x[2] : variable_type (['void00','sint08','sint16','sint32','uint08','uint16','uint32'])
	# tp == 'function' or tp == 'array' or tp == 'const' or tp == 'variable' or tp == 'port':
	name = x[0]
	tp = x[1]
	vtype = x[2]
	print 'assignr ',x,reg
	if tp == 'function':
		##prefuncname 调用  x[0] : funcName
		##corvar      ---  functionDict[funcName].vardict
		##params      传给  functionDict[funcName].params
		funcName = name[:name.find('(')].strip()
		params = name[name.find('(')+1:name.rfind(')')].strip()
		if params == '':
			params = []
		else:
			params = [x.strip() for x in params.split(',')]

		if len(params) != len(functionDict[funcName].params):
			throw_error(get_cur_info() + x)
			return False

		outputln('PUSHA ##'+prefuncname)
		f = functionDict[funcName]
		##开始传参数
		for i in range(len(params)):
			here = params[i]
			aimName, aimVarType = f.params[i]
			aimRealName = f.vardict[aimName].corname
			if here in corvar and corvar[here].type > 1 and f.vardict[aimName].type > 1: #传递整个数组
				hereRealName = corvar[here].corname
				hereVarType = corvar[here].vtype
				size = f.vardict[aimName].type
				for i in range(size):
					readArrayInData('$a0',hereRealName,hereVarType,i)
					saveToArrayInData('$a0',aimRealName,aimVarType,i)
				continue
			elif here in corvar and corvar[here].type > 1 or f.vardict[aimName].type > 1:
				throw_error(get_cur_info() + x)
				rassignr(reg, '$zero')
				return
			else: ##aim 必定是0 - reg, 1 - 内存的单个变量两种形式;
				ansvtype = dealExpression(here, '$a0', prefuncname, corvar)
				var = f.vardict[aimName]
				print 'func: aimName:' + aimName,'var:'+aimRealName, ansvtype
				if var.type == 0:
					rassignrWithStyle(aimRealName, '$a0', var.vtype, ansvtype)
				elif var.type == 1:
					saveToArrayInData('$a0', aimRealName, aimVarType, 0)
				print 'func:var assign end'
		#函数执行
		outputln('jal ' + funcName + '_begin')
		#执行结束, 结果存于$v0

		outputln('POPA ##' + prefuncname) #PUSHA, POPA操作不能动$v的值
		rassignr('$v0', reg)
	elif tp == 'array':
		arrayName = x[0][:name.find('[')].strip()
		param = name[name.find('[')+1:name.rfind(']')].strip()
		dealExpression(param, '$a0', prefuncname, corvar)
		realArrayName = corvar[arrayName].corname
		readArrayInData(reg, realArrayName, vtype, '$a0')
	elif tp == 'const': # vtype must be sint32
		exp = x[0]
		realnum = 0
		if exp.find('x') != -1:
			realnum = int(exp,16)
		else:
			realnum = int(exp,10)
		if abs(realnum) <= 65535:
			outputln('ori %s,$zero,%s'%(reg,exp))
		else:
			pre = (realnum >> 16) & ((1 << 16) - 1)
			aft = realnum & ((1 << 16) - 1)
			pres = ''
			afts = ''
			for i in range(16):
				pres += str(pre & 1)
				pre >>= 1
				afts += str(aft & 1)
				aft >>= 1
			pre = int(pres[::-1],2)
			aft = int(afts[::-1],2)
			outputln('ori %s,$zero,%d'%(reg,pre))
			outputln('sll %s,%s,16'%(reg,reg))
			outputln('ori %s,$zero,%d'%(reg,aft))
	elif tp == 'variable':
		var = corvar[name]
		if var.type == 0:
			rassignr(reg, var.corname)
		elif var.type == 1:
			if vtype == 'sint08':
				outputln('lb %s,%s(%s)'%(reg, var.corname, '$zero'))
				pass
			elif vtype == 'uint08':
				outputln('lbu %s,%s(%s)'%(reg, var.corname, '$zero' ))
				pass
			elif vtype == 'sint16':
				outputln('lh %s,%s(%s)'%(reg, var.corname, '$zero' ))
				pass
			elif vtype == 'uint16':
				outputln('lhu %s,%s(%s)'%(reg, var.corname, '$zero' ))
				pass
			elif vtype.strip() == 'sint32' or vtype.strip() == 'uint32':
				outputln('lw %s,%s(%s)'%(reg, var.corname, '$zero'))
			else:
				throw_error(get_cur_info() + name)
				rassignr(reg, '$zero')
			pass
	elif tp == 'port':
      	outputln('POP ' + reg)
		outputln('lw %s,0(%s)'%(reg,name))
	else:
		throw_error(get_cur_info() + x[0])
		rassignr(reg, '$zero')
	return True

和汇编器协商, 自定义了PUSHA/POPA这么一个伪代码, 功能是将所有寄存器+所在函数所有变量(寄存器型+.data型)全部push/pop到栈里. 这样, 在调用一个函数时, 首先PUSHA, 之后传值, 跳转到函数开头, return到调用函数处, POPA恢复现场. 一切完美. 递归只是一种特殊的函数调用, 没有什么特别的.

注意, 在生成PUSHA命令的时候, 编译器不仅仅输出PUSHA, 同时在后面空了一个空格后, 输出这么一条注释: ##函数名. (函数名即为当前所在函数的函数名); POPA同理. 比如:

PUSHA ##main

这样, 汇编器在识别出PUSHA/POPA之后, 读取后面的注释就可以知道当前所在函数的函数名, 同理也就知道了.data中该函数的入口位置,(还记得我们的这次实现中最讨巧的地方么? .data区的变量都是按照函数簇集的, 在每块函数所属的变量前都加了一个新的变量, 变量名为函数名, 值为该函数之后所占.data区的字节(8位大小)个数. ) 读取该位置的值就知道了该函数在.data里占用的大小, 继续向后读取该大小的8位数并push到栈里即可. 这样函数的递归就可以实现了.

指针/端口的处理

在本编译器中, 指针是一种特殊的运算. 指针类型的数据, 比如 int *a 这种, 仅仅是在定义时的特殊处理, 编译器内部其实将其解析成了int a类型. 因为真正是端口操作时, 运算还需要*操作符. 所以, *操作符可以看成是1元右结合运算符, 当它出现时, 提取星号和一个操作数, 并将其值赋给一个寄存器, 类型设为port, 重新压回堆栈. 之后出现赋值时直接sw|lw即可.

强制类型转换

每条语句的处理, 最后都可以化简为两种运算: 单元运算或二元运算. 单元运算包括 非, 负, 否, 指针; 其它运算,包括赋值运算都归为2元运算. 所以通过两个函数来处理即可. 因为涉及不同位数和unsigned类型, 里面同样有各种坑, 比如一个未越界但满32位的uint32 减一个未越界的sint32. 这时候因为要把uint转为sint来处理, 所以会造成越界, 但语义上其实结果不应该越界. 所以必须仍然按照uint判断正负值并计算, 最后再根据正负值转为回sint.

写在最后

alpha版历时一周, 每日从早9点写到早2点. 虽不健康, 自有其乐趣. 后发现被MiniC要求版本坑, 更新beta版, 大概3,4日左右. 其中两个calc就花了1天. 最后验收之前发现大量bug, 一路从1.0改到2.0, 直到验收完之后现在在更新手册时又发现了指针bug和传数组bug... 总之能改的都改了.

P.S. 写文档时发现, 陪伴了2年的RMP屏幕出现了亮斑..保修期已过..