本书是在计算机领域本科教育教学改革试点工作计划“编译原理”课程组的组织下编写的理论教材之一。本书从理论和实践两个方面指导与帮助学生深刻理解编译器的工作原理。其中，理论方法的教学使得学生能够理解编译器运行过程中的核心算法，而实践技术则帮助学生掌握理论方法及算法在代码实现层面的设计与编码要点，最后结合实践内容对理论方法与实践技术进行巩固。本书适合作为高校计算机及相关专业编译原理课程的教材，也适合作为研发人员了解编译技术的参考书。

本书是在计算机领域本科教育教学改革试点工作计划“编译原理”课程组的组织下编写的理论教材之一。本书从理论和实践两个方面指导与帮助学生深刻理解编译器的工作原理。其中，理论方法的教学使得学生能够理解编译器运行过程中的核心算法，而实践技术则帮助学生掌握理论方法及算法在代码实现层面的设计与编码要点，最后结合实践内容对理论方法与实践技术进行巩固。本书适合作为高校计算机及相关专业编译原理课程的教材，也适合作为研发人员了解编译技术的参考书。

前　　言
本书是在计算机领域本科教育教学改革试点工作计划（简称“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周开始布置，以保证前期进行了必要的理论方法和实践技术的讲授和准备，而后续章节的实践内容可与教学同步进行。一般而言，如果一个

许畅，南京大学计算机科学与技术系教授，“101 计划”编译课程建设专家。2008年在香港科技大学获得博士学位，2010年入选新世纪优秀人才支持计划，2011年获得国
家科技进步二等奖，2015年获得CCF青年科学家奖，2021年入选长江学者奖励计划。主持和参与了多项国家和省部级科研项目，包括国家重点研发计划和自然科学基金重点项目等。研究兴趣包括大数据、软件工程、智能软件测试与分析，以及自适应与自控软件系统。发表了180余篇学术论文，工作被包括 TOSEM、TSE、ESEC/FSE、ICSE 和《中国科学》等在内的国内外知名期刊和会议收录，曾获 ACM SIGSOFT 杰出论文奖 4 次和国际会议最佳论文奖 3次。服务于 ESEC/FSE、ICSE 和 ASE 等程序委员会，担任 JSEP、JCST、FCS 和《计算机科学》等期刊
编委。
冯洋，南京大学计算机科学与技术系助理研究员。2019年在加州大学欧文分校获得博士学位。主要研究方向为复杂软件系统的质量保障及可信程序设计语言工程技术，研究课题包括大型复杂软件系统的质量保障问题及可信软件基础设施构建与工程技术问题。主持和参与了多项国家和省部级科研项目，包括国家重大专项计划、自然科学基金面上项目和青年项目。近年来在软件工程领域的
ICSE、FSE、ASE、ISSTA、TSE、TOSEM、《中国科学》《软件学报》等期刊和会议发表学术论文 40余篇，获得 ACM 杰出论文奖两次。申请发明专利多项，部分专利成果已经在华为、百度等知名公司转化应用。
郑艳伟，山东大学计算机科学与技术学院副研究员。2019年在北京航空航天大学获博士学位。主要研究方向包括计算机视觉、目标驱动的视觉导航、编译器构造。主持了国家重点研发计划与课题和自然科学基金重点项目与课题；主持多项横向项目，曾参与华为昇腾芯片算子和众智项目开发，曾在 RPA 中设计了一种脚本语言并开发了解释器。近年来在 ICDE、Com-Com、IoT-J、WASA、《中国科学》等期刊和会议发表学术论文 20余篇，申请发明专利 30 余项，担任IoT-J、JMLC、SPL、CIT 等期刊审稿人。
陈鄞，哈尔滨工业大学计算学部软件学院副教授。2008年在哈尔滨工业大学获得计算机应用专业博士学位。国家一流课程“编译原理”负责人，首批高校计算机专业优秀教师奖励计划获奖者。主要研究方向为软件工程、自然语言处理、机器学习等。参与完成多项国家自然科学基金项目和国家重点研发计划项目。2008年至今一直从事一线教学工作，主讲“编译原理”“信息检索”“自
然语言处理”“中文信息处理”等本科和研究生课程。获哈尔滨工业大学教学优秀奖 1 次，主编教材 3 部。
谭添， 南京大学计算机科学与技术系准聘助理授。2017年在新南威尔士大学获得博士学位，2017~2019年在奥胡斯大学从事博士后研究工作。主要研究方向为程序分析与程序设计语言，研究成果发表在TOPLAS、TOSEM、TSE、PLDI、OOPSLA、FSE 等领域内高水平期刊与会议上。
陈林，南京大学计算机科学与技术系副教授。2009年在东南大学获得博士学位。主持和参与了多项国家和省部级科研项目，包括国家重点研发计划和自然科学基金项目等，多次获得省部级科技进步奖。研究兴趣包括软件分析测试、软件生态系统质量保障等，与合作者在TSE、TOSEM、ICSE、FSE、《中国科学》和《软件学报》等国内外期刊和会议上发表论文100余篇，部分成果在华为等知名公司转化应用。

