编译器设计基础

作者:(美国)梅杜纳 (Alexander Meduna) 译者:杨萍 王生原

Alexander Meduna，PhD，布尔诺理工大学计算机科学系教授，于1988年在那里获得博士学位。从1988至1997年，他在美国密苏里哥伦比亚大学讲授计算机科学。从2000年起，他在布尔诺理工大学任教，更加专注于讲授计算机科学和数学。除了这两所大学，他还在美洲、欧洲和日本的几所大学短期讲授计算机科学。他的课程主要集中于编译器的编写。他所教授的内容也涵盖了多种主题，包括自动机、离散数学、形式语言、操作系统、程序设计语言原理以及计算理论。

第1章 导引/1

1.1 数学基础/1

1.1.1 集合与序列/1

1.1.2 语言/2

1.1.3 关系与翻译/3

1.1.4 图/4

1.1.5 证明/6

1.2 编译/8

1.2.1 编译阶段/8

1.2.2 编译器构造/12

1.3 重写系统/13

1.3.1 语言模型/14

本书要点/15

习题/15

部分习题解答/17

第2章 词法分析/19

2.1 模型/19

2.1.1 正规表达式/19

2.1.2 有穷自动机/20

2.1.3 有穷自动机的表示/22

2.1.4 简化/23

2.1.5 有穷变换机/28

2.2 方法/29

2.2.1 单词与单词记号/29

2.2.2 词法分析器/33

2.2.3 额外的任务/39

2.3 理论/39

2.3.1 正规表达式到有穷自动机的变换/39

2.3.2 有穷自动机的化简/44

2.3.3 非正规词法构造/51

2.3.4 判定问题/60

习题/62

部分习题解答/67

第3章 语法分析/69

3.1 模型/69

3.1.1 文法/69

3.1.2 下推自动机/80

3.2 方法/83

3.2.1 自上而下分析/83

3.2.2 递归下降分析程序/86

3.2.3 消除左递归/89

3.2.4 自下而上分析/91

3.3 理论/96

3.3.1 分析模型的能力/97

3.3.2 验证文法形式的语法描述/97

3.3.3 文法的简化/99

3.3.4 文法的范式和基于它们的分析/108

3.3.5 文法不能描述的语法/114

3.3.6 判定问题/120

习题/122

部分习题解答/127

第4章 确定的自上而下分析/130

4.1 预测集合和LL文法/130

4.2 预测分析/136

4.2.1 递归下降预测分析/136

4.2.2 表驱动的预测分析/139

4.2.3 处理错误/144

习题/145

部分习题解答/149

第5章 确定的自下而上分析/151

5.1 优先分析/151

5.1.1 算符优先分析算法/151

5.1.2 算符优先表的构造/154

5.1.3 处理错误/155

5.1.4 扩展/158

5.1.5 限制/160

5.2 LR语法分析/160

5.2.1 LR分析算法/160

5.2.2 构造LR表/163

5.2.3 LR分析中的错误处理/170

习题/172

部分习题解答/175

第6章 语法制导翻译和中间代码生成/178

6.1 自下而上语法制导翻译和中间代码生成/179

6.1.1 语法树/180

6.1.2 三地址码/185

6.1.3 波兰式/188

6.2 自上而下的语法制导翻译/189

6.3 语义分析/191

6.4 符号表/192

6.4.1 组织/192

6.4.2 存储标识符名字/193

6.4.3 块结构的符号表/194

6.5 语法制导翻译的软件工具/195

6.5.1 Lex/196

6.5.2 Yacc/197

习题/201

部分习题解答/203

第7章 优化和目标代码生成/205

7.1 跟踪变量的使用/205

7.1.1 基本块/206

7.1.2 基本块内变量的使用/208

7.1.3 基本块之间变量的使用/211

7.2 中间代码优化/214

7.3 目标代码的优化和生成/218

习题/222

部分习题解答/225

结束语/226

文献纪要/226

研究生层次的话题/227

