计算机网络第五版第一章.ppt

第1章 引论 1,第1章 引论,1.1 什么是编译程序 1.2 编译过程和编译程序的结构 1.3 解释程序,第1章 引论 2,1.1 什么是编译程序(compiler),从功能上看，一个编译程序就是一个语言翻译程序。它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。源语言通常是一个高级语言，如FORTRAN，C 或Pascal。目标语言通常是一个低级语言,如汇编或机器语言。编译程序的功能见下图。,第1章 引论 3,1.1 什么是编译程序(compiler),术语 编译程序的源语言(源程序) 编译程序的目标语言(目标程序),注意：所谓的源程序和目标程序的等价是什么含义-他们的功能一样。,第1章 引论 4,1.1 什么是编译程序(compiler),机器语言计算机指令系统 低级语言 语言 汇编语言符号化的指令系统 高级语言算法语言，不依赖具体机器， 面向问题,在计算机上如何执行一个高级语言程序？ 把高级语言程序翻译成机器语言程序 运行所得到的机器语言程序来求得计算结果,第1章 引论 5,1.1 什么是编译程序(compiler),源程序 翻译程序 目标程序,汇编语言程序 汇编程序 机器语言程序 计算机,高级语言程序 编译程序 连接程序,源语言 实现语言 目标语言,汇编语言 汇编程序 机器语言,高级语言 编译程序 低级语言,高级语言 编译程序 高级语言,翻译对象 翻译程序 翻译结果,第1章 引论 6,1.1 什么是编译程序(compiler),如果从计算机系统的角度看，什么是编译程序呢？我们说编译程序是一种软件，是系统软件。通常认为系统软件是居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。系统软件和具体的应用领域无关，如编译系统和操作系统等。,第1章 引论 7,1.1 什么是编译程序(compiler),来自计算机百科全书的定义 软件：计算机系统中的程序及其文档 系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。,注：最外一层为应用软件层,编译系统,第1章 引论 8,1.1 什么是编译程序(compiler),图1.2 语言处理过程,第1章 引论 9,1.1 什么是编译程序(compiler),编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。对有些高级语言甚至配置了几个不同性能的编译程序。 一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。,第1章 引论 10,1.1 什么是编译程序(compiler),编译程序的必要性：计算机是当代科学发展的重要工具，已渗入到各行各业乃至家庭生活中，所以如何让它为人类工作服务，就必须建立人与计算机之间的信息交流。 但计算机只认识由0和1构成的机器语言，并不认识C、C+、Java等高级程序设计语言，每台计算机都有自己独特的指令系统，即机器语言，最早的程序就是用8进制和16进制的机器语言书写的。,第1章 引论 11,1.1 什么是编译程序(compiler),例如计算园面积 C程序： void circle() int r; float s; scanf(“%d”, ,Pascal程序： procedure circle() var r:integer; s:real; read(r); s:=3.1416*r*r; write(s); end,第1章 引论 12,1.2 编译过程和编译程序的结构,编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。 编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。 编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。事实上，某些阶段可能组合在一起。,第1章 引论 13,1.2.1编译过程概述,图1.3编译的各个阶段,编译过程划分成六个阶段：词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成 另外两个重要的工作： 表格管理 出错处理,第1章 引论 14,1.2.1编译过程概述,编译过程 词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成,翻译过程 识别出句子中的一个个单词 分析句子的语法结构 根据句子的含义进行分析 写出初步的翻译 对译文进行修饰 写出最后译文,第1章 引论 15,1词法分析,任务 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。 单词 单词是高级语言中有意义的最小语法单位，它由字符组成。比如标识符用于表示变量名,是由字母字符开头，后跟字母、数字字符的字符序列组成的一种单词。保留字(关键字或基本字)也是一种单词，此外还有算符，界符等等。,第1章 引论 16,1词法分析,例如某源程序片断如下： begin var sum, first, count: real; sum=first+count*10 end.,1. 保留字begin 2. 保留字var 3. 标识符sum 4. 逗号， 5. 标识符first 6. 逗号， 7. 标识符count 8. 冒号： 9. 保留字real 10. 分号；,11. 标识符sum 12. 赋值号= 13. 标识符first 14. 加号+ 15. 标识符count 16. 乘号* 17. 整数10 18. 保留字end 19. 界符,这些单词间的空格在词法分析阶段都被滤掉了。词法分析阶段将构成这段程序的字符组成了如下19个单词序列：,第1章 引论 17,1词法分析,识别右边程序中的单词 基本字：void int float 标识符：a,b,c,d,x,y,jisuan 整常数：50 运算符：，*， 界限符： ; ,(),void jisuan() int y,c,d; float x,a,b; x=a+b*50; y=c+)d*(x+b; ,第1章 引论 18,1词法分析,有关的英文 词法分析-lexical analysis 或者scanning 单词-token 保留字-reserved word 标识符 -identifier(user-defined name),第1章 引论 19,2语法分析,任务： 在词法分析的基础上，根据语言的语法规则把单词符号组成各类的语法单位：短语、子句、语句、过程、程序。 语法规则 语言的规则，又称为文法：规定单词如何构成短语、语句、过程和程序。 语法规则的表示： BNF：A:=B|C,第1章 引论 20,2语法分析,语法分析是编译过程的第二个阶段。语法分析的任务是在词法分析的基础上将单词序列分解成各类语法短语，如“程序”、“语句”、“表达式“等等。一般这种语法短语，也称语法单位可表示成语法树，比如上述程序段中的单词序列： id1=id2+id3*10 经语法分析得知其是PASCAL语言的“赋值语句”，表示成如图1.4所示的语法树,第1章 引论 21,2语法分析,图1.4 id1=id2+id3*10语法树,第1章 引论 22,2语法分析,语法分析的功能是进行层次分析，把源程序的单词序列组成语法短语(表示成语法树)。依据的是语法规则。Pascal语言的赋值语句的规则为： :=“:=” :=“+” :=“* ” :=“(”“)” :=id :=n 单词序列id1 = id2 + id3 * 10之所以能表示成图1.4的语法树，依据的是赋值语句和表达式的定义规则。,第1章 引论 23,2语法分析,第1章 引论 24,3语义分析,任务 审查源程序有无语义错误。 工作 完成静态语义审查和处理 上下文相关性审查 类型匹配审查 类型转换,第1章 引论 25,3语义分析,源程序中有些语法成分，按照语法规则去判断，它是正确的，但它不符合语义规则，比如： 使用了没有声明的变量； 给一个过程名赋值； 调用函数时参数类型不合适或者参加运算的两个变量类型不匹配等等。 比如下边的程序片段： int arr2,c; c = arr1 * 10 ; 其中的赋值语句是符合语法规则的，但是因为没有声明变量arr1，而存在语义错。,第1章 引论 26,3语义分析,请你说出error1和error2分别违背了什么语义规则，warning呢？,Program p(input,output); Var rate:real; procedure initial; position := initial + rate * 60 /* error1 */ /* error2 */ /* warning1 */;,Program p(input,output); Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60 ,第1章 引论 27,3语义分析,某些语言规定运算对象可被强制。 那么当二目运算施于一个整型量和一个实型量时，编译程序应将整型量自动转换成实型量而不能认为是源程序的错误，或者给出警告信息后将整型量自动转换成实型量。,第1章 引论 28,3语义分析,假如在赋值语句sum=first+count*10中，算符*的两个运算对象分别是count和10,而count是实型变量，10是整型量.语义分析阶段进行类型审查之后，将整型量提升为实型量.在语法分析所得到的分析树上增加一个一目算符结点，这个结点的名称为inttoreal，表示进行将整型量变成实型量的语义处理。,图1.6 插入语义处理结点的树,第1章 引论 29,4中间代码生成,任务 对语法分析识别出的几类语法范畴，分析其含义，进行初步翻译，产生介于源代码和目标代码之间的一种代码。 中间代码形式 所谓“中间代码“是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。 四元式，三元式，逆波兰式,第1章 引论 30,4中间代码生成,很多编译程序采用了一种近似“三地址指令”的“四元式”中间代码，这种四元式的形式为： (运算符，运算对象1，运算对象2，结果) 例如： id1:= id2 + id3 * 60 (1) (inttoreal, 60 - t1 ) (2) (* , id3 t1 t2 ) (3) (+ , id2 t2 t3 ) (4) (:= , t3 - id1 ),第1章 引论 31,4中间代码生成,四元式(运算符，运算对象1，运算对象2，结果)常写成赋值语句的形式(结果=运算对象1 运算符 运算对象2)，比如c语言的源程序a = b * c + b * d 的四元式序列为 (1) t1 = b * c (2) t2 = b * d (3) t3 = t1 + t2 (4) a = t3,第1章 引论 32,5代码优化,任务 对前面产生的中间代码进行加工变换，以期在最优阶段能产生更高效的目标代码 原则：等价变换 主要方面：公共子表达式的提取，合并已知量，删除无用语句，循环优化等。,第1章 引论 33,5代码优化,id1:= id2 + id3 * 60 (1) (inttoreal 60 - t1 ) (2) ( * id3 t1 t2 ) (3) ( + id2 t2 t3 ) (4) ( := t3 - id1 ) 变换 （1） ( * id3 60.0 t1 ) ( 2）（ + id2 t1 id1 ),第1章 引论 34,5代码优化,t1 = b* c t1 = b* c t2 = t1+ 0 t2 = t1 + t1 t3 = b* c a = t2 t4 = t2 + t3 a = t4,第1章 引论 35,5代码优化,k=1; 10 If k=100 then m= i+10*k; n= j+10*k; k+; goto 10; ,k=1;m=i;n=j; 10 If k=100 then m= m+10; n= n+10; k+; goto 10; ,第1章 引论 36,5代码优化,代码优化工作会降低编译程序的编译速度。 因此编译优化阶段常常作为可选择阶段。 编译程序具有控制机制以允许用户在编译速度和目标代码的质量间进行权衡。,第1章 引论 37,6目标代码生成,任务：把经过优化的中间代码转换成特定机器上的低级语言代码。 目标代码的形式 绝对指令代码：可立即执行的代码 汇编指令代码：汇编语言程序，需要通过汇编程序汇编后才能运行。 可重定位指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码。,第1章 引论 38,6目标代码生成,第一条指令将id3的内容送至寄存器R2，第二条指令将其与实常数60.0相乘，这里用#表明60.0处理为常数，第三条指令将id2移至寄存器R1，第四条指令加上前面计算出的R2中的值，第五条指令将寄存器R1的值移到id1的地址中。,mov id3,R2 mul #60.0,R2 mov id2,R1 add R2,R1 mov R1,id1,第1章 引论 39,编译过程的阶段划分,编译过程的阶段划分是一种典型的处理模式，事实上并非所有的编译程序都包括这样几个阶段。 有些编译程序并不要中间代码，即不存在中间代码生成阶段； 有些编译程序不进行优化，优化阶段即可省去; 有些最简单的编译程序只有词法分析，语法分析，语义分析和目标代码生成。,第1章 引论 40,1.2.2编译程序的结构,图1.10编译程序的结构框图,第1章 引论 41,1.2.2编译程序的结构,编译程序的另外两个重要的工作是表格管理和出错处理.他们与上述六个阶段都有联系。 表格管理：编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作； 出错处理：如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。,第1章 引论 42,表格与表格管理,表格作用 用来记录源程序的各种信息以及编译过程中的各种状态。 与编译前三阶段有关的表格 符号表，常数表，标号表，分程序入口表，中间代码表,第1章 引论 43,1）符号表,符号表：用来登记源程序中的常量名，变量名，数组名，过程名等，记录它们的性质、定义和应用情况。,第1章 引论 44,（2）常量表和标号表,常量表,标号表,（登记各类常量值）,（登记标号的定义与应用）,第1章 引论 45,3）入口名表,作用：登记过程的层号，分程序符号表入口等,第1章 引论 46,出错处理,任务：如果源程序有错误，编译程序应设法发现错误，并报告给客户。 错误类型： 语法错误：在词法分析和语法分析阶段检查出来。 语义错误：一般在语义分析阶段检测。,第1章 引论 47,1.2.3编译阶段的组合,编译阶段也常常划分为两大步骤，分析步骤和综合步骤 分析步骤是指对源程序的分析 线性分析(词法分析或扫描) 层次分析(语法分析) 语义分析 综合步骤是指后端的工作，为目标程序的生成而进行的综合。,第1章 引论 48,1.2.3编译阶段的组合 几个基本定义,编译的前端（front end）前端的工作主要依赖于源语言而与目标机无关,包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作, 即中间代码优化也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。 编译的后端（back end）后端工作依赖于目标机而一般不依赖源语言.后端工作包括目标代码生成和目标代码优化，以及相关出错处理和符号表操作。,第1章 引论 49,1.2.3编译阶段的组合,遍（趟pass ）从头到尾扫描源程序（各种形式）。每一遍扫视可完成上述一个阶段或多个阶段的工作。 例如一遍可以只完成词法分析工作； 一遍完成词法分析和语法分析工作； 甚至一遍完成整个编译工作。 对于多遍的编译程序，第一遍的输入是用户书写的源程序，最后一遍的输出是目标语言程序，其余是上一遍的输出为下一遍的输入。,第1章 引论 50,1.2.3编译阶段的组合,编译的几个阶段的工作究竟应该怎样组合？ 编译程序究竟分成几遍：参考的因素主要是源语言和机器(目标机)的特征。 比如源语言的结构直接影响编译的遍的划分； 有些语言，允许名字的说明出现在名字的使用之后，那么在看到名字之前是不便为包含该名字的表达式生成代码的，这种语言的编译程序至少分成两遍才容易生成代码。 另外机器的情况，即编译程序工作的环境也影响编译程序的遍数的划分。 遍数对编译的影响：遍数多一点，整个编译程序的逻辑结构可能清晰些，但遍数多即意味着增加读写中间文件的次数，势必消耗较多时间，一般会比一遍的编译要慢。,第1章 引论 51,1.3解释程序和一些软件工具 1.3.1解释程序,解释程序：接受某个语言的程序并立即运行这个源程序。 特点： 不生成目标代码,第1章 引论 52,编译程序与解释程序的区别,编译：是按源程序的实际输入顺序，处理程序语句，得到可执行的目标程序。 解释：是按源语言的定义边解释边执行。 解释程序的优点：交互方便，节省空间。 解释程序的缺点：效率低。因对源程序的循环语句部分要反复解释执行。 共同点：都需进行词法、语法、语义分析。 可比喻为： 编译是笔译（产生目标程序） 解释是口译（不产生目标程序）,第1章 引论 53,编译程序与解释程序的区别,从存储组织来看： 编译程序，存储区一般要有源程序缓冲区，目标代码缓冲区，各种表格等等。在运行阶段，存储区只有目标代码和数据区了。 解释程序，在它工作的自始至终，存储区中要有源程序，名字表，标号表等表格，输入输出缓冲区以及数据区等等.,第1章 引论 54,编译阶段和运行阶段存储结构,编译时 运行时,名字表,目标代码缓冲区,编译用源程序中 间表示各种表格,目标代码区,数据区,源程序缓冲区,第1章 引论 55,解释系统存储结构,解释系统,源程序,工作单元 名字表,标号表,缓冲区 (输入输出),栈区,第1章 引论 56,第1章 小结,什么是编译程序 编译过程和编译程序的结构 本章没有难以理解的内容，重点对编译程序的功能