《编译原理实践及应用》编译原理概述

《编译原理实践及应用》编译原理实践及应用----清华大学出版社《编译原理实践及应用》2020年1月19日星期日第2页教材及主要参考资料•教材：编译原理实践及应用，黄贤英，清华大学出版社•主要参考资料：•(1)编译原理，陈火旺，国防工业出版社•程序设计语言编译方法，肖军模，大连理工大学出版社•编译原理，张素琴，吕映芝，清华大学出版社•编译原理，alfredV.Aho等著，李建中等译，人民邮电出版社《编译原理实践及应用》2020年1月19日星期日第3页C语言程序voidmain(){intx,y,z;x=3;y=2;z=x+y;}内存地址内存内容单元名字………………200H3x：局部变量201H2y：局部变量202H5z：局部变量…………汇编语言程序……movax,3movx,axmovax,2movy,axmovax,xmovbx,yaddax,bxmovz,ax......300302304306308……序言《编译原理实践及应用》2020年1月19日星期日第4页为什么要学习编译原理？•1、有助于深刻理解和正确使用程序设计语言，加深对高级语言程序执行过程的理解•2、有助于加深对整个计算机系统的理解。•3、设计开发编译程序的软件技术同样可以用于其他软件的设计开发。•4、随着微处理器技术的飞速发展，处理器性能在很大程度上取决于编译器的质量、编译技术成为计算机的核心技术，地位变得越来越重要。《编译原理实践及应用》2020年1月19日星期日第5页《编译原理》课程在计算机科学中的重要地位•(1)学习编程最初是学习一门高级语言，C或Pascal，掌握编写一些简单程序的方法；•(2)学习数据结构，建立“算法”的概念，对编程有更深入的理解。遇到问题的时候，能够寻找相应的数据结构模型，设计适当的算法来解决问题；•(3)学习汇编语言，这门课程是我们真正深入了解计算机内部工作的第一门课程。通过学习了解汇编语言如何变为机器语言，如何对应于一条指令；•(4)计算机组成原理课程的学习使我们了解到计算机的硬件组成，以及机器指令程序如何在计算机中运行的过程。•(5)编译原理课程帮助我们了解高级语言程序转换成机器指令程序的过程。可以帮助我们更深刻地理解高级语言程序运行的内部机制。《编译原理实践及应用》2020年1月19日星期日第6页《编译原理》课程在计算机科学中的地位高级语言程序设计离散数学数据结构编译原理操作系统系统软件应用软件软件工程信息系统电子商务汇编语言计算机组成原理《编译原理实践及应用》2020年1月19日星期日第7页学习本课程的目的和任务•加深对编程语言设计和实现的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用，提升自身的编程能力•掌握编译程序的基本结构，掌握常用的编译技术和方法，将编译原理的理论和方法应用于一般的软件设计中•培养团队协作能力《编译原理实践及应用》2020年1月19日星期日第8页本课程的特点•(1)本课程理论性很强，学习时需要很强的逻辑思维能力•(2)涉及的算法复杂，要深入地理解这些算法很困难•(3)整个编译程序的构造方法非常精妙，就像一部走时精确的时钟，很多齿轮、部件协调地运转，以驱动指针准确地旋转；编译程序也是如此，一边扫描源程序，一边经过各个部件的运算，准确地输出为目标语言。•(4)编译原理课程各个部分之间的独立性很强，包括词法分析、语法分析、存储的组织与分配、中间语言、语法制导翻译、代码生成与优化这几大部分。词法分析和语法分析是其中的重点，语言分析也是难点，需要掌握比较复杂的算法逻辑；其他部分相对来说知识性更强一些。各部分之间的方法也互相独立，在学习时，便于逐个击破。•(5)考试考查的内容相对来说是很稳定的，绝大多数题目的解法都非常机械。《编译原理实践及应用》2020年1月19日星期日第9页学习方法•(1)尽可能地掌握编译原理的思想，要站得高一点，尽可能理解算法的思想，而不是背固定的算法。应该尽力理解为什么要这样做，逐渐在头脑中建立起编译器的整体概念，而不是零零散散的一些算法。•(2)很多题目的解法比较固定，要熟练掌握相应的具体方法。•(3)多做习题,对于编译这样的学科，题目的规模很大，步骤繁多，而且前面的步骤一旦出错，后面都错。•(4)要扎扎实实地牢记重要算法，配合大量的习题进行练习，达到拿到题目就可以动手做的地步。•(5)一边学习，一边总结，关键是找差异：同一问题可以用多种方法来求解，不同方法适用于不同的文法，对文法的限制和要求，相应的表格的构造、使用等，各个方面的差异都要关注。•(6)亲自动手实现书上的一些算法,完成实验指导书上给出的一个简单的编译程序，或者编译程序的一部分，这样能更灵活地掌握编译程序构造的精髓。《编译原理实践及应用》2020年1月19日星期日第10页编译技术的发展•1954年至1957年间，FORTRAN语言及其编译器的开发。花了18个人年。•几乎与此同时，NoamChomsky开始研究语言文法(grammar，结构规则)的难易程度以及识别它们所需的算法来为语言分类。•在60年代和70年代进行的分析问题(parsingproblem，用于限定上下文无关语言的识别的有效算法)的研究。•有穷自动机(finiteautomata)和正规式(regularexpression)的研究与乔姆斯基的研究几乎同时开始，引出了表示程序设计语言的单词的符号方式。•接着又深化了生成有效的目标代码的方法，这就是最初的编译器，实际上应称作代码改进技术(codeimprovementtechnique)。•当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器的自动构造。Lex与Yacc。•在70年代后期和80年代早期，大量的项目都关注于编译器其他部分的生成自动化，这其中就包括了代码生成。这些尝试并未取得多少成功。《编译原理实践及应用》2020年1月19日星期日第11页编译器设计最近的发展•与复杂的程序设计语言的发展结合在一起。如用于函数语言编译的Hindley-Milner类型检查的统一算法。•编译器已成为基于窗口的交互开发环境(IDE)的一部分，IDE的标准并没有多少，但已对标准的窗口环境进行了开发。近年来对此进行了大量研究，但是基本的编译器设计近20年来没有多大的改变，现在正迅速地成为计算机科学课程中的中心一环。•由多处理机的发展以及对并行处理的要求，最近的研究方向是并行编译。•随着嵌入式应用的迅速增长，推动了交叉编译技术的发展；对系统芯片设计方法和关键EDA技术的研究，也带动了专用语言VHDL等及其编译技术的不断深化。《编译原理实践及应用》2020年1月19日星期日第12页编译技术的应用•语言的结构化编辑器:Turbo-Edit、editplus和Ultraedit等•语言程序的调试工具•语言程序的测试工具•高级语言之间的转换工具•交叉编译程序《编译原理实践及应用》引论第一章《编译原理实践及应用》2020年1月19日星期日第14页本章要求•主要内容：各种翻译程序的概念，编译过程和阶段划分，编译程序的组成和结构，编译程序的构造方法•重点掌握：编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。《编译原理实践及应用》2020年1月19日星期日第15页•机器语言(machinelanguage)C70600000002•汇编语言(assemblerlanguage)MOVX,2•高级语言(high-levellanguage)X=2为什么要使用编译器？《编译原理实践及应用》2020年1月19日星期日第16页计算机中的语言层次和转换关系高级语言1高级语言层转换程序高级语言2编译程序1编译程序2汇编语言层汇编语言1机器语言层汇编程序反汇编程序机器语言1计算机1机器语言2计算机2高级语言3高级语言4编译程序3编译程序4汇编语言2汇编程序交叉编译程序交叉汇编程序解释程序1《编译原理实践及应用》2020年1月19日星期日第17页高级语言语言处理程序操作系统汇编语言编译程序所处的层次计算机硬件C编译程序C语言Basic解释程序Basic语言Fortran编译程序Fortran语言............《编译原理实践及应用》2020年1月19日星期日第18页1.1什么叫编译程序•翻译程序：能够将某种语言写的程序转换成另一种语言的程序，而且后者与前者在逻辑上是等价的。•编译程序：是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序•解释程序：接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。《编译原理实践及应用》2020年1月19日星期日第19页1.1什么叫编译程序编译程序（Compiler）——将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。功能编译程序源程序目标程序计算机运行输入数据结果《编译原理实践及应用》2020年1月19日星期日第20页解释程序解释程序（Interpreter）——将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。功能解释程序源程序输入数据结果《编译原理实践及应用》2020年1月19日星期日第21页对编译程序的一些说明•编译程序实质上是一个翻译程序，要注意等价变换•本课程的任务就是讲解在这个转换过程中所涉及到的一些理论和方法，最后，使用这些理论和方法，自己编写一个小的编译器•转换是一个总体的功能，要抓住总体结构，逐层细分，写编译器时要体现软件工程中软件设计的原则，自顶向下，逐层分解。•编译器要完成的转换任务相当复杂，实现编译器时必须分步骤分阶段实现。分阶段实现的好处是能够简化程序的设计，当然也可以不分阶段实现。《编译原理实践及应用》2020年1月19日星期日第22页编译程序的分类•诊断编译程序•优化编译程序•可变目标编译程序•交叉编译程序《编译原理实践及应用》2020年1月19日星期日第23页与编译程序相关的程序•解释程序(Interpreter)•汇编程序(assembler)•连接程序(linker)–连接系统函数与系统资源•装入程序(loader)–重定位(relocation)•预处理器(Preprocessor)•编辑器(editor)•Debugger,Profiler,ProjectManager《编译原理实践及应用》2020年1月19日星期日第24页编译原理是讨论编译程序设计的基本理论、基本概念、基本方法什么是编译原理《编译原理实践及应用》2020年1月19日星期日第25页1.2编译过程概述•1、逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成每个阶段把源程序从一种表示变换成另一种表示源程序编译器目标程序词法分析语法分析语义分析与中间代码生成代码优化目标代码生成《编译原理实践及应用》2020年1月19日星期日第26页•按照词法分析、语法分析、语义分析等这种方式来划分阶段的原因是：每个阶段的复杂程度不同，所依据的理论基础不同，实现时采用的方法也不同。主要是方便理解和实现。•划分阶段的依据是什么？每个阶段所实现的功能相对独立。《编译原理实践及应用》2020年1月19日星期日第27页第一阶段：词法分析任务:从左到右扫描源程序，识别出每个单词o附加任务：a、滤掉空格b、识别单词o单词符号是语言的基本组成成分o词法分析的工作主要依据语言的词法规则，描述词法规则的有效工具是正规式和有限自动机。o单词的种类：（1）标识符（2）关键字（char、int、if、else、switch、while、for等）（3）运算符（即运算符号+、－、*、/、&等）（4）界符（常见的有；，：（）等）（5）常数《编译原理实践及应用》2020年1月19日星期日第28页beginresult:=5＋B*C＋B*Cend;单词类型内部形式begin关键字$beginresult标识符id1:=界符:=5常数int1+算符+B标识符id1*算符*C标识符id2+算符+B标识符i