编译原理和技术

第1章编译概述

1．1翻译和解释

1．2编译程序的组成部分

1．2．1分析

1．2．2综合

1．2．3表格管理

1．2．4错误处理

1．3编译程序的组织

第2章程序语言的基本知识

2．1符号串的集合

2．1．1字母表

2．1．2符号串

2．1．3语言

2．2文法和语言

2．2．1引言

2．2．2文法和语言的形式定义

2．3分析树和二义性

2．3．1分析树

2．3．2分析树的构造

2．3．3二义性

2．4形式语言概观

2．4．1形式语言分类

2．4．2非上下文无关的语言结构

2．4．3上下文无关语言和正则语言的区别

练习

第3章词法分析

3．1词法分析程序的设计

3．1．1词法分析程序的功能

3．1．2单词的词类和属性

3．1．3词法分析程序作为一个独立子程序

3．2词法分析程序的手工构造

3．2．1确定的有限自动机

3．2．2构造识别单词的：DFA

3．2．3编写词法分析程序

3．3有限自动机

3．3．1非确定有限自动机

3．3．2确定的有限自动机的化简

3．4正规表达式与有限自动机

3．4．1正规表达式与单词

3．4．2正规表达式与有限自动机的等价性

3．5词法分析程序的自动构造工具

练习

第4章语法分析

4．1语法分析器概述

4．2预测分析器

4．2．1预测分析

4．2．2递归预测分析器的构造

4．2．3非递归的预测分析器的构造

4．3书写文法

4．3．1消除左递归

4．3．2提取左因子

4．4自底向上分析

4．4．1规范归约

4．4．2“移进一归约”分析法的栈实现

4．5算符优先分析法

4．5．1利用算符优先关系寻找右句型的可归约串

4．5．2算符优先关系表的构造

4．5．3优先函数

4．5．4算符优先分析法的错误处理示例

4．6LR分析器

4．6．1LR分析器的逻辑结构及工作过程

4．6．2SLR分析表的构造

4．6．3LR(1)分析表的构造

4．6．4LALR分析表的构造

4．7LR分析方法对二义文法的应用

4．8分析器的生成器Yacc

4．8．1引言

4．8．2书写Yacc的源程序

4．8．3用Yacc处理二义文法

4．8．4用Lex建立Yacc的词法分析器

4．8．5Yacc的错误恢复

练习

第5章语法制导翻译

5．1语法制导定义

5．1．1语法制导定义的形式

5．1．2综合属性

5．1．3继承属性

5．1．4依赖图

5．1．5计算顺序

5．2语法树的构造

5．2．1语法树

5．2．2建立表达式的语法树

5．2．3建立语法树的语法制导定义

5．2．4关于表达式的有向非循环图

5．3S-属性定义及其自底向上的计算

5．4L-属性定义

5．4．1L-属性定义的含义

5．4．2翻译模式

5．5自顶向下的翻译

5．5．1从翻译模式中消除左递归

5．5．2预测翻译器的设计

5．6自底向上计算继承属性

5．6．1从翻译模式中去掉嵌入的动作

5．6．2分析栈中的继承属性

5．6．3模拟继承属性的计算

练习

第6章运行时刻环境的组织

6．1有关源语言中的一些问题的讨论

6．1．1过程

6．1．2活动树

6．1．3控制栈

6．1．4说明的作用域

6．1．5名字的绑定

6．1．6提出的问题

6．2存储组织

6．2．1运行时刻内存的划分

6．2．2活动记录

6．2．3编译时刻的局部数据的设计

6．3运行时刻存储分配策略

6．3．1静态存储分配

6．3．2栈式存储分配

6．3．3堆式存储分配

6．4对非局部名字的访问

6．4．1块

6．4．2不含嵌套过程的词法作用域

6．4．3含有嵌套过程的词法作用域

6．4．4动态作用域

6．5参数传递

6．5．1传值调用

6．5．2引用调用

6．5．3复制恢复

6．5．4传名调用

6．5．5过程作为参数

6．6符号表

6．6．1符号表的作用

6．6．2符号表的表项

6．6．3符号表的存储结构

练习

第7章中间代码生成

7．1中间语言

7．1．1图表示法

7．1．2三地址代码

7．1．3三地址语句的种类

7．1．4语法制导翻译生成三地址代码

7．1．5三地址代码的具体实现

