编译原理

　　本书介绍编译系统的一般构造原理、基本设计方法、主要实现技术和一些自动构造工具，主要由语言基础知识、词法分析、语法分析、中间代码生成、代码优化、目标代码生成、符号表的构造和运行时存储空间的组织等8部分组成。本书首先从剖析一个简单的编译程序（PL/0）入手，对编译程序设计的基本理论，如有穷自动机、上下文无关文法等给予必要的介绍；对于广泛使用的语法分析方法和语义分析技术，如递归子程序法、算符优先分析、LR分析及语法制导翻译等进行了详细的讲解；对编译程序的结构及其各部分功能、实现方法以及整体的设计考虑等给予了描述；此外还介绍了编译程序的构造工具。同时引入“PL/0语言的编译程序”结构及文本，还引入LEX、YACC使用方法与实例。各章末附有习题。“编译原理”是一门对实践性要求较高的课程，为此，我们拟定了教学实验要求，列在附录D中。实验所参考的PL/0编译程序文本列在附录A中。附录B和C是对编译程序构造工具LEX和YACC的介绍。配合本书的教学自行研制了“编译原理计算机辅助教学软件”，附录E对该软件的功能和使用进行了说明。本书是高等院校计算机科学与技术专业的教材，也可作为教师、研究生或软件工程技术人员的参考书。

暂缺《编译原理》作者简介

前言

第1章 编译程序概论

1.1什么是编译程序

1.2编译过程概述

1.3编译程序的结构

1.4编译阶段的组合

1.5编译技术和软件工具

第2章 PL/0编译程序的实现

2.1PL/0语言描述

2.1.1PL/0语言的语法描述图

2.1.2PL/0语言文法的EBNF

表示

2.2PL/0编译程序的结构

2.3PL/0编译程序的词法分析

2.4PL/0编译程序的语法分析

2.5PL/0编译程序的目标代码结构

和代码生成

2.6PL/0编译程序的语法错误

处理

2.7PL/0编译程序的目标代码解释

执行时的存储分配

2.8练习

第3章 文法和语言

3.1文法的直观概念

3.2符号和符号串

3.3文法和语言的形式定义

3.4文法的类型

3.5上下文无关文法及其语法树

3.6句型的分析

3.6.1自上而下的分析方法

3.6.2自下而上的分析方法

3.6.3句型分析的有关问题

3.7有关文法实用中的一些说明

3.7.1有关文法的实用限制

3.7.2上下文无关文法中的

ε规则

3.8练习

第4章 词法分析

4.1词法分析程序的设计

4.1.1词法分析程序与语法

分析程序的接口方式

4.1.2词法分析程序的输出

4.1.3将词法分析工作分离

的考虑

4.2单词的描述工具

4.2.1正规文法

4.2.2正规式

4.2.3正规文法到正规式

4.3有穷自动机

4.3.1确定的有穷

自动机（DFA）

4.3.2不确定的有穷

自动机（NFA）

4.3.3NFA→DFA的转换

4.3.4确定有穷自动机的化简

4.4正规式和有穷自动机的等

价性

5正规文法和有穷自动机间

的转换

4.6词法分析程序的自动构造

工具

4.6.1LEX语言

4.7练习

第5章 自顶向下语法分析方法

5.1确定的自顶向下分析思想

5.2LL（1）文法的判别

5.3某些非LL（1）文法到LL（1）

文法的等价变换

5.4不确定的自顶向下分析思想

5.5确定的自顶向下分析方法

5.5.1递归子程序法

5.5.2预测分析方法

5.6练习

第6章 自底向上优先分析法

6.1自底向上优先分析法概述

6.2简单优先分析法

6.2.1优先关系

6.2.2简单优先文法的定义

6.2.3简单优先分析法

6.3算符优先分析法

6.3.1直观算符优先分析法

6.3.2算符优先文法的定义

6.3.3算符优先关系表的构造

6.3.4算符优先分析算法

6.3.5优先函数

6.3.6算符优先分析法的

局限性

6.4练习

第7章 LR分析法

7.1LR分析概述

7.2LR（0）分析

7.2.1可归前缀和子前缀

7.2.2识别活前缀的有限

自动机

7.2.3活前缀及其可归前缀的

一般计算方法

7.2.4LR（0）项目集规范族

的构造

7.3SLR（1）分析

7.4LR（1）分析

7.4.1LR（1）项目集族的

构造

7.4.2LR（1）分析表的构造

7.5LALR（1）分析

7.6二义性文法在LR分析中

的应用

7.7练习

第8章 语法制导翻译和中间代码生成

8.1属性文法