当前趋势/230

附录A实现/233

A.1 概念/233

类接口/234

A.2 代码/236

参考文献/256

出版社: 清华大学出版社; 第1版 (2009年4月1日)

外文书名: Elements Of Compiler Design

丛书名: 世界著名计算机教材精选

平装: 277页

正文语种: 简体中文

开本: 16

ISBN: 9787302193340

条形码: 9787302193340

尺寸: 25.6 x 18.4 x 1.4 cm

重量: 762 g

《编译器设计基础》是编译器编写方面的入门教材，适用于一个学期的高年级本科课程。《编译器设计基础》坚持在这一主题的理论和实践方法之间维持一种平衡。从理论角度来看，《编译器设计基础》介绍了编译及其核心阶段的基本模型。基于这些模型，它讲解了编译器中用到的概念、方法和技术。《编译器设计基础》还简述了编译以及相关话题的数学基础，这些话题包括形式语言理论、自动机和变换机。同时，从实践的视角来看，《编译器设计基础》描述了编译器技术是如何实现的。一个案例学习贯穿全书，《编译器设计基础》设计一种新的类Pascal程序设计语言，并构造其编译器;在讨论编译器各种方法的同时，这个案例学习用作其实现的实例说明。此外，《编译器设计基础》提供了许多详细的例子和计算机程序，以强调编译算法的实际应用。《编译器设计基础》中也涵盖了核心软件工具。学完《编译器设计基础》之后，学生应该能够掌握编译过程，编写简单的真实编译器，并可以继续学习关于该主题的更深入的书籍。

编译 器可以生成用来在与编译器本身所在的计算机和操作系统(平台)相同的环境下运行的目标代码，这种编译器又叫做"本地"编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。"源码到源码编译器"是指用一种高级语言作为输入，输出也是高级语言的编译器。例如: 自动并行化编译器经常采用一种高级语言作为输入，转换其中的代码，并用并行代码注释对它进行注释(如OpenMP)或者用语言构造进行注释(如FORTRAN的DOALL指令)。

作用是通过代入预定义等程序段将源程序补充完整。

前端主要负责解析(parse)输入的源代码，由语法分析器和语意分析器协同工作。语法分析器负责把源代码中的'单词'(Token)找出来，语意分析器把这些分散的单词按预先定义好的语法组装成有意义的表达式，语句 ，函数等等。 例如"a = b + c;"前端语法分析器看到的是"a， =， b ， +， c;"，语意分析器按定义的语法，先把他们组装成表达式"b + c"，再组装成"a = b + c"的语句。 前端还负责语义(semantic checking)的检查，例如检测参与运算的变量是否是同一类型的，简单的错误处理。最终的结果常常是一个抽象的语法树(abstract syntax tree，或 AST)，这样后端可以在此基础上进一步优化，处理。

编译器后端主要负责分析，优化中间代码(Intermediate representation)以及生成机器代码(Code Generation)。

一般说来所有的编译器分析，优化，变型都可以分成两大类: 函数内(intraprocedural)还是函数之间(interprocedural)进行。很明显，函数间的分析，优化更准确，但需要更长的时间来完成。

编译是从源代码(通常为高级语言)到能直接被计算机或虚拟机执行的目标代码(通常为低级语言或机器语言)的翻译过程。然而，也存在从低级语言到高级语言的编译器，这类编译器中用来从由高级语言生成的低级语言代码重新生成高级语言代码的又被叫做反编译器。也有从一种高级语言生成另一种高级语言的编译器，或者生成一种需要进一步处理的的中间代码的编译器(又叫级联)。

典型的编译器输出是由包含入口点的名字和地址， 以及外部调用(到不在这个目标文件中的函数调用)的机器代码所组成的目标文件。一组目标文件，不必是同一编译器产生，但使用的编译器必需采用同样的输出格式，可以链接在一起并生成可以由用户直接执行的EXE,

所以我们电脑上的文件都是经过编译后的文件。