7．2类型检查

7．2．1类型表达式

7．2．2类型表达式的等价

7．2．3类型检查

7．2．4类型转换

7．3说明语句

7．3．1过程中的说明语句

7．3．2保留作用域信息

7．3．3记录中的域名

7．4赋值语句

7．4．1符号表中的名字

7．4．2数组元素地址分配

7．4．3访问数组元素的翻译模式

7．4．4访问记录中的域

7．5布尔表达式和控制流语句

7．5．1翻译布尔表达式的方法

7．5．2数值表示法

7．5．3控制流语句

7．5．4控制流语句中布尔表达式的翻译

7．6CASE语句

7．7回填

7．7．1使用回填翻译布尔表达式

7．7．2使用回填翻译控制流语句

7．7．3标号和转移语句

7．8过程调用

练习

第8章代码生成

8．1目标机器

8．2运行存储管理

8．2．1静态分配管理

8．2．2栈式分配管理

8．2．3名字的运行地址

8．3基本块和流图

8．3．1基本块

8．3．2流图

8．4下次引用信息

8．5一个简单的代码生成器

8．5．1寄存器描述器和地址描述器

8．5．2代码生成算法

8．6基本块的dag表示法

8．6．1dag的构造

8．6．2dag的应用

8．7从dag生成目标代码

练习

第9章中间代码的优化

9．1引言

9．1．1代码优化的标准

9．1．2争取较好的性能

9．1．3优化编译器的组织

9．2优化的主要种类

9．2．1公共子表达式

9．2．2复写传播

9．2．3死代码删除

9．2．4循环优化

9．3流图中的循环

9．3．1必经结点

9．3．2自然循环

9．3．3内循环

9．3．4前置结点

9．3．5归约流图

9．4全局数据流分析介绍

9．4．1点和路径

9．4．2到达一定值

9．4．3集合的表示

9．4．4局部的到达一定值

9．4．5引用一定值链

9．5数据流方程的迭代求解

9．5．1到达一定值的迭代算法

9．5．2可用表达式

9．5．3活跃变量分析

9．5．4定值一引用链

9．5．5流图结点的深度优先次序

9．5．6用深度优先次序改进数据流求解算法

9．6优化的实现

9．6．1删除公共子表达式

9．6．2复写传播

9．6．3寻找循环不变计算

9．6．4代码外提

9．6．5代码外提后维持数据流信息

9．6．6归纳变量

9．6．7有循环不变计算的归纳变量

练习

参考文献

　　本书共分9章。第1章的编译概述讨论了编译程序的各个组成部分，从中读者可以了解到编译程序构造的各主要方面。第2章介绍有关形式语言的一些基本概念，这些是学习本书必要的基础知识。第3章介绍词法分析，它是整个分析过程的一个子任务。设计词法分析程序的理论基础是有限自动机。文中详细讨论了正规表达式和有限自动机的等价转换算法。第4章详细讨论了用于编译程序构造中的一些典型的语法分析方法。第5章的语法制导翻译中，为使文法的产生式和语义规则联系起来，引进了语法制导定义和翻译模式这两个概念，并给出如何书写L-属性的翻译模式的方法。第6章讨论用来支持一个程序的运行时刻环境的有关存储组织的各种问题。之后，在第7章利用语法制导定义和翻译模式这两个概念来讨论中间代码生成。第8章在上一章的基础上介绍目标代码生成。最后，第9章集中讨论中间代码优化，比较详细地阐述了数据流分析和主要的全局优化方法。　　编译原理和技术是计算机专业的基础课程，本书系统介绍了与编译相关的知识。全书共分9章，第1章的编译概述讨论了编译程序的各个组成部分：第2章介绍有关形式语言的一些基本概念；第3章介绍词法分析，它是整个分析过程的一个子任务；第4章详细讨论了用于编译程序构造中的一些典型的语法分析方法；第5章引入了语法制导定义和翻译模式这两个概念，并给出了如何书写L-属性的翻译模式的方法；第6章讨论用来支持一个程序的运行时刻环境的有关存储组织的各种问题；第7章讨论的是中间代码生成；第8章介绍目标代码生成；第9章集中讨论中间代码优化。　　为方便教师讲解和学生实验，本书配有光盘。　　本书适合作为计算机专业编译原理课程的教材，也可作为广大工程技术人员的参考资料。