《《编译原理实践及应用》第1章编译原理概述.ppt》由会员分享，可在线阅读，更多相关《《编译原理实践及应用》第1章编译原理概述.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理实践及应用编译原理实践及应用主讲人：董明刚12二月2023第2页教材及主要参考资料教材及主要参考资料教材教材：编译原理实践及应用，黄贤英，清华大学出版社主要参考资料：主要参考资料：编译原理，陈火旺，国防工业出版社编译原理(原书第2版)(龙书)，ALFREDV.AHOetc著，赵建华郑滔等译，机械工业出版社,2008.12程序设计语言编译方法，肖军模，大连理工大学出版社编译原理，张素琴，吕映芝，清华大学出版社更多教材及参考资料参见编译原理精品课程网站。C语言程序voidmain()intx,y,z;x=3;y=2;z=x+y;内存地址内存地址内存内容内存内容单元名字单元名字200H3x：
2、局部变量202H2y：局部变量204H5z：局部变量300H3A03302H3AE1304H3A02306H3AE2308HDA6C.3A71汇编语言程序movax,3movx,axmovbx,2movy,bxaddax,bxmovz,ax.序言在内存中：在内存中：数据区代码区？编译原理概述编译原理概述第一章第一章 12二月2023第5页本章要求本章要求主要内容主要内容：各种翻译程序的概念，编译各种翻译程序的概念，编译过程和阶段划分，编译程序的组成和结过程和阶段划分，编译程序的组成和结构，编译程序的构造方法构，编译程序的构造方法重点掌握：重点掌握：编译程序工作的基本过程及编译程序工作的基本过程
3、及其各阶段的基本任务，编译程序总框。其各阶段的基本任务，编译程序总框。12二月2023第6页1.1 程序设计语言与翻译程序程序设计语言与翻译程序机器语言机器语言(machine language)C7 06 0000 0002汇编语言汇编语言(assembler language)MOV X,2高级语言高级语言(high-level language)X=2为什么要使用编译程序？为什么要使用编译程序？12二月2023第7页机器语言机器语言(machine language)C7 06 0000 0002汇编语言汇编语言(assembler language)MOV X,2高级语言高级语言(hi
4、gh-level language)X=2为什么要使用编译程序？为什么要使用编译程序？12二月2023第8页计算机中的语言层次和翻译程序计算机中的语言层次和翻译程序12二月2023第9页什么叫翻译程序什么叫翻译程序翻译程序翻译程序：能够将某种语言写的程序转换成另一种语言的程序，而且后者与前者在逻辑上是等价的。编译程序编译程序：将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。解释程序解释程序：将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。12二月2023第10页高级语言语言处理程序操作系统汇编语言翻译程序所处的层次
5、翻译程序所处的层次计算机硬件C编译程序C语言Basic解释程序Basic语言Fortran编译程序Fortran语言.12二月2023第11页编译程序编译程序编译程序编译程序源程序源程序目标程序目标程序计算机运行计算机运行输入数据输入数据结果结果解释程序解释程序解释程序解释程序源程序源程序输入数据输入数据结果结果12二月2023第12页对编译程序的一些说明对编译程序的一些说明编译程序实质上是一个翻译程序翻译程序，要注意等价等价变换本课程的任务任务就是讲解在这个转换过程中所涉及到的一些理论和方法，最后，使用这些理论和方法，自己编写一个小的编译器转换是一个总体的功能，要抓住总体结构，逐层细分，写编
6、译器时要体现软件工程中软件设计的软件设计的原则原则，自顶向下，逐层分解。编译器要完成的转换任务相当复杂，实现编译器时必须分步骤分阶段分步骤分阶段实现。分阶段实现的好处是能够简化程序的设计简化程序的设计，当然也可以不分阶段实现。12二月2023第13页编译程序的分类编译程序的分类诊断编译程序诊断编译程序优化编译程序优化编译程序可变目标编译程序可变目标编译程序交叉编译程序交叉编译程序12二月2023第14页编译器的伙伴编译器的伙伴编辑器编辑器(editor)(editor)预处理器预处理器(Preprocessor)(Preprocessor)将源程序汇集到一起，宏展开等将源程序汇集到一起，宏展开
7、等汇编程序汇编程序(assembler)(assembler)连接程序连接程序(linker)(linker)连接系统函数与系统资源连接系统函数与系统资源装入程序装入程序(loader)(loader)重定位重定位(relocation)(relocation)Debugger,Profiler,Project Debugger,Profiler,Project ManagerManager12二月2023第15页编译原理是讨论编译程序设计的基本理论、基本概念、基本方法什么是编译原理什么是编译原理12二月2023第16页1.2 编译过程概述编译过程概述1、逻辑上分五个阶段：词法分析、语法分析、
8、语义分析与中间代码生成、代码优化、目标代码生成 每个阶段把源程序从一种表示变换成另一种表示词法分析语法分析语义分析与中间代码生成代码优化目标代码生成12二月2023第17页按照词法分析、语法分析、语义分析等这种方式来划分阶段的原因是：每个阶段的复杂程度不同，所依据的理论基础不同理论基础不同，实现时采用的方法也不方法也不同同。主要是方便理解和实现。划分阶段的依据是什么？每个阶段所实现的功能功能相对独立相对独立。用一个例子说明各阶段的功能12二月2023第18页/*一个PASCAL语言的源程序*/program test;/*this is an example,computing an area
9、*/var area,length,width:integer;begin length:=5;width:=5;area:=5length*widthlength*widthend.12二月2023第19页第一阶段：词法分析第一阶段：词法分析任务任务:从左到右扫描源程序，识别出每个单词从左到右扫描源程序，识别出每个单词o附加任务：a、滤掉空格b、去掉注释o单词符号是语言的基本组成成分o词法分析的工作主要依据语言中单词的构成规则o单词的种类：（1）标识符（2）关键字（char、int、if、else、while、for等）（3）运算符（即运算符号+、*、/、&等）（4）界符（常见的有；，：（）
10、等）（5）常数12二月2023第20页beginarea:=5length*widthlength*widthend;单词类型内部形式begin关键字$beginarea标识符id1:=界符:=5常数int1+算符+length标识符id1*算符*width标识符id2+算符+length标识符id2*算符*width标识符id3end关键字$end;界符;例:12二月2023第21页第二阶段：语法分析第二阶段：语法分析任务任务:在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。o确定整个输入串是否构成语法上正确的程序。o根据规则判定：根据规则判
11、定：赋值语句：赋值语句：标识符标识符:表达式表达式 表达式：表达式：标识符、常数是表达式标识符、常数是表达式 表达式的运算也是表达式表达式的运算也是表达式例：识别符号串id1:=int1+id2*id3+id2*id3是一个赋值语句（area:=5length*widthlength*width）而int1+id2*id3+id2*id3是一个表达式（5length*widthlength*width）12二月2023第22页语法分析所依据的是语言的语法规则id1:=int1+id2*id3+id2*id312二月2023第23页第三阶段：语义分析和中间代码生成第三阶段：语义分析和中间代码生成
12、任务任务：对语法分析所识别出的各类语法短语分析其含义，进行初步的翻译(翻译成中间代码)。o静态语义审查变量定义类型匹配类型转换例：C:=A*B(检查C与、类型)o中间代码的翻译中间代码有多种形式，如：四元式:(运算符，运算对象1，运算对象2，结果)12二月2023第24页例：对赋值语句：id1:=int1+id2*id3+id2*id31.检查area、length、width是否定义、类型2.生成中间代码(运算符，运算对象运算符，运算对象1，运算对象，运算对象2，结果，结果)(*,id2,id3,T1)(+,int1,T1,T2)(*,id2,id3,T3)(+,T2,T3,T4)(:=,T
13、4,_,id1)id1:=int1+id2*id3+id2*id312二月2023第25页第四阶段：第四阶段：代码优化代码优化任务任务：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。o优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。o代码的优化依据的是程序的等价变换规则。序号 四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(*,id2,id3,T3)4(+,T2,T3,T4)5(:=,T4,_,id1)序号 四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(+,T2,T1,id1)12二月2023第26页第五阶段：
14、目标代码的生成第五阶段：目标代码的生成任务任务：把中间代码(或经优化的中间代码)变换成特定机器上的低级语言代码。o依赖于机器的硬件系统结构和机器指令的含义o目标代码可以是：绝对指令代码、可重定位的指令代码、汇编指令代码序号 四元式1(*,id2,id3,T1)2(+,int1,T1,T2)3(+,T2,T1,id1)（1）mov AX,id2（2）mul AX,id3（3）mov BX,AX（4）add AX,int1（5）add AX,BX（6）mov id1,AX12二月2023第27页1.2编译程编译程序的结构序的结构由左图可以看出，词法分析是实现编译器的基础，语法分析是实现编译器的关键
15、。因此按照这个顺序来实现编译器每一步的实现都依赖于一定的理论基础。数学，尤其是离散数学是程序设计方法学的理论基础12二月2023第28页编译阶段的组合编译阶段的组合几个概念遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成12二月2023第29页编译阶段的组合编译阶段的组合12二月2023第30页为什么生成中间代码为什么生成中间代码12二月2023第31页编
16、译程序中的主要数据结构编译程序中的主要数据结构(续续)Token表符号表常数表错误信息语法树中间代码表临时文件目标代码表12二月2023第32页(1)Token表表 当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。(2)语法树（语法树（syntax tree）如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。编译程序中的主要数据结构介绍编译程序中的主要数
17、据结构介绍:12二月2023第33页(3)符号表（符号表（symbol table）这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分析程序将增加数据类型和其他信息；优化阶段和代码生成阶段也将利用由符号表提供的信息选出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。12二月2023第34页(4)常数表（常数表（literal table）常数表
18、的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也十分重要。但是，在其中却无需删除，这是因为它的数据全程应用于程序而且常量或字符串在该表中只出现一次。(5)中间代码（中间代码（intermediate code）根据中间代码的类型（例如三元式代码）和优化的类型，该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允许简单重组的表示。12二月2023第35页(6)目标目标代码（代码（intermediate code）存放最终生成的目标代码，该代码最终是文本形式的文件。(7)临时文件（临时文件（t e m p o r a ry f
19、ile）计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足够信息用以处理翻译）解决了。12二月2023第36页1.3 编译程序的设计编译程序的设计构造编译程序要掌握以下几方面的内容：源语言：理解其结构和含义目标语言：必须清楚硬件的系统结构和指令的格式等编译方法12二月2023第37页1.3 编译程序的构造编译程序的构造一般实现编译程序的方法有：1.直接用机器语言编写编译程序2.用汇编语言编写编译程序注：编译程序核心部分常用汇编语言编写3.用高级语言编写编译程序注：这是普遍采用的方法4.
20、自编译5.用编译工具自动生成:LEX(词法分析)与YACC(用于自动产生LALR分析表)6.移植（同种语言的编译程序在不同类型的机器之间移植）12二月2023第38页本书构成及编译程序框架本书构成及编译程序框架12二月2023第39页1.4 编译技术的发展编译技术的发展1954年至1957年间，FORTRAN语言及其编译器的开发。花了18个人年。几乎与此同时，Noam Chomsky开始研究语言文法(grammar，结构规则)的难易程度以及识别它们所需的算法来为语言分类。在6 0年代和7 0年代进行的分析问题(parsing problem，用于限定上下文无关语言的识别的有效算法)的研究。有穷
21、自动机(finite automata)和正规式(regular expression)的研究与乔姆斯基的研究几乎同时开始，引出了表示程序设计语言的单词的符号方式。接着又深化了生成有效的目标代码的方法，这就是最初的编译器，实际上应称作代码改进技术(code improvement technique)。当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器的自动构造。Lex与Yacc。在70年代后期和80年代早期，大量的项目都关注于编译器其他部分的生成自动化，这其中就包括了代码生成。这些尝试并未取得多少成功。12二月2023第40页1.4 编译技术最近的发展编译技术
22、最近的发展与复杂的程序设计语言的发展结合在一起。如用于函数语言编译的Hindley-Milner类型检查的统一算法。编译器已成为基于窗口的交互开发环境(IDE)的一部分，IDE的标准并没有多少，但已对标准的窗口环境进行了开发。近年来对此进行了大量研究，但是基本的编译器设计近20年来没有多大的改变，现在正迅速地成为计算机科学课程中的中心一环。由多处理机的发展以及对并行处理的要求，最近的研究方向是并行编译。随着嵌入式应用的迅速增长，推动了交叉编译技术的发展；对系统芯片设计方法和关键EDA技术的研究，也带动了专用语言VHDL等及其编译技术的不断深化。12二月2023第41页1.4 编译技术的应用编译
23、技术的应用语言的结构化编辑器语言的结构化编辑器:Turbo-Edit、editplus和Ultraedit等程序的格式化工具程序的格式化工具语言程序的调试工具语言程序的调试工具语言程序的测试工具语言程序的测试工具程序理解工具程序理解工具高级语言之间的转换工具高级语言之间的转换工具交叉编译程序交叉编译程序12二月2023第42页思考题思考题1 11.1.什么是编译程序什么是编译程序？2.2.编译过程分哪些阶段？各阶段的功能和任务是什么编译过程分哪些阶段？各阶段的功能和任务是什么?3.3.写出写出C C语言中字符集、单词、数据类型、各种表达语言中字符集、单词、数据类型、各种表达式、语句和程序的组成式、语句和程序的组成4.4.查阅如下一种资料：查阅如下一种资料：(1)(1)与某种语言与某种语言(如如javajava、VBVB等等)的编译程序有关的编译程序有关(2)(2)与编译程序的理论有关与编译程序的理论有关(3)(3)与某种高级语言的发展有关与某种高级语言的发展有关5.5.用某种熟悉的语言的编译程序来理解层次和遍用某种熟悉的语言的编译程序来理解层次和遍