编译方法、技术与实践

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

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

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