第一章编译程序概论

1、第一章第一章 编译程序概论编译程序概论学习目标：学习目标：v掌握：编译的各个阶段掌握：编译的各个阶段v理解：编译程序的概念理解：编译程序的概念v了解：解释器，编译程序的结构和组合了解：解释器，编译程序的结构和组合1.11.1 什么是编译程序什么是编译程序1.21.2 编译过程概述编译过程概述1.31.3 编译程序的结构编译程序的结构1.41.4 编译阶段的组合编译阶段的组合1.51.5 编译技术和软件工具编译技术和软件工具1.11.1 什么是编译程序什么是编译程序1.1. 编译程序（编译程序（compiler）将用将用高级语言高级语言（如（如FORTRAN,PASCALFORTRAN,PASC

2、AL或或C C）书写）书写的程序翻译成等价的的程序翻译成等价的低级语言低级语言程序（如程序（如汇编汇编语言或机器语言语言或机器语言），这种翻译程序称为编译），这种翻译程序称为编译程序程序(compiler)。编译程序的输入对象称为编译程序的输入对象称为源程序源程序(Source program)输出对象称为输出对象称为目标程序目标程序（Targer or Object program）高级语高级语言程序言程序编译程序编译程序低级语低级语言程序言程序出错和警告信息出错和警告信息2.2. 解释器解释器(interpreter)与编译器与编译器共同点：都是语言的一个实现系统共同点：都是语言的一个实现

3、系统不同点：不同点：o解释器是源程序的一个解释器是源程序的一个执行系统执行系统，工作结果得到，工作结果得到源程序的执行结果；源程序的执行结果；o编译器是源程序的编译器是源程序的转换系统转换系统，工作结果得到等价，工作结果得到等价于源程序的某种目标程序于源程序的某种目标程序解释程序解释程序解释器和编译器解释器和编译器编译程序编译程序源程序源程序源程序源程序数据数据计算结果计算结果目标程序目标程序练习：v例1：编译器和解释器是两种高级语言处理程序，与编译器相比， 。 A、解释器不参与运行控制，程序执行的速度慢 B、解释器参与运行控制，程序执行的速度慢 C、解释器参与运行控制，程序执行的速度快 D、

4、解释器不参与运行控制，程序执行的速度快提高：v解释型：直接执行源程序或源程序的内部形式，其最大的特点是不产生目标程序，每使用一次就要解释一次。v翻译型：第一次使用时将可执行语句翻译成对应的机器代码并保存下来，之后直接使用保持的机器码，故运行效率高。效率高！效率高！灵活！灵活！扩展：程序设计语言分类分类分类主要特点主要特点代表代表命令式命令式( (过程式过程式) )基于动作的语言Fortran，c，Pascal函数式函数式以表操作进行处理Lisp，ML面向对象面向对象 对象与类是核心概念，封装、继承和多态是核心机制C+，SmallTalk，Java，C# ,Python逻辑程序逻辑程序设计设计以

5、形式逻辑为基础Prolog、VHDL、VerLog面向方面面向方面隔离横切式系统关注点Aspect脚本脚本编写脚本使用Python、Javascript练习：v例1： 可用于编写独立程序和快速脚本的语言是 (20) 。(20) APython BProlog CJava DC#v例2：下面关于程序语言的叙述，错误的是（22）A.脚本语言属于动态语言，其程序结构可以在运行中改变 B.脚本语言一般通过脚本引擎解释执行，不产生独立保存的目标程序C.php、JavaScript属于静态语言，其所有成分可在编译时确定 D.C语言属于静态语言，其所有成分可在编译时确定练习：v例3下列叙述中错误的是（22）

6、。A.面向对象程序设计语言可支持过程化的程序设计 B.给定算法的时间复杂性与实现该算法所采用的程序设计语言无关C.与汇编语言相比，采用脚本语言编程可获得更高的运行效率 D.面向对象程序设计语言不支持对一个对象的成员变量进行直接访问面向对象程序设计语言不支持对成员变量进行直接访问需预处理的源程序需预处理的源程序预处理程序预处理程序源程序源程序编译程序编译程序目标汇编程序目标汇编程序汇编程序汇编程序可再装配的机器代码可再装配的机器代码装配装配/连接连接-编辑程序编辑程序绝对机器代码绝对机器代码可再装配目标文件可再装配目标文件3.3. 高级语言程序的处理过程高级语言程序的处理过程编译程序的基本任务：

7、编译程序的基本任务：将源语言程序翻译成等将源语言程序翻译成等价的目标语言程序价的目标语言程序4. 编译程序的发展编译程序的发展第一个编译程序的出现：第一个编译程序的出现：2020世纪世纪5050年代年代早期，主要将算术公式翻译成机器代码早期，主要将算术公式翻译成机器代码2020世纪世纪5050年代中期，一批编译系统程序年代中期，一批编译系统程序开发成功开发成功2020世纪世纪5050年代末，开始研究编译程序的年代末，开始研究编译程序的自动生成工具自动生成工具2020世纪世纪6060年代，研究使用自展技术年代，研究使用自展技术并行编译技术并行编译技术1.2 1.2 编译程序概述编译程序概述v一个

