《编译原理课程教案》第1章：编译原理概述.ppt

编译原理实践及应用编译原理实践及应用编译原理实践及应用-中南大学 肖健宇编译原理实践及应用12二月2023第2页教材及主要参考资料教材及主要参考资料教材：编译原理实践及应用，黄贤英，清华大学出版社主要参考资料：(1)编译原理，陈火旺，国防工业出版社(2)程序设计语言编译方法，肖军模，大连理工大学出版社(3)编译原理，张素琴，吕映芝，清华大学出版社(4)编译原理，alfredV.Aho等著，李建中等译，人民邮电出版社编译原理实践及应用12二月2023第3页序序 言言 编译原理实践及应用12二月2023第4页C语言程序voidmain()intx,y,z;x=3;y=2;z=x+y;什么是编译？什么是编译？从程序员可以理解的高级语言高级语言程序到机器可以理解的机器语言机器语言程序的自动翻译自动翻译过程。编译原理实践及应用12二月2023第5页汇编语言程序movax,3movx,axmovax,2movy,axmovax,xmovbx,yaddax,bxmovz,ax.300302304306308内存地址 内存内容单元名字200H3x：局部变量201H2y：局部变量202H5z：局部变量机器码编译原理实践及应用12二月2023第6页为什么要学习编译原理？为什么要学习编译原理？1、有助于深刻理解和正确使用程序设计语言，加深对高级语言程序执行过程的理解2、有助于加深对整个计算机系统的理解。3、设计开发编译程序的软件技术同样可以用于其他软件的设计开发。4、随着微处理器技术的飞速发展，处理器性能在很大程度上取决于编译器的质量、编译技术成为计算机的核心技术，地位变得越来越重要。编译原理实践及应用12二月2023第7页编译原理编译原理课程在计算机科学中课程在计算机科学中的重要地位的重要地位(1)学习编程最初是学习一门高高级级语语言言，C或Pascal，掌握编写一些简单程序的方法；(2)学习数数据据结结构构，建立“算法”的概念，对编程有更深入的理解。遇到问题的时候，能够寻找相应的数据结构模型，设计适当的算法来解决问题；(3)学习汇汇编编语语言言，这门课程是我们真正深入了解计算机内部工作的第一门课程。通过学习了解汇编语言如何变为机器语言，如何对应于一条指令；(4)计算机组成原理计算机组成原理课程的学习使我们了解到计算机的硬件组成，以及机器指令程序如何在计算机中运行的过程。(5)编编译译原原理理课程帮助我们了解高级语言程序转换成机器指令程序的过程。可以帮助我们更深刻地理解高级语言程序运行的内部机制。编译原理实践及应用12二月2023第8页编译原理编译原理课程在计算机科学中课程在计算机科学中的地位的地位高级语言程序设计离散数学数据结构编译原理操作系统系统软件应用软件软件工程信息系统电子商务汇编语言计算机组成原理编译原理实践及应用12二月2023第9页学习本课程的目的和任务学习本课程的目的和任务加深对编程语言设计和实现的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用，提升自身的编程能力掌握编译程序的基本结构，掌握常用的编译技术和方法，将编译原理的理论和方法应用于一般的软件设计中培养团队协作能力编译原理实践及应用12二月2023第10页本课程的特点本课程的特点(1)本课程理论性很强，学习时需要很强的逻辑思维能力(2)涉及的算法复杂，要深入地理解这些算法很困难(3)编译原理课程各个部分之间的独立性很强，包括词法分析、语法分析、存储的组织与分配、中间语言、语法制导翻译、代码生成与优化这几大部分。词法分析、及语义分析是重点；其他部分相对来说知识性更强一些。编译原理实践及应用引引 论论第一章第一章 编译原理实践及应用12二月2023第12页本章要求本章要求主要内容主要内容：各种翻译程序的概念，编译各种翻译程序的概念，编译过程和阶段划分，编译程序的组成和结过程和阶段划分，编译程序的组成和结构，编译程序的构造方法构，编译程序的构造方法重点掌握：重点掌握：编译程序工作的基本过程及编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。其各阶段的基本任务，编译程序总框。编译原理实践及应用12二月2023第13页问题：问题：1.什么是编译程序？2.编译程序的工作过程是什么样的？3.编译程序的总体结构是什么样的？4.什么叫编译前端、编译后端？5.什么叫“遍”（pass）？6.编译程序有哪些生成方法？编译原理实践及应用12二月2023第14页v编译程序（编译程序（Compiler）将高级程序设计语言将高级程序设计语言将高级程序设计语言将高级程序设计语言程序翻译成逻辑上等价的低级语言程序翻译成逻辑上等价的低级语言程序翻译成逻辑上等价的低级语言程序翻译成逻辑上等价的低级语言(汇编语言汇编语言汇编语言汇编语言,机机机机器语言器语言器语言器语言)程序的翻译程序。程序的翻译程序。程序的翻译程序。程序的翻译程序。v功能功能编译程序编译程序源程序源程序目标程序目标程序计算机运行计算机运行输入数据输入数据结果结果1.1 编译程序是什么编译程序是什么编译原理实践及应用12二月2023第15页计算机中的语言层次和转换关系计算机中的语言层次和转换关系编译原理实践及应用12二月2023第16页解释程序解释程序v解释程序（解释程序（Interpreter）将高级程序设计将高级程序设计将高级程序设计将高级程序设计语言写的源程序作为输入，边解释边执行源程语言写的源程序作为输入，边解释边执行源程语言写的源程序作为输入，边解释边执行源程语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。序本身，而不产生目标程序的翻译程序。序本身，而不产生目标程序的翻译程序。序本身，而不产生目标程序的翻译程序。v功能功能解释程序解释程序源程序源程序输入数据输入数据结果结果编译原理实践及应用12二月2023第17页编译程序的分类编译程序的分类诊断编译程序诊断编译程序优化编译程序优化编译程序可变目标编译程序可变目标编译程序交叉编译程序交叉编译程序编译原理实践及应用12二月2023第18页与编译程序相关的程序与编译程序相关的程序解释程序解释程序(Interpreter)(Interpreter)汇编程序汇编程序(assembler)(assembler)连接程序连接程序(linker)(linker)连接系统函数与系统资源连接系统函数与系统资源装入程序装入程序(loader)(loader)重定位重定位(relocation)(relocation)预处理器预处理器(Preprocessor)(Preprocessor)编辑器编辑器(editor)(editor)Debugger,Profiler,Project Debugger,Profiler,Project ManagerManager编译原理实践及应用12二月2023第19页编译原理是讨论编译程序设计的基本理论、基本概念、基本方法什么是编译原理什么是编译原理编译原理实践及应用12二月2023第20页1.2 编译过程概述编译过程概述逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。词法分析语法分析语义分析与中间代码生成代码优化目标代码生成编译原理实践及应用编译过程和英文翻译过程对比编译过程和英文翻译过程对比把英文翻把英文翻译为译为中文中文 识别出句子中的一个个单词；识别出句子中的一个个单词；分析句子的语法结构；分析句子的语法结构；根据句子的含义进行初步翻译；根据句子的含义进行初步翻译；对译文进行修饰；对译文进行修饰；写出最后的译文。写出最后的译文。词法分析词法分析语法分析语法分析中间代码中间代码产生产生优化优化目标代码目标代码产生产生编译原理实践及应用12二月2023第22页第一阶段：词法分析第一阶段：词法分析任务任务:从左到右扫描源程序，识别出每个单词o附加任务：a、滤掉空格b、识别单词o单词符号是语言的基本组成成分o词法分析的工作主要依据语言的词法规词法规则则，描述词法规则的有效工具是正规式正规式和有限自动机和有限自动机。编译原理实践及应用12二月2023第23页beginresult:=5B*CB*Cend;单词类型内部形式begin关键字$beginresult标识符id1:=界符:=5常数int1+算符+B标识符id1*算符*C标识符id2+算符+B标识符id2*算符*C标识符id3end关键字$end;界符;例:编译原理实践及应用12二月2023第24页第二阶段：语法分析第二阶段：语法分析任务任务:o在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。o确定整个输入串是否构成语法上正确的程序。o语法分析所依据的是语言的语法规则，表示语法规则的工具是上下文无关文法，用下推自动机实现。编译原理实践及应用12二月2023第25页id1:=int1+id2*id3+id2*id3例：识别符号串id1:=int1+id2*id3+id2*id3（即result:=5B*CB*C）是一个赋值语句。编译原理实践及应用12二月2023第26页第三阶段：语义分析和中间代码生成第三阶段：语义分析和中间代码生成任务任务：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)。o静态语义审查变量定义类型匹配类型转换例：C:=A*B(检查C与、类型)o中间代码的翻译中间代码有多种形式，如：四元式:(运算符，运算对象1，运算对象2，结果)编译原理实践及应用12二月2023第27页例：对赋值语句：id1:=int1+id2*id3+id2*id31.检查result、C是否定义类型2.生成中间代码(运算符，运算对象运算符，运算对象1，运算对象，运算对象2，结果，结果)(*,id2,id3,T1)(+,int1,T1,T2)(*,id2,id3,T3)(+,T2,T3,T4)(:=,T4,_,id1)id1:=int1+id2*id3+id2*id3编译原理实践及应用12二月2023第28页第四阶段：第四阶段：代码优化代码优化任务任务：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。o优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。o代码的优化依据的是程序的等价变换规则。编译原理实践及应用12二月2023第29页序号 四元式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第五阶段：目标代码的生成第五阶段：目标代码的生成任务任务：把中间代码(或经优化的中间代码)变换成特定机器上的低级语言代码。o依赖于机器的硬件系统结构和机器指令的含义o目标代码可以是：绝对指令代码、可重定位的指令代码、汇编指令代码编译原理实践及应用12二月2023第31页第31页序号 四元式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,AX例：编译原理实践及应用12二月2023第32页1.3 编译程序的结构编译程序的结构编译原理实践及应用12二月2023第33页编译原理实践及应用12二月2023第34页几个概念符号表：登记源程序中出现的名字以及名字的各种属性。遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化。编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成。编译原理实践及应用12二月2023第35页编译阶段的组合编译阶段的组合编译原理实践及应用12二月2023第36页为什么要生成中间代码为什么要生成中间代码编译原理实践及应用12二月2023第37页(1)记号记号(token)当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。编译程序中的主要数据结构编译程序中的主要数据结构:编译原理实践及应用12二月2023第38页(2)语法树（语法树（syntax tree）如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。编译原理实践及应用12二月2023第39页(3)符号表（符号表（symbol table）这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分析程序将增加数据类型和其他信息；优化阶段和代码生成阶段也将利用由符号表提供的信息选出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。编译原理实践及应用12二月2023第40页(4)常数表（常数表（literal table）常数表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也十分重要。但是，在其中却无需删除，这是因为它的数据全程应用于程序而且常量或字符串在该表中只出现一次。编译原理实践及应用12二月2023第41页(5)中间代码（中间代码（intermediate code）根据中间代码的类型（例如三元式代码）和优化的类型，该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允许简单重组的表示。编译原理实践及应用12二月2023第42页(6)临时文件（临时文件（t e m p o r a ry file）计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足够信息用以处理翻译）解决了。编译原理实践及应用12二月2023第43页1.4 构造编译程序构造编译程序一般生成编译程序的方法有：1.直接用机器语言编写编译程序2.用汇编语言编写编译程序3.用高级语言编写编译程序4.用编译工具自动生成:LEX(词法分析)与YACC(用于自动产生LALR分析表)5.移植（同种语言的编译程序在不同类型的机器之间移植）编译原理实践及应用12二月2023第44页本书构成本书构成编译原理实践及应用12二月2023第45页思考题思考题1.1.什么是编译程序什么是编译程序？2.2.编译过程分哪些阶段？各阶段的功能和任务是什么编译过程分哪些阶段？各阶段的功能和任务是什么?3.3.写出写出pascalpascal语言中字符集、单词、数据类型、各种语言中字符集、单词、数据类型、各种表达式、语句和程序的组成表达式、语句和程序的组成4.4.查阅如下一种资料：查阅如下一种资料：(1)(1)与某种语言与某种语言(如如javajava、VBVB等等)的编译程序有关的编译程序有关(2)(2)与编译程序的理论有关与编译程序的理论有关(3)(3)与某种高级语言的发展有关与某种高级语言的发展有关5.5.用某种熟悉的语言的编译程序来理解层次和遍用某种熟悉的语言的编译程序来理解层次和遍