5. 目标代码生成
本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C 源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIM Simulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。
选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。
需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。
5.1 实验内容
5.1.1 实验要求
为了完成实验四，我们建议你首先下载并安装SPIM Simulator用于对生成的目标代码进行检查和调试，SPIM Simulator的官方下载地址为：https://www.doczj.com/doc/2b6292639.html,/~larus/spim.html。这是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍有关SPIM Simulator的使用方法。
你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。因此，以下几个方面不属于检查范围：
1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的
正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。
2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使
用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即MIPS32汇编代码）能运行正确。
当然，不检查并不代表不重要。我们建议你试着去遵守MIPS32中的各种约定，否则你的程序生成的目标代码在SPIM Simulator中运行时可能会出现一些意想不到的错误。
另外，实验四对作为输入的C--源代码有如下的假设：
1)假设1：输入文件中不包含任何词法、语法或语义错误。
2)假设2：不会出现注释、八进制或十六进制整型常数、浮点型常数或者变量。
3)假设3：整型常数都在16bits位的整数范围内，也就是说你不必考虑如果某个常数无法
在addi等包含立即数的指令中表示时该怎么办。
4)假设4：不会出现类型为结构体或高维数组（高于1维的数组）的变量。
5)假设5：所有的变量均不重名，变量的存储空间都放到该变量所在的函数的活动记录
中。
6)假设6：任何函数参数都只能是简单变量，也就是说数组和结构体不会作为参数传入某
个函数中。
7)假设7：函数不会返回结构体或数组类型的值。
8)假设8：函数只会进行一次定义（没有函数声明）。
在进行实验四之前，请阅读后面的实验指导部分，以确保你已经了解MIPS32汇编语言以及SPIM Simulator的使用方法，这些内容是你顺利完成实验四的前提。
5.1.2 输入格式
你的程序的输入是一个包含C--源代码的文本文件，你的程序需要能够接收一个输入文件名和一个输出文件名作为参数。例如，假设你的程序名为cc、输入文件名为test1.cmm、输出文件名为out.s，程序和输入文件都位于当前目录下，那么在Linux命令行下运行./cc test.cmm out.s 即可将输出结果写入当前目录下名为out.s的文件中。
5.1.3 输出格式
实验四要求你的程序将运行结果输出到文件。对于每个输入文件，你的程序应当输出相应的MIPS32汇编代码。我们将使用SPIM Simulator对你输出的汇编代码的正确性进行测试，任何能被SPIM Simulator执行并且结果正确的输出都将被接受。
5.1.4 测试环境
你的程序将在如下环境中被编译并运行：
1)GNU Linux Release: Ubuntu 12.04, kernel version 3.2.0-29；
2)GCC version 4.6.3；
3)GNU Flex version 2.5.35；
4)GNU Bison version 2.5；
5)QtSPIM version 9.1.9。
一般而言，只要避免使用过于冷门的特性，使用其它版本的Linux或者GCC等，也基本上不会出现兼容性方面的问题。注意，实验四的检查过程中不会去安装或尝试引用各类方便编程的函数库（如glib等），因此请不要在你的程序中使用它们。
5.1.5 提交要求
实验四要求提交如下内容（同实验一）：
1)Flex、Bison以及C语言的可被正确编译运行的源程序。
2)一份PDF格式的实验报告，内容包括：
a)你的程序实现了哪些功能？简要说明如何实现这些功能。清晰的说明有助于助教
对你的程序所实现的功能进行合理的测试。
b)你的程序应该如何被编译？可以使用脚本、makefile或逐条输入命令进行编译，请
详细说明应该如何编译你的程序。无法顺利编译将导致助教无法对你的程序所实
现的功能进行任何测试，从而丢失相应的分数。
c)实验报告的长度不得超过一页！所以实验报告中需要重点描述的是你的程序中的
亮点，是你认为最个性化、最具独创性的内容，而相对简单的、任何人都可以做
的内容则可不提或简单地提一下，尤其要避免大段地向报告里贴代码。实验报告
中所出现的最小字号不得小于五号字（或英文11号字）。
5.1.6 样例
实验四无选做要求，因此下面只列举必做内容的样例。请仔细阅读样例，以加深对实验要求以及输出格式要求的理解。
样例1：
输入：
1 int main()
2 {
3 int a = 0, b = 1, i = 0, n;
4 n = read();
5 while (i < n)
6 {
7 int c = a + b;
8 write(b);
9 a = b;
10 b = c;
11 i = i + 1;
12 }
13 return 0;
14 }
输出：
该样例程序读入一个整数n，然后计算并输出前n个Fibonacci数的值。将其翻译为一段能在SPIM Simulator中执行的正确的目标代码可以是这样的：
图15. 样例1汇编代码的运行结果。
1 .data
2 _prompt: .asciiz "Enter an integer:"
3 _ret: .asciiz "\n"
4 .globl main
5 .text
6 read:
7 li $v0, 4
8 la $a0, _prompt
9 syscall
10 li $v0, 5
11 syscall
12 jr $ra
13
14 write:
15 li $v0, 1
16 syscall
17 li $v0, 4
18 la $a0, _ret
19 syscall
20 move $v0, $0
21 jr $ra
22
23 main:
24 li $t5, 0
25 li $t4, 1
26 li $t3, 0
27 addi $sp, $sp, -4
28 sw $ra, 0($sp)
29 jal read
30 lw $ra, 0($sp)
31 addi $sp, $sp, 4
32 move $t1, $v0
33 move $t2, $t1
34 label1:
35 blt $t3, $t2, label2
36 j label3
37 label2:
38 add $t1, $t5, $t4
39 move $a0, $t4
40 addi $sp, $sp, -4
41 sw $ra, 0($sp)
42 jal write
43 lw $ra, 0($sp)
44 addi $sp, $sp, 4
45 move $t5, $t4
46 move $t4, $t1
47 addi $t1, $t3, 1
48 move $t3, $t1
49 j label1
50 label3:
51 move $v0, $0
52 jr $ra
该汇编代码在命令行SPIM Simulator中的运行结果如图15所示（输入7，则输出前7个Fibonacci数）。
样例2：
输入：
1 int fact(int n)
2 {
3 if (n == 1)
4 return n;
5 else
6 return (n * fact(n - 1));
7 }
8
9 int main()
10 {
11 int m, result;
12 m = read();
13 if (m > 1)
14 result = fact(m);
15 else
16 result = 1;
17 write(result);
18 return 0;
19 }
输出：
该样例程序读入一个整数n，然后计算并输出n!的值。将其翻译为一段能在SPIM Simulator 中执行的正确的目标代码可以是这样的：
1 .data
2 _prompt: .asciiz "Enter an integer:"
3 _ret: .asciiz "\n"
4 .globl main
5 .text
6 read:
7 li $v0, 4
8 la $a0, _prompt
9 syscall
10 li $v0, 5
11 syscall
12 jr $ra
13
14 write:
15 li $v0, 1
16 syscall
17 li $v0, 4
18 la $a0, _ret
19 syscall
20 move $v0, $0
21 jr $ra
22
23 main:
24 addi $sp, $sp, -4
25 sw $ra, 0($sp)
26 jal read
27 lw $ra, 0($sp)
28 addi $sp, $sp, 4
29 move $t1, $v0
30 li $t3, 1
31 bgt $t1, $t3, label6
32 j label7
33 label6:
34 move $a0, $t1
图16. 样例2汇编代码的运行结果。
35 addi $sp, $sp, -4
36 sw $ra, 0($sp)
37 jal fact
38 lw $ra, 0($sp)
39 addi $sp, $sp, 4
40 move $t2, $v0
41 j label8
42 label7:
43 li $t2, 1
44 label8:
45 move $a0, $t2
46 addi $sp, $sp, -4
47 sw $ra, 0($sp)
48 jal write
49 lw $ra, 0($sp)
50 addi $sp, $sp, 4
51 move $v0, $0
52 jr $ra
53
54 fact:
55 li $t4, 1
56 beq $a0, $t4, label1
57 j label2
58 label1:
59 move $v0, $a0
60 jr $ra
61 label2:
62 addi $sp, $sp, -8
63 sw $a0, ($sp)
64 sw $ra, 4($sp)
65 sub $a0, $a0, 1
66 jal fact
67 lw $a0, ($sp)
68 lw $ra, 4($sp)
69 addi $sp, $sp, 8
70 mul $v0, $v0, $a0
71 jr $ra
该汇编程序在QtSPIM中的运行结果如图16所示（输入7，输出5040）。
除了上面给的两个样例以外，你的程序要能够将其它符合假设的C 源代码翻译为目标代码，我们将通过检查目标代码是否能在SPIM Simulator上运行并得到正确结果来判断你的程序的正确性。
5.2 实验指导
在实验三中，我们已经将输入程序翻译为涉及相当多底层细节的中间代码。这些中间代码在很大程度上已经可以很容易地翻译成许多RISC的机器代码，不过仍然存在以下问题：
1)中间代码与目标代码之间并不是严格一一对应的。有可能某条中间代码对应多条目标
代码，也有可能多条中间代码对应一条目标代码。
图17. QtSPIM运行界面。
2)中间代码中我们使用了数目不受限的变量和临时变量，但处理器所拥有的寄存器数量
是有限的。RISC机器的一大特点就是运算指令的操作数总是从寄存器中获得。
3)中间代码中我们并没有处理有关函数调用的细节。函数调用在中间代码中被抽象为若
干条ARG语句和一条CALL语句，但在目标机器上一般不会有专门的器件为我们进行参数传递，我们必须借助于寄存器或栈来完成这一点。
其中，第一个问题被称为指令选择（Instruction Selection）问题，第二个问题被称为寄存器分配（Register Allocation）问题，第三个问题则需要考虑如何对栈进行管理。在实验四中我们的主要任务就是编写程序来处理这三个问题。
5.2.1 QtSPIM简易教程
“工欲善其事，必先利其器”，在着手解决前面所说的三个问题之前，让我们先来考察实验四所要用到的工具SPIM Simulator。
SPIM Simulator有两种版本：命令行版和GUI版，这两个版本功能相似。命令行版使用起来更简洁，GUI版使用起来更直观，你可以根据自己的喜好进行选择。如果选择命令行版，则可以直接在终端键入sudo apt-get install spim命令进行安装（注意需要机器已经连接外网），如果
图18. 内存中的数据信息。
图19. 运行参数设置对话框。
选择GUI版，则需要访问SPIM Simulator的官方地址https://www.doczj.com/doc/2b6292639.html,/~larus/spim.html来下载并安装QtSPIM的Linux版本。命令行版的使用很简单，键入
spim -file [汇编代码文件名]
即可运行。其更详细的使用方法可以通过阅读手册man spim进行学习，下面的介绍主要针对GUI版本。
成功安装并运行QtSPIM之后，可以看到如图17所示的界面。其中中间面积最大的一片是代码区，里面显示了许多MIPS用户代码和内核代码，而左侧列出了MIPS中的各个寄存器以及这些寄存器中保存的内容。无论是代码还是寄存器内容，都可以通过上面的菜单选项切换二进制/十进制/十六进制的显示方式。
从图中我们可以看到用户代码区已经存在一部分代码了，该代码的主要作用是布置初始运行环境并调用名为main的函数。此时由于我们没有载入任何包含main标签的代码，如果我们运行这段代码，会发现运行到jal main那一行就会出错。现在我们将一段包含main标签以及声明main标签为全局标签的“.globl main”语句的MIPS32代码（例如前面样例1的输出）保存为后缀名为.s或者.asm的文件。单击QtSPIM工具栏上的按钮来选择我们保存好的文件，此时就可以看到文件中的代码已经被载入到QtSPIM的代码区，再运行这段代码就能在Console窗口观察到运行结果了。你也可以使用QtSPIM工具栏上的按钮或按F10快捷键来单步执行该代码。
表7. 数据段中常见的storage_type。
表8. 常用的伪指令。
使用SPIM Simulator的一个好处就是我们不需要干预内存的分配，它会帮我们自动划分内存中的代码区、数据区和栈区。SPIM Simulator具体采用大端（Big Endian，即数据从高位字节到低位字节在内存中按照从低地址到高地址的顺序依次存储）还是小端（Little Endian，即数据从低位字节到高位字节在内存中按照从低地址到高地址的顺序依次存储）的存储方式取决于你机器的处理器的存储方式（由于大多数台式机或笔记本都使用了Intel x86体系结构的处理器，不出意外的话你会发现自己的SPIM Simulator是小端机）。
在代码区上方的选项卡处切换到“Data”选项卡，就可以看到当前内存中的数据信息，如图18所示。单击菜单栏上的Simulator Run parameters，在弹出的对话框（如图19所示）中可以设置程序运行的起始地址以及传给main函数的命令行参数。
5.2.2 MIPS32汇编代码书写
SPIM Simulator不仅是一个MIPS32的模拟器，也是一个MIPS32的汇编器。想要让SPIM Simulator正常模拟，你首先需要为它准备符合格式的MIPS32汇编代码文本文件。非操作系统内核的汇编代码文件必须以.s或者.asm作为文件的后缀名。汇编代码由若干代码段和若干数据段组成，其中代码段以.text开头，数据段以.data开头。汇编代码中的注释以#开头。
数据段可以为汇编代码中所要用到的常量和全局变量申请空间，其格式为：
表9. MIPS体系结构中的寄存器。
表10. 系统调用。
name: storage_type value(s)
其中name代表内存地址（标签）名，storage_type代表数据类型，value代表初始值。常见的storage_type有表7所列的几类。
下面是三个例子：
1 var1: .word 3 # create a single integer variable with
2 # an initial value of 3
3 array1: .byte 'a','b' # create a 2-element character array with
4 # its elements initialized to a and b
5 array2: .space 40 # allocate 40 consecutive bytes, with storage
6 # uninitialized; could be used as a 40-element
7 # character array, or a 10-element integer array
代码段由一条条MIPS32指令或者标签组成，标签后面要跟冒号，而指令与指令之间要以换行符分开。前面的样例输出中有很多像la、li这样的指令。这些指令不属于MIPS32指令集，它们叫伪指令（Pseudo Instruction）。每条伪指令对应一条或者多条MIPS32指令，便于汇编指令的书写和记忆。几条比较常用的伪指令如表8所示。
MIPS体系结构共有32个寄存器，在汇编代码中你可以使用$0至$31来表示它们。为了便于表示和记忆，这32个寄存器也拥有各自的别名，如表9所示。
表11. 中间代码与MIPS32指令对应的一个示例。
最后，SPIM Simulator也为我们提供了方便进行控制台交互的机制，这些机制通过系统调用syscall的形式体现。为了进行系统调用，你首先需要向寄存器$v0中存入一个代码以指定具体要进行哪种系统调用。如有必要还需向其它寄存器中存入相关的参数，最后再写一句syscall即可。例如：
1 li $v0, 4
2 la $a0, _prompt
3 syscall
进行了系统调用print_string(_prompt)。与实验四相关的系统调用类型如表10所示。
到此，如果对照前面的样例输出并仔细阅读这节的内容，你可以基本了解在实验四中你的程序需要输出什么。
5.2.3 指令选择
指令选择可以看成是一个模式匹配问题。无论中间代码是线形还是树形的，我们都需要在其中找到特定的模式，然后将这些模式对应到目标代码上（这有点类似于将语法树翻译为中间代码的过程）。指令选择可以是简单寻找以一一对应，也可以是涉及到许多细节处理和计算的复杂过程。这取决于中间代码本身蕴含信息的多少，以及目标机器采用的是RISC还是CISC类
1reg(x)表示变量x所分配的寄存器。
2乘法、除法以及条件跳转指令均不支持非零常数，所以如果中间代码包括类似于“x := y * #7”的语句，其中的立即数7必须先加载到一个寄存器中。
图20. 树形IR翻译示例。
型的指令集。相对而言，我们所采用的MIPS32指令集属于处理起来比较简单的RISC指令集，因此指令选择在实验四中也属于比较简单的任务。
如果你的程序使用了线形IR，那么最简单的指令选择方式是逐条将中间代码对应到目标代码上。表11是将实验三的中间代码对应到MIPS32指令的一个例子，当然这个翻译方案并不唯一。
很多时候，这种逐条翻译的方式往往得不到高效的目标代码。举个简单的例子：假设要访问某个数组元素a[3]。变量a的首地址已经被保存到了寄存器$t1中，我们希望将保存在内存中的a[3]的值放到$t2里。如果按照上表使用的逐条翻译的方式，由于这段功能对应到我们的中间代码里至少需要两条，故翻译出来的MIPS32代码也需要两条指令：
1 addi $t3, $t1, 12
2 lw $t2, 0($t3)
但这两条指令可以利用MIPS32中的基址寻址机制合并成一条指令：
1 lw $t2, 12($t1)
这个例子启示我们，有的时候为了得到更高效的目标代码，我们需要一次考察多条中间代码，以期可以将多条中间代码翻译为一条MIPS32代码。这个过程可以看作是一个多行的模式匹配，也可以看成用一个滑动窗口（Sliding Window）或一个窥孔（Peephole）滑过中间代码并查找可能的翻译方案的过程。这非常类似于我们课本上介绍的“窥孔优化”（Peephole Op-timization）的局部代码优化技术。
树形IR的翻译方式类似于线形IR，也是一个模式匹配的过程。不过我们需要寻找的模式不再是一句句线形代码，而是某种结构的子树。树形IR的匹配与翻译算法被称为“树重写”（Tree-rewriting）算法，这在课本上也有介绍。我们仍用一个例子来说明这种方法，假设我们有一条翻译模式如图20所示。
如何在中间代码中找到该图所对应的模式呢？答案是遍历。我们可以按照深度优先的顺序考察树形IR中的每一个结点及其结节点的类型是否满足相应的模式。例如，图中的模式匹配写成代码可以是：
1 if (current_node -> kind == ASSIGN)
2 {
3 left = current_node -> left;
4 right = current_node -> right;
5 if (left->kind == TEMP && right->kind == EXP)
6 {
7 op1 = right -> op1;
8 op2 = right -> op2;
9 if (right->op == '+' && op1->kind == TEMP && op2->kind == CONST)
10 emit_code("addi " + get_reg(left) + ", " + get_reg(op1) + ", "
11 + get_value(op2));
12 }
13 }
你可以根据自己的树形IR写出翻译模式，然后使用类似于上面的方法进行翻译。
5.2.4 寄存器分配（朴素寄存器分配算法）
RISC机器的一个很显著的特点是，除了load/store型指令之外，其余指令的所有操作数都必须来自寄存器而不是内存。除了数组和结构体必须放到内存中之外，中间代码里的任何一个非零变量或临时变量，只要它参与运算，其值必须被载入到某个寄存器中。在某个特定的程序点上选择哪个寄存器来保存哪个变量的值，这就是寄存器分配所要研究的问题。
寄存器可以说是现代计算机中最宝贵的资源之一。由于寄存器的访问性能远高于内存，这使得寄存器分配算法对于我们编译出来的目标代码的效率的影响尤其明显。为一段包含单个基本块、只有一种数据类型、访存代价固定的中间代码生成代价最少的寄存器分配方案是可以在多项式时间内被计算出来的。在此基础上，几乎添加任何假设（如多于一个基本块、多于一种数据类型、使用多级存储模型等）都会使得寻找最优寄存器分配方案变成一个NP-hard问题1。因此，目前编译器使用的寄存器分配算法大都是近似最优分配方案。下面我们将介绍三种不同的寄存器分配算法，它们的实现难度依次递增，但产生的目标代码的访存代价却是依次递减。这节我们介绍朴素寄存器分配算法，其它算法以及相关的讨论我们放到后面介绍。
朴素寄存器分配算法的思想最简单，也最低效：将所有的变量或临时变量都放在内存里。如此一来，每翻译一条中间代码之前我们都需要把要用到的变量先加载到寄存器中，得到该代码的计算结果之后又需要将结果写回内存。这种方法的确能将中间代码翻译成可以正常运行的目标代码，而且实现和调试都特别容易，不过它最大的问题是对寄存器的利用率实在太低。它不仅闲置了MIPS为我们提供的大部分通用寄存器，那些未被闲置的寄存器也没有对减少目标代码的访存次数做出任何贡献。
5.2.5 寄存器分配（局部寄存器分配算法）
寄存器分配之所以难是因为寄存器的数量有限，被迫共用同一寄存器的变量太多，导致这些变量在使用时不得不在寄存器里换入换出，从而产生较大的访存开销。我们考虑如何通过合理安排变量对寄存器的共用关系来最大限度地减少寄存器内容换入换出的代价。有一种较好的方法叫局部寄存器分配算法，该方法会事先将整段代码分拆成一个个基本块（将一段代码划
1《Engineering a Compiler》，第2版，Keith D. Cooper和Linda Torczon著，Morgan Kaufmann出版社，第689页，2011年。
分成基本块的过程课本上有介绍，我们这里不再赘述），在每个基本块内部我们根据各种启发式原则为块里出现的变量分配寄存器。但在基本块结束时这种算法会与前面提到的朴素算法一样，需要将本块中所有修改过的变量都写回内存。为了方便说明，我们假设所有的中间代码都形如z := x op y，其中x和y是两个要用到的操作数，z是运算结果，op代表一个任意的二元运算符（一元或多元运算符的处理与二元类似）。在基本块开始时，所有的寄存器都是闲置的。算法的大概框架如下：
1 for each operation z = x op y
2 r x = Ensure(x)
3 r y = Ensure(y)
4 if (x is not needed after the current operation)
5 Free(r x)
6 if (y is not needed after the current operation)
7 Free(r y)
8 r z = Allocate(z)
9 emit MIPS32 code for r z = r x op r y
其中Free(r)表示将寄存器r标记为闲置。算法还用到另外两个辅助函数Ensure和Allocate，它们的实现为：
1 Ensure(x):
2 if (x is already in register r)
3 result = r
4 else
5 result = Allocate(x)
6 emit MIPS32 code [lw result, x]
7 return result
8
9 Allocate(x):
10 if (there exists a register r that currently has not been assigned to
11 any variable)
12 result = r
13 else
14 result = the register that contains a value whose next use is farthest
15 in the future
16 spill result
17 return result
其中Allocate函数会用到每个变量在各个程序点的使用信息，这些信息可以由一次对基本块中代码自后向前的扫描而得到。
上述算法的核心思想其实很简单：对基本块内部的中间代码逐条扫描，如果当前代码中有变量需要使用寄存器，就从当前空闲的寄存器中选一个分配出去；如果没有空闲的寄存器，不得不将某个寄存器中的内容写回内存（该操作称为溢出或spilling）时，则选择那个包含本基本块内将来用不到或最久以后才用到的变量的寄存器。通过这种启发式规则，该算法期望可以最大化每次溢出操作的收益，从而减少访存所需要的次数。
课本上也介绍了一种和上述算法功能相似的局部寄存器分配函数get_reg。课本上的方法是通过引入寄存器描述符与变量描述符这两种数据结构，完全消除寄存器之间的数据移动，并且期望使溢出操作所产生的store指令的数量最小化。这里介绍的方法与课本上的方法各有优劣，你可以酌情选择，也可以在它们的基础上设计自己的局部寄存器分配算法。
5.2.6 寄存器分配（图染色算法）
局部寄存器分配算法虽然是启发式算法，但在实际应用中它对于只包含一个基本块的中间代码来说非常有效。不过，当我们尝试将其推广到多个基本块时，会遇到一个非常不易克服的困难：我们无法单看中间代码就确定程序的控制流走向。例如，假设当前的基本块运行结束时寄存器中有一个变量x，而当前基本块的最后一条中间代码是条件跳转。我们知道控制流既有可能跳转到一个不使用x的基本块中，又有可能跳转到一个使用x的基本块中，那么此时变量x 的值究竟是应该溢出到内存里，还是应该继续保留在寄存器里呢？
局部寄存器分配算法的这一弱点启发我们去寻找一个适用于全局的寄存器分配算法，这种全局分配算法必须要能有效地从中间代码的控制流中获取变量的活跃信息，而活跃变量分析（Liveliness Analysis）恰好可以为我们提供这些信息。如何进行活跃变量分析我们在后面介绍，现在假设我们已经进行过这种分析并了解到了在每个程序点上哪些变量在将来的控制流中可能还会被使用到。一个显而易见的寄存器分配原则就是，同时活跃的两个变量尽量不要分配相同的寄存器。这是因为同时活跃的变量可能在之后的运行过程中被用到，如果把它们分到一起那么很可能会产生寄存器内变量的换入换出操作，从而增加访存代价。不过这里存在两个特例：
1)在赋值操作x := y中，即使x和y在这条代码之后都活跃，因为二者值是相等的，它们仍
然可以共用寄存器。
2)在类似于x := y + z这样的中间代码中，如果变量x在这条代码之后不再活跃，但变量y
仍然活跃，那么此时虽然x和y不同时活跃，二者仍然要避免共用寄存器以防止之后对x 的赋值会将活跃变量y在寄存器中的值覆盖掉。
据此我们定义，两个不同变量x和y相互干扰的条件为：
1)存在一条中间代码i，满足x ∈ out[i]且y ∈ out[i]。
2)或者存在一条中间代码i，这条代码不是赋值操作x := y或y := x，且满足x ∈ def[i]且y ∈
out[i] 。
其中out[i]与def[i]都是活跃变量分析所返回给我们的信息，它们的具体含义后面会有介绍，建议阅读完后面的活跃变量分析一节之后再返回来这里考察这个定义。这里你只需要明白，x 和y相互干扰就意味着我们应当尽可能地为二者分配不同的寄存器。
如果将中间代码中出现的所有变量和临时变量都看作顶点，两个变量之间若相互干扰则在二者所对应的顶点之间连一条边，那么我们就可以得到一张干涉图（Interference Graph）。如果此时我们为每个变量都分配一个固定的寄存器，而将处理器中的k个寄存器看成k种颜色，我们又要求干涉图中相邻两顶点不能染同一种颜色，那么寄存器分配问题就变成了一个图染色（Graph-coloring）问题。对于固定的颜色数k，判断一张干涉图是否能被k着色是一个NP-
Complete问题。因此，为了能够在多项式时间内得到寄存器分配结果，我们只能使用启发式算法来对干涉图进行着色。一个比较简单的启发式染色算法（称作Kempe算法）为：
1)如果干涉图中包含度小于或等于k-1的顶点，就将该顶点压入一个栈中并从干涉图中删
除。这样做的意义在于，如果我们能够为删除该顶点之后的那张图找到一个k着色的方案，那么原图也一定是k可着色的。删掉这类顶点可以对原问题进行简化。
2)重复执行上述操作，如果最后干涉图中只剩下了少于k个顶点，那么此时就可以为剩下
的每个顶点分配一个颜色，然后依次弹出栈中的顶点添加回干涉图中，并选择它的邻居都没有使用过的颜色对弹出的顶点进行染色。
3)当我们删除顶点到某一步时，如果干涉图中所有的顶点都至少包含了k个邻居，此时能
否断定原图不能被k着色呢？如果你能证明这一点，就相当于构造性地证明P = NP。事实上，这样的图在某些情况下仍然是k可着色的。如果出现了干涉图中所有的顶点都至少为k度，我们仍然选择一个顶点删除并且将其压栈，并且标记这样的顶点为待溢出的顶点，之后继续删点操作。
4)被标记为待溢出的顶点在最后被弹出栈时，如果我们足够幸运，有可能它的邻居总共
被染了少于k种颜色。此时我们就可以成功地为该顶点染色并清除它的溢出标记。否则，我们无法为这个顶点分配一个颜色，它所代表的变量也就必须要被溢出到内存中了。
到这里，中间代码中出现的所有变量要么被分配了一个寄存器，要么被标记为溢出。现在的问题是，那些被标记为溢出的变量的值在参与运算时仍然需要临时被载入到某个寄存器中，在运算结束后也仍然需要某个寄存器临时保存要溢出到内存里的值，这些临时使用的寄存器从哪里来呢？最简单的解决方法是在进行前面图染色算法之前预留出专门用来临时存放溢出变量的值的寄存器。如果你觉得这样做比较浪费寄存器资源，想要追求更有效率的分配方案，你可以通过不断地引入更多的临时变量重写中间代码、重新进行活跃变量分析和图染色来不断减少需要溢出的变量的个数，直到所有的溢出变量全部被消除掉。另外，对于干涉图中那些不相邻的顶点，我们还可以通过合并顶点的操作来显式地令这些不互相干扰的变量共用同一个寄存器。引入合并以及溢出变量这两种机制会使得全局寄存器分配算法变得更加复杂，想要了解具体细节可以自行查阅更多的资料。
5.2.7 寄存器分配（活跃变量分析）
之前在图染色算法中，为了构造干涉图我们需要明确变量与变量之间的干扰关系，而为了得到干扰关系又需要知道哪些变量是同时活跃的。现在我们来讨论如何得到变量在中间代码中的活跃信息。首先我们严格定义什么叫活跃变量：称变量x在某一特定的程序点是活跃变量当且仅当：
1)如果某条中间代码使用到了变量x的值，则x在这条代码运行之前是活跃的。
2)如果变量x在某条中间代码中被赋值，并且x没有被该代码使用到，则x在这条代码运行
之前是不活跃的。
3)如果变量x在某条中间代码运行之后是活跃的，而这条中间代码并没有给x赋值，则x在
这条代码运行之前也是活跃的。
4)如果变量x在某条中间代码运行之后是活跃的，则x在这条中间代码运行之后可能跳转
到的所有的中间代码运行之前都是活跃的。
在上述的四条规则中，第一条规则指出了活跃变量是如何产生的，第二条规则指出了活跃变量是如何消亡的，第三和第四条规则指出了活跃变量是如何传递的。
我们定义第i条中间代码的后继集合succ[i]为：
1)如果第i条中间代码为无条件跳转语句GOTO，并且跳转的目标是第j条中间代码，则
succ[i] = { j }。
2)如果第i条中间代码为条件跳转语句IF，并且跳转的目标是第j条中间代码，则succ[i] =
{ j, i + 1 }。
3)如果第i条中间代码为返回语句RETURN，则succ[i] = φ。
4)如果第i条中间代码为其他类型的语句，则succ[i] = { i + 1 }。
我们再定义def[i]为被第i条中间代码赋值了的变量的集合，use[i]为被第i条中间代码使用到的变量的集合，in[i]为在第i条中间代码运行之前活跃的变量的集合，out[i]为在第i条中间代码运行之后活跃的变量的集合。活跃变量分析问题可以转化为解下述数据流方程的问题：
。
in[i]=use[i]∪(out[i]?def[i])和out[i]=?in[j]
j∈succ[i]
我们可以通过迭代的方法对这个数据流方程进行求解。算法开始时我们令所有的in[i]为φ，之后每条中间代码对应的in和out集合按照上式进行运算，直到这两个集合的运算结果收敛为止。格理论告诉我们，in和out集合的运算顺序不影响数据流方程解的收敛性，但会影响解的收敛速度。对于上述数据流方程而言，按照i从大到小的顺序来计算in和out往往要比按照i从小到大的顺序进行计算要快得多。
为了能更高效地对集合in和out进行计算，在实现时我们往往采用位向量（Bit Vector）来表示这两个集合。假设待处理的中间代码包含10个变量或临时变量，那么in[i]（或out[i]）可以分别由10bits组成，其中第j个比特位为1就代表第j个变量属于in[i]（或out[i]）。两个集合之间的并集对应于位向量中的或运算，两个集合之间的交集对应于位向量中的与运算，一个集合的补集对应于位向量中的非运算。位向量表示法凭借其表示紧凑、运算速度快的特点，几乎成为了解数据流方程所采用数据结构的不二之选。
实际上，数据流方程这一强大的工具不仅可以用于活跃变量分析，也可以用在诸如到达定值（Reaching Definition）、可用表达式（Available Expression）等各种与代码优化有关的分析中。另外我们上面介绍的方法是以语句为单位来进行分析的，而类似的方法也适用于以基本块为单位的情况，并且使用基本块的话分析效率还会更高一些。有关数据流方程的其它应用，课本上有很详细的介绍，我们在这里就不再赘述了。
5.2.8 寄存器分配（MIPS寄存器的使用）
在结束对寄存器分配问题的讨论之前，我们还需要了解MIPS32指令集对于寄存器的使用有哪些规范，从而明确哪些寄存器可以随便用、哪些不能用、哪些可以用但要小心。严格地讲，采用MIPS体系结构的处理器本身并没有强制规定其32个通用寄存器应该如何使用（除了$0之外，其余31个寄存器在硬件上都是等价的），但MIPS32标准对于汇编代码的书写的确是提出了一些约定。“约定”这个词有两层意思：其一，因为它是约定，所以没有人逼你去遵守它，你大可以违反它却仍然使你写出的汇编代码能够正常运行起来；其二，因为它是约定，所以除了你之外的绝大部分人（还有包括SPIM Simulator在内的绝大多数汇编器）都在遵守它。如果你不遵守它，那么你的程序不仅在运行效率以及可移植性等方面会遇到各种问题，同时也可能无法被SPIM Simulator所正常执行。
$0这个寄存器非常特殊，它在硬件上本身就是接地的，因此其中的值永远是0，我们无法改变。$at、$k0、$k1这三个寄存器是专门预留给汇编器使用的，如果你尝试在汇编代码中访问或修改它们的话SPIM Simulator会报错。$v0和$v1这两个寄存器专门用来存放函数的返回值。在函数内部也可以使用，不过要注意在当前函数返回或调用其它函数时应妥善处理这两个寄存器中原有的数据。$a0至$a3四个寄存器专门用于存放函数参数，在函数内部它们可以视作与$t0至$t9等同。
$t0至$t9这10个寄存器可以由我们任意使用，但要注意它们属于调用者保存的寄存器，在函数调用之前如果其中保存有任何有用的数据都要先溢出到内存中。$s0至$s7也可以任意使用，不过它们是被调用者保存的寄存器，如果一个函数内要修改$s0至$s7的话，需要在函数的开头先将其中原有的数据压入栈，并在函数末尾恢复这些数据。关于调用者保存和被调用者保存这两种机制，我们会在后面详细介绍。
$gp固定指向64K静态数据区的中央，$sp固定指向栈的顶部。这两个寄存器都是具有特定功能的，对它们的使用和修改必须伴随明确的语义，不能随便将数据往里送。$30这个寄存器比较特殊，有些汇编器将其作为$s8使用，也有一些汇编器将其作为栈帧指针$fp使用，你可以在这两个方案里任选其一。$ra专门用来保存函数的返回地址，MIPS32中与函数跳转有关的jal指令和jr指令都会对该寄存器进行操作，因此我们也不要随便去修改$ra的值。
图21. 函数的活动记录结构。
总而言之，MIPS的32个通用寄存器中能让我们随意使用的有$t0至$t9以及$s0至$s8，不能随意使用的有$at、$k0、$k1、$gp、$sp和$ra，可以使用但在某些情况下需要特殊处理的有$v0至$v1以及$a0至$a3，最后$0可用但其值无法修改。
5.2.9 栈管理
在过程式程序设计语言中，函数调用包括控制流转移和数据流转移两个部分。控制流转移指的是将程序计数器PC当前的值保存到$ra中然后跳转到目标函数的第一句处，这件事情已经由硬件帮我们做好，我们可以直接使用jal指令实现。因此，编译器编写者在目标代码生成时所需要考虑的问题是如何在函数的调用者与被调用者之间进行数据流的转移。当一个函数被调用时，调用者需要为这个函数传递参数，然后将控制流转移到被调用函数的第一行代码处；当被调用函数返回时，被调用者需要将返回值保存到某个位置，然后将控制流转移回调用者处。在MIPS32中，函数调用使用jal指令，函数返回使用jr指令。参数传递采用寄存器与栈相结合的方式：如果参数少于4个，则使用$a0至$a3这四个寄存器传递参数；如果参数多于4个，则前4个参数保存在$a0至$a3中，剩下的参数依次压到栈里。返回值的处理方式则比较简单，由于我们约定C 中所有函数只能返回一个整数，因此直接将返回值放到$v0中即可，$v1可以挪作它用。
下面我们着重讨论在函数调用过程中至关重要的结构：栈。栈在本质上就是按照后进先出原则维护的一块内存区域。除了上面提到的参数传递之外，栈在程序运行过程中还具有如下功能：
1)如果我们在一个函数中使用jal指令调用了另一个函数，寄存器$ra中的内容就会被覆盖
掉。为了能够使得另一个函数返回之后能将$ra中原来的内容恢复出来，调用者在进行函数调用之前需要负责把$ra暂存起来，而这暂存的位置自然是在栈中。
2)对于那些在寄存器分配过程中需要溢出到内存中的变量来说，它们究竟要溢出到内存
中的什么地方呢？如果是全局变量，则需要被溢出到静态数据区；如果是局部变量，
则一般会被溢出到栈中。为了简化处理，实验四中你的程序可以将所有需要被溢出的变量都安排到栈上。
3)不管占用多大的空间，数组和结构体一定会被分配到内存中去。同溢出变量一样，这
些内存空间实际上都在栈上。
每个函数在栈上都会占用一块单独的内存空间，这块空间被称为活动记录（Activation Record）或者栈帧（Stack Frame）。不同函数的活动记录虽然在占用内存大小上可能会有所不同，但基本结构都差不多。一个比较典型的活动记录结构如图21所示。
在图中，栈指针$sp指向栈的顶部，帧指针$fp指向当前活动记录的底部。假设图中栈顶为上方而栈底为下方，则$fp之下是传给本函数的参数（只有多于4个参数时这里才会有内容），而$fp之上是返回地址、被调用者保存的寄存器内容以及局部数组、变量或临时变量。这个活动记录的布局并不是唯一可行的，不同的体系结构之间布局不尽相同，同一体系结构的在不同的介绍中也可能不一样，这里并没有一个统一的标准。理论上来讲只要能将应该保存的内容都存下来，并且能够正确地将它们都取出来就行。你的程序不必完全遵循上图中的布局方式。
在栈的管理中，有一个栈指针$sp其实已经足够了，$fp并不是必需的，前面也提到过某些编译器甚至将$fp挪用作$s8。引入$fp主要是为了方便访问活动记录中的内容：在函数的运行过程中，$sp是会经常发生变化的（例如，当压入新的临时变量、压入将要调用的另一个函数的参数、或者想在栈上保存动态大小的数组时），根据$sp来访问栈帧里保存的局部变量比较麻烦，因为这些局部变量相对于$sp的偏移量会经常改变。而在函数内部$fp一旦确定就不再变化，所以根据$fp访问局部变量时并不需要考虑偏移量的变化问题。假如你学过有关x86汇编的知识就会发现，MIPS32中的$sp实际上相当于x86中的%esp，而MIPS32中的$fp则相当于x86中的%ebp。如果决定使用$fp的话，为了能够使本函数返回之后能够恢复上层函数的$fp，需要在活动记录中找地方把$fp中的旧值也存起来。
如果一个函数f调用了另一个函数g，我们称函数f为调用者（Caller），函数g为被调用者（Callee）。控制流从调用者转移到被调用者之后，由于被调用者使用到一些寄存器，而这些寄存器中有可能原先保存着有用的内容，故被调用者在使用这些寄存器之前需要先将其中的内容保存到栈中，等到被调用者返回之前再从栈中将这些内容恢复出来。现在的问题是：保存寄存器中原有数据这件事情究竟是由调用者完成还是由被调用者完成？如果由调用者保存，由于调用者事先不知道被调用者会使用到哪些寄存器，它只能将所有的寄存器内容全部保存，于是会产生一些无用的压栈和弹栈操作；如果由被调用者保存，由于被调用者事先不知道调用者在调用自己之后有哪些寄存器不需要了，它同样也只能将所有的寄存器内容全部保存，于是同样会产生一些无用的压栈和弹栈操作。为了减少这些无用的访存操作，可以采用一种调用者和被调用者共同保存的策略：MIPS32约定$t0至$t9由调用者负责保存，而$s0~$s8由被调用者负责
《编译原理》课后习题 第1 章引论 第1 题解释下列术语： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。 答案：一个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式 的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的 各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源 程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 第3 题何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案：翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编 写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是， 源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功
编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。
实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则
一、填空题（每空2分，共30分） 1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段，另外还有两个重要的工作是表格管理和出错处理 2、规范规约中的可归约串是句柄，算符优先分析中的可归约串是最左素短语。 3、语法分析方法主要可分为自顶向下和自底向上两大类。 4、LR（0）文法的项目集中不会出现移进-归约冲突和归约-归约冲突。 5、数据空间的动存态储分配方式可分为栈式和堆式两种。 6、编译程序是指能将源语言程序翻译成目标语言程序的程序。 7、确定有穷自动机DFA是NFA 的一个特例。 8、表达式(a+b)*c 的逆波兰表示为ab+c* 。 二、选择题（每题2分，共20分） 1、L R语法分析栈中存放的状态是识别 B 的DFA状态。 A、前缀 B、可归前缀 C、项目 D、句柄 2、 D 不可能是目标代码。 A、汇编指令代码 B、可重定位指令代码 C、绝对机器指令代码 D、中间代码 3、一个控制流程图就是具有 C 的有向图 A、唯一入口结点 B、唯一出口结点 C、唯一首结点 D、唯一尾结点 4、设有文法G[S]：S→b|bB B→bS ，则该文法所描述的语言是 C 。 A、L（G）={b i|i≥0} B、L（G）={b2i|i≥0} C、L（G）={b2i+1|i≥0} D、L（G）={b2i+1|i≥1} 5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。 A、编译器 B、汇编器 C、解释器 D、预处理器 6、在目标代码生成阶段，符号表用于 D 。 A、目标代码生成 B、语义检查 C、语法检查 D、预处理器地址分配0 7、规范归约是指 B 。 A、最左推导的逆过程 B、最右推导的逆过程 C、规范推导 D、最左归约逆过程
[实验任务] 完成以下正则文法所描述的Pascal语言子集单词符号的词法分析程序。 <标识符>→字母︱<标识符>字母︱<标识符>数字 <无符号整数>→数字︱<无符号整数>数字 <单字符分界符> →+ ︱－︱* ︱; ︱(︱) <双字符分界符>→<大于>=︱<小于>=︱<小于>>︱<冒号>=︱<斜竖>* <小于>→< <等于>→= <大于>→> <冒号> →: <斜竖> →/ 该语言的保留字：begin end if then else for do while and or not 说明：1 该语言大小写不敏感。 2 字母为a-z A-Z，数字为0-9。 3可以对上述文法进行扩充和改造。 4 ‘/*……*/’为程序的注释部分。 [设计要求] 1、给出各单词符号的类别编码。 2、词法分析程序应能发现输入串中的错误。 3、词法分析作为单独一遍编写，词法分析结果为二元式序列组成的中间文件。 4、设计两个测试用例（尽可能完备），并给出测试结果。 demo.cpp #include
5. 目标代码生成 本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C 源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIM Simulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。 选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。 需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。 5.1 实验内容 5.1.1 实验要求 为了完成实验四，我们建议你首先下载并安装SPIM Simulator用于对生成的目标代码进行检查和调试，SPIM Simulator的官方下载地址为：https://www.doczj.com/doc/2b6292639.html,/~larus/spim.html。这是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍有关SPIM Simulator的使用方法。 你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。因此，以下几个方面不属于检查范围： 1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的 正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。 2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使 用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即MIPS32汇编代码）能运行正确。
第1章引言 1、解释下列各词 源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 （结果程序）一般可由计算机直接执行。 低级语言：机器语言和汇编语言。 高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言）， 然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。 2、什么叫“遍”？ 指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。 3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。 词法分析：输入源程序，进行词法分析，输出单词符号。 语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。 中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。 优化：对中间代码进行优化处理。 目标代码生成：把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别？ 编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。 5、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？ 编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。 6、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。
第一章 1．典型的编译程序在逻辑功能上由哪几部分组成？ 答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。 2. 实现编译程序的主要方法有哪些？ 答：主要有：转换法、移植法、自展法、自动生成法。 3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？ 答：编译法、解释法。 4. 编译方式和解释方式的根本区别是什么？ 答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快； 解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。
第二章 1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关 系如何？ 答：1）0型文法、1型文法、2型文法、3型文法。 2） 2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。 答： Z→SME | B S→1|2|3|4|5|6|7|8|9 M→ε | D | MD D→0|S B→2|4|6|8 E→0|B 3. 设文法G为： N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 请给出句子123、301和75431的最右推导和最左推导。 答：N?ND?N3?ND3?N23?D23?123 N?ND?NDD?DDD?1DD?12D?123 N?ND?N1?ND1?N01?D01?301 N?ND?NDD?DDD?3DD?30D?301 N?ND?N1?ND1?N31?ND31?N431?ND431?N5431?D5431?75431 N?ND?NDD?NDDD?NDDDD?DDDDD?7DDDD?75DDD?754DD?7543D?75431 4. 证明文法S→iSeS|iS| i是二义性文法。 答：对于句型iiSeS存在两个不同的最左推导： S?iSeS?iiSes S?iS?iiSeS 所以该文法是二义性文法。 5. 给出描述下面语言的上下文无关文法。 （1）L1={a n b n c i |n>=1,i>=0 } （2）L2={a i b j|j>=i>=1} （3）L3={a n b m c m d n |m,n>=0} 答： （1）S→AB A→aAb | ab B→cB | ε （2）S→ASb |ab
实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表
编译原理上机实验试题 一、实验目的 通过本实验使学生进一步熟悉和掌握程序设计语言的词法分析程序的设计原理及相关的设计技术， 如何针对确定的有限状态自动机进行编程序；熟悉和 掌握程序设计语言的语法分析程序的设计原理、熟悉 和掌握算符优先分析方法。 二、实验要求 本实验要求：①要求能熟练使用程序设计语言编程；②在上机之前要有详细的设计报告（预习报告）； ③要编写出完成相应任务的程序并在计算机上准确 地运行；④实验结束后要写出上机实验报告。 三、实验题目 针对下面文法G(S)： S→v = E E→E+E│E-E│E*E│E/E│（E）│v │i 其中，v为标识符，i为整型或实型数。要求完成 ①使用自动机技术实现一个词法分析程序； ②使用算符优先分析方法实现其语法分析程序，在 语法分析过程中同时完成常量表达式的计算。
1、题目（见“编译原理---实验题目.doc，“实验题目”中的第一项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理： (1)单词分类：标识符，保留字，常数，运算符，分隔符等等 (2)单词类型编码 (3)自动机 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
1、题目（见“编译原理---实验题目.doc，“实验题目”中的第二项） 2、目的与要求（见“编译原理---实验题目.doc”） 3、设计原理：构造出算法优先关系表 4、程序流程框图 5、函数原型（参数，返回值） 6、关键代码（可打印，只打印关键代码） 7、调试： （1）调试过程中遇到的错误，如何改进的； （2）需要准备测试用例（至少3个，包含输入和输出）——（可打印） 8、思考： (1)你编写的程序有哪些要求是没有完成的，你觉得该采用什么方法去完成； (2)或者是你觉得程序有哪些地方可以进一步完善，简述你的完善方案。
一、选择 1．将编译程序分成若干个“遍”是为了_使程序的结构更加清晰__。 2．正规式 MI 和 M2 等价是指__.M1 和 M2 所识别的语言集相等_。 3．中间代码生成时所依据的是 _语义规则_。 4．后缀式 ab+cd+/可用表达式__(a+b)/(c+d)_来表示。 6．一个编译程序中，不仅包含词法分析，_语法分析 ____，中间代码生成，代码优化，目标代码生成等五个部分。 7．词法分析器用于识别__单词___。 8．语法分析器则可以发现源程序中的___语法错误__。 9．下面关于解释程序的描述正确的是__解释程序的特点是处理程序时不产生目标代码 ___。 10．解释程序处理语言时 , 大多数采用的是__先将源程序转化为中间代码 , 再解释执行___方法。 11．编译过程中 , 语法分析器的任务就是__(2)(3)(4)___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 12．编译程序是一种__解释程序__。 13．文法 G 所描述的语言是_由文法的开始符号推出的所有终极符串___的集合。 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___正则文法__。 15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _产生式__。 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_表格处理和出错处理__。 17．文法 G[N]= （ {b} ， {N ， B} ， N ， {N→b│ bB ， B→bN} ），该文法所描述的语言是L(G[N])={b2i+1│ i ≥0} 18．一个句型中的最左_简单短语___称为该句型的句柄。 19．设 G 是一个给定的文法，S 是文法的开始符号，如果 S->x( 其中 x∈V*), 则称 x 是 文法 G 的一个__句型__。 21．若一个文法是递归的，则它所产生的语言的句子_是无穷多个___。 22．词法分析器用于识别_单词_。 23．在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_终极符集 ___。 24．在自底向上的语法分析方法中，分析的关键是_寻找句柄 ___。 25．在 LR 分析法中，分析栈中存放的状态是识别规范句型__活前缀__的 DFA 状态。 26．文法 G 产生的__句子___的全体是该文法描述的语言。 27．若文法 G 定义的语言是无限集，则文法必然是 __递归的_ 28．四种形式语言文法中，1 型文法又称为 _短语结构文法__文法。 29．一个文法所描述的语言是_唯一的__。 30． _中间代码生成___和代码优化部分不是每个编译程序都必需的。 31．_解释程序和编译程序___是两类程序语言处理程序。 32．数组的内情向量中肯定不含有数组的_维数___的信息。 33. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组__D___。 34．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 2 型文法是__上下文无关文法__。 35．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __产生式___。 36．__ BASIC ___是一种典型的解释型语言。 37．与编译系统相比，解释系统___比较简单 , 可移植性好 , 执行速度慢__。 38．用高级语言编写的程序经编译后产生的程序叫__目标程序___。 39．编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过__(1)(2)(3)__这几步: (1) 编辑 (2) 编译 (3) 连接 (4) 运行 40．把汇编语言程序翻译成机器可执行的目标程序的工作是由__编译器__完成的。 41．词法分析器的输出结果是__单词的种别编码和自身值__。 42．文法 G ：S→xSx|y 所识别的语言是_ xnyxn(n≥0)___。 43．如果文法 G 是无二义的，则它的任何句子α__最左推导和最右推导对应的语法树必定相同_。 44．构造编译程序应掌握___源程序目标语言编译方法___。 45．四元式之间的联系是通过__临时变量___实现的。 46．表达式( ┐ A ∨B)∧(C∨D)的逆波兰表示为___ A ┐ B∨CD∨∧__。 47. 优化可生成__运行时间短且占用存储空间小___的目标代码。 48．下列__删除多余运算 ____优化方法不是针对循环优化进行的。 49．编译程序使用__说明标识符的过程或函数的静态层次___区别标识符的作用域。 50．编译程序绝大多数时间花在___表格管理__ 上。 51．编译程序是对__高级语言的翻译___。
实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: ";
第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
编译原理实验报告 ******************************************************************************* ******************************************************************************* PL0语言功能简单、结构清晰、可读性强，而又具备了一般高级程序设计语言的必须部分，因而PL0语言的编译程序能充分体现一个高级语言编译程序实现的基本方法和技术。PL/0语言文法的EBNF表示如下： <程序>::=<分程序>. <分程序> ::=[<常量说明>][<变量说明>][<过程说明>]<语句> <常量说明> ::=CONST<常量定义>{，<常量定义>}; <常量定义> ::=<标识符>=<无符号整数> <无符号整数> ::= <数字>{<数字>} <变量说明> ::=VAR <标识符>{, <标识符>}; <标识符> ::=<字母>{<字母>|<数字>} <过程说明> ::=<过程首部><分程序>{; <过程说明> }; <过程首部> ::=PROCEDURE <标识符>; <语句> ::=<赋值语句>|<条件语句>|<当循环语句>|<过程调用语句> |<复合语句>|<读语句><写语句>|<空> <赋值语句> ::=<标识符>:=<表达式> <复合语句> ::=BEGIN <语句> {;<语句> }END <条件语句> ::= <表达式> <关系运算符> <表达式> |ODD<表达式> <表达式> ::= [+|-]<项>{<加法运算符> <项>} <项> ::= <因子>{<乘法运算符> <因子>} <因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’ <加法运算符> ::= +|- <乘法运算符> ::= *|/ <关系运算符> ::= =|#|<|<=|>|>= <条件语句> ::= IF <条件> THEN <语句> <过程调用语句> ::= CALL 标识符 <当循环语句> ::= WHILE <条件> DO <语句> <读语句> ::= READ‘(’<标识符>{,<标识符>}‘)’ <写语句> ::= WRITE‘(’<表达式>{,<表达式>}‘)’ <字母> ::= a|b|…|X|Y|Z <数字> ::= 0|1|…|8|9 【预处理】 对于一个pl0文法首先应该进行一定的预处理，提取左公因式，消除左递归（直接或间接），接着就可以根据所得的文法进行编写代码。 【实验一】词法分析 【实验目的】给出PL/0文法规，要求编写PL/0语言的词法分析程序。 【实验容】已给PL/0语言文法，输出单词（关键字、专用符号以及其它标记）。
1. 源语言：书写源程序所使用的语言 2. 源程序：用程序设计语言书写的程序 3. 目标语言：计算机的机器指令。目标语言可以是机器语言，也可以是汇编语言， 或者是其他中间语言，但最终结果必是机器语言。 4. 目标程序：由机器指令构成的程序。目标程序是经过翻译程序加工后用目标语言 表示的程序。 5. 翻译程序：能够把某一种语言程序(源程序)改造成另一种语言程序(目标程序)将 源程序译成逻辑上等价的目标程序的程序。翻译程序有两种工作方式：编译和解释。 6. 编译程序：也称翻译程序 7. 解释程序：有些翻译程序在翻译过程中并不产生完整的目标程序，而是翻译一句， 解释执行一句，这样的称为解释程序。 8. 汇编程序：由汇编语言写成的程序 9. 词法分析：执行词法分析的程序成为词法分析器，词法分析依据的是语言构词规 则。词法分析器从文件读入源程序，由字符拼接单词。每当识别出一个单词，词法分析器就输出这个单词的内部码。 10. 语法分析：执行语法分析的程序叫做语法分析器。语法分析的任务就是根据语言 的规则，将词法分析器所提供的单词种别分成各类语法范畴。 11. 中间代码生成：中间代码产生有时称为语义分析，执行中间代码产生的程序称为 中间代码生成器。他的任务时按照语法分析器所识别出的语法范畴产生相应的中间代码，并建立符号表、常数表，等各种表格。 12. 目标代码生成：执行目标代码生成的程序称为目标代码生成器。他的任务是根据 中间代码和表格信息，确定各类数据在内存中的位置，选择合适的指令代码，将中间代码翻译成汇编语言或机器指令，这部分工作与计算机硬件有关。 13. 符号表：用于记录源程序中出现的标识符，一个标识符往往具有一系列的语义 值，她包括标识符的名称、种属、类型、值存放的地址等等。 14. 常数表：用于记录在源程序中出现的常数。 15. 编译程序前端：是由词法分析器、语法分析器和中间代码产生器组成的。她的特 点是依赖于被编译的源程序，输出结果用中间代码描述，和目标机器无关。16. 编译程序后端：是由目标代码生成器组成，他的特点是和源程序无关，以中间代 码形式的源程序为输入进行处理，输出结果依赖于目标机器。 17. 文本文件：文本文件的内容由94个图形字符‘！‘-' ~ '(33-126)和4个 控制字符换行(10)、回车(13)、空格(32)、TAB( 9)构成，文本文件又称为 ASCII码文件，扩展名通常为TXT,文件尾用控制字符EOF( 26)指示。 18. 二进制文件：由机器指令即二进制数构成，因二进制数可能是26 (文件结束控制 符)，故文件尾用文件长度(文件的字节数)指示，扩展名通常为EX E。 19. 源代码(source code)—预处理器(preprocessor) —编译器(compiler) —汇编程序 (assembler)—目标代码(object code)—链接器(Linker) —可执行程序 (executables) 20. 编译程序的流程是： 源程序―》词法分析―》语法分析―》语义分析(中间代码产生)―》目标 代码生成-》目标程序
第一章 1、将编译程序分成若干个“遍”是为了。 a．提高程序的执行效率 b．使程序的结构更加清晰 c．利用有限的机器内存并提高机器的执行效率 d．利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法d．以上三项都是 3、变量应当。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、不可能是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则b．语法规则 c．产生规则d．词法规则 7、词法分析器的输入是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于。 2、编译过程通常可分为5个阶段，分别是、语法分析、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是，最后阶段的输出为程序。 4、编译程序是指将程序翻译成程序的程序。 单选解答 1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。 2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。 3、对编译而言，变量既持有左值又持有右值，故选c。 4、编译程序打交道最多的就是各种表格，因此选d。 5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。 6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。 7、b 8、c 9、d 10、c 多选解答 1．b、c 2. a、b、c、e 填空解答
第一章引论 1.编译过程的阶段 由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 2.编译程序的概念 3.编译程序的结构 例：（B）不是编译程序的组成部分。 A. 词法分析器； B. 设备管理程序 C. 语法分析程序； D. 代码生成程序 4.遍的概念 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 5.编译程序与解释程序的区别 例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D）。 A. 单用户与多用户的差别 B. 对用户程序的差错能力 C. 机器执行效率 D. 是否生成目标代码 第三章文法和语言 文法的概念 字母表、符号串和集合的概念及运算 例：(ab|b)*c 与下面的那些串匹配？（ACD） A. ababbc； B. abab； C. c； D. babc； E. aaabc 例：ab*c*(a|b)c 与后面的那些串匹配？（BC） A.acbbc B.abbcac C.abc D.acc 例：(a|b)a+(ba)*与后面的那些串匹配? （ADE）A.ba B.bba C.ababa D.aa E.baa 文法的定义（四元组表示） 文法G定义为四元组（V N，V T，P，S） V N：非终结符集 V T：终结符集 P：产生式（规则）集合 S：开始符号（或识别符号） 例：给定文法，A::= bA | cc，下面哪些符号串可由其推导出（①② ⑤）。 ①cc ②b*cc ③b*cbcc ④bccbcc ⑤bbbcc 什么是推导 例：已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 试给出下述表达式的推导：i*i+i 推导过程：E->E+T ->T+T ->T*F+T ->F*F+T ->i*F+T ->i*i+T ->i*i+F ->i*i+i ●句型、句子的概念 例：假设G一个文法，S是文法的开始符 号，如果S=>*x，则称x是句型。 例：对于文法G，仅含终结符号的句型称 为句子。 ●语言的形式定义 例：设r=(a|b|c)(x|y|z)，则L(r)中元素为 9个。 例：文法G产生式为S→AB，A→aAb|ε， B→cBd|cd，则B∈L(G)。 A. ababcd； B. ccdd； C. ab； D. aabb ●等价文法 例：如果两个文法描述了同一个语言，则这两个文法是等价文法。 ●文法的类型 0型：左边至少有一个非终结符 1型：右边长度>=左边长度 2型：左边有且仅有一个非终结符 3型：形如：A->aB,A->a 各类型文法都是逐级包含关系， 例：文法S→abC|c，bC→d是几型文法？0 型 例：文法S→abC，bC→ad是几型文法？1 型 例：文法G[A]：A→ε，A→aB，B→Ab，B→a 是几型文法？2型 例：文法S→a|bC，C→d是几型文法？ 3
《编译原理》实验报告 实验3 递归下降分析器的设计 学号班级计科1001班 时间：2012/4/15 地点:文波 同组人：无 指导教师：朱少林 实验目的 使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。 实验容 a.运用所学知识，编程实现递归下降语法分析程序。使用递归下降分析算法分析表达式 是否符合下文法： exp →exp addop term | term Addop →+ | - term→term mulop factor | factor mulop →* | / factor →(exp) | id | number 其中number可以是多位的十进制数字串（整数即可），因此这里还需要一个小的词法分析器来得到id 和number的值。 b.从数据文件中读出符号串，输出表达式并给出其正误评判。 实验数据文件中应该有多个表达式，可能有正确的也应该有错误的表达式；表达式有形式简
单的也应该有复杂的。每个表达式写在一行，以回车结束。 实验环境 软件：VC++6.0 实验前准备 1、方案设计： ①准备模拟数据：本实验中使用“work..cpp” ②程序思想： 为了使用递归向下的分析，为每个非终结符根据其产生式写一个分析程序，由于写入读出的操作频繁。所以程序中还有一个match(char t)函数，该函数是将字符写入文件打印输出同时从文件中读取下一个字符，而由于id和number可能是多个字符构成，故写了number()和id（）来分析数字和标识符，它们的功能仅仅是把整个number或id完整的读取出来并写入文件，打印输出。 由于分析的文件中可能出现非法字符，而一旦发现非法字符就无需再接着分析，所以在每次读取一个字符时调用islegal函数判断是否是合法字符，并返回0或1. 在main()函数中，while((lookahead=='\n'||lookahead==' ')&&lookahead!=EOF) fscanf(resource,"%c",&lookahead); 是为了忽略分析文件中的换行或空格，之后进入分析阶段，根据返回值判断是否是合法的表达式。在该程序中只有发现了非法字符才会返回0，否则就返回1，而对于合法的表达式，递归程序最后分析的字符就是换行符，不合法的表达式在未分析到换行符就会停止分析，所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。
1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？ 【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。 1.3 请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？ 【解答】编译程序总框图如图所示。 作为一个编译程序的总设计师，首先要深刻理解被编 译的源语言其语法及语义；其次，要充分掌握目标指令的 功能及特点，如果目标语言是机器指令，还要搞清楚机器 的硬件结构以及操作系统的功能；第三，对编译的方法及 使用的软件工具也必须准确化。总之，总设计师在设计编 译程序时必须估量系统功能要求、硬件设备及软件工具等 诸因素对编译程序构造的影响等。 2.2 什么是扫描器？扫描器的功能是什么？ 【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。