编译原理实践与指导教程

本书的编写面向开设计算机学科的大专院校，提供一门接近实际C++语言的C—语言语法，给出详细的实践步骤和指导过程，引导性地完成一个实际可用的编译器，并提供测试样例来验证编译器实现的正确性。本书的实验设计包括词法分析与语法分析、语义分析、中间代码生成以及目标代码生成四个部分，贯穿整个编译器设计的全过程。它具有接近实际、拥有指导、提供验证和难度可调四个特点，并给出了详细的使用方式、时间安排和质量控制方案。

许畅，南京大学计算机科学与技术系副教授、博士生导师。于2008年在香港科技大学获得博士学位，主要研究领域为软件工程、程序测试与分析、普适计算等。在相关领域承担科研项目10多项，发表论文70余篇。曾于2005和2006年获得IBM PHD Fellowship两次，2010年入选教育部新世纪优秀人才支持计划，2011年获得南京大学青年骨干教师称号和国家科学技术进步二等奖，2012年获得中创软件人才奖，2013年入选南京大学登峰人才支持计划，2014年获得南京大学北京银行“京”英奖教金和ACM南京分会新星奖，并获得ICSE2014 ACM SIGSOFT Distirnguished Paper Award和APSEC 2014 Best Paper Award。

丛书序言
前言
第1章 词法分析与语法分析 1
1.1 实验内容 1
1.1.1 实验要求 1
1.1.2 输入格式 2
1.1.3 输出格式 2
1.1.4 测试环境 3
1.1.5 提交要求 3
1.1.6 样例（必做内容） 4
1.1.7 样例（选做要求） 7
1.2 实验指导 11
1.2.1 词法分析概述 12
1.2.2 GNU Flex介绍 13
1.2.3 Flex：编写源代码 14
1.2.4 Flex：书写正则表达式 17
1.2.5 Flex：高级特性 19
1.2.6 词法分析提示 21
1.2.7 语法分析概述 22
1.2.8 GNU Bison介绍 24
1.2.9 Bison：编写源代码 26
1.2.10 Bison：属性值的类型 28
1.2.11 Bison：语法单元的位置 30
1.2.12 Bison：二义性与冲突处理 31
1.2.13 Bison：源代码的调试 33
1.2.14 Bison：错误恢复 35
1.2.15 语法分析提示 36
第2章 语义分析 38
2.1 实验内容 38
2.1.1 实验要求 38
2.1.2 输入格式 40
2.1.3 输出格式 41
2.1.4 测试环境 41
2.1.5 提交要求 41
2.1.6 样例（必做内容） 42
2.1.7 样例（选做要求） 48
2.2 实验指导 51
2.2.1 属性文法 52
2.2.2 符号表 53
2.2.3 支持多层作用域的符号表 56
2.2.4 类型表示 58
2.2.5 语义分析提示 61
第3章 中间代码生成 63
3.1 实验内容 63
3.1.1 实验要求 63
3.1.2 输入格式 66
3.1.3 输出格式 66
3.1.4 测试环境 67
3.1.5 提交要求 67
3.1.6 样例（必做内容） 67
3.1.7 样例（选做要求） 70
3.2 实验指导 73
3.2.1 中间代码的分类 74
3.2.2 中间代码的表示（线形） 76
3.2.3 中间代码的表示（树形） 77
3.2.4 初探运行时环境 78
3.2.5 翻译模式（基本表达式） 81
3.2.6 翻译模式（语句） 83
3.2.7 翻译模式（函数调用） 84
3.2.8 翻译模式（数组与结构体） 85
3.2.9 中间代码生成提示 86
第4章 目标代码生成 88
4.1 实验内容 88
4.1.1 实验要求 88
4.1.2 输入格式 89
4.1.3 输出格式 90
4.1.4 测试环境 90
4.1.5 提交要求 90
4.1.6 样例 91
4.2 实验指导 95
4.2.1 QtSPIM简易教程 95
4.2.2 MIPS32汇编代码书写 97
4.2.3 指令选择 100
4.2.4 寄存器分配（朴素寄存器分配算法） 102
4.2.5 寄存器分配（局部寄存器分配算法） 103
4.2.6 寄存器分配（图染色算法） 104
4.2.7 寄存器分配（活跃变量分析） 106
4.2.8 寄存器分配（MIPS寄存器的使用） 107
4.2.9 栈管理 108
4.2.10 目标代码生成提示 113
附录A C——语言文法 115
附录B 虚拟机小程序使用说明 122
附录C 资源下载和安装介绍 125
参考文献 127 

