编译原理实验：目标代码的生成

版权所有南京大学计算机科学与技术系许畅等2015版835.目标代码生成本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIMSimulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。5.1实验内容5.1.1实验要求为了完成实验四，我们建议你首先下载并安装SPIMSimulator用于对生成的目标代码进行检查和调试，SPIMSimulator的官方下载地址为：~larus/spim.html。这是由原Wisconsin-Madison的JameLarus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍有关SPIMSimulator的使用方法。你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。“正确”是指该汇编代码在SPIMSimulator（命令行或Qt版本均可）上运行结果正确。因此，以下几个方面不属于检查范围：1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIMSimulator中的正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即MIPS32汇编代码）能运行正确。版权所有南京大学计算机科学与技术系许畅等2015版84当然，不检查并不代表不重要。我们建议你试着去遵守MIPS32中的各种约定，否则你的程序生成的目标代码在SPIMSimulator中运行时可能会出现一些意想不到的错误。另外，实验四对作为输入的C源代码有如下的假设：1)假设1：输入文件中不包含任何词法、语法或语义错误。2)假设2：不会出现注释、八进制或十六进制整型常数、浮点型常数或者变量。3)假设3：整型常数都在16bits位的整数范围内，也就是说你不必考虑如果某个常数无法在addi等包含立即数的指令中表示时该怎么办。4)假设4：不会出现类型为结构体或高维数组（高于1维的数组）的变量。5)假设5：所有的变量均不重名，变量的存储空间都放到该变量所在的函数的活动记录中。6)假设6：任何函数参数都只能是简单变量，也就是说数组和结构体不会作为参数传入某个函数中。7)假设7：函数不会返回结构体或数组类型的值。8)假设8：函数只会进行一次定义（没有函数声明）。在进行实验四之前，请阅读后面的实验指导部分，以确保你已经了解MIPS32汇编语言以及SPIMSimulator的使用方法，这些内容是你顺利完成实验四的前提。5.1.2输入格式你的程序的输入是一个包含C源代码的文本文件，你的程序需要能够接收一个输入文件名和一个输出文件名作为参数。例如，假设你的程序名为cc、输入文件名为test1.cmm、输出文件名为out.s，程序和输入文件都位于当前目录下，那么在Linux命令行下运行./cctest.cmmout.s即可将输出结果写入当前目录下名为out.s的文件中。5.1.3输出格式实验四要求你的程序将运行结果输出到文件。对于每个输入文件，你的程序应当输出相应的MIPS32汇编代码。我们将使用SPIMSimulator对你输出的汇编代码的正确性进行测试，任何能被SPIMSimulator执行并且结果正确的输出都将被接受。5.1.4测试环境你的程序将在如下环境中被编译并运行：1)GNULinuxRelease:Ubuntu12.04,kernelversion3.2.0-29；2)GCCversion4.6.3；3)GNUFlexversion2.5.35；4)GNUBisonversion2.5；版权所有南京大学计算机科学与技术系许畅等2015版855)QtSPIMversion9.1.9。一般而言，只要避免使用过于冷门的特性，使用其它版本的Linux或者GCC等，也基本上不会出现兼容性方面的问题。注意，实验四的检查过程中不会去安装或尝试引用各类方便编程的函数库（如glib等），因此请不要在你的程序中使用它们。5.1.5提交要求实验四要求提交如下内容（同实验一）：1)Flex、Bison以及C语言的可被正确编译运行的源程序。2)一份PDF格式的实验报告，内容包括：a)你的程序实现了哪些功能？简要说明如何实现这些功能。清晰的说明有助于助教对你的程序所实现的功能进行合理的测试。b)你的程序应该如何被编译？可以使用脚本、makefile或逐条输入命令进行编译，请详细说明应该如何编译你的程序。无法顺利编译将导致助教无法对你的程序所实现的功能进行任何测试，从而丢失相应的分数。c)实验报告的长度不得超过一页！所以实验报告中需要重点描述的是你的程序中的亮点，是你认为最个性化、最具独创性的内容，而相对简单的、任何人都可以做的内容则可不提或简单地提一下，尤其要避免大段地向报告里贴代码。实验报告中所出现的最小字号不得小于五号字（或英文11号字）。5.1.6样例实验四无选做要求，因此下面只列举必做内容的样例。请仔细阅读样例，以加深对实验要求以及输出格式要求的理解。样例1：输入：1intmain()2{3inta=0,b=1,i=0,n;4n=read();5while(in)6{7intc=a+b;8write(b);9a=b;10b=c;11i=i+1;12}13return0;14}输出：该样例程序读入一个整数n，然后计算并输出前n个Fibonacci数的值。将其翻译为一段能在SPIMSimulator中执行的正确的目标代码可以是这样的：版权所有南京大学计算机科学与技术系许畅等2015版861.data2_prompt:.asciizEnteraninteger:3_ret:.asciiz\n4.globlmain5.text6read:7li$v0,48la$a0,_prompt9syscall10li$v0,511syscall12jr$ra1314write:15li$v0,116syscall17li$v0,418la$a0,_ret19syscall20move$v0,$021jr$ra2223main:24li$t5,025li$t4,126li$t3,027addi$sp,$sp,-428sw$ra,0($sp)29jalread30lw$ra,0($sp)31addi$sp,$sp,432move$t1,$v033move$t2,$t134label1:35blt$t3,$t2,label236jlabel337label2:38add$t1,$t5,$t439move$a0,$t440addi$sp,$sp,-441sw$ra,0($sp)42jalwrite43lw$ra,0($sp)44addi$sp,$sp,445move$t5,$t446move$t4,$t147addi$t1,$t3,148move$t3,$t149jlabel150label3:51move$v0,$052jr$ra图15.样例1汇编代码的运行结果。版权所有南京大学计算机科学与技术系许畅等2015版87该汇编代码在命令行SPIMSimulator中的运行结果如图15所示（输入7，则输出前7个Fibonacci数）。样例2：输入：1intfact(intn)2{3if(n==1)4returnn;5else6return(n*fact(n-1));7}89intmain()10{11intm,result;12m=read();13if(m1)14result=fact(m);15else16result=1;17write(result);18return0;19}输出：该样例程序读入一个整数n，然后计算并输出n!的值。将其翻译为一段能在SPIMSimulator中执行的正确的目标代码可以是这样的：1.data2_prompt:.asciizEnteraninteger:3_ret:.asciiz\n4.globlmain5.text6read:7li$v0,48la$a0,_prompt9syscall10li$v0,511syscall12jr$ra1314write:15li$v0,116syscall17li$v0,418la$a0,_ret19syscall20move$v0,$021jr$ra2223main:24addi$sp,$sp,-425sw$ra,0($sp)26jalread27lw$ra,0($sp)28addi$sp,$sp,429move$t1,$v030li$t3,131bgt$t1,$t3,label632jlabel733label6:34move$a0,$t1版权所有南京大学计算机科学与技术系许畅等2015版8835addi$sp,$sp,-436sw$ra,0($sp)37jalfact38lw$ra,0($sp)39addi$sp,$sp,440move$t2,$v041jlabel842label7:43li$t2,144label8:45move$a0,$t246addi$sp,$sp,-447sw$ra,0($sp)48jalwrite49lw$ra,0($sp)50addi$sp,$sp,451move$v0,$052jr$ra5354fact:55li$t4,156beq$a0,$t4,label157jlabel258label1:59move$v0,$a060jr$ra61label2:62addi$sp,$sp,-863sw$a0,($sp)64sw$ra,4($sp)65sub$a0,$a0,166jalfact67lw$a0,($sp)68lw$ra,4($sp)69addi$sp,$sp,870mul$v0,$v0,$a071jr$ra该汇编程序在QtSPIM中的运行结果如图16所示（输入7，输出5040）。除了上面给的两个样例以外，你的程序要能够将其它符合假设的C源代码翻译为目标代码，我们将通过检查目标代码是否能在SPIMSimulator上运行并得到正确结果来判断你的程序的正确性。5.2实验指导在实验三中，我们已经将输入程序翻译为涉及相当多底层细节的中间代码。这些中间代码在很大程度上已经可以很容易地翻译成许多RISC的机器代码，不过仍然存在以下问题：1)中间代码与目标代码之间并不是严格一一对应的。有可能某条中间代码对应多条目标代码，也有可能多条中间代码对应一条目标代码。图16.样例2汇编代码的运行结果。版权所有南京大学计算机科学与技术系许畅等2015版892)中间代码中我们使用了数目不受限的变量和临时变量，但处理器所拥有的寄存器数量是有限的。RISC机器的一大特点就是运算指令的操作数总是从寄存器中获得。3)中间代码中我们并没有处理有关函数调用的细节。函数调用在中间代码中被抽象为若干条ARG语句和一条CALL语句，但在目标机器上一般不会有专门的器件为我们进行参数传递，我们必须借助于寄存器或栈来完成