8、编译程序的整个工作过程是划分成一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序从一种阶段进行的，每个阶段将源程序从一种表示形式转换成另一种表示形式。表示形式转换成另一种表示形式。v典型的划分方法：典型的划分方法：目标程序目标程序源程序源程序词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成表格管理表格管理出错处理出错处理编译的各个阶段编译的各个阶段1.1.词法分析词法分析 (lexical analysis or scanning)v任务任务: :从左到右一个字符一个字符地读入从左到右一个字符一个字符地读入源程序，对构

9、成源程序的字符流进行扫描源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个和分解，从而识别出一个个单词单词(Token)(Token)。逻辑上紧密相连的逻辑上紧密相连的一组字符，这些字一组字符，这些字符具有集体含义。符具有集体含义。单词：标识符，基本字，算符，界符等单词：标识符，基本字，算符，界符等例例: :源程序片断源程序片断begin var sum,first,count:real;begin var sum,first,count:real;sum:=first+countsum:=first+count* *10 10 end.end. r r0 0u u; ; ; s s

10、t tl li ia af fe e, ,r rt t: :n nm mu uu us sa ac cr ro ov v, ,n ni ig ge eb bs* *1 1t tn nu uo oc ct t+ +s si ir rf f= =: :m m. . n nd d e e 源程序在文件中的表示源程序在文件中的表示 (基本字基本字,real)(标识符标识符,first)(冒号冒号, :)(逗号逗号, ,)(标识符标识符,count)(分号分号, ;)(基本字基本字,var)(逗号逗号, ,)(标识符标识符,sum)(基本字基本字,begin)(赋值号赋值号, :=)(乘号乘号, *)(

11、加号加号, +)(标识符标识符,count)(标识符标识符,first)(标识符标识符,sum)(界符界符, .)(整数整数,10)(基本字基本字,end)词法分析后程序的图形表示词法分析后程序的图形表示空格空格换行换行字符的内部表示即字符的内部表示即ASC码码单词表示成二元式（单词的种别，单词自身值）单词表示成二元式（单词的种别，单词自身值）2.2.语法分析语法分析 (syntax analysis or parsing)v 任务任务单词符号串单词符号串(Token串串)语法分析语法分析语法短语语法短语v 识别规则：语法规则识别规则：语法规则( (描述程序结构的规则描述程序结构的规则, ,通

12、常是由通常是由递归规则表示的递归规则表示的) )注注: :语法短语又称语法单位，如语法短语又称语法单位，如“表达式表达式”、“语句语句”、“分程序分程序”、“程序程序”等等v 结果结果: :判断判断输入串是否构成一个语法上正确的程序输入串是否构成一个语法上正确的程序, ,并并生成生成语法树语法树例例: :赋值语句赋值语句 sum:=first+countsum:=first+count* *1010 赋值语句规则赋值语句规则 :=:= “:=:=” :=:= “+ +” :=:= “* *” :=:=“( (” “) )” :=:= :=:= :=:= sum赋值语句赋值语句标识符标识符:=表

13、达式表达式表达式表达式+表达式表达式标识符标识符first表达式表达式*表达式表达式标识符标识符count整数整数10语法树为语法树为:3.3.语义分析语义分析 (semantic analysis)v任务任务: :审查源程序是否有语义错误，为代审查源程序是否有语义错误，为代码生成阶段收集类型信息码生成阶段收集类型信息v类型审查（静态语义）：类型审查（静态语义）：上下文相关性上下文相关性类型匹配：每个算符是否具有语言规类型匹配：每个算符是否具有语言规范允许的运算对象范允许的运算对象类型转换类型转换例：例：program p( )var rate:real;procedure initial;p

