《编译原理概述课件.ppt》由会员分享，可在线阅读，更多相关《编译原理概述课件.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理概述第1页，此课件共63页哦计算机专业的专业基础课专业基础课，主要解决高级语言的运行问题是软件技术的基础计算机专业学生必修的一门主干课程是本学科研究生入学考试的课程之一课程概述课程概述1 1：课程地位：课程地位第2页，此课件共63页哦本课程介绍如何将高级程序设计语言变换成计算机硬件所能识别的机器语言。编译原理介绍编译程序的原理编译程序的原理，如何编程使高到低。其理论基础坚实，其形式化系统不仅应用于编译技术，还大量应用于人工智能、多媒体技术及数据库等领域。例如：翻译风，一个翻译的过程课程概述课程概述2 2：编译的作用：编译的作用第3页，此课件共63页哦掌握编译理论基础理论基础和形式化系统
2、形式化系统（过程、思想，对其思想用数学格式描述）了解编译的全过程及其具体实现方法课程概述课程概述3 3：学习任务：学习任务第4页，此课件共63页哦认真听课，理论书中基本概念、基本原理与基本算法（枯燥，原理性强，数学性强，符号多，自己看书比较麻烦）弄懂书中例题和认真对待课后习题在看书或理解例题时，一定要划出相应的细节变化过程，通过画图来加深理解在理解基础上记忆（算法原理概念都是经典内容）课程概述课程概述4 4：学习方法：学习方法第5页，此课件共63页哦上课认真听讲，独立完成作业成绩考核：平时成绩占30（出勤、课堂表现、作业）期末考试占70（笔试）课程概述课程概述5 5：学习要求：学习要求第6页，
3、此课件共63页哦编译原理编译原理知识结构知识结构第7页，此课件共63页哦1.1.掌握编译程序中所涉及的有关名词术语掌握编译程序中所涉及的有关名词术语2.2.理解编译程序总的框架，明确编译程序工作的理解编译程序总的框架，明确编译程序工作的基本过程及各阶段的基本任务基本过程及各阶段的基本任务教学目标教学目标第第1 1章章编译概述编译概述第8页，此课件共63页哦自然语言人与人交流的一种工具人与计算机如何交流？通过程序设计语言将问题编写成程序，计算机按程序的计算步骤计算出结果程序设计语言程序设计语言第9页，此课件共63页哦低级语言低级语言（Low level Language)字位码、机器语言、汇编语
4、言字位码、机器语言、汇编语言特特点点：与与特特定定的的机机器器有有关关，功功效效高高，但但使使用用复复杂杂、繁繁琐、费时、易出错琐、费时、易出错高级语言高级语言 -Fortran、Pascal、C 语言等语言等特点：不依赖具体机器，移植性好、对用户要求低、易使特点：不依赖具体机器，移植性好、对用户要求低、易使用、易维护等。用、易维护等。程序设计语言程序设计语言第10页，此课件共63页哦计算机的核心部件只能读懂自己的指令系统，不能执行非机器语言编写的程序计算机如何执行高级语言？把高级语言程序翻译翻译成机器语言程序运行运行所得机器语言程序求得计算结果 程序设计语言程序设计语言第11页，此课件共63
5、页哦源程序源程序 用汇编语言或高级语言编写的程序称为源程序目标程序目标程序 用目标语言所表示的程序 目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。翻译程序翻译程序 将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。第12页，此课件共63页哦源程序、翻译程序、目标程序源程序、翻译程序、目标程序 三者关系：三者关系：源程序翻译程序目标程序SOURCE PROGRAMTRANSLATER OBJECT PROGRAM即源程序是翻译程序的输入，目标程序是翻译
6、程序的输出即源程序是翻译程序的输入，目标程序是翻译程序的输出S OI第13页，此课件共63页哦汇编程序汇编程序 若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过程称为“汇编”(Assemble）编译程序编译程序 若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称“编译”（Compile)汇编程序与编译程序都是翻译程序翻译程序，主要区别是加工对象的不同。由于汇编语言格式简单，常与机器语言之间有一一对应的关系。汇编程序所要做的翻译工作比编译程序简单的多。第14页，此课件共63页哦源程序的编译和运行源程序的编译和运行编译或汇编阶段编
7、译或汇编阶段源程序目标程序编译程序编译程序或汇编程序或汇编程序输出数据目标程序目标程序+运行子程序运行子程序输入数据运行阶段运行阶段第15页，此课件共63页哦n编译程序是现代计算机系统的基本组成部分n从功能上看，一个编译程序就是一个语言翻译程序语言翻译程序n它是把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价等价的程序 编译程序编译程序第16页，此课件共63页哦n两阶段转换：编译运行（compilerun）术语术语编译程序的源语言(源程序)编译程序的目标语言(目标程序)源程序编译程序目标代码编译时初始数据运行子程序目标代码计算结果运行时(*.C/*.PAS)(*.OBJ
8、/*.EXE)编译的过程转换编译的过程转换第17页，此课件共63页哦n三阶段转换：编译汇编运行源程序编译程序汇编语言编译时目标代码汇编程序汇编时初始数据运行子程序目标代码计算结果运行时.exe.obj 编译的过程转换编译的过程转换第18页，此课件共63页哦高级语言程序的处理过程第19页，此课件共63页哦n以源程序作为输入，不产生目标程序，一边解释一边执行不产生目标程序，每次执行源程序，都必须解释一次不产生目标程序，每次执行源程序，都必须解释一次 解释程序解释程序 特点：与编译系统比较，解释系统较简单、可移植性好，易于查错，但速度慢输出数据解释程序解释程序输入数据源程序第20页，此课件共63页哦
9、编译编译 （笔译，程序到程序）由高级语言转换为低级语言，如C，Pascal语言解释解释 （口译，语句到语句）接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。不产生目标程序不产生目标程序，直观简单，但效率低，如Basic语言n翻译：能把某种语言的源程序，在不改变语义不改变语义的条件下，转换成另一种语言程序目标语言程序。n两种实现方式：程序设计语言的转换程序设计语言的转换第21页，此课件共63页哦编译程序是源程序的一个转换系统转换系统解释程序是源程序的一个执行系统执行系统两者在实现技术上并无很大差别，都要完成词法分析、语法分析、语义分析等工作。编译
10、和解释编译和解释第22页，此课件共63页哦1.2 1.2 编译过程和编译程序的结构编译过程和编译程序的结构翻译和编译工作的比较翻译和编译工作的比较翻译外文编译程序分析识别单词分析句子根据语义进行初步翻译词法分析语法分析语义分析、生成中间代码综合修辞加工写出译文代码优化目标代码生成第23页，此课件共63页哦编译程序工作时，先分析，后综合分析分析：指词法分析和语法分析；综合：综合：指代码优化，存储分配和代码生成。为完成上述分析综合任务，编译程序采用对源程序进行一次或多次扫描的办法。如：第一遍扫描做词法分析；第二遍扫描做语法分析；第三遍扫描做代码优化和存储分配；第四遍扫描做代码生成。编译过程编译过程
11、第24页，此课件共63页哦 从输入源程序开始到输出目标程序为止的整个过程可分为六个阶段：词法分析语法分析语义分析中间代码生成代码优化目标代码生成对源程序结构的分析 编译过程编译过程第25页，此课件共63页哦任务：任务：根据根据词法规则词法规则分析和识别单词单词一、词法分析一、词法分析单词单词：是语言的基本语法单位 保留字保留字（如:if、else、while）标识符标识符（如:max、min、str）常数常数 （如:12、6.8、a）算符、界符算符、界符（如:+、-、*、/、;、（、）字符序列字符序列编码形式编码形式第26页，此课件共63页哦词法分析程序的结果词法分析程序的结果-二元式二元式y
12、=x+r*6单词值单词类别y标识符=算符（赋值）x标识符+算符（加号）r标识符*算符（乘号）6常数第27页，此课件共63页哦Void jisuan（）（）int y,c,d;float x,a,b;x=a+b*50;y=c+)d*(x+b;请识别上段代码中的单词第28页，此课件共63页哦词法分析(lexical analysis or scanning)-The stream of characters making up a source program is read from left to right and grouped into tokens,which are sequence
13、s of characters that have a collective meaning.单词-token保留字-reserved word标识符-identifier(user-defined name)相关术语相关术语第29页，此课件共63页哦任务：任务：根据根据语法规则语法规则（即语言的文法），分析并识别出各（即语言的文法），分析并识别出各种种语法成分语法成分（如表达式、语句、函数等），并进行（如表达式、语句、函数等），并进行语法语法正确性检查正确性检查。通过语法分解，确定整个输入串是否构成语法上正确的句子、程序等语法规则的表示：语法规则：规定单词如何构成短语、语句、过程、程序A:=
14、B|CBNF表示二、语法分析（编译的核心）二、语法分析（编译的核心）第30页，此课件共63页哦 A:=V:=E E:=T|E+T T:=F|T*F F:=V|(E)|C V:=标识符 C:=常数递递归归定定义义q描述程序结构的规则q赋值语句语法分析的依据语法分析的依据语法规则语法规则第31页，此课件共63页哦赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*Id1Id2Id360position:=initial+rate*60id1:=id2+id3*60第32页，此课件共63页哦id1:=id2+id3*60:=+N 60*id1 Positionid2 initiali
15、d3 rate第33页，此课件共63页哦n推导（derive)、归约(reduce)推导：从文法的开始符号开始，按照语法规则，每次选择某规则右部的一个候选式取代左部，直至识别了语句或者找到错误为止。其过程可用语法树描述归约：按照语法规则，每次选择某规则左部取代右部的一个候选式注：语法词法规则语法规则语法分析的方法语法分析的方法第34页，此课件共63页哦三、语义分析及中间代码生成三、语义分析及中间代码生成任务：任务：依据语义规则对识别出的各种语法成依据语义规则对识别出的各种语法成分析其含义分析其含义，并进行初步翻译，生成并进行初步翻译，生成中间代码中间代码。静态：静态：分析语法成份的含义，进行语
16、义上的正确性检查分析语法成份的含义，进行语义上的正确性检查动态：动态：根据相应语义，生成根据相应语义，生成中间代码（中间代码（介于源语言和目标语言介于源语言和目标语言之间的中间语言形式）之间的中间语言形式）第35页，此课件共63页哦生成中间代码的目的：生成中间代码的目的：利于代码优化利于代码优化 利于目标代码的移植利于目标代码的移植中间代码的形式：中间代码的形式：四元式、三元式、逆波兰表示四元式、三元式、逆波兰表示第36页，此课件共63页哦四元式四元式其中t1、t2、t3为编译程序引入的临时工作单元例：y =x+r*6运算符左运算对象 右运算对象结果(1)inttoreal 6-t1(2)*r
17、t1t2(3)+t2xt3(4)=t3y第37页，此课件共63页哦任务：任务：对中间代码进行加工变换加工变换，以得到高质量（省时间、省空间）的目标代码四、代码优化四、代码优化依据原则：依据原则：程序的等价变换规则等价变换规则主要优化内容主要优化内容 公共子表达式提取、合并已知量、删除无用赋值语句、循环优化等第38页，此课件共63页哦t1=b*ct2=t1+0t3=b*ct4=t2+t3 a=t4t1=b*c t2=t1+t1a=t2优化举例优化举例第39页，此课件共63页哦(1)(inttoreal 60 -t1 )(2)(*id3 t1 t2 )(3)(+id2 t2 t3 )(4)(:=t
18、3 -id1)id1:=id2+id3*60（1）(*id360.0t2 )(2）（+id2 t2 id1 )(*(*id3id360.060.0t2 )t2 )(+(+id2id2t2t2id1)id1)优化举例优化举例第40页，此课件共63页哦目标代码的形式：绝对指令代码绝对指令代码：可立即执行的代码(如.exe)汇编指令代码汇编指令代码：汇编语言程序，需通过汇编程序汇编后才能运行可重定位的指令代码可重定位的指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可运行的绝对指令代码（如.obj）五、目标代码生成五、目标代码生成任务：任务：把中间代码变换成特定机器
19、上的低级语言代码低级语言代码第41页，此课件共63页哦(*,id360.0 t1)(+,id2t1id1)movid3,R2mul#60.0,R2movid2,R1addR2,R1movR1,id1目标代码生成举例目标代码生成举例第42页，此课件共63页哦目标代码生成程序代码优化程序语义分析生成中间代码语法分析程序词法分析程序编译过程小结编译过程小结S.PO.P第43页，此课件共63页哦编译程序结构编译程序结构(components)典型的编译程序具有典型的编译程序具有7个逻辑部分个逻辑部分S.PO.P语义分析及语义分析及生成中间代码生成中间代码程序程序代码生成程序代码生成程序代码优化代码优化
20、程序程序语法分析程序语法分析程序词法分析程序词法分析程序错错误误处处理理符符号号表表管管理理第44页，此课件共63页哦诊察错误，并能报告用户错误性质和位置出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。填表：把源程序中的信息和编译过程中所产生的信息登记在表格中查表：在随后的编译过程中同时又要不断的查找这些表格中的信息符号表管理符号表管理错误处理错误处理第45页，此课件共63页哦编译阶段的组合编译阶段的组合根据编译程序各部分功能，将编译程序分成根据编译程序各部分功能，将编译程序分成前端前端和和后端后端 前端前端：通常将与：通常将与源程序源程序有关的编译部分称为前端。有关的编译部分称为前端
21、。词法分析、语法分析、语义分析、中间代码生成词法分析、语法分析、语义分析、中间代码生成 -分析部分分析部分 特点：与特点：与源语言源语言有关有关 后端后端：与：与目标机目标机有关的部分称为后端。有关的部分称为后端。代码优化、代码生成代码优化、代码生成-综合部分综合部分 特点：与特点：与目标机目标机有关有关第46页，此课件共63页哦n源程序 中间代码 目标代码 仅依赖源程序 仅依赖目标计算机n遍遍（PASS)：对输入文件（源程序或其等价的中间形式）从头到尾扫视，完成预定的处理。遍输入文件输出文件前前端端后后端端编译程序（器）的组织编译程序（器）的组织第47页，此课件共63页哦n指对源程序或源程序
22、的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标代码的过程。n遍与阶段的关系：每一遍扫视可完成一个或多个阶段的工作一阶段可分几遍扫描n遍的划分视具体情况而定（内存的大小、源语言的繁简、目标程序质量的高低）遍（遍（pass）第48页，此课件共63页哦语法分析语法分析扫描器语义子程序源程序目标代码编译程序取单词类号内码归约返回优点优点优点优点：不必产生中间代码，可避免重复性工作，速度快；缺点缺点缺点缺点：当出现语法语义错误时，前面工作半途而废，且不便于分工、优化，结构和算法不够清晰。一遍扫描一遍扫描第49页，此课件共63页哦n直接用机器语言编写编译程序直接用机器语言编写编译程
23、序n用汇编语言编写编译程序用汇编语言编写编译程序注：编译程序核心部分常用汇编语言编注：编译程序核心部分常用汇编语言编写写n用高级语言编写编译程序用高级语言编写编译程序注：这是普遍采用的方法注：这是普遍采用的方法编译程序生成编译程序生成第50页，此课件共63页哦n自编译o先对语言的核心部分构造一个小小的编译程序，再以它为工具构造一个能编译更多语言成分的较大编译器，如此扩展下去像滚雪球般，最后形成人们期望的整个编译程序。通过一系列自展途径形成编译程序的过程称为自编译过程。n编译工具:LEX(词法分析)与YACC(用于自动产生LALR分析表)n移植（同种语言的编译程序在不同类型的机器之间移植）编译程
24、序生成编译程序生成第51页，此课件共63页哦功能 让计算机执行高级语言（basic,lisp,prolog)与编译程序的不同 1）不生成目标代码 2）能支持交互环境 （同增量式编译系统）源 程 序 初始数据 解释程序计算结果1.3 高级语言解释系统高级语言解释系统(interpreter)第52页，此课件共63页哦直接对源程序中的语句进行分析，执行其隐含的操作。如：b:=2 ;a:=b+2 ;编译程序 write a ;Mov#2.0 r1Mov r1 bMov b r2Add r1 r2Mov r1 a生成代码解释程序直接将4的值输出（显示）解释系统解释系统第53页，此课件共63页哦 编译阶
25、段和运行阶段存储结构 编译时 运行时 名字表目标代码缓冲区编译用源程序中间表示各种表格源程序缓冲区目标代码区数据区解释系统存储结构解释系统源程序工作单元名字表标号表缓冲区(输入输出)栈区第54页，此课件共63页哦语言范型(paradigms)命令式(imperative language)应用式(applicative)基于规则的（rule-based）面向对象的（object-oriented）1.4 程序设计语言范型程序设计语言范型第55页，此课件共63页哦懂得编译，有助于深刻理解和正确使用程序设计语言编译内容涉及计算机组织结构、指令系统、操作系统等，有助于加深对整个计算机系统的理解设计开
26、发编译程序的软件技术同样有助于其他软件的设计开发变量说明、出错提示位置为何要学习编译技术为何要学习编译技术第56页，此课件共63页哦第一章 小结内容 什么是编译程序什么是编译程序 编译过程和编译程序的结构编译过程和编译程序的结构 什么是解释程序什么是解释程序本章没有难以理解的内容,重点对编译程序的功能和结构做一综述，希望大家能够宏观掌握。第57页，此课件共63页哦课内习题1编译程序各阶段工作都涉及_。A.词法分析B.表格管理C.语法分析D.语义分析第58页，此课件共63页哦课内习题2编译程序将源程序加工成目标程序是_之间的转换。A.词法B.规则C.语法D.语义第59页，此课件共63页哦课内习题3解释和编译程序的区别在于_。A.是否生成中间代码B.加工的对象不同C.使用的实现技术不同D.是否生成目标程序第60页，此课件共63页哦课内习题4编译程序不能够检查、处理的错误是程序中的_错误。A.静态语义B.动态语义C.语法D.词法第61页，此课件共63页哦课内习题5可以作为目标代码的语言是_语言。A.高级B.中间C.低级D.程序设计第62页，此课件共63页哦课内习题6开发一个编译程序应掌握_。A.源语言B.目标语言C.编译技术D.以上三项全是第63页，此课件共63页哦