自制编译器

第1章　开始制作编译器　　11.1　本书的概要　　2本书的主题　　2本书制作的编译器　　 2编译示例　　2可执行文件　　3编译　　4程序运行环境　　61.2　编译过程　　8编译的4 个阶段　　8语法分析　　8语义分析　　9生成中间代码　　9代码生成　　10优化　　10总结　　101.3　使用cь编译器进行编译　　11cь编译器的必要环境　　11安装cь编译器　　11cь的hello, world!　　12第2章　cь和cbc　　132.1　cь语言的概要　　14cь的hello, world ！　　14cь中删减的功能　　 14import 关键字　　15导入文件的规范　　162.2　cь编译器cbc 的构成　　17cbc 的代码树　　17cbc 的包　　18compiler 包中的类群　　18main 函数的实现　　 19commandmain 函数的实现　　19java5 泛型　　20build 函数的实现　　 20java 5 的foreach 语句　　21compile 函数的实现　　21第1部分　代码分析第3章　语法分析的概要　　243.1　语法分析的方法　　25代码分析中的问题点　　25代码分析的一般规律　　25词法分析、语法分析、语义分析　　25扫描器的动作　　26单词的种类和语义值　　27token　　28抽象语法树和节点　　293.2　解析器生成器　　30什么是解析器生成器　　30解析器生成器的种类　　30解析器生成器的选择　　313.3　javacc 的概要　　33什么是javacc　　33语法描述文件　　33语法描述文件的例子　　34运行javacc　　35启动javacc 所生成的解析器　　36中文的处理　　37第4章　词法分析　　394.1　基于javacc 的扫描器的描述　　40本章的目的　　40javacc 的正则表达式　　40固定字符串　　41连接　　41字符组　　41排除型字符组　　41重复1 次或多次　　42重复0 次或多次　　42重复n 次到m 次　　 42正好重复n 次　　43可以省略　　43选择　　434.2　扫描没有结构的单词　　44token 命令　　44扫描标识符和保留字　　44选择匹配规则　　45扫描数值　　464.3　扫描不生成token 的单词　　48skip 命令和special_token 命令　　48跳过空白符　　48跳过行注释　　494.4 扫描具有结构的单词　　50*长匹配原则和它的问题　　50基于状态迁移的扫描　　50more 命令　　51跳过块注释　　52扫描字符串字面量　　53扫描字符字面量　　53第5章　基于javacc 的解析器的描述　　555.1　基于ebnf 语法的描述　　56本章的目的　　56基于javacc 的语法描述　　56终端符和非终端符　　57javacc 的ebnf 表示法　　58连接　　58重复0 次或多次　　59重复1 次或多次　　59选择　　60可以省略　　605.2　语法的二义性和token 的超前扫描　　61语法的二义性　　61javacc 的局限性　　62提取左侧共通部分　　63token 的超前扫描　　63可以省略的规则和冲突　　64重复和冲突　　65更灵活的超前扫描　　66超前扫描的相关注意事项　　66第6章　语法分析　　686.1　定义的分析　　69表示程序整体的符号　　69语法的单位　　69import 声明的语法　　70各类定义的语法　　71变量定义的语法　　72函数定义的语法　　73结构体定义和联合体定义的语法　　74结构体成员和联合体成员的语法　　75typedef 语句的语法　　76类型的语法　　76c 语言和cь在变量定义上的区别　　77基本类型的语法　　776.2　语句的分析　　79语句的语法　　79if 语句的语法　　80省略if 语句和大括号　　80while 语句的语法　　81for 语句的语法　　81各类跳转语句的语法　　826.3　表达式的分析　　83表达式的整体结构　　83expr 的规则　　83条件表达式　　84二元运算符　　856.4　项的分析　　88项的规则　　88前置运算符的规则　　88后置运算符的规则　　89字面量的规则　　89第2部分　抽象语法树和中间代码第7章　javacc 的action 和抽象语法树　　927.1　javacc 的action　　93本章的目的　　93简单的action　　93执行action 的时间点　　93返回语义值的action　　95获取终端符号的语义值　　95token 类的属性　　96获取非终端符号的语义值　　98语法树的结构　　99选择和action　　99重复和action　　100本节总结　　1027.2　抽象语法树和节点　　103node 类群　　103node 类的定义　　105抽象语法树的表示　　105基于节点表示表达式的例子　　107第8章　抽象语法树的生成　　1108.1　表达式的抽象语法树　　111字面量的抽象语法树　　111类型的表示　　112为什么需要typeref 类　　113一元运算的抽象语法树　　114二元运算的抽象语法树　　116条件表达式的抽象语法树　　117赋值表达式的抽象语法树　　1188.2　语句的抽象语法树　　121if 语句的抽象语法树　　121while 语句的抽象语法树　　122程序块的抽象语法树　　1238.3　声明的抽象语法树　　125变量声明列表的抽象语法树　　125函数定义的抽象语法树　　126表示声明列表的抽象语法树　　127表示程序整体的抽象语法树　　128外部符号的import　　128总结　　1298.4　cbc 的解析器的启动　　132parser 对象的生成　　132文件的解析　　133解析器的启动　　134第9章　语义分析（1）引用的消解　　1359.1　语义分析的概要　　136本章目的　　136抽象语法树的遍历　　137不使用visitor 模式的抽象语法树的处理　　137基于visitor 模式的抽象语法树的处理　　138vistor 模式的一般化　　140cbc 中visitor 模式的实现　　141语义分析相关的cbc 的类　　1429.2　变量引用的消解　　144问题概要　　144实现的概要　　144scope 树的结构　　145localresolver 类的属性　　146localresolver 类的启动　　146变量定义的添加　　147函数定义的处理　　148pushscope 方法　　149currentscope 方法　　149popscope 方法　　150添加临时作用域　　150建立variablenode 和变量定义的关联　　151从作用域树取得变量定义　　1519.3　类型名称的消解　　153问题概要　　153实现的概要　　153typeresolver 类的属性　　153typeresolver 类的启动　　154类型的声明　　154类型和抽象语法树的遍历　　155变量定义的类型消解　　156函数定义的类型消解　　157第10章　语义分析（2）静态类型检查　　15910.1　类型定义的检查　　160问题概要　　160实现的概要　　161检测有向图中的闭环的算法　　162结构体、联合体的循环定义检查　　16310.2　表达式的有效性检查　　165问题概要　　165实现的概要　　165dereferencechecker 类的启动　　166semanticerror 异常的捕获　　167非指针类型取值操作的检查　　167获取非左值表达式地址的检查　　168隐式的指针生成　　16910.3　静态类型检查　　170问题概要　　170实现的概要　　170cь中操作数的类型　　171隐式类型转换　　172typerchecker 类的启动　　173二元运算符的类型检查　　174隐式类型转换的实现　　175第11章　中间代码的转换　　17811.1　cbc 的中间代码　　179组成中间代码的类　　180中间代码节点类的属性　　181中间代码的运算符和类型　　182各类中间代码　　183中间代码的意义　　18411.2　irgenerator 类的概要　　185抽象语法树的遍历和返回值　　185irgenerator 类的启动　　185函数本体的转换　　186作为语句的表达式的判别　　18711.3　流程控制语句的转换　　189if 语句的转换（1）概要　　189if 语句的转换（2）没有else 部分的情况　　190if 语句的转换（3）存在else 部分的情况　　191while 语句的转换　　191break 语句的转换（1）问题的定义　　192break 语句的转换（2）实现的方针　　193break 语句的转换（3）实现　　19411.4　没有副作用的表达式的转换　　196unaryopnode 对象的转换　　196binaryopnode 对象的转换　　197指针加减运算的转换　　19811.5　左值的转换　　200左边和右边　　200左值和右值　　200cbc 中左值的表现　　201结构体成员的偏移　　202成员引用（expr.memb）的转换　　203左值转换的例外：数组和函数　　204成员引用的表达式（ptr->memb）的转换　　20511.6　存在副作用的表达式的转换　　206表达式的副作用　　206有副作用的表达式的转换方针　　206简单赋值表达式的转换（1）语句　　207临时变量的引入　　208简单赋值表达式的转换（2）表达式　　209后置自增的转换　　210第3部分　汇编代码第12章　x86 架构的概要　　21412.1　计算机的系统结构　　215cpu 和存储器　　215寄存器　　215地址　　216物理地址和虚拟地址　　216各类设备　　217缓存　　21812.2　x86 系列cpu 的历史　　220x86 系列cpu　　22032 位cpu　　220指令集　　221ia-32 的变迁　　222ia-32 的64 位扩展——amd64　　22212.3　ia-32 的概要　　224ia-32 的寄存器　　224通用寄存器　　225机器栈　　226机器栈的操作　　227机器栈的用途　　227栈帧　　228指令指针　　229标志寄存器　　22912.4　数据的表现形式和格式　　231无符号整数的表现形式　　231有符号整数的表现形式　　231负整数的表现形式和二进制补码　　232字节序　　233对齐　　233结构体的表现形式　　234第13章　x86 汇编器编程　　23613.1　基于gnu 汇编器的编程　　237gnu 汇编器　　237汇编语言的hello, world!　　237基于gnu 汇编器的汇编代码　　23813.2　gnu 汇编器的语法　　240汇编版的hello, world!　　240指令　　241汇编伪操作　　241标签　　241注释　　242助记符后缀　　242各种各样的操作数　　243间接内存引用　　244x86 指令集的概要　　24513.3　传输指令　　246mov 指令　　246push 指令和pop 指令　　247lea 指令　　248movsx 指令和movzx 指令　　249符号扩展和零扩展　　25013.4　算术运算指令　　251add 指令　　251进位标志　　252sub 指令　　252imul 指令　　252idiv 指令和div 指令　　253inc 指令　　254dec 指令　　255neg 指令　　25513.5　位运算指令　　256and 指令　　256or 指令　　257xor 指令　　257not 指令　　257sal 指令　　258sar 指令　　258shr 指令　　25913.6　流程的控制　　260jmp 指令　　260条件跳转指令（jz、jnz、je、jne、……）　　261cmp 指令　　262test 指令　　263标志位获取指令（setcc）　　263call 指令　　264ret 指令　　265第14章　函数和变量　　26614.1　程序调用约定　　267什么是程序调用约定　　267linux/x86 下的程序调用约定　　26714.2　linux/x86 下的函数调用　　269到函数调用完成为止　　269到函数开始执行为止　　270到返回原处理流程为止　　271到清理操作完成为止　　271函数调用总结　　27214.3　linux/x86 下函数调用的细节　　274寄存器的保存和复原　　274caller-save 寄存器和callee-save 寄存器　　274caller-save 寄存器和callee-save 寄存器的灵活应用　　275大数值和浮点数的返回方法　　276其他平台的程序调用约定　　277第15章　编译表达式和语句　　27815.1　确认编译结果　　279利用cbc 进行确认的方法　　279利用gcc 进行确认的方法　　28015.2　x86 汇编的对象与dsl　　282表示汇编的类　　282表示汇编对象　　28315.3　cbc 的x86 汇编dsl　　285利用dsl 生成汇编对象　　285表示寄存器　　286表示立即数和内存引用　　287表示指令　　287表示汇编伪操作、标签和注释　　28815.4　codegenerator 类的概要　　290codegenerator 类的字段　　290codegenerator 类的处理概述　　290实现compilestmts 方法　　291cbc 的编译策略　　 29215.5　编译单纯的表达式　　294编译int 节点　　294编译str 节点　　294编译uni 节点(1) 按位取反　　295编译uni 节点(2) 逻辑非　　29715.6　编译二元运算　　298编译bin 节点　　298实现compilebinaryop 方法　　299实现除法和余数　　300实现比较运算　　30015.7　引用变量和赋值　　301编译var 节点　　301编译addr 节点　　302编译mem 节点　　 303编译assign 节点　　30315.8　编译jump 语句　　305编译labelstmt 节点　　305编译jump 节点　　305编译cjump 节点　　305编译call 节点　　306编译return 节点　　307第16章　分配栈帧　　30816.1　操作栈　　309cbc 中的栈帧　　309栈指针操作原则　　310函数体编译顺序　　31016.2　参数和局部变量的内存分配　　312本节概述　　312参数的内存分配　　312局部变量的内存分配：原则　　313局部变量的内存分配　　314处理作用域内的局部变量　　315对齐的计算　　316子作用域变量的内存分配　　31616.3　利用虚拟栈分配临时变量　　318虚拟栈的作用　　318虚拟栈的接口　　319虚拟栈的结构　　319virtualpush 方法的实现　　320virtualstack#extend 方法的实现　　320virtualstack#top 方法的实现　　321virtualpop 方法的实现　　321virtualstack#rewind 方法的实现　　321虚拟栈的运作　　32216.4　调整栈访问的偏移量　　323本节概要　　323stackframeinfo 类　　323计算正在使用的callee-save寄存器　　324计算临时变量区域的大小　　325调整局部变量的偏移量　　325调整临时变量的偏移量　　32616.5　生成函数序言和尾声　　327本节概要　　327生成函数序言　　327生成函数尾声　　32816.6　alloca 函数的实现　　330什么是alloca 函数　　330实现原则　　330alloca 函数的影响　　331alloca 函数的实现　　331第17章　优化的方法　　33317.1　什么是优化　　334各种各样的优化　　334优化的案例　　334常量折叠　　334代数简化　　335降低运算强度　　335削除共同子表达式　　335消除无效语句　　336函数内联　　33617.2　优化的分类　　337基于方法的优化分类　　337基于作用范围的优化分类　　337基于作用阶段的优化分类　　33817.3　cbc 中的优化　　339cbc 中的优化原则　　339cbc 中实现的优化　　339cbc 中优化的实现　　33917.4　更深层的优化　　341基于模式匹配选择指令　　341分配寄存器　　342控制流分析　　342大规模的数据流分析和ssa 形式　　342总结　　343第4部分　链接和加载第18章　生成目标文件　　34618.1　elf 文件的结构　　347elf 的目的　　347elf 的节和段　　348目标文件的主要elf 节　　348使用readelf 命令输出节头　　349使用readelf 命令输出程序头　　350使用readelf 命令输出符号表　　351readelf 命令的选项　　351什么是dwarf 格式　　35218.2　全局变量及其在elf 文件中的表示　　354分配给任意elf 节　　354分配给通用elf 节　　354分配.bss 节　　355通用符号　　355记录全局变量对应的符号　　357记录符号的附加信息　　357记录通用符号的附加信息　　358总结　　35818.3　编译全局变量　　360generate 方法的实现　　360generateassemblycode 方法的实现　　360编译全局变量　　361编译立即数　　362编译通用符号　　363编译字符串字面量　　364生成函数头　　365计算函数的代码大小　　366总结　　36618.4　生成目标文件　　367as 命令调用的概要　　367引用gnuassembler 类　　367调用as 命令　　367第19章　链接和库　　36919.1　链接的概要　　370链接的执行示例　　370gcc 和gnu ld　　371链接器处理的文件　　372常用库　　374链接器的输入和输出　　37419.2　什么是链接　　375链接时进行的处理　　375合并节　　375重定位　　376符号消解　　37719.3　动态链接和静态链接　　379两种链接方法　　379动态链接的优点　　379动态链接的缺点　　380动态链接示例　　380静态链接示例　　381库的检索规则　　38119.4　生成库　　383生成静态库　　383linux 中共享库的管理　　383生成共享库　　384链接生成的共享库　　385第20章　加载程序　　38720.1 加载elf 段　　388利用mmap 系统调用进行文件映射　　388进程的内存镜像　　389内存空间的属性　　390elf 段对应的内存空间　　390和elf 文件不对应的内存空间　　392elf 文件加载的实现　　39320.2　动态链接过程　　395动态链接加载器　　395程序从启动到终止的过程　　395启动ld.so　　396系统内核传递的信息　　397aux 矢量　　397读入共享库　　398符号消解和重定位　　399运行初始化代码　　400执行主程序　　401执行终止处理　　402ld.so 解析的环境变量　　40220.3　动态加载　　404所谓动态加载　　404linux 下的动态加载　　404动态加载的架构　　40520.4　gnu ld 的链接　　406用于cbc 的ld 选项的结构　　406c 运行时　　407生成可执行文件　　408生成共享库　　408第21章　生成地址无关代码　　41021.1 地址无关代码　　411什么是地址无关代码　　411全局偏移表（got）　　412获取got 地址　　412使用got 地址访问全局变量　　413访问使用got 地址的文件内部的全局变量　　414过程链接表（plt）　　414调用plt 入口　　416地址无关的可执行文件：pie　　41621.2　全局变量引用的实现　　418获取got 地址　　418picthunk 函数的实现　　418删除重复函数并设置不可见属性　　419加载got 地址　　420locatesymbols 函数的实现　　421全局变量的引用　　421访问全局变量：地址无关代码的情况下　　 422函数的符号　　423字符串常量的引用　　42421.3　链接器调用的实现　　425生成可执行文件　　425generatesharedlibrary 方法　　42621.4　从程序解析到执行　　428build 和加载的过程　　428词法分析　　429语法分析　　429生成中间代码　　430生成代码　　431汇编　　432生成共享库　　432生成可执行文件　　433加载　　433第22章　扩展阅读　　43422.1 参考书推荐　　435编译器相关　　435语法分析相关　　435汇编语言相关　　43622.2 链接、加载相关　　43722.3 各种编程语言的功能　　438异常封装相关的图书　　438垃圾回收　　438垃圾回收相关的图书　　439面向对象编程语言的实现　　439函数式语言　　440附　　录　　441a.1 参考文献　　442a.2 在线资料　　444a.3 源代码　　445