编译原理(1).ppt

《编译原理(1).ppt》由会员分享，可在线阅读，更多相关《编译原理(1).ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 编译原理（编译原理（1 1）山东师范大学信息科学与工程学院山东师范大学信息科学与工程学院山东师范大学信息科学与工程学院山东师范大学信息科学与工程学院课程的性质与任务课程的性质与任务 本课程地位属于计算机科学与技术专业的一门重要的专业必修课。本课程的学习有助于对语言的执行系统、程序语言的理解。通过本课程的学习，要掌握编译程序的一般构造原理，包括语言基础知识、词法分析程序设计原理和构造方法。各种语法分析技术和中间代码生成符号表的构造、代码优化、并行编译技术常识及运行时存储空间的组织等基本方法和主要实现技术。课程的地位课程的地位语言的发展机器语言汇编语言 高级语言查询语言、标注语言第第1章章 编译

2、程序概论编译程序概论1.1 什么是编译程序1.2 编译过程概述1.3 编译程序的结构1.4 编译阶段的组合1.5 编译技术和软件工具参考书1.1什么是编译程序什么是编译程序1.1.1 语言处理程序语言处理程序 语言处理程序语言处理程序：把较高级语言编写的程序语义等价地变换成较低级语言程序的程序。汇编程序 语言处理程序 解释程序 编译程序源程序目标程序语言处理程序（0）语言的执行方式n解释方式（Basic)口译n编译方式(C,pascal)笔译 (1)汇编程序汇编程序 汇编程序汇编程序：把用汇编语言编写的程序翻译成机器语言的程序。汇编语言汇编语言是为特定的计算机或计算机系统设计的面向机器的语言。

3、如：8086/8088 PC、Z-80、VAX汇编语言 汇编的过程汇编的过程就是对汇编指令逐行进行处理，最终得到机器代码的过程。汇编语言程序可重定位的机器语言程序汇编程序(2)解释程序解释程序 解释程序解释程序：对用高级语言编写的程序进行逐句分析并立即得到结果。解释程序按源程序中语句的动态顺序逐句进行分析翻译，并立即予以执行，它不产生目标代码。BASIC APL LISP Java等语言就是采用解释方法实现的。计算结果解释程序源程序初始数据高级语言解释系统高级语言解释系统(interpreter)功能 让计算机执行高级语言（basic,lisp,prolog)与编译程序的不同 1）不生成目标代

4、码 2）能支持交互环境 （同增量式编译系统）源 程 序 初始数据 解释程序计算结果解释系统解释系统直接对源程序中的语句进行分析，执行其隐含的操作。如：b:=2 ;a:=b+2 ;编译程序 write a ;解释程序直接将4的值输出（显示）Int 2St bLd badd 2St a生成代码(3)编译程序编译程序 编译程序编译程序：把用高级语言编写的源程序翻译成等价的低级语言(称作目标语言)程序。编译系统是编译程序和运行系统的合称。高级语言源程序低级语言目标程序编译程序编译程序（续）编译程序（续）一个编译程序把一个高级语言源程序翻译成目标程序的工作可分为前后衔接的六个阶段：词法分析、语法分析、语

5、义分析、中间代码生成、代码优化及目标代码生成。大多数高级语言是采用编译的方法实现的。如 PASCAL、FORTRAN、ADA、C、C+、PL/1、ALGOL 60、ALGOL 68,等等。1.1.2 什么是编译程序什么是编译程序(compiler)编译程序是现代计算机系统的基本组成部分.从功能上看，一个编译程序就是一个语言翻译程序,它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序.编译程序的功能编译程序的功能术语术语编译程序的源语言(源程序)编译程序的目标语言(目标程序)编译程序的实现语言S OI 高级语言书写的程序 编译程序低级语言程序S TI 软件软件：计算