8.2语法制导翻译概论

8.3中间代码的形式

8.3.1逆波兰记号

8.3.2三元式和树形表示

8.3.3四元式

8.4简单赋值语句的翻译

8.5布尔表达式的翻译

8.5.1布尔表达式的翻译方法

8.5.2控制语句中布尔表达式

的翻译

8.6控制结构的翻译

8.6.1条件转移

8.6.2开关语句

8.6.3for循环语句

8.6.4出口语句

8.6.5goto语句

8.6.6过程调用的四元式产生

8.7说明语句的翻译

8.7.1简单说明句的翻译

8.7.2过程中的说明

8.8数组和结构的翻译

8.8.1数组说明和数组元

素的引用

8.8.2结构（记录）说明和引

用的翻译

8.9练习

第9章 符号表

9.1符号表的作用和地位

9.2符号的主要属性及作用

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.5练习

第10章 目标程序运行时的存储组织

10.1数据空间的三种不同使用方法和

管理方法

10.1.1静态存储分配

10.1.2动态存储分配

10.1.3栈式动态存储分配

10.1.4堆式动态存储分配

10.2栈式存储分配的实现

10.2.1简单的栈式存储分配的

实现

10.2.2嵌套过程语言的栈式

实现

10.2.3分程序结构的存储

管理

10.3参数传递

10.3.1传值

10.3.2传地址

10.3.3过程参数

10.4过程调用、过程进入和过程

返回

10.5练习

第11章 代码优化

11.1优化技术简介

11.1.1优化技术简介

11.2局部优化

11.2.1基本块的划分

11.2.2基本块的变换

11.2.3基本块的DAG表示

11.2.4DAG的应用

11.2.5DAG构造算法讨论

11.3控制流分析和循环优化

11.3.1程序流图与循环

11.3.2循环

11.3.3循环的查找

11.3.4可归约流图

11.3.5循环优化

11.4数据流的分析与全局优化

11.4.1一些主要的概念

11.4.2数据流方程的一般

形式

11.4.3到达一定值数据流

方程

11.4.4可用表达式及其数据

流方程

11.4.5活跃变量数据流方程

11.4.6复写传播

11.5练习

第12章 代码生成

12.1代码生成概述

12.2一个计算机模型

12.3一个简单的代码生成器

12.3.1寄存器分配的原则

12.3.2待用信息链表法

12.3.3代码生成算法

12.4代码生成研究现状

12.4.1中间语言的选择

12.4.2代码生成的自动化

研究

12.5练习

第13章 编译程序实现的途径

13.1编译程序的书写语言与T

型图

13.2编译程序的自展技术

13.3交叉编译与编译程序的移植

13.4编译程序的构造工具

13.4.1基于LALR（1）的语法

分析程序的生成器

YACC

13.4.2基于LL（2）文法的编

译器的构造工具

（SD&EBNF－LL（2））

13.4.3词法分析程序的

生成器LEX

13.5练习

附录A PL/0编译程序文本

附录B 词法分析程序生成器LEx的使

用方法

B.1LEX概述

B.2LEX源程序的格式

B.3LEX用的正规式

B.4LEX源程序中的动作

B.5识别规则的二义性

B.6LEX源程序中的辅助定义

部分

B.7怎样在UNIX系统中使

用LEX

B.8LEX源程序例子

B.9再谈上下文相关性的处理

B.10LEX源程序格式总结

附录C 语法分析程序自动产生器YACC

的使用方法

C.1YACC概述

C.2YACC源程序的一般格式

C.3YACC源程序说明部分的写法

C.3.1头文件表

C.3.2宏定义

C.3.3数据类型定义

C.3.4全局变量定义

C.3.5语法开始符定义

C.3.6语义值类型定义

C.3.7终结符定义

C.3.8运算符优先级及结合

性定义

C.4YACC源程序中语法规则部分

的写法

C.4.1语法规则的书写格式

C.4.2语义动作

C.4.3YACC解决二义性和冲突

的方法

C.4.4语法分析中的错误

处理

C.5程序段部分

C.5.1主程序

C.5.2错误信息报告程序

C.5.3词法分析程序

C.5.4其它程序段

C.6YACC源程序例子说明

C.6.1YACC的源程序例1

C.6.2YACC的源程序例2

附录D 编译原理实验要求

附录E 编译原理辅助教学软件功能介绍

和使用说明

E.1功能介绍

E.1.1THPLoCAI的功能

E.1.2TH－CCAIS的功能

E.2使用说明

E.2.1THPLoCAI使用说明

E.2.2TH－CCAIS使用说明

E.2.3其它补充说明

参考文献