编译原理：第一章 编译引论

1、 课 程 内 容第 1 章 编 译 引 论第 2 章 形式语言与自动机基础第 3 章 词法分析 (Lexical Analysis)第 4 章 语法分析(Syntax Analysis) 自上而下分析法第 5 章 语法分析(Syntax Analysis) 自下而上分析法第 6 章 语义分析与中间代码生成第 7 章 运 行 环 境第 8 章 代码优化（optimization）1.1 程序设计语言与编译程序1.2 编译程序的表示与分类1.3 编译程序的结构与组织1.4 语言开发环境中的伙伴程序1.5 编译程序结构的实例模型1.6 编译程序的构造与实现 第一章 编译引论 Compiler ? 第

2、一章 编译引论 1.1 程序设计语言与编译程序 Compiler ? 借助编译程序可以执行高级语言编写的程序； 编译程序是语言处理系统 ； 人、机交互的工具; 定义1.1 : 将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序, 称之为编译程序(compiler) 。 第一章 编译引论 1.1 程序设计语言与编译程序源语言： (source language) 编写源程序的语言是源语言。源程序： (source program)被翻译(编译）的程序称为源程序。 第一章 编译引论 1.1 程序设计语言与编译程序源语言一般是汇编语言或高级程序设计语言。 Compiler ? 编译程序是

3、语言处理系统 ； 编译程序是将高级语言翻译成机器语言的程序； 人、机交互的工具; 定义1.1 : 将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序, 称之为编译程序(compiler) 。 第一章 编译引论 1.1 程序设计语言与编译程序源程序目标程序：(target program) 源程序经过翻译（编译）后生成的程序称之为目标程序。 第一章 编译引论 1.1 程序设计语言与编译程序目标语言：(target language) 目标程序的描述语言称为目标语言。 Compiler ? 编译程序是语言处理系统 ； 编译程序是将高级语言翻译成机器语言的程序； 人、机交互的工具; 定义

4、1.1 : 将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序, 称之为编译程序(compiler) 。 第一章 编译引论 1.1 程序设计语言与编译程序源程序目标程序 Compiler ? 编译程序是语言处理系统 ； 编译程序是将高级语言翻译成机器语言的程序； 人、机交互的工具; 定义1.1 : 将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序, 称之为编译程序(compiler) 。 第一章 编译引论 1.1 程序设计语言与编译程序 将源程序翻译成等价的目标程序的程序, 称之为编译程序(compiler) 。 宿主语言： 编译程序的实现语言。 宿主机（目标机）：

5、编译程序的运行环境(运行编译程序的计算机）。 第一章 编译引论 1.1 程序设计语言与编译程序( 3 ) 用户直接关心的工具。( 2 ) 软件学科的重要分支；( 1 ) 人、机交互的基本界面；Compiler源程序目标程序等价变换作用地位 第一章 编译引论 1.1 程序设计语言与编译程序被编译的程序为A语言程序，编译的最终结果为B语言代码，编写编译程序的语言为C语言。那么， 语言是源语言， 语言是宿主语言， 语言是目标语言。 Ch2 形式语言自动机理论基础ACB1.1 程序设计语言与编译程序1.2 编译程序的表示与分类1.3 编译程序的结构与组织1.4 语言开发环境中的伙伴程序1.5 编译程序

6、结构的实例模型1.6 编译程序的构造与实现 第一章 编译引论一. 编译程序的分类与执行模式编译程序（实现）解释程序汇编程序编译程序解释程序： 接受某语言的源程序将其直接翻译成目标 代码且执行。编译程序： 接受某语言的源程序将其直接翻译成等价 的目标代码，然后执行且允许重复执行。汇编程序： 接受汇编源程序将其翻译成等价的机器语 言的目标程序，然后执行且允许重复执行。 第一章 编译引论 1.2 编译程序的表示与分类 编译执行和解释执行的区别： 编译执行是由编译程序生成一个与源程序等价的目标程序，它可以完全取代源程序，该目标程序可以运行任意次。 解释执行不生成目标程序，仅是对源程序逐句解释逐句执行。

7、 编译执行类似于自然语言的笔译；解释执行类似自然语言的口译。 第一章 编译引论 1.2 编译程序的表示与分类解释执行：编译执行：结果Compiler源程序目标程序computer运行程序computer数据Step 1Step 2 第一章 编译引论 1.2 编译程序的表示与分类解释程序源程序computer结果数据二. 编译程序的表示 1） 函数表示 ： T = C（S）T: 目标语言 C: 宿主语言 S: 源语言2） T型图表示源语言目标语言宿主语言C源目宿3）符号表示 第一章 编译引论 1.2 编译程序的表示与分类CCS TCST(体现编译程序的三个要素) 第一章 编译引论 1.2 编译程

8、序的表示与分类 T型图的组合ABCCXLLABABCCXLLABCCLLAABBX例1.1 : 用T型图描述将A机器上已经存在的L语 言的编译程序移植到B机器上的过程。 第一章 编译引论 1.2 编译程序的表示与分类分析:已知的编译器:ALA要得到的编译器:BLB 第一章 编译引论 1.2 编译程序的表示与分类 T型图的组合ABCCXLLABCCLLAABBALABLB已知的编译器:得到的编译器:例1.1 : 用T型图描述将A机器上已经存在的L语 言的编译程序移植到B机器上的过程。LLBStep1:Step2:L B LL A AL B AL B LL B AL B BStep3: 第一章 编

9、译引论 1.2 编译程序的表示与分类若目标机指令系统与宿主机的指令系统不同（即运行在宿主机A上的某编译程序为另一台机器B生成目标代码），这样的编译器称为交叉编译器。 例1.1 : 用T型图描述将A机器上已经存在的L语 言的编译程序移植到B机器上的过程。 第一章 编译引论 1.2 编译程序的表示与分类LLBALALLBALBBLB例1.1 : 用T型图描述将A机器上已经存在的L语 言的编译程序移植到B机器上的过程。LLBStep1:Step2:L B LL B LL B B 第一章 编译引论 1.2 编译程序的表示与分类1.1 程序设计语言与编译程序1.2 编译程序的表示与分类1.3 编译程序的

10、结构与组织1.4 语言开发环境中的伙伴程序1.5 编译程序结构的实例模型1.6 编译程序的构造与实现 第一章 编译引论 表 格 管 理 源 语 语 中 代 代 程 法 义 间 生 码 码 目标 分处 代 成 优 生 序词法分析析理 码化 成 程序 出 错 处 理 front end back end ( 分析 )（综合） 第一章 编译引论 1.3 编译程序的结构与组织 编译程序的逻辑结构 (经典划分) 1. 词法分析 (lexical analysis)依次扫描读入的源程序中的每个字符,识别出源程序中有独立意义的源语言单词(属性字或记号),并用某种特定的数据结构进行表示。Scanner源程序L

11、属性字流L1 第一章 编译引论 1.3 编译程序的结构与组织词法分析阶段是对输入的符号串形式的源程序进行最初的加工处理。词法分析实际上是一种线性分析。属性字的数据结构:类型标识和内码两个数据项。例1.2: 有如下C代码行 ： aindex = 12 * 3 ； 词法分析： ( 1 ) a 标识符 ( 2 ) 左方括号 ( 3 ) index 标识符 ( 4 ) 右方括号 ( 5 ) = 赋值 ( 6 ) 12 整常数 ( 7 ) * 乘号 ( 8 ) 3 整常数 ( 9 ) ; 分号 识别出9个单词。属性字流源程序 第一章 编译引论 1.3 编译程序的结构与组织 表 格 管 理 源词 语 中

12、代 代 程 法 义 间 生 码 码 目标 分 处 代 成 优 生 序析语法分析理 码化 成 程序 出 错 处 理 front end back end ( 分析 )（综合） 第一章 编译引论 1.3 编译程序的结构与组织 编译程序的逻辑结构 (经典划分)2. 语法分析 (Syntax analysis) 语法分析的任务是依据语言文本所规定的语法规则对词法分析的结果(属性字流)进行语法检查, 识别出单词序列所对应的语法范畴。通常将语法分析的结果表示为语法分析树或抽象语法树，它是一种层次结构的形式。例1.2中的C语言的赋值表达式语句经过语法分析，确认合乎C语言的语法规则且语法范畴为表达式语句, 产

13、生的语法分析树形式的语法分析结果如下图所示。 第一章 编译引论 1.3 编译程序的结构与组织C语句 aindex = 12 * 3 ；的语法分析树语法范畴 第一章 编译引论 1.3 编译程序的结构与组织常数 12 常数 3 标识符a 表达式 * 表达式表达式赋值表达式 数组元素引用 表达式标识符index 表 格 管 理 源词 语 代 代 程 法 法 码 码 目标 分 分 优 生 序析析 语中义间生处代成理码化 成 程序 出 错 处 理 front end back end ( 分析 )（综合） 第一章 编译引论 1.3 编译程序的结构与组织 编译程序的逻辑结构 (经典划分)3. 语义分析 (

14、semantic analysis)与中间代码生成 语义分析阶段的任务是依据语言文本限定的语义规则对语法分析所识别的语法范畴进行语义检查 和处理, 直至最后翻译成与其等价的某种中间代码或 目标代码。 第一章 编译引论 1.3 编译程序的结构与组织语义分析是整个编译程序完成的最实质性的翻译 任务。例1.3: 设有赋值语句 x=(a+b)*c * T1 c T2 = T2 x + a b T1 产生的四元式形式的中间代码： 第一章 编译引论 1.3 编译程序的结构与组织 表 格 管 理 源词 语 语 中 代 程 法 法 义 间 生 码 目标 分 分处 代 成 生 序析析理 码代码优化 成 程序 出

15、 错 处 理 front end back end ( 分析 )（综合） 第一章 编译引论 1.3 编译程序的结构与组织 编译程序的逻辑结构 (经典划分)4. 代码优化 (optimization) 代码优化是在不改变源程序语义的基础上对其进行加工变换, 以期获得高效的目标代码。 第一章 编译引论 1.3 编译程序的结构与组织代码优化可以在中间代码或目标代码级上进行。运行时间的缩短和存贮空间的节省。例1.4: 设有语句 for (i=1; i=200; i+) y=y*i+y; x=x1/cos(x2) x=x1/cos(x2)for (i=1; i=200; i+) y=y*i+y; 优化后

16、 第一章 编译引论 1.3 编译程序的结构与组织 表 格 管 理 源词 语 语 中 代 程 法 法 义 间 生 码 目标 分 分处 代 成 优 序析析理 码化 代码生成 程序 出 错 处 理 front end back end ( 分析 )（综合） 第一章 编译引论 1.3 编译程序的结构与组织 编译程序的逻辑结构 (经典划分)5. 目标代码生成 (code generator) 根据中间代码及编译过程中产生的各种表格的有关信息,最终生成所期望的目标代码程序。一般为特定机器的机器语言代码或汇编语言代码, 生成中需要充分考虑计算机硬件和软件所提供的资源, 以生成较高质量的目标程序。 第一章 编

17、译引论 1.3 编译程序的结构与组织 对例1.2 “aindex = 12 * 3 ；”的语句生成代码。要考虑怎样存储整型数来为数组元素的引用生成目标代码，以假设的汇编语言描述如下：MOV R0, index ; 索引值赋给寄存器R0MUL R0, 2 ; 存储按字节编址，整型数 ; 占2个字节MOV R1, &a ; &a表示数组a的基地址ADD R1, R0 ; 计算aindex的地址MOV *R1, 36 ; aindex = 36 第一章 编译引论 1.3 编译程序的结构与组织 表 格 管 理 源词 语 语 中 代 代 程 法 法 义 间 生 码 码 目标 分 分处 代 成 优 生 序

18、析析理 码化 成 程序 出 错 处 理 front end back end ( 分析 )（综合） 第一章 编译引论 1.3 编译程序的结构与组织 编译程序的逻辑结构 (经典划分) 编译阶段与自然语言的翻译对比 编 译 程 序 自 然 语 言 翻 译词法分析查字典、识别单词语法分析分析识别句子产生中间代码翻译初稿代码优化对初稿润色修饰目标代码生成译文定稿 第一章 编译引论 1.3 编译程序的结构与组织 源词 语 语 中 代 代 程 法 法 义 间 生 码 码 目标 分 分处 代 成 优 生 序析析理 码化 成 程序 表格管理出错处理 front end back end ( 分析 )（综合）

19、第一章 编译引论 1.3 编译程序的结构与组织 编译程序的逻辑结构 (经典划分) 表格管理 编译程序的公共辅助部分。对源程序中的各种量进行管理，登记在相应的表格。编译程序处理时通过查表得到所需的信息。 出错处理 编译程序的公共辅助部分。对源程序中的各种错误检查、定位、定性、报告，并尽可能将错误限制在尽可能小的范围内，保障编译继续。 第一章 编译引论 1.3 编译程序的结构与组织 源词 语 语 中 代 代 程 法 法 义 间 生 码 码 目标 分 分处 代 成 优 生 序析析理 码化 成 程序 表格管理出错处理 front end back end( 分析 )（综合） 第一章 编译引论 1.3

20、编译程序的结构与组织 编译程序的逻辑结构 (经典划分) 定义1.2 : ( 遍 Pass ) 对源程序或源程序的中间形式从头到尾扫描一遍，并做有关的分析加工，生成新的与源程序等价的中间形式或生成目标程序。 遍数多的优点： 1）编译程序逻辑结构清晰； 2）减少对主存容量的要求； 3）优化准备充分等。 第一章 编译引论 1.3 编译程序的结构与组织 遍设置的考虑因素 1） 宿主机存储容量； 2） 编译程序功能的强弱； 3） 源语言的繁简及约束； 4） 优化因素； 5） 设计、实现的环境、工具及人员因素等。 第一章 编译引论 1.3 编译程序的结构与组织1.1 程序设计语言与编译程序1.2 编译程序

21、的表示与分类1.3 编译程序的结构与组织1.4 语言开发环境中的伙伴程序1.5 编译程序结构的实例模型1.6 编译程序的构造与实现 第一章 编译引论 一遍扫描的编译程序结构模型(Pascal编译器） 第一章 编译引论 1.4 编译程序结构的实例模型 语法分析程序源程序语义处理目标程序词法分析代码生成 AHPL模拟器（两遍扫描的编译程序结构模型） AHPL模拟器 第一遍 第二遍 AHPL 词法分析语法 操作表 源程序 分析语义处理 （目标程序）模拟结果代码生成 第一章 编译引论 1.4 编译程序结构的实例模型C源程序词法分析语法分析语义处理（中间代码生成）中间代码代 码 生 成代 码 优 化目标代码 （汇编） 汇编代码 PDP 11 C编译器结构模型（三遍扫描的编译程序结构模型） 第一章 编译引论 1.4 编译程序结构的实例模型Gcc compiler structureC+source fileC source fileF source fileC+ ParserC Parser语法树RTL 生成器优化器汇编器Fortran Parser寄存器转换语言RTL 表示Assembly