14、osition:=initial+rate*60/*error*/*error*/*warnning*/例例 源程序：源程序：Sum:=first + count Sum:=first + count * * 10 10countcount是实型是实型,10,10是整型是整型, ,语义分析后得到新语法树为语义分析后得到新语法树为: :赋值语句赋值语句标识符标识符:=表达式表达式sum表达式表达式+表达式表达式标识符标识符first表达式表达式*表达式表达式标识符标识符count实数实数10inttoreal4.4.中间代码生成中间代码生成(intermediate code generatio

15、n)v 任务：将源程序生成一种内部表示形式，这种内部表任务：将源程序生成一种内部表示形式，这种内部表示形式叫中间代码。示形式叫中间代码。v 四元式中间代码四元式中间代码: :( (运算符，运算对象运算符，运算对象1 1，运算对象，运算对象2 2，结果，结果) )v 例如：将例如：将Sum:=first + count Sum:=first + count * * 10 10翻译成四元式翻译成四元式(1)(1)(inttoreal 10 - T1 )(inttoreal 10 - T1 )(2)(2)( (* * count T1 T2) count T1 T2)(3)(3)(+ first T

16、2 T3)(+ first T2 T3)(4)(4)(:= T3 - sum)(:= T3 - sum)5.5.代码优化代码优化 (code optimization)v 任务：对中间代码进行等价变换，以便生成更高效的任务：对中间代码进行等价变换，以便生成更高效的目标代码目标代码v 举例举例: :(1)(1) (inttoreal 10 - T1 )(inttoreal 10 - T1 )(2)(2) ( (* * count T1 T2) count T1 T2)(3)(3) (+ first T2 T3)(+ first T2 T3)(4)(4) (:= T3 - sum)(:= T3 -

17、 sum)简化后简化后: :( (* * count 10.0 T1) count 10.0 T1)(+ first T1 sum)(+ first T1 sum)6.6.目标代码生成目标代码生成 (code generation)v 任务：把中间代码变换成特定机器上的绝对指令代码任务：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码或可重定位的指令代码或汇编指令代码, ,它的工作与硬它的工作与硬件系统和指令含义有关件系统和指令含义有关. .v 例如例如: :( (* * count 10.0 T1 ) count 10.0 T1 )(+ first T1 sum)(

18、+ first T1 sum)生成汇编代码如下生成汇编代码如下: : MOV count, R2MOV count, R2MUL #10.0, R2MUL #10.0, R2MOV first, R1MOV first, R1ADD R1, R2ADD R1, R2MOV R1, sum MOV R1, sum 7.7.表格管理和出错处理表格管理和出错处理v 出错处理：编译过程中，发现源程序有错误（词法错出错处理：编译过程中，发现源程序有错误（词法错误、语法错误、语义错误），编译程序应报告错误的误、语法错误、语义错误），编译程序应报告错误的性质和出错的地点，并将错误所造成的影响限制在尽性质和出

19、错的地点，并将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分继续被编译可能小的范围内，使得源程序的其余部分继续被编译下去。这些工作称为出错处理下去。这些工作称为出错处理(error handling)。v 编译过程中源程序的各种信息被保留在种种不同的表编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作涉及到构造、查找或更新有格里，编译各阶段的工作涉及到构造、查找或更新有关的表格，因此需要有表格管理工作。关的表格，因此需要有表格管理工作。1.3 1.3 编译程序的结构编译程序的结构(components)源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序

20、语义分析程序语义分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序目标代码生成程序目标代码生成程序表格管理程序表格管理程序出错处理程序出错处理程序目标程序目标程序1.4 1.4 编译阶段的组合编译阶段的组合1.1. 分析与综合分析与综合(analysis and synthesis)(analysis and synthesis)分析阶段：词法分析、语法分析、语义分析，只分析阶段：词法分析、语法分析、语义分析，只对程序进行识别和检查，没作实质翻译对程序进行识别和检查，没作实质翻译综合阶段：中间代码的生成，代码优化，目标代综合阶段：中间代码的生成，代码优化，目标代码生成，对源程序进

21、行翻译，生成目标代码码生成，对源程序进行翻译，生成目标代码编译过程的划分：编译过程的划分：2.2. 前端与后端前端与后端 前端前端( (依赖于源语言而与依赖于源语言而与目标机无关目标机无关) )：词法分析、语法分析、语义分析和中间词法分析、语法分析、语义分析和中间代码的生成，中间代码优化代码的生成，中间代码优化; ; 后端后端( (依赖于目标机而一般不依赖源语依赖于目标机而一般不依赖源语言言) )：目标代码生成：目标代码生成; ;编译过程的实现：编译过程的实现：一个编译过程可以由一遍、两遍或多遍完成一个编译过程可以由一遍、两遍或多遍完成v遍遍(pass)(pass) : :对源程序或中间语言程序从头对源程序或中间语言程序从头到尾扫描并完成规定任务的过程。到尾扫描并完成规定任务的过程。v一遍的编译器是通过一遍扫描直接从源程一遍的编译器是通过一遍扫描直接从源程序生成出目标代码，而多遍的编译器则通序生成出目标代码，而多遍的编译器则通过多遍扫描产生目标代码。比如第一遍进过多遍扫描产生目标代码。比如第一遍进行词法分析、语法分析、中间代码生成和行词法分析、语法分析、中间代码生成和中间代码优化，而第二遍扫描则从中间代中间代码优化，而第二遍扫描则从中间代码产生目标代码码产生目标代码v影响分遍的因素：源语言结构，目标机资影响分遍的因素：源语言结构，目标机资源源1.5 1.5 编译技术和软件工