编译器设计实战：基于Python的增量式设计

本书将带领读者使用Python语言动手构建编译器，通过循序渐进的方法，在设计和实现编译器的过程中了解基本概念、算法和数据结构等相关知识。本书将每章作为构建编译器的一个基本“步骤”，逐步为编译器添加功能。全书涵盖变量、寄存器、条件、循环、元组、函数、动态类型、通用类型等内容。本书适合作为高等院校编译原理等课程的教材，也适合相关技术人员参考。

杰里米·G. 希克（Jeremy G. Siek） <br />印第安纳大学信息、计算与工程学院的计算机科学教授。他的主要研究方向为编程语言设计、类型系统、使用证明助手的机械化定理证明以及编译器优化。Jeremy曾出版The Boost Graph Library，还设计了C++的受限模板。他发明了渐变类型，这是一种在同一编程语言中整合动态类型和静态类型的类型系统。2009年，他获得美国国家科学基金会（NSF）教师早期职业发展奖，以资助其“弥合原型与生产之间的差距”项目；2010年和2015年，他获得苏格兰信息学与计算机科学联盟（SICSA）杰出访问学者奖学金。他是印第安纳大学编程系统中心的成员。

目　　录<br />Essentials of Compilation: An Incremental Approach in Python<br />译者序<br />前言<br />第1章　预备知识　1<br />1.1　抽象语法树　1<br />1.2　语法　3<br />1.3　模式匹配　5<br />1.4　递归函数　6<br />1.5　解释器　7<br />1.6　编译器示例：部分求值器　10<br />第2章　整数与变量　12<br />2.1　LVar语言　12<br />2.1.1　通过方法覆盖来扩展<br />解释器　13<br />2.1.2　LVar的定义性解释器　14<br />2.2　x86Int汇编语言　16<br />2.3　规划x86汇编之旅　20<br />2.4　移除复杂操作数　21<br />2.5　选择指令　23<br />2.6　分配变量存储　24<br />2.7　修补指令　25<br />2.8　生成起始和收尾代码　26<br />2.9　挑战：LVar的部分求值器　26<br />第3章　语法分析　28<br />3.1　词法分析和正则表达式　28<br />3.2　文法和解析树　30<br />3.3　二义性文法　32<br />3.4　从解析树到抽象语法树　33<br />3.5　Earley算法　34<br />3.6　LALR（1）算法　39<br />3.7　进一步阅读　42<br />第4章　寄存器分配　43<br />4.1　寄存器和调用约定　44<br />4.2　活跃性分析　46<br />4.3　构建干涉图　49<br />4.4　利用数独进行图着色　50<br />4.5　修补指令　55<br />4.6　生成起始和收尾代码　56<br />4.7　挑战：传送偏置　57<br />4.8　进一步阅读　59<br />第5章　布尔值和条件表达式　61<br />5.1　LIf语言　62<br />5.2　LIf 程序的类型检查　64<br />5.3　CIf中间语言　67<br />5.4　x86If 语言　68<br />5.5　收缩LIf语言　70<br />5.6　移除复杂操作数　70<br />5.7　详细控制　71<br />5.8　选择指令　77<br />5.9　寄存器分配　78<br />5.9.1　活跃性分析　78<br />5.9.2　构建干涉图　79<br />5.10　修补指令　79<br />5.11　生成起始和收尾代码　79<br />5.12　挑战：优化块和移除跳转　81<br />5.12.1　优化块　81<br />5.12.2　移除跳转　82<br />5.13　进一步阅读　83<br />第6章　循环和数据流分析　84<br />6.1　LWhile语言　84<br />6.2　循环控制流和数据流分析　86<br />6.3　移除复杂操作数　89<br />6.4　详细控制　89<br />6.5　寄存器分配　90<br />第7章　元组和垃圾回收　91<br />7.1　LTup语言　91<br />7.2　垃圾回收　94<br />7.2.1　双空间复制收集器　94<br />7.2.2　通过Cheney算法进行图的<br />复制　96<br />7.2.3　数据表示　97<br />7.2.4　垃圾回收器的实现　98<br />7.3　显露分配　99<br />7.4　移除复杂操作数　101<br />7.5　详细控制和CTup语言　101<br />7.6　选择指令和x86Global语言　102<br />7.7　寄存器分配　106<br />7.8　生成起始和收尾代码　106<br />7.9　挑战：数组　107<br />7.9.1　数据表示　110<br />7.9.2　重载解析　111<br />7.9.3　边界检查　111<br />7.9.4　显露分配　111<br />7.9.5　移除复杂操作数　112<br />7.9.6　详细控制　112<br />7.9.7　选择指令　112<br />7.10　进一步阅读　112<br />第8章　函数　114<br />8.1　LFun语言　114<br />8.2　x86汇编下的函数　118<br />8.2.1　调用约定　118<br />8.2.2　高效的尾调用　120<br />8.3　收缩LFun语言　121<br />8.4　揭示函数和LFunRef语言　121<br />8.5　限制函数　122<br />8.6　移除复杂操作数　122<br />8.7　详细控制和CFun语言　123<br />8.8　选择指令和语言　124<br />8.9　寄存器分配　126<br />8.9.1　活跃性分析　127<br />8.9.2　构建干涉图　127<br />8.9.3　分配寄存器　127<br />8.10　修补指令　127<br />8.11　生成起始和收尾代码　128<br />8.12　翻译举例　129<br />第9章　词法作用域函数　131<br />9.1　Lλ语言　132<br />9.2　赋值和词法作用域函数　136<br />9.3　唯一化变量　137<br />9.4　赋值转换　138<br />9.5　闭包转换　140<br />9.6　显露分配　142<br />9.7　详细控制和CClos　143<br />9.8　选择指令　143<br />9.9　挑战：优化闭包　144<br />9.10　进一步阅读　146<br />第10章　动态类型　147<br />10.1　LDyn语言　147<br />10.2　标记值的表示　151<br />10.3　LAny语言　151<br />10.4　强制转换插入：编译LDyn为<br />LAny　154<br />10.5　揭示强制转换　155<br />10.6　赋值转换　156<br />10.7　闭包转换　156<br />10.8　移除复杂操作数　156<br />10.9　详细控制和CAny　156<br />10.10　选择指令　157<br />10.11　LAny语言的寄存器分配　159<br />第11章　渐变类型　161<br />11.1　类型检查L?　162<br />11.2　解释LCast　166<br />11.3　重载解析　170<br />11.4　插入强制转换　170<br />11.5　低层类型转换　171<br />11.6　区分代理　172<br />11.7　揭示强制转换　174<br />11.8　闭包转换　174<br />11.9　选择指令　174<br />11.10　进一步阅读　176<br />第12章　泛型　178<br />12.1　编译泛型　183<br />12.2　解析实例化　184<br />12.3　擦除泛型类型　185<br />附录　x86指令集快速参考　188<br />参考文献　190