编译器构造

本书是一本经典的面向本科生理解编译原理和编译器构造的课程教材。本书以简洁、清晰的风格全面介绍了编译器构造的基本知识与关键技术。本书的三位原作者大学拥有30余年的编译器课程教学经验，根据他们丰富的教学经验和研究经验编写了这本教材。本书结合程序语言和编译技术的发展，以Java语言作为编译器的分析对象，并且采用面向对象的设计模式来组织编译器中的数据结构，在很大程度上降低了编译器构造的复杂程度，使初学编译器的读者能更加容易地上手实现自己的编译器。

本书面向初学者，从编译器构造的角度进行分析，旨在帮助读者深入理解编译器的设计原理和方法。全书共14章，主要内容包括：词法分析和语法分析、语法制导翻译、符号表和声明处理、语义分析、虚拟机代码、运行时支持、目标代码生成等。全书内容安排紧凑合理，对编译器构造的基本知识与关键技术进行了深入浅出的讲解，并提供了详尽清晰的算法，倡导在实践中学习编译器构造的相关技术。本书不仅可作为计算机专业本科生或研究生的教材，也适合作为相关领域技术人员的参考书。

目　　录<br />Crafting a Compiler<br />前言<br />致谢<br />第1章　引言　1<br />1.1　编译技术历史　1<br />1.2　编译器的功能　2<br />1.2.1　编译器生成的机器代码　3<br />1.2.2　目标代码格式　4<br />1.3　解释器　5<br />1.4　语法和语义　6<br />1.4.1　静态语义　7<br />1.4.2　运行时语义　7<br />1.5　编译器的组织　9<br />1.5.1　词法分析器　10<br />1.5.2　语法分析器　10<br />1.5.3　类型检查器　10<br />1.5.4　翻译器　10<br />1.5.5　符号表　11<br />1.5.6　优化器　11<br />1.5.7　代码生成器　11<br />1.5.8　编译器编写工具　12<br />1.6　程序设计语言和编译器设计　12<br />1.7　计算机体系结构和编译器设计　13<br />1.8　编译器设计考虑　13<br />1.8.1　调试编译器　14<br />1.8.2　优化编译器　14<br />1.8.3　可重定位编译器　14<br />1.9　集成开发环境　15<br />习题　15<br />第2章　一个简单的编译器　18<br />2.1　ac语言的一个非形式化定义　18<br />2.2　ac的形式化定义　19<br />2.2.1　语法规范　19<br />2.2.2　单词规范　20<br />2.3　一个简单编译器的各阶段　21<br />2.4　词法分析　22<br />2.5　语法分析　23<br />2.5.1　预测语法分析例程　24<br />2.5.2　实现产生式　25<br />2.6　抽象语法树　25<br />2.7　语义分析　27<br />2.7.1　符号表　27<br />2.7.2　类型检查　27<br />2.8　代码生成　29<br />习题　31<br />第3章　词法分析——理论与实践　32<br />3.1　词法分析器概述　32<br />3.2　正则表达式　34<br />3.3　示例　35<br />3.4　有限自动机与词法分析器　36<br />3.5　词法分析器生成器　39<br />3.5.1　在Lex中定义单词　40<br />3.5.2　字符集　40<br />3.5.3　使用正则表达式定义单词　41<br />3.5.4　使用Lex处理字符　43<br />3.6　其他词法分析器生成器　44<br />3.7　构建词法分析器的实际考虑　45<br />3.7.1　处理标识符和字面值　45<br />3.7.2　使用编译器指示以及列出<br />源码行　48<br />3.7.3　结束词法分析器　49<br />3.7.4　多超前字符　49<br />3.7.5　性能考虑　51<br />3.7.6　词法错误恢复　52<br />3.8　正则表达式和有限自动机　53<br />3.8.1　将正则表达式转换为NFA　54<br />3.8.2　创建DFA　54<br />3.8.3　优化有限自动机　56<br />3.8.4　将有限自动机转换为正则<br />表达式　58<br />3.9　总结　60<br />习题　61<br />第4章　文法和语法分析　64<br />4.1　上下文无关文法　64<br />4.1.1　最左推导　66<br />4.1.2　最右推导　66<br />4.1.3　语法分析树　66<br />4.1.4　其他类型的文法　67<br />4.2　CFG的性质　68<br />4.2.1　归约文法　68<br />4.2.2　二义性　68<br />4.2.3　错误的语言定义　69<br />4.3　转换扩展文法　69<br />4.4　语法分析器和识别器　70<br />4.5　文法分析算法　72<br />4.5.1　文法表示　72<br />4.5.2　推导空字符串　73<br />4.5.3　First集　74<br />4.5.4　Follow集　77<br />习题　79<br />第5章　自顶向下语法分析　82<br />5.1　概述　82<br />5.2　LL(k)文法　83<br />5.3　递归下降LL(1)语法分析器　85<br />5.4　表驱动LL(1)语法分析器　86<br />5.5　获得LL(1)文法　88<br />5.5.1　公共前缀　88<br />5.5.2　左递归　89<br />5.6　一个非LL(1)语言　90<br />5.7　LL(1)分析器的性质　92<br />5.8　分析表的表示　92<br />5.8.1　紧凑存储　93<br />5.8.2　压缩　94<br />5.9　语法错误恢复和修复　96<br />5.9.1　错误恢复　96<br />5.9.2　错误修复　96<br />5.9.3　LL(1)分析器中的错误检测　97<br />5.9.4　LL(1)分析器中的错误恢复　97<br />习题　98<br />第6章　自底向上语法分析　102<br />6.1　概述　102<br />6.2　移进–归约语法分析器　103<br />6.2.1　LR语法分析器和最右推导　103<br />6.2.2　LR分析如针织　104<br />6.2.3　LR分析引擎　105<br />6.2.4　LR分析表　105<br />6.2.5　LR(k)分析　107<br />6.3　构造LR(0)分析表　109<br />6.4　冲突诊断　113<br />6.4.1　二义性文法　114<br />6.4.2　非LR(k)文法　116<br />6.5　冲突消解和表构造　117<br />6.5.1　SLR(k)分析表构造　117<br />6.5.2　LALR(k)分析表构造　120<br />6.5.3　LALR传播图　122<br />6.5.4　LR(k)表构造　125<br />习题　129<br />第7章　语法制导翻译　135<br />7.1　概述　135<br />7.1.1　语义动作和语义值　135<br />7.1.2　综合属性和继承属性　136<br />7.2　自底向上语法制导翻译　137<br />7.2.1　示例　137<br />7.2.2　 产生式克隆　139<br />7.2.3　强制执行语义动作　140<br />7.2.4　激进的文法重构　141<br />7.3　自顶向下语法制导翻译　142<br />7.4　抽象语法树　143<br />7.4.1　具体语法树与抽象语法树　144<br />7.4.2　一种高效的AST数据结构　144<br />7.4.3　创建AST的基础架构　145<br />7.5　AST设计和构造　146<br />7.5.1　设计　147<br />7.5.2　构造　148<br />7.6　左值和右值的AST结构　150<br />7.7　AST设计模式　152<br />7.7.1　节点类层次　152<br />7.7.2　访问者模式　153<br />7.7.3　反射访问者模式　154<br />习题　157<br />第8章　符号表和声明处理　160<br />8.1　构造符号表　160<br />8.1.1　静态作用域　161<br />8.1.2　符号表接口　162<br />8.2　块结构语言和作用域　163<br />8.2.1　处理作用域　163<br />8.2.2　单符号表还是多符号表　163<br />8.3　基本实现技术　164<br />8.3.1　插入和查找名字　164<br />8.3.2　名字空间　166<br />8.3.3　一个高效的符号表实现　166<br />8.4　高级特性　169<br />8.4.1　记录和类型名　169<br />8.4.2　重载和类型层次　170<br />8.4.3　隐式声明　170<br />8.4.4　导出指示和导入指示　171<br />8.4.5　改变搜索规则　171<br />8.5　声明处理基础　172<br />8.5.1　符号表中的属性　172<br />8.5.2　类型描述符结构　172<br />8.5.3　使用抽象语法树进行类型<br />检查　173<br />8.6　变量和类型声明　174<br />8.6.1　简单变量声明　174<br />8.6.2　处理类型名　175<br />8.6.3　类型声明　176<br />8.6.4　变量声明再探　178<br />8.6.5　静态数组类型　179<br />8.6.6　结构和记录类型　180<br />8.6.7　枚举类型　181<br />8.7　类和方法声明　183<br />8.7.1　处理类声明　184<br />8.7.2　处理方法声明　186<br />8.8　类型检查简介　188<br />8.8.1　简单标识符和字面量　190<br />8.8.2　赋值语句　190<br />8.8.3　检查表达式　191<br />8.8.4　检查复杂名字　191<br />8.9　总结　194<br />习题　195<br />第9章　语义分析　198<br />9.1　控制结构的语义分析　198<br />9.1.1　可达性和终止分析　199<br />9.1.2　if语句　200<br />9.1.3　while、do和repeat循环<br />语句　203<br />9.1.4　for循环语句　204<br />9.1.5　break、continue、return和<br />goto语句　205<br />9.1.6　switch和case语句　210<br />9.1.7　异常处理　214<br />9.2　方法调用的语义分析　218<br />9.3　总结　223<br />习题　223<br />第10章　中间表示　227<br />10.1　概述　227<br />10.1.1　示例　228<br />10.1.2　中端　229<br />10.2　Java虚拟机　230<br />10.2.1　简介和设计原则　230<br />10.2.2　类文件内容　231<br />10.2.3　JVM指令　232<br />10.3　静态单赋值形式　237<br />习题　239<br />第11章　虚拟机代码生成　241<br />11.1　代码生成访问者　241<br />11.2　类和方法声明　243<br />11.2.1　类声明　243<br />11.2.2　方法声明　245<br />11.3　MethodBodyVisitor　245<br />11.3.1　常量　245<br />11.3.2　局部存储引用　246<br />11.3.3　静态引用　246<br />11.3.4　表达式　247<br />11.3.5　赋值　248<br />11.3.6　方法调用　249<br />11.3.7　字段引用　250<br />11.3.8　数组引用　251<br />11.3.9　条件执行　252<br />11.3.10　循环　252<br />11.4　LHSVisitor　253<br />11.4.1　局部引用　254<br />11.4.2　静态引用　254<br />11.4.3　字段引用　255<br />11.4.4　数组引用　255<br />习题　256<br />第12章　运行时支持　258<br />12.1　静态分配　258<br />12.2　栈分配　259<br />12.2.1　类和结构中的字段访问　260<br />12.2.2　运行时访问帧　261<br />12.2.3　处理类和对象　262<br />12.2.4　处理多重作用域　263<br />12.2.5　块级分配　264<br />12.2.6　关于帧的更多讨论　265<br />12.3　数组　267<br />12.3.1　静态一维数组　267<br />12.3.2　多维数组　270<br />12.4　堆管理　272<br />12.4.1　分配机制　272<br />12.4.2　释放机制　274<br />12.4.3　自动垃圾收集　274<br />12.5　基于区域的内存管理　279<br />习题　280<br />第13章　目标代码生成　284<br />13.1　翻译字节码　285<br />13.1.1　分配内存地址　286<br />13.1.2　分配数组和对象　286<br />13.1.3　方法调用　288<br />13.1.4　字节码翻译过程的示例　290<br />13.2　翻译表达式树　291<br />13.3　寄存器分配　294<br />13.3.1　动态寄存器分配　294<br />13.3.2　使用图着色进行寄存器<br />分配　296<br />13.3.3　基于优先级的寄存器分配　300<br />13.3.4　过程间寄存器分配　301<br />13.4　代码调度　302<br />13.4.1　改进代码调度　305<br />13.4.2　全局和动态代码调度　306<br />13.5　指令自动选择　307<br />13.5.1　使用BURS选择指令　308<br />13.5.2　使用Twig选择指令　310<br />13.5.3　其他方法　310<br />13.6　窥孔优化　311<br />13.6.1　窥孔优化级别　311<br />13.6.2　自动生成窥孔优化器　313<br />习题　314<br />第14章　程序优化　318<br />14.1　概述　318<br />14.2　控制流分析　323<br />14.2.1　控制流图　323<br />14.2.2　程序和控制流结构　325<br />14.2.3　直接过程调用图　325<br />14.2.4　深度优先生成树　326<br />14.2.5　支配关系　329<br />14.2.6　简单的支配关系计算算法　330<br />14.2.7　快速的支配关系计算算法　332<br />14.2.8　支配前沿　339<br />14.2.9　区间　341<br />14.3　数据流分析介绍　349<br />14.3.1　可用表达式　349<br />14.3.2　活跃变量　351<br />14.4　数据流框架　352<br />14.4.1　数据流评估图　353<br />14.4.2　交格　354<br />14.4.3　转移函数　355<br />14.5　求解　356<br />14.5.1　迭代　356<br />14.5.2　初始化　359<br />14.5.3　终止和快速框架　360<br />14.5.4　满足分配律的框架　363<br />14.6　常量传播　364<br />14.7　SSA形式　366<br />14.7.1　放置函数　368<br />14.7.2　重命名　369<br />习题　371<br />参考文献　378