×
暂无评论
图文详情
  • ISBN:9787030734396
  • 装帧:一般胶版纸
  • 册数:暂无
  • 重量:暂无
  • 开本:16开
  • 页数:228
  • 出版时间:2022-10-01
  • 条形码:9787030734396 ; 978-7-03-073439-6

内容简介

本书围绕编译程序分析、设计和实现方面的主题,介绍上下文无关文法、有限自动机的基础知识,以及构造程序设计语言编译程序的一般原理、设计方法和实现技术,包括词法分析、语法分析、语义分析、中间代码生成、目标代码生成、运行时刻环境和代码优化;设计了一个案例语言,给出该语言翻译器的分析、设计和实现的完整过程;介绍了开源编译器GCC的逻辑结构、典型中间代码形式和存储管理策略,也围绕目标文件介绍了汇编和链接。 本书可以作为高校计算机科学与技术等相关专业的本科生教材,也可以作为相关专业教师和学生的参考书。

目录

目录
第1章 引论 1
1.1 编译器 1
1.2 编译器的结构 2
1.2.1 词法分析 3
1.2.2 语法分析 3
1.2.3 语义分析 4
1.2.4 中间代码生成 4
1.2.5 代码优化 5
1.2.6 目标代码生成 5
1.2.7 编译器的组织 5
1.3 GCC概述 6
1.3.1 GCC的语言处理过程 6
1.3.2 GCC的逻辑结构 7
1.4 编译程序的发展 8
1.4.1 程序设计语言的发展 8
1.4.2 编译技术的发展 8
习题 9
第2章 上下文无关文法和分析 10
2.1 概述 10
2.2 符号串及运算 11
2.3 文法 12
2.3.1 上下文无关文法的定义 12
2.3.2 推导和归约 13
2.3.3 文法定义的语言 14
2.3.4 文法的分类 15
2.3.5 文法在应用中的说明 17
2.4 语法树 18
2.4.1 语法树的定义 18
2.4.2 文法的二义性 20
2.4.3 短语和句柄 21
习题 22
第3章 词法分析 25
3.1 正规表达式 25
3.2 有限自动机 26
3.2.1 确定的有限自动机 27
3.2.2 非确定的有限自动机 28
3.2.3 含e的非确定的有限自动机 28
3.2.4 非确定有限自动机的确定化 29
3.2.5 确定有限自动机的*小化 31
3.3 正规表达式和有限自动机 32
3.3.1 从正规表达式到有限自动机 32
3.3.2 从有限自动机到正规表达式 33
3.4 有限自动机和正规文法 35
3.5 词法分析程序 36
3.5.1 DFA的实现 36
3.5.2 词法分析程序实现应考虑的问题 37
习题 39
第4章 语法分析 42
4.1 自顶向下的语法分析 42
4.1.1 确定的自顶向下语法分析 42
4.1.2 LL(1)文法 46
4.1.3 左递归和左公因子的消除 49
4.1.4 递归下降的语法分析 51
4.1.5 表驱动的语法分析 53
4.2 自底向上的语法分析 55
4.2.1 移进-归约的语法分析 55
4.2.2 LR语法分析 57
4.2.3 项目和项目集 60
4.2.4 LR(0)分析表构造 62
4.2.5 SLR(1)分析表构造 64
4.2.6 LR(1)分析表构造 66
4.2.7 LALR(1)分析表构造 68
4.3 语法错误的恢复 71
4.3.1 递归下降分析中的语法错误的恢复 71
4.3.2 LL分析中的语法错误的恢复 73
4.3.3 LR语法分析中的语法错误的恢复 74
习题 75
第5章 语义分析 77
5.1 语义分析概述 77
5.2 属性文法 78
5.2.1 属性文法及相关概念 78
5.2.2 语法制导定义 80
5.3 属性计算 81
5.3.1 依赖图 81
5.3.2 属性的计算顺序 83
5.3.3 S属性和L属性的语法制导定义 83
5.4 语法制导翻译 85
5.4.1 自顶向下语法分析中属性计算 85
5.4.2 自底向上语法分析中综合属性计算 92
5.4.3 自底向上语法分析中继承属性计算 94
5.5 符号表 98
5.5.1 符号表的作用 98
5.5.2 符号的属性和存储方法 99
5.5.3 符号表的设计 103
5.5.4 符号表的管理 105
5.5.5 嵌套作用域的管理 105
5.6 声明 109
5.7 类型检查 110
5.7.1 类型表达式 110
5.7.2 类型检查规则 112
5.7.3 类型转换 112
习题 113
第6章 中间代码生成 119
6.1 中间代码概述 119
6.1.1 线性中间代码 119
6.1.2 树型中间代码 121
6.1.3 图式中间代码 121
6.2 赋值语句的翻译 122
6.2.1 简单赋值语句的翻译 123
6.2.2 数组引用的翻译 125
6.3 布尔表达式的翻译 127
6.3.1 直接对布尔表达式求值 128
6.3.2 通过控制流翻译布尔表达式 129
6.4 典型控制结构的翻译 132
6.5 GCC的中间代码 134
6.5.1 GENERIC 134
6.5.2 GIMPLE 135
6.5.3 RTL 136
习题 137
第7章 运行时刻环境 139
7.1 存储组织 139
7.1.1 程序运行时的内存映像 139
7.1.2 存储分配策略 139
7.2 活动记录 141
7.2.1 活动记录的一般结构 141
7.2.2 变长数据的分配 143
7.3 基于栈的过程管理 143
7.3.1 过程调用和返回 143
7.3.2 过程间的值传递 145
7.4 非局部变量的访问 147
7.4.1 无嵌套过程的非局部变量 148
7.4.2 过程嵌套定义的非局部变量 148
7.5 GCC的存储管理策略 151
7.5.1 程序运行时的内存映像 151
7.5.2 x86-64栈结构 152
7.5.3 函数和参数 153
习题 156
第8章 代码优化 160
8.1 基本块和流图 160
8.1.1 基本块 160
8.1.2 流图 161
8.1.3 循环 161
8.2 数据流分析 163
8.2.1 数据流分析模式 163
8.2.2 到达定值分析 163
8.2.3 活跃变量分析 166
8.2.4 可用表达式分析 167
8.3 窥孔优化 170
8.4 基本块的优化 171
8.4.1 基本块的有向无环图表示 172
8.4.2 基于DAG的代码重建 175
8.5 循环优化 175
8.5.1 代码外提 175
8.5.2 归纳变量相关的优化 178
习题 179
第9章 目标代码生成 182
9.1 代码生成的主要问题 182
9.1.1 指令选择 182
9.1.2 寄存器分配 183
9.1.3 指令调度 183
9.2 一个简单的代码生成器 184
9.2.1 目标语言 184
9.2.2 一个目标代码生成算法 186
9.2.3 表达式优化代码的生成 189
9.3 基于图着色的寄存器分配 191
9.4 目标文件 192
9.4.1 目标文件格式 193
9.4.2 汇编 195
9.4.3 链接 197
习题 199
第10章 简单语言的翻译程序 202
10.1 源语言及其定义 202
10.1.1 语法定义 202
10.1.2 其他约束 204
10.2 词法分析的实现 205
10.2.1 词法记号 205
10.2.2 词法单元的定义 206
10.2.3 单词的识别 206
10.3 语法分析的实现 208
10.3.1 文法的分析和变换 208
10.3.2 递归下降的语法分析程序 209
10.4 符号表的实现 210
10.4.1 符号表的设计 210
10.4.2 符号表的管理 212
10.5 中间代码生成 213
10.5.1 中间代码的定义 214
10.5.2 生成中间代码的构造 215
10.5.3 中间代码生成和优化 220
10.6 目标代码生成 221
10.6.1 虚拟目标机 221
10.6.2 运行时刻环境 223
10.6.3 从中间代码到目标代码的转换 224
10.6.4 虚拟机解释程序 225
10.7 课程设计 226
参考文献 229
展开全部