目　　录
出版说明
前言
第1章　概述　1
1.1　内容组织　1
1.2　编译器的结构　3
1.2.1　词法分析　4
1.2.2　语法分析　5
1.2.3　语义分析　5
1.2.4　中间代码生成　6
1.2.5　目标代码生成　7
1.2.6　中间代码优化　7
1.3　语言和工具简介　8
1.3.1　源语言C--简介　9
1.3.2　目标语言MIPS简介　9
1.3.3　MIPS模拟器简介　11
1.3.4　实践环境　12
第2章　词法分析和语法分析　13
2.1　词法分析和语法分析的理论方法　16
2.1.1　词法分析概要　16
2.1.2　正则表达式　18
2.1.3　有限状态自动机　21
2.1.4　从NFA到DFA的转换　24
2.1.5　状态最小化算法　25
2.1.6　语法分析概要　26
2.1.7　上下文无关文法　28
2.1.8　自顶向下的语法分析算法　30
2.1.9　自底向上的语法分析算法　33
2.2　词法分析和语法分析的实践技术　36
2.2.1　词法分析实现思想概述　37
2.2.2　GNU Flex介绍　37
2.2.3　Flex：编写源代码　38
2.2.4　Flex：书写正则表达式　41
2.2.5　Flex：高级特性　42
2.2.6　词法分析实践的额外提示　45
2.2.7　语法分析实现思想概述　46
2.2.8　GUN Bison介绍　46
2.2.9　Bison：编写源代码　48
2.2.10　Bison：属性值的类型　51
2.2.11　Bison：词法单元的位置　52
2.2.12　Bison：二义性与冲突处理　53
2.2.13　Bison：源代码的调试　55
2.2.14　Bison：错误恢复　56
2.2.15　语法分析实践的额外提示　57
2.3　词法分析和语法分析的实践内容　58
2.3.1　实践要求　58
2.3.2　输入格式　58
2.3.3　输出格式　59
2.3.4　验证环境　59
2.3.5　提交要求　60
2.3.6　样例（必做部分）　60
2.3.7　样例（选做部分）　63
2.4　本章小结　67
习题　67
第3章　语义分析　69
3.1　语义分析的理论方法　72
3.1.1　属性文法　72
3.1.2　基于属性文法的处理方式　73
3.1.3　S属性文法和L属性文法　75
3.1.4　语法制导的定义　76
3.1.5　语法制导的翻译方案　77
3.1.6　SDT中左递归的消除　78
3.1.7　类型检查　80
3.2　语义分析的实践技术　82
3.2.1　语义分析实现思想概述　82
3.2.2　符号表的设计与实现　83
3.2.3　支持多层作用域的符号表　85
3.2.4　类型表示　87
3.2.5　语义分析实践的额外提示　89
3.3　语义分析的实践内容　89
3.3.1　实践要求　89
3.3.2　输入格式　91
3.3.3　输出格式　91
3.3.4　验证环境　92
3.3.5　提交要求　92
3.3.6　样例（必做部分）　92
3.3.7　样例（选做部分）　98
3.4　本章小结　101
习题　102
第4章　中间代码生成　105
4.1　中间代码生成的理论方法　108
4.1.1　运行时环境概要　108
4.1.2　存储组织与栈帧设计方法　108
4.1.3　中间表示　110
4.1.4　类型与声明　111
4.1.5　表达式的翻译　113
4.1.6　控制流与回填　117
4.2　中间代码生成的实践技术　122
4.2.1　线形中间表示　122
4.2.2　图形中间表示　123
4.2.3　运行时环境简介　123
4.2.4　基本表达式的翻译模式　124
4.2.5　语句的翻译模式　125
4.2.6　函数调用的翻译模式　126
4.2.7　数组和结构体的翻译模式　127
4.3　中间代码生成的实践内容　127
4.3.1　实践要求　127
4.3.2　输入格式　130
4.3.3　输出格式　130
4.3.4　验证环境　130
4.3.5　提交要求　130
4.3.6　样例（必做部分）　131
4.3.7　样例（选做部分）　133
4.4　本章小结　135
习题　136
第5章　目标代码生成　139
5.1　目标代码生成的理论方法　142
5.1.1　代码生成概述　142
5.1.2　指令集架构　145
5.1.3　基本块与流图　147
5.1.4　指令选择算法　150
5.1.5　寄存器分配算法　153
5.1.6　窥孔优化　156
5.1.7　代码生成器构建　159
5.2　目标代码生成的实践技术　162
5.2.1　QtSpim简介　162
5.2.2　MIPS32汇编代码简介　165
5.2.3　指令选择算法实现　167
5.2.4　朴素寄存器分配算法实现　169
5.2.5　局部寄存器分配算法实现　170
5.2.6　活跃变量分析算法实现　170
5.2.7　图染色算法实现　171
5.2.8　MIPS寄存器的使用　174
5.2.9　MIPS栈管理　175
5.2.10　目标代码生成实践的额外提示　179
5.3　目标代码生成的实践内容　180
5.3.1　实践要求　180
5.3.2　输入格式　181
5.3.3　输出格式　181
5.3.4　验证环境　181
5.3.5　提交要求　181
5.3.6　样例（必做部分）　182
5.4　本章小结　185
习题　186
第6