编译方法、技术与实践

本书是在教育部计算机领域本科教育教学改革试点工作计划（简称“101计划”）“编译原理”课程组的组织下编写的理论教材之一。与其他同类理论教材相比，本书在介绍编译理论和方法的同时，更强调实践技术，并注重编译理论与实践的结合。在内容方面，本书的理论部分涵盖了当前主流编译器编译过程中的核心技术要点，实践部分则引导学生基于理论知识构建一个能够将以类C语言编写的源程序编译为MIPS目标语言代码的完整编译器。在教学中，教师能够参考本书完整地进行理论教学和实践指导，其内容已经包括了相关资料。

一方面，当前许多“编译原理”课程理论教材以传授理论知识为主，其中的内容离编译器具体实践尚有一定的距离。这可能使学生偏重学习理论和方法，而对编译器实现缺乏更为深刻的理解。另一方面，常规的“编译原理”实践课程大多基于一门相对简易的编程语言，要求学生实现支持该语言语法和语义处理部分的编译器。由于缺乏规范化的实践指导，有时会降低教学要求，不得不允许学生“灵活”（较为随意）地实现编译器的功能；又或者由于教学要求过高，学生在无实践指导的情况下对编译器实现无法下手，而对课程产生较大的抵触心理。针对这些问题，本书面向开设计算机学科的大专院校，提供一门接近实际C语言的C--语言，从理论方法的解说到实践指导的进行，引导性地讲解理论知识和编译器的具体实现，并提供充分的测试样例来验证编译器实现的正确性。

整体而言，基于本书介绍的理论方法和实践技术，我们设计了相应的实践内容，系统性地覆盖理论方法和实践技术部分的各个知识点。本书的实践内容具有四个特点：一是接近实际，所采用的语言是C--语言，该语言接近现实中常用的C语言，这使得所设计与实现的编译器更为实用，甚至在特定领域可以直接或经过少量修改后使用；二是结合相关的实践技术进行介绍，引导学生完成一个完整编译器的设计与实现，不会使学生出现面对编译器实现要求无从下手或不得不求助于第三方额外资料的情况；三是具备相关的实现验证帮助，我们提供了充分的测试样例来帮助验证编译器实现的正确性，而无须自行设计测试用例；四是难度可调，我们提供了实践内容的多种执行方案，既可以统一难度要求，也可以区分必做内容和选做内容，还可以采用学生分组方案，使得每个组队实现不同的功能组合，激发学生的思考创新能力，并锻炼其合作能力。下面我们就本书的使用方式、时间安排以及质量控制给出一些建议。

使用方式

本书包含五个核心章（从第2章至第6章），前后贯穿，分别为词法分析和语法分析、语义分析、中间代码生成、目标代码生成以及中间代码优化。每章的理论和实践内容依赖于前续章，教学需按顺序进行。在这五章中，除了第5章之外，其他章节的实践内容均分为必做部分和选做部分，而选做部分则进一步分为几种不同的要求（第5章仅有必做部分）。这五章中的实践内容特别考虑了不同院校的教学要求以及学生之间的能力差异，因而可以采用多种方式教学：

1.对所有学生要求相同：这是最简单的使用方式，适用于学习编译原理的所有学生都需要通过相同考核要求的情况。具体而言，可进一步划分为下面三种情况：

(1)对所有学生要求最低：完成所有实践的必做部分，即可获得满分。

(2)对所有学生要求最高：完成所有实践的必做部分和选做部分，才可获得满分。

(3)对所有学生要求自选：完成所有实践的必做部分，即可得满分。但若能额外完成实践的选做部分，则可视完成的情况获得额外奖励。

2.对不同学生要求不同：这种使用方式适用于学习编译原理的学生需要通过不同考核要求的情况。比如强化班和普通班的学生一起上编译原理课程，则要求强化班学生完成所有实践的必做部分和选做部分才可获得满分，而普通班学生完成所有实践的必做部分即可得满分，但若能额外完成实践的选做部分，则可获得额外奖励。

3.对不同组队要求不同：这是最复杂的使用方式，适用于允许学生自由组队以共同完成实践要求的情况。推荐的组队规模是一至三人，比如，若双人组队则为正常模式，可获得实践满分，若三人组队则为互助模式，需适当减少实践总分（如变为原来满分的90%），若单人组队则为高手模式，可适当提高实践总分（如变为原来满分的110%）。在实践要求方面，仍可考虑不同的考核要求而组合不同的必做和选做部分，或者完成指定或随机选择的实践要求。比如，一位强化班学生需要完成所有实践的必做部分和选做部分才可获得满分，他可以单人组队进入高手模式以获得更高的总分，也可以双人组队进入正常模式，以减少实践难度。

时间安排