前  言本书与机械工业出版社于2009年出版的南京大学赵建华、郑滔和戴新宇所译的《编译原理》课本配合使用。该课本对应的英文版教材是美国哥伦比亚大学、斯坦福大学和Avaya实验室的Alfred V. Aho、Monica S. Lam、Ravi Sethi和Jeffrey D. Ullman所著的《Compilers: Principles, Techiques and Tools》，由于该书封面配有骑士和恐龙的图案，也被称为龙书。在下文中，如无特殊说明，课本均指该书（无论是中文翻译版还是英文原版）。 需要指出的是，虽然本书配合课本使用，但其内容已经包括所有相关的资料，因而它是内在完整的。这意味着，即使教学时使用其他编译原理相关的教材，本书仍能作为实践课程的教材，而不会出现所需资料不完整的情况。 设计思想通常而言，编译原理实践课程较难设计，原因是其对应的理论教材以传授知识为主，离具体实践有较大的距离。而常规的实践课程大多会给出一门简易语言的语法，要求学生实现对应于该语言的编译器。由于缺乏规范化的指导，时常导致要么降低教学要求，允许学生较为随意地实现编译器；要么要求过高，致使学生们无从下手，从而对编译原理实践课程产生较大的抵触心理。针对这些问题，本书面向开设计算机学科的大专院校，提供一门接近实际C/C++的C––语言语法，给出了详细的实验步骤和指导过程，引导性地完成一个实际可用的编译器，并提供了充分的测试样例来验证编译器实现的正确性。 本书共分为四章，分别关注编译器设计的四个重要阶段—词法分析与语法分析、语义分析、中间代码生成以及目标代码生成。每章都给出具体的实验要求、实验指导以及测试样例等，它们共同覆盖了一个实用编译器的设计与实现的全过程。 本书的实验设计具有四个特点：一是接近实际，所采用的语言是C––，接近现实中常用的C/C++，这使得所设计的编译器非常实用，甚至在特定的领域可以直接或经过少量修改后使用；二是配有指导教程，引导性地完成整个编译器的设计与实现，不会出现面对实验要求无从下手或不得不求助第三方资料的情况；三是具备验证帮助，提供大量的测试样例来验证编译器实现的正确性，而无需自行特别设计测试用例；四是难度可调，提供多种实验执行方案，既可统一难度要求，也可区分必做内容和选做内容，更可实现分组方案，使得每个组队实现不同的功能组合，激发学生的思考和锻炼协作能力。 使用方式本书四章对应四个实验，前后贯穿，分别为词法分析与语法分析、语义分析、中间代码生成以及目标代码生成，简称为实验一、实验二、实验三和实验四。每个实验依赖于其前面的实验，需按顺序进行。 在四个实验中，除了最后的实验之外，前三个实验均有必做部分和选做部分，而选做部分又进一步分为几个不同的要求。具体而言，实验一的要求包括必做部分和三个选做部分（要求1.1、要求1.2和要求1.3），实验二的要求包括必做部分和三个选做部分（要求2.1、要求2.2和要求2.3），实验三的要求包括必做部分和两个选做部分（要求3.1和要求3.2），最后的实验四则只有必做部分的要求。 这四个实验的设计特别考虑了不同院校的不同学生的能力和考核要求上的差异，具备多种使用方式。 1）所有学生相同要求  这是最简单的使用方式，适用于学习编译原理的所有学生需要通过相同考核要求的情况。具体而言，可细分为下面三种情况： 所有学生最低要求：完成所有实验的必做部分即可得满分。 所有学生最高要求：完成所有实验的必做部分和选做部分才可得满分。 所有学生自选要求：完成所有实验的必做部分即可得满分；若能完成实验的选做部分，则视完成情况给予额外奖励。 2）不同学生不同要求  这种使用方式适用于学习编译原理的学生需要通过不同考核要求的情况。比如强化班和普通班的学生一起上编译原理课程，则可要求强化班的学生完成所有实验的必做部分和选做部分才可得满分，而普通班的学生完成所有实验的必做部分即可得满分，若能完成实验的选做部分，则可获得额外奖励。 3）不同组队不同要求  这是最复杂的使用方式，适用于允许学生自由组队以共同完成实验要求的情况。推荐的组队规模是1～3人，如两人组队则为正常模式可获得实验满分，如三人组队则为互助模式需减少实验总分（如变为原来满分的90%），如单人组队则为高手模式可提高实验总分（如变为原来满分的110%）。在实验要求方面，仍可考虑不同的考核要求而选择不同的必做和选做部分，或者完成指定的或随机选择的实验要求。比如一位强化班的学生需要完成所有实验的必做部分和选做部分才可得满分，他可以单人组队进入高手模式以获得更高的总分，也可以两人组队进入正常模式以减少实验的难度。 4）编译优化额外奖励  实验三的设计特别考虑了编译优化的程度，即中间代码的执行效率（具体要求见实验三的实验内容部分）。编译优化属于额外奖励部分，如果中间代码的执行效率位于所有学生实验的前50%，则可获得实验三满分额外20%的奖励（即总分变为原来满分的120%）；如果中间代码的执行效率位于所有学生实验的前20%，则可获得实验三满分额外50%的奖励（即总分变为原来满分的150%）。这部分额外奖励与前面的三种使用方式既不重叠也不冲突，可根据实际情况考虑是否采用。 时间安排四个实验的安排依顺序进行，每个实验持续四周，每完成一个实验即可开始下一个实验，但实验一的开始可推迟两周，以等待对应的课本知识讲授。一般而言，如果一个学期时长18周，从第3周开始实验一，在第6周末结束实验一并在第7周开始实验二，在第10周末结束实验二并在第11周开始实验三，在第14周末结束实验三并在第15周开始实验四，在第18周末结束实验四以完成整个编译实践。如果一个学期时长更短或更长，可做相应调整。比如在更短的情况下，可以适当减少实验一的推迟时间（由两周减为一周）或实验三的时间（由四周减为三周）。 上面的实验时间安排是根据课本的知识体系而制订的，如果是其他编译原理教材，只要有下述的内容，也可模仿进行： 第1～6周：引论、词法分析、语法分析（实验一）；第7～10周：语法制导的翻译、中间代码生成（实验二）；第11～14周：中间代码生成、运行时刻环境、代码生成（实验三）；第15～18周：代码生成、机器无关的优化（实验四）。 如果由于教学上的特殊安排或别的原因，导致课本理论知识的讲解落后于实验安排，也可以采取推迟部分实验的结束时间并同时保证后续实验的开始时间的方法来安排实验。比如，若语法分析部分的课程讲授无法在第6周完成，那么可以允许实验一推迟一至两周结束（即在第7周或第8周结束），而实验二仍保持在第7周开始。这样既可以帮助部分学生更好地完成实验一（他们可能因为没有学习相应的课本知识而无法进行实验一），也可以允许另外的学生正常地开始实验二（与实验相关的内容在本书的实验指导部分已经提供，课本知识并不是必需的，但能帮助学生更好地理解知识）。 质量控制编译原理实践的质量控制是指在完成实验的过程中，鼓励学生增强学习兴趣，提高所实现编译器的质量以及抑制不良行为（如作弊）的发生。本书的实验设计正有这方面的考虑： 1）提高实验质量  本书从测试用例和编译优化两方面来提高实验质量。 测试用例：本书提供了大量测试样例来帮助学生自检编译器的实现是否符合实验要求，教学中可引入更多的额外测试用例（可根据实验要求和书中测试样例推导出）来进一步测试学生所实现编译器的质量，这将促使学生们考虑更多的细节来更好地实现编译器。 编译优化：实验三的设计特别考虑了编译优化的额外奖励，这将鼓励学生们努力尝试以获得更多的额外奖励。 2）抑制不良行为  本书从分组实验和克隆检测两方面来抑制不良行为。 分组实验：本书的实验设计了必做部分和选做部分，而选做部分又分为不同的要求，它们之间相互独立。在允许学生自由组队来协作完成实验内容的情况下，可进行必做部分和选做部分的随机组合。比如，根据抽签随机决定一组学生必须完成实验一的必做部分和选做部分的要求1.1，而另一组学生必须完成实验一的必做部分和选做部分的要求1.2，以此类推，后续的实验也可随机组合实验内容。这样可以增强不同组队间需要完成的实验内容的差异性，增加实验作弊的难度。也可以进一步要求不允许完成其他组队的选做实验（如前一组学生不能完成实验一选做部分的要求1.2），这样也可以抑制不同组队之间的作弊行为（可通过测试用例区别出是否跨组完成了实验要求）。但要注意这将与第一种使用方式中的“所有学生自选要求”的情况相抵触，在实验执行中要注意。 克隆检测：最后，本书的实验设计也允许进行实验代码间的克隆检测，特别是在分组实验的情况下，学生间实验代码几乎无法近似。为避免代码复制后经过简单变量名和函数名替换后重新提交为新的实验代码，建议采用基于可执行代码的克隆检测。采用必要的克隆检测可以进一步抑制学生实验作弊的行为。 以上介绍了本书编译原理实践的设计思想、使用方式、时间安排和质量控制。在使用过程中如有任何问题，欢迎和我们交流；如有不妥当之处，也敬请指出。