节选

第1章 引论 1.1 编译器 一种高级程序设计语言(简称高级语言)定义一个编程抽象,这个抽象可以使编程更容易,使编写的程序可读性更高、可移植性更好。然而,系统执行高级语言编写的程序时需要将程序转换成目标机能够识别的指令,并将这些指令按照一定的格式存储在存储器中。 图1-1所示的是一个C语言的示例程序test.c,经过gcc-5.4.0编译产生x86-64目标程序,该目标程序是一个二进制的文件。 图1-1 C语言的示例程序test.c 图1-2 目标代码示例 从上面的示例程序可以看出,编译器就是一个翻译程序,将一种语言编写的源程序翻译为另一种语言编写的目标程序。显然,识别并报告源程序中的错误也是编译器的一个重要任务。在大多数程序员的眼中,编译器可以看作图1-3所示的一个“黑箱”。 图1-3 编译器 编译器将源程序转换成目标程序,系统再将目标程序加载到内存中并运行,*终可以实现程序的输入处理和输出。解释器是另一种程序设计语言处理器,和编译器一样,解释器需要检查程序的正确性并分析程序的语法和语义。然而,与编译器不同,解释器不生成目标程序,而是直接根据源程序和用户输入执行程序。一般来说,编译器产生的目标程序执行比解释器快,但是解释器的错误诊断效果比编译器好。 将源程序转换成可执行目标程序时,编译器往往还需要和一些相关程序紧密结合,这些程序包括预处理器、汇编器、链接器等。预处理器、编译器、汇编器和链接器一起构成编译系统。预处理器是在翻译之前由编译器调用的独立程序,主要处理宏定义和文件包含等信息。汇编语言不仅容易转换成目标机指令,也容易调试,所以为编译器提供了通用的输出语言。然而,汇编语言程序还需要经过汇编器转换成目标代码。如果程序被分成多个部分进行编译,那么汇编器得到的多个汇编语言程序还需要通过链接器进行链接,*后才能得到可执行的目标文件。 1.2 编译器的结构 编译将一种语言编写的源程序映射成另一种语言编写的目标程序,但是将高级语言程序直接有效地转换为目标机代码的映射规则往往难以找到,所以“黑箱”中的映射过程可以分为前端和后端两个部分(图1-4)。 图1-4 编译器的前端和后端 前端把源程序分解为若干个组成元素,并对这些元素附加语法结构,然后根据这个结构构建源程序的中间表示(Intermediate Representation,IR),同时收集源程序的信息并将其存入符号表。后端根据得到的中间表示和符号表中的信息构建目标程序。简单地说,前端致力于理解源程序,后端致力于把程序映射到目标机上。 事实上,编译器在生成目标代码之前可能使用多种中间表示。这些中间表示的使用可以使编译器的前端语言和后端机器相对独立,降低编译的难度,同时可以更好地支持编译器的移植。此外,引入中间表示可以将编译过程进一步细化为若干个转换阶段,每一个阶段将源程序由一种中间表示转换成另一种中间表示。一个典型的编译过程可以分解为词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、目标代码优化,如图1-5所示。其中,中间代码优化和目标代码优化统称为代码优化,是可选的步骤。另外,中间表示不一定是被编译器明确地构建出来的。 图1-5 编译器的典型编译过程 1.2.1 词法分析 编译器的**个任务就是词法分析。词法分析的任务是从源程序的连续字符序列中识别出有意义的单词。 对于每个单词,词法分析程序将它转换为一种内部表示形式,称为词法单元。词法单元一般包括单词的词法记号和属性。词法记号是用于语法分析的抽象记号,可以理解为一类单词的标签。典型的词法记号包括关键字、整数、实数、标识符、运算符、分隔符等。单词*典型的属性是标识符的名字、整数的数值等。例如,示例程序(图1-1)中的int、main是关键字,3和2是整数,a和b是标识符,“=”和“;”分别是运算符和分隔符。 因此,每个词法单元可以表示为一个二元组。其中,tokenID表示词法记号,token_value表示单词属性。如果标识符、“=”和“+”的词法记号分别是id、becomes和addtoken,那么示例程序(图1-1)中语句sum=a+b经过词法分析可以输出如下词法单元序列: 词法分析中,对程序执行结果没有影响的元素将被忽略,如空格、回车符、换行符、制表符、注释等。此外,如果一个词法记号仅仅定义一个单词,那么没有必要同时使用tokenID和token_value。例如,假设addtoken仅仅是“+”的抽象,那么输出可以表示为。 1.2.2 语法分析 语法分析程序判定从词法分析输出的词法单元序列是否符合语言的语法结构,并构造其中间表示形式。一种常用的中间表示是树型结构,称为语法树。 示例程序(图1-1)中语句sum=a+b可以表示为图1-6所示的树型结构。其中,每个结点都表示一个语法元素。 语法树以一种层次定义关系忠实地反映语法元素之间的语法结构,但是语法树的具体形式依赖于语法元素之间的定义。例如,图1-6所示的语法树中,赋值语句通过表达式定义,表达式可以通过表达式递归定义,也可以通过标识符直接定义。这种语法关系将采用上下文无关文法进行描述,并进一步构造出有效的语法分析程序。 图1-6 语法树示例 1.2.3 语义分析 语法分析在词性和语法规则上确定句子的合法性,局限于拼写和语法范畴,但是语法分析忽略单词的含义。例如,sum=a+b和y=b+c在语法结构上是完全一样的。因此,在前端将源程序翻译成中间表示之后,编译器必须进行语义分析。 语义分析主要根据语言的语义约束检查程序的一致性,收集相关信息并将其存储到符号表或者语法树中。例如,程序(图1-1)将sum、a和b声明为整型变量,语义分析程序首先在处理声明时将这些信息填入符号表或者存储到语法树的相应结点中。 语义分析的一个主要任务是类型检查。例如,针对赋值语句sum=a+b(图1-1),首先需要根据a和b的类型信息判断它们是否相容,并进一步确定a+b结果的类型;接着确定sum和a+b结果的类型是否相容。 语义分析和符号表密切相关,但是符号表不只和语义分析相关,它几乎与编译器的所有阶段都进行交互。词法分析阶段和语法分析阶段识别符号的名称与抽象的词法记号;语义分析阶段将增加数据类型和其他信息;代码生成阶段和代码优化阶段也将利用由符号表提供的信息选出恰当的代码。 1.2.4 中间代码生成 中间代码是在源语言和目标语言之间引入的一种中间表示形式,可以看作某种虚拟机的抽象。通过中间代码,编译器可以避开直接从源语言到目标语言翻译时较大的语义跨度。中间代码的引入使编译程序的逻辑结构更加简单明确,也有利于实现程序优化和编译器的移植。 中间代码一般具有两个重要的性质:容易生成,同时容易转换成目标机上的程序。树型结构和线性中间代码是两种*重要的中间表示形式。语法树和抽象语法树就是树型结构中间代码;三地址代码是一种线性中间代码,这种代码类似于汇编指令,每条代码有三个分量。例如,图1-1中的赋值语句sum=a+b可以表示为如下的三地址代码: 其中,T1是存储加法运算结果的临时变量。此外,从上面的三地址代码可以看出,每条指令只能有一个运算,所以指令顺序和运算顺序一致。更多形式的中间代码和处理技术将在第6章介绍。 1.2.5 代码优化 代码优化的目的是提高程序执行的时空效率,可以分为与机器有关的优化和与机器无关的优化。与机器无关的优化主要针对中间代码进行,也称为中间代码优化;与机器有关的优化主要针对目标代码进行,也称为目标代码优化。 把高级结构和数据存储运算直接翻译成代码,其运行的效率可能比较低。在图1-1中的sum=a+b,如果直接翻译,那么得到的目标程序每次运行不仅需要访问a和b的存储空间,还需要进行加法运算。如果考虑sum=a+b之前a和b的值是个常量,那么赋值号右边的a和b可以分别用2和3替换;此外,2+3可由编译器直接计算并得到结果5。因此,sum=a+b可以被优化为sum=5。 好的优化能够提高代码的质量。然而,引入优化使得源代码和目标代码之间的关系变得模糊,同时使得程序调试变得困难。其次,不管多么复杂的优化,都不能为所有的程序产生*优代码,而且很多编译优化问题都是不可判定的。此外,代码优化是以增加编译器的开销为代价的,所以优化工作量大势必会降低编译器编译源程序的效率。因此,不同的编译器会在编译效率和源程序执行效率之间进行权衡,并采用不同的优化策略和优化技术。 1.2.6 目标代码生成 代码生成器以源程序或者源程序的中间表示形式作为输入,并把它映射为目标机上的代码。代码生成与目标机的特性密切相关,目标机上的指令格式、寻址达式、寄存器分配、数据表示等都是影响代码生成的因素。 代码生成不仅需要确定选择哪些指令,还要确定指令高效执行的顺序,确定哪些值应该放入寄存器中,哪些值放入内存中。因此,指令选择、寄存器分配、指令的调度是代码生成的三个主要问题。这三个问题相互作用,对生成代码的质量有直接的影响。指令选择就是选择一组实现中间操作的目标指令集。因为寄存器是存储层次结构中访问速度*快的资源,所以操作数存储在寄存器中的指令比操作数存储在内存中的指令的执行速度快。然而,寄存器的数量有限,所以一些指令执行之后不得不将其操作数移入内存,为即将执行的指令空出寄存器。从寄存器移进内存或者从内存移进寄存器的指令将增加代码运行的开销,所以要充分考虑指令执行顺序及其操作数之间的关系,可以尽可能提高代码的性能。 和代码生成密切相关的一个问题是如何对源程序中的标识符进行存储分配,编译器将在中间代码或目标代码生成阶段做出存储分配的决定。 1.2.7 编译器的组织 编译器的结构强调编译程序的逻辑过程和步骤。在实现编译器的时候,可以将每个步骤组织为一遍,也可以将几个步骤组织为一遍。每遍读入一个输入文件并产生一个输出,将一种中间表示形式转换成另一种中间表示形式。例如,可以将词法分析、语法分析、语义分析和中间代码生成组织成一遍,代码生成和代码优化组织成一遍。 实际上,编译程序也可以通过一遍完成所有的编译步骤,这样的编译器称为单遍编译器。一个典型的单遍编译器可以按照图1-7所示的方式组织,其中的核心程序是语法语义分析程序,只有核心程序需要单词时才会调用词法分析程序识别一个单词,同样只有核心程序需要生成代码的时候才会调用代码生成程序。单遍编译器不用显式构造中间表示,适合实现翻译需求相对简单的程序设计语言。 图1-7 一个单遍编译器的模型 和单遍编译器相对的就是多遍编译器。在多遍编译器中,编译器围绕一组精心设计的中间表示形式进行组织,每一遍将源程序或一种中间表示形式转换成另一种表示形式。多遍编译器比较灵活,适合进行具有复杂语言功能的程序设计语言的翻译。此外,精心设计的中间表示形式使得编译器可以将不同的前端和不同的后端结合起来,提高编译器的可移植性。 1.3 GCC概述 GCC是一套GNU(GNU’s Not UNIX)开发的编译器环境,不仅支持多种语言,还支持多种硬件平台。 1.3.1 GCC的语言处理过程 高级程序设计语言程序只有转化为目标机上的代码才能执行。GCC将源程序转换成可执行文件的过程可以细分为4个阶段:预处理、编译、汇

预估到手价 ×

预估到手价是按参与促销活动、以最优惠的购买方案计算出的价格(不含优惠券部分),仅供参考,未必等同于实际到手价。

确定
快速
导航