6、机系统中的程序及其文档 系统软件系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。他和具体的应用领域无关，如编译系统和操作系统等。操作系统编译系统裸机 语言处理系统语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。软件语言软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言 预处理器编译器汇编器装配连接编辑骨架程序 源程序 目标汇编程序 可重定位机器代码 绝对机器码可重定位目标文件库高级语言程序的处理过程高级语言程序的处理过程语言转(变）换系统C+编译器C+CJavaBytecodeJava编译器

7、术语术语 编译程序编译程序(compiler)编译程序的源语言编译程序的源语言(源程序源程序)(source language)(source program)编译程序的目标语言编译程序的目标语言(目标程序目标程序)(object or target language)(object or target program)编译程序的实现语言编译程序的实现语言(implementation language)语言处理程序语言处理程序(language processor)语言转（变）换语言转（变）换(language transformation)1.2 编译过程概述编译过程概述编译逻辑过程词法分

8、析语法分析语义分析中间代码生成代码优化目标代码生成 1.2.1 词法分析词法分析 这个阶段的任务是从左至右、从上到下一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。var sum,first,count:real;sum:=first+count*10 单词类型单词类型 单词值单词值 标识符1(id1)sum 算符(赋值):=标识符2(id2)first 算符(加)+标识符3(id3)count 算符(乘)*整数 10 分号 ；又如一个C源程序片断：int a;a=a+2;词法分析后可能返回:单词类型单词类型单词值单词值 保留字 int 标识符(变量名)

9、a 界符 ;标识符(变量名)a 算符(赋值)=标识符(变量名)a 算符(加)+整数 2 界符 ；有关术语有关术语 词法分析词法分析-从左到右读字符流的源程序、识别（拼）单词。单词单词-具有独立意义的基本语法单位。保留字保留字-具有特殊规定的意义，不允许用户将它们作为别用，是用户定义标识符的禁区。标识符标识符-用来表示程序、过程、函数、类型、常量和变量等名称的符号。1.2.2语法分析语法分析 在词法分析的基础上，根据语言的语法规则（文法规则），把单词符号串分解成各类语法单位，如“短语”、“句子”、“程序段”和“程序”。通过语法分解，确定整个输入串是否构成一个语法上正确的程序。例:符号串 X+0.

10、168*Y,经语法分析就可识别出这个字符串属于算术表达式。Y:=X+0.168*Y;语法分析所依循的是语言的语法规则，用产生式描述。sum:=first+count*10规则规则:=“:=”:=“+”:=“*”:=“(”“)”:=:=:=语法分析器读入单词，将它们组合成按产生式规定的各类语法单位。赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*id1:=id2+id3*N:=+N 10*id1 sumid2 firstid3 count术语术语 语法语法：定义语言各语法成分的形式或结构。语法分析语法分析：依据依据源程序的语法规则语法规则把源程序的单词序列组成语法短语(表示成

11、语法树)。语法树语法树(推导树推导树)：表示句型推导（或归约）的树型结构。语法树有助于理解一个句子语法结构的层次。1.2.3 语义分析语义分析语义审查(静态语义)上下文相关性类型匹配类型转换例:Program p();Var rate:real;procedure initial;“position:=initial +rate*60/*error*/*error*/*warning*/;语义分析的一个重要内容是类型检查,对表达式及语句中的各语法成分作类型检查和分析.如:Var count:real;Var first:real;Var sum:real;sum:=first +count*1

12、0 语义分析的一个重要内容是类型检查，上例语义分析的一个重要内容是类型检查，上例中进行类型检查之后增加了内部节点中进行类型检查之后增加了内部节点inttoreal.10:=+*Id1 sumId2 firstId3 countinttoreal术语术语 语法语法：用来定义语言中各语法成份的形式或结构。语义语义：用来规格各语法成份的含义和功能，即规定它们的属性或在执行时应进行的运算或操作。语义分析语义分析：检查源程序是否包含语义错误，并搜集类型，供后面的代码生成阶段使用，只有语法和语义正确的源程序才可被翻译成目标代码。语义分析程序需要进行频繁的造表和查表工作。语义分析之后生成一种介于源语言和目标

13、语言之间的中间语言代码。中间代码有多种形式：三元式、四元式、逆波兰表示、树型结构例：a:=b*c 三元式：逆波兰表示式：abc*:=(1)(*,b,c)树：:=(2)(:=,a,(1)a *四元式：b c（*,b,c,a)1.2.4 中间代码生成中间代码生成id1:=id2+id3*10 因运算需要，需设置临时变量t1,t2,t3来存放中间运算结果。四元式 (算符 第一运算量 第二运算量 运算结果 )(1)(inttoreal,10,-,t1)(2)(*,id3,t1,t2)(3)(+,id2,t2,t3)(4)(:=,t3,-,id1)中间代码的几种形式中间代码的几种形式逆波兰表示：运算符在

14、其运算量之后的表达式。三元式：（OP，ARG1，ARG2）四元式：（OP，ARG1，ARG2，RESULT）树：根结点OP，左子树ARG1，右子树ARG2。1.2.5 代码优化代码优化对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和省空间）的目标代码，代码优化代码优化id1:=id2+id3*10(1)(inttoreal10-t1)(2)(*id3t1t2)(3)(+id2t2t3)(4)(:=t3-id1)变换变换 （1）(*id310.0t1)(2）（+id2 t1id1)代码优化代码优化t1=b*c t1=b*c t2=t1+0 t2=t1+t1t3=b*c

15、 a=t2t4=t2+t3a=t4在本例中，b、c的值没有改变，故t1=t3，由第二个表达式知道t2=t1。1.2.6 目标代码生成目标代码生成 将前阶段产生的中间代码翻译为机器语言或汇编语言形式的目标程序。目标程序总是按某一具体计算机的机器语言或汇编语言来产生的。目标代码生成目标代码生成(*,id310.0t1)(+,id2t1id1)movfid3,R2mulf#10.0,R2movfid2,R1addfR2,R1movfR1,id11.2.7 符号表管理符号表管理记录源程序中使用的名字收集每个名字的各种属性信息类型、作用域、分配存储信息Const1常量值：35Var1变量类型：实层次：2

16、 在编译过程中，源程序中的标识符及其各种属性都要记录在符号表中，这些属性可以提供标识符的存储分配信息、类型信息、作用域信息等等。对于过程标识符，还要有参数信息，包括参数的个数和类型、实参和形参的结合方式等等。符号表是一种含记录的数据结构，通常一个标识符在符号表中占一个记录，记录中除了标识符的名字域之外，还有记录该标识符属性的域。符号表结构符号表结构名字符号属性1.2.8 出错处理出错处理 编译的每一个阶段都会发现源程序的错误，在发现错误之后，一般要对其有一定的处理措施，因而编译还可继续执行，不会一有错误就停止编译工作。出错处理出错处理(error handling)(error reporti

17、ng and error recovery)在词法词法分析中，能发现单词拼写错误。在语法分析语法分析中，检查单词串是否符合语法的结构规则。在语义分析中，编译程序进一步查出语法上虽正确但含有无意义的操作部分，如两个标识符相加，一个是数组名，一个是过程名，虽然语法上允许，但语义上不允许，各种错误，都应在相应的阶段进行处理。出错处理出错处理(error handling)(error reporting and error recovery)检查错误报告出错信息（错误种类及位置）校错及排错恢复编译工作1.3 编译程序的结构编译程序的结构(components)词法分析程序语法分析程序语义分析程序中间

18、代码生成程序代码优化程序目标代码生成程序符号表管理程序出错处理程序出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理1.4 编译阶段的组合编译阶段的组合 分析，综合(synthesis)源程序的分析线性分析层次分析语义分析目标程序的综合 编译的前端（front end）:这些阶段以来于源语言、与目标机无关。编译的后端（back end）：依赖于目标机器的阶段。遍（趟）遍（趟）从头到尾扫描源程序（各种形式）一遍遍(pass)编译阶段和运行阶段存储结构编译阶段和运行阶段存储结构 编译时 运行时 名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区

19、数据区源程序缓冲区1.5 编译技术和软件工具编译技术和软件工具编译程序实现方式 手工机器语言汇编系统程序设计语言自动构造工具lex yacc gccS OI 1.5.1 编译程序的发展编译程序的发展Human-orientedlanguageComputer-orientedlanguage计算模式，语言范式语言应用领域编译程序冯诺曼机体系结构并行体系结构嵌入系统 编译程序的发展编译程序的发展语言范型(paradigms)命令式(imperative language)应用式(applicative)基于规则的（rule-based）面向对象的（object-oriented）编译程序执行环境

20、批处理交互环境嵌入系统环境(1)语言范型（支持的计算模式）语言范型（支持的计算模式）命令式：程序特点：语言执行的解释：编译技术发展快：语句1；改变机器状态 系统语言语句2；内存 自动化生成技术语句3；各种寄存器 的内容 外存 与万诺曼机的 体系结构一般 应用式（函数式）：程序特点：Function n(funetion2(funetion1(data)程序执行：执行一个个函数施用在数据上的变换最终得到的结果编译：语法分析容易；语义处理复杂；基于规则的语言（prolog,yacc)：程序特点：使能条件1 动作1 使能条件2 动作2 使能条件3 动作3 面向对象语言：抽象数据类型，继承机制编译：动

21、态绑定；(2)执行环境执行环境批处理环境：将源程序作为整体处理 排除程序错误不能依靠用户的外部帮助交互环境：解释 增量式编译嵌入式系统环境：交叉编译分布并行环境：并行编译程序创建和测试环境：独立编译 编译和调试同时设计考虑 1.5.2 编译技术和软件工具编译技术和软件工具结构化编辑器程序调试工具程序测试工具 静态分析 动态分析 度量工具 结构度量 模块接口复杂度 c分析工具(source insight)高级语言转换工具广泛的语言领域 数据库系统查询 脚本语言 置标语言(SGML.HTML.XML)1.5.3 研究领域研究领域并行编译技术交叉编译技术自展编译技术(1)并行化编译技术并行化编译技

22、术目的：提高并行计算机体系结构的性能。超大规模计算的日益增长的需求 高性能计算机 并行软件并行体系结构单机速度并行体系结构途径1途径2 并行体系结构 编译技术支持 串行程序并行化编译技术支持 并行程序设计语言编译 依赖于目标机的优化（低层）性能发挥 并行算法复杂，难掌握，难编程 开发并行 软件的困难 并行程序的不确定行为，难调试，验证设计新的并行算法 修改已有串行程序尽量（直接用并行程序 并行化（研究算法和设计语言和并行程 应用的人同时工作）序库实现。).HPF.Occom.PVM 途径12嵌入式嵌入式(2)交叉编译器交叉编译器由于目标机指令系统与宿主机的指令系统不同，编译由于目标机指令系统与

23、宿主机的指令系统不同，编译时将应用程序的源程序在宿主机上生成目标机代码，时将应用程序的源程序在宿主机上生成目标机代码，称为交叉编译。称为交叉编译。SOIOAB(3)自展编译技术自展编译技术 用被编译的语言来书写该语言自身的编译程序。第第1章章 小结小结 内容 1 什么是编译程序 2 编译过程和编译程序的结构 3 为什么要学习编译程序 本章重点对编译程序的功能和结构做了综合概述,要求学生了解编译程序各个成分在编译阶段的逻辑关系以及它们怎样作为一个整体完成编译任务的。参考书参考书 Compilers:Principles,Techniques,and Tools/编 译 原 理 技 术 与 工 具（英 文 版）ALFRED V.AHO,RAVISETHI,JEFFREY D.ULLMAN.程序设计语言编译原理 陈火旺，国防工业出版社，2000编译原理及编译程序构造高仲仪、金茂忠，北京航空学院出版社，1990.12 参考书参考书编译原理胡伦骏、徐兰芳、刘建农编，电子工业出版社.2002年编译程序原理与技术李赣生、王华民编著，清华大学出版社编译原理技术陈意云，中国科技大学出版社编译原理习题精选陈意云、张昱著，中国科技大学出版社 习题习题1.什么是编译程序？2.简要介绍编译过程的六个阶段，并给出编译程序的结构。