编译程序构造原理和实现技术

第一章编译程序概述
1.1编译程序和解释程序
1.2编译程序的功能分解和组织结构
1.3编译程序的复杂性
1.4编译程序的设计实现
1.5编译程序的测试与维护
1.6几个经典编译程序
第二章一个微小编译器
2.1微小语言Micro
2.2Micro的词法分析
2.3Micro的语法分析
2.4Micro的语义分析
2.5Micro的目标代码
练习题
第三章有限自动机与词法分析器
3.1词法分析
3.1.1词法分析器的功能
3.1.2单词的内部表示
3.1.3保留字
3.1.4空格符.制表符和换行符
3.1.5括号类配对预检
3.1.6向前看多个字符的处理
3.1.7字符串空间
3.1.8词法错误校正
3.1.9词法分析的结束
3.2正则表达式
3.2.1基本概念
3.2.2正则表达式及其一些性质
3.2.3正则定义
3.2.4正则表达式的局限性
3.3有限自动机(FA)
3.3.1确定有限自动机(DFA)
3.3.2确定有限自动机的实现
3.3.3非确定有限自动机(NFA)
3.3.4NFA到DFA的转换
3.3.5确定有限自动机的化简
3.3.6正则表达式到DFA的转换
3.4词法分析器的构造
3.4.1用DFA人工构造词法分析器
3.4.2使用词法分析器的生成器ScanGen
3.4.3Lex
练习题
第四章文法与语法分析
4.1语法分析的功能
4.1.1语法分析器和识别器
4.1.2语法分析器的输入
4.1.3语法错误类别及关键性错误
4.1.4语法错误处理
4.2上下文无关文法
4.2.1文法和语言
4.2.2最左推导和最右推导
4.2.3语法分析树与二义性
4.2.4文法分析算法
4.2.5自顶向下方法概述
4.2.6自底向上方法概述
4.3递归下降法--自顶向下分析
4.3.1递归下降法原理
4.3.2消除公共前缀
4.3.3消除左递归
4.4LL分析方法--自顶向下分析
4.4.1LL(1)文法
4.4.2LL(1)分析表
4.4.3LL(1)分析的驱动器
4.4.4LL(1)中的if-then-else问题
4.4.5LL(1)分析器的自动生成器LLGen
4.5LR方法--自底向上分析
4.5.1句柄
4.5.2活前缀和归约活前缀
4.5.3线性正则式的状态机
4.5.4LR状态机的构造
4.5.5LR(0)和SLR(1)文法
4.5.6LR(1)文法
4.5.7LALR(1)文法
4.5.8二义性文法的处理
4.5.9另一种Shift-Reduce分析技术
4.5.10LL(1)与LALR(1)的比较
4.6LR分析器的生成器
4.6.1LALR分析器的生成器Yacc
4.6.2LALR分析器的生成器LALRGen
4.7语法错误处理
4.7.1错误恢复和错误修复
4.7.2递归下降分析的错误恢复
4.7.3LL分析的错误恢复
4.7.4LR分析的错误恢复
练习题
第五章语义分析
5.1语义分析基础
5.1.1语义分析内容
5.1.2标识符的内部表示
5.1.3类型的内部表示
5.1.4值的内部表示
5.2符号表
5.2.1表处理技术
5.2.2符号表的局部化
5.2.3二叉式局部符号表
5.2.4散列式全局符号表
5.2.5嵌套式局部符号表
5.2.6符号表界面
5.3类型表达式
5.3.1类型的等价性和相容性
5.3.2类型的分析
5.3.3枚举类型--EnumTYPE
5.3.4子界类型--SubRangeTYPE
5.3.5数组类型--ArrayTYPE
5.3.6集合类型--SetTYPE
5.3.7文件类型--FileTYPE
5.3.8指针类型--PointerTYPE
5.3.9记录类RecordTYPE
5.4声明的语义分析
5.4.1标号声明部分--kabelDecPart
5.4.2常量声明部分--ConstDecPart
5.4.3类型声明部分--TypeDecPart
5.4.4变量声明部分--VarDecPart
5.4.5子程序首部--RoutHead
5.4.6过程／函数的向前声明
5.5执行体Body的语义分析
5.5.1表达式分析
5.5.2定位性标号和使用性标号
5.5.3赋值语句和调用语句分析
5.5.4结构语句分析
练习题
第六章运行时的存储空间
6.1运行时的存储空间结构
6.2运行时的存储空间分配
6.2.1静态区的存储分配
6.2.2栈区的存储分配
6.2.3堆区的存储分配
6.2.4堆区空间管理
6.3运行时的过程活动记录与栈区的组织结构
6.3.1过程活动记录(ActivationRecord)
6.3.2动态链(DynamicChain)
6.3.3活跃活动记录
6.4运行时的变量访问
6.4.1变量的访问环境
6.4.2局部Display表方法
6.4.3静态链方法(StaticChain)
6.4.4全局Display表方法和寄存器方法
6.5非正常出口和形式过程语句
6.5.1非正常出口的动态链和Display表
6.5.2形式过程语句和Display表
6.5.3奇特型调用和DisplaY表
6.6分程序记录和动态数组空间
6.6.1分程序的记录
6.6.2动态数组的分配
练习题
第七章动作文法和属性文法
7.1动作文法(ActionGrammar)
7.1.1动作符(ActionSymb01)
7.1.2动作文法(ActionGrammar)
7.1.3尾动作文法
7.1.4抽象动作文法
7.2动作文法的实现
7.2.1动作文法的LL实现
7.2.2动作文法的LR实现
7.2.3Yacc--LALR分析器的生成器
7.3属性文法
7.3.1属性文法的定义
7.3.2继承属性和综合属性
7.3.3属性规则
7.3.4属性树和属性依赖图
7,3.5属性求值
7.3.6拷贝型属性文法
7.4属性文法在编译器设计中的应用
7.4.1类型分析的属性文法描述
7.4.2声明分析的属性文法描述
7.4.3语句分析的属性文法描述
7.5S--属性文法及其属性求值
7.5.1S--属性文法
7.5.2S--属性文法的递归实现--自顶向下求值
7.5.3S--属性文法的LL实现--自顶向下求值
7.5.4S--属性文法的LR实现--自底向上求值
7.6L--属性文法及其属性求值
7.6.1L--属性文法
7.6.2LL--L属性文法的递归实现--自顶向下求值
7.6.3LL--L属性文法的LL实现--自顶向下求值
7.6.4L--属性文法的栈式遍历树实现
7.6.5LR--L属性文法的LR实现--自底向上求值
7.6.6LALR分析器的生成器LALRGen
练习题
第八章中间代码生成
8.1中间语言
8.1.1中间语言设置和直接代码生成
8.1.2栈式中间代码--后缀式
8.1.3三地址中间代码
8.1.4抽象语法树和DAG
8.1.5多元式中间代码
8.2简单表达式的中间代码生成
8.2.1表达式的语义信息
8.2.2表达式的中间代码结构
8.2.3类型转换
8.2.4表达式中间代码的生成
8.2.5布尔表达式的短路中间代码
8.2.6变量的中间代码
8,3多维下标变量的中间代码生成
8.3.1多维下标变量
8.3.2多维下标变量的地址公式
8.3.3多维下标变量的中间代码结构
8.4原子语句的中间代码
8.4.1输入输出语句的中间代码
8.4.2赋值语句的中间代码
8.4.3过程调用和函数调用的中间代码
8.4.4GOTD语句和标号定位的中间代码
8.5结构语句的中间代码
8.5.1条件语句的中间代码
8.5.2While语句的中间代码
8.5.3Repeat语句的中间代码
8.5.4For语句的中间代码
8.5.5Case语句的中间代码
8.6声明的中间代码
8.6.1变量声明的中间代码
8.6.2过程和函数的中间代码
练习题
第九章中间代码优化
9.1引言
9.1.1优化目标和要求
9.1.2优化的必要性
9.1.3优化内容和难点
9.1.4局部优化和全局优化
9.1.5基本块和程序流图
9.2常量表达式优化
9.2.1常量表达式的局部优化
9.2.2基于常量定值分析的常量表达式全局优化
9.2.3可用常量定值的数据流分析
9.3公共表达式优化
9.3.1基于相似性的公共表达式局部优化
9.3.2基于值编码的公共表达式局部优化
9.3.3基于DAG的公共表达式局部优化
9.3.4基于可用表达式分析的公共表达式全局优化
9.3.5可用表达式定值的数据流分析
9.4循环不变表达式外提
9.4.1循环识别
9.4.2外提对象和安全性
9.4.3不变式外提的实现原理
9.4.4过程／函数的副作用分析
9.4.5一种简单的外提优化
9.4.6循环必经点分析
9.5循环内归纳表达式的优化
9.5.1归纳变量和归纳表达式
9.5.2归纳表达式的优化原理
9.5.3乘法运算的强度削减优化
练习题
第十章目标代码生成
10.1目标代码
10.1.1虚拟目标代码
10.1.2实际目标代码
10.1.3窥孔优化
10.2临时变量
10.2.1临时变量的特点
10.2.2临时变量的存储空间
10.2.3变量的状态描述
10.3寄存器
10.3.1寄存器分类
10.3.2寄存器的状态描述
10.3.3寄存器的分配
10.3.4寄存器的释放代价
10.4基于多元式的代码生成
10.4.1编址模式(AddressingMode)
10.4.2间接编址模式的转换
10.4.3目标代码生成基本技术
10.4.4其他寄存器的状态追踪
10.5基于树结构的代码生成
10.5.1多元式到树的转换
10.5.2计算寄存器个数
10.5.3从带寄存器个数标记的树生成代码
10.6基于DAG的代码生成
10.6.1从树构造DAG
10.6.2给DAG结点标上序号和虚寄存器
10.6.3从带排序和虚寄存器标记的DAG生成代码
10.7代码生成器的生成器
10.7.1代码生成器的自动化
10.7.2基于指令模板匹配的代码生成技术
10.7.3基于语法分析的代码生成技术
10.8其他
10.8.1标号和GOTO的代码生成
10.8.2过程／函数调用的代码生成
练习题
参考文献