本书从第2章至第6章是核心教学内容，一个学期完成教学，预计时长17周，每周2～3课时。各章的内容应依顺序进行教学，每完成前一章中理论方法和实践技术部分的教学即可开始后一章中对应部分的教学。实践内容部分作为课程项目布置，可略晚开始，比如，第2章的实践内容可从第2周开始布置，以保证前期进行了必要的理论方法和实践技术的讲授和准备，而后续章节的实践内容可与教学同步进行。一般而言，如果一个学期时长17周，建议第1章和第2章的教学内容在第1～5周内完成，第3章的教学内容在第6～9周内完成，第4章的教学内容在第10～12周内完成，第5章和第6章的教学内容在第13～17周内完成，其中第5章的理论教学在第13周和第14周内完成，第6章的理论教学内容在第15～17周内完成。下图展示了一个教学计划的安排示例。

教学安排计划甘特图

需要说明的是，第5章和第6章实践内容的输入均是中间代码。在我们完成了第5章的实践内容之后，基本上就实现了从C--源程序到MIPS目标程序的整个编译过程。我们设计第6章实践内容的目的是引导学生完成中间代码的优化，让编译器生成更为高效的目标代码。因此，第6章的实践内容相对于其他章节较为独立，可以根据教学和实践情况进行取舍。对于学有余力的学生，建议将第4章实践内容输出的中间代码，输入至第6章实践内容构建的中间代码优化模块中完成优化之后，再输入至第5章构建的中间代码到目标代码的翻译器内，完成整个编译过程。基于此，我们建议从第2周开始第2章词法和语法分析的实践内容，在第5周末结束这部分实践内容并开始第3章语义分析的实践内容，在第9周末结束语义分析的实践内容并开始第4章中间代码生成的实践内容，在第12周末结束中间代码生成的实践内容并同时开始第5章目标代码生成和第6章中间代码优化的实践内容。在第17周末结束时完成第5章和第6章的实践内容，内部可以自由分配两者的时间，最终实现整个编译器。如果一个学期的教学时长更短或更长，可做相应微调，比如，在学时更短的情况下，可以适当提前第2章实践内容的结束时间（由四周变为三周）。

如果由于教学上的特殊安排或其他原因，导致本书的理论方法和实践技术教学落后于实践内容的安排，也可以推迟部分实践内容的结束时间并同时保证后续实践内容的开始时间来形成更为紧凑的安排。比如，若第2章的理论方法和实践技术教学无法在第5周完成，那么可以允许第2章的实践内容推迟一周结束（即在第6周结束），但第3章的实践内容仍保持在第5周开始（即两者重叠一周时间）。这样既可以帮助部分学生更好地完成第2章的实践内容，也可以允许其余学生正常地开始第3章的实践内容。

质量控制

编译原理课程实践的质量控制旨在鼓励学生在完成实践内容的过程中增强学习兴趣，提高所实现编译器的质量，以及抑制不良行为（如抄袭代码）的发生。本书的实践内容设计也正有这方面的考虑。

1.提高实践质量：本书从测试用例方面来提高实践内容的质量。

本书的实践内容部分提供了大量测试样例来帮助学生自检编译器的实现是否符合实践要求，在教学中也可引入更多的测试用例（可根据实践内容的要求和已有的测试样例推导）来进一步测试学生所实现的编译器的质量，这将促使学生考虑更多的细节来更好地实现编译器。对于教师，我们也可提供更多的测试用例。

2.抑制不良行为：本书从分组实践和克隆检测两方面来抑制不良行为。

(1)分组实践：本书的实践内容设计了必做部分和选做部分，而选做部分又分为不同的要求，它们之间相互独立。在允许学生自由组队来协作完成实践内容的情况下，可进行必做部分和选做部分的随机组合。比如，根据抽签随机决定一组学生必须完成第2章实践内容的必做部分和选做部分的要求2.1，而另一组学生必须完成必做部分和选做部分的要求2.2，以此类推，后续章节的实践内容也可随机组合。如此可以增强不同组队间所完成内容的差异性，增大抄袭的难度。也可以进一步要求不允许完成其他组队的实践要求，这样也可以抑制不同组队之间的抄袭行为（可以通过测试用例的执行结果区别出是否完成了不允许的实践要求）。但要注意这种做法将与前述使用方式中的“对所有学生要求自选”的情况相抵触。

(2)克隆检测：本书的实践内容设计也允许在不同的学生代码之间进行克隆检测，特别是在分组实践的情况下，学生提交的代码不会完全类似（因为需要实现不同的要求）。为避免代码复制后经过简单变量名和函数名替换后重新提交为新的代码，建议采用基于可执行代码的二进制级克隆检测，并加以源码人工比对确认。采用必要的克隆检测可以进一步抑制学生抄袭代码的行为。

整体而言，本书强调从理论和实践两个方面指导与帮助学生深刻理解编译器的工作原理。其中，理论方法的教学使学生能够理解编译器运行过程中的核心算法，而实践技术则可帮助学生掌握理论方法及算法在代码实现层面的设计与编码要点，最后结合实践内容对理论方法与实践技术进行巩固。同时，本书在设计过程中加入了不同难度的实验要求，教师可以针对实际教学需求，选择不同的教学内容进行授课。

如果在阅读本书的过程中发现谬误，也请各位读者不吝赐教！