编译原理重点PPT第1章概述(08.3.3).3.3%29.ppt

编译原理,2020年6月,与课程有关的问题,时间安排：讲课：32学时实验：16学时,参考书：程序设计语言编译原理，陈火旺等，第三版，国防工业出版社计算机编译原理，第二版，张幸儿，科学出版社编译程序原理与技术，李赣生、王华民，清华大学出版社,作业：视所讲内容布置1-2道习题,成绩：以考试为主，参考平时成绩(作业、实验等),与课程有关的问题,本课程的性质、目的和任务：本课程是计算机类专业的专业课，目的是使学生了解并掌握编译程序的基本理论和方法，具有分析和实现编译程序的初步能力。,本课程的基本要求：通过对本课程的学习，对形式语言有初步了解，并能对编译程序的整个结构有较清楚地了解，熟悉和掌握几种主要编译方法。,课程内容的重点、深度与广度：重点是：文法和形式语言、词法分析和有穷自动机、语法分析、语义分析。此外还涉及到目标代码的生成，此外还要求掌握和了解符号表的构造、存储分配与管理、代码优化和错误校正。,课程内容,第1章：编译程序概述第2章：文法和语言的形式定义第3章：有穷自动机与词法分析第4章：语法分析第5章：语义分析和中间代码生成第6章：符号表的组织与管理第7章：代码优化第8章：运行阶段的存储组织与分配第9章：目标代码生成第10章：并行编译技术基本知识,本节内容简介,程序的翻译,编译程序的工作过程,编译程序的结构,编译程序的组织方式,编译程序的构造,1.1翻译程序与编译程序,问题:计算机只能识别二进制数0、1表示的指令和数构成的本计算机系统的机器语言。如何让计算机执行高级语言程序呢？,高级语言beginx:=9+2end,1.1.1程序设计语言的发展,机器语言001110010010,汇编语言ADDR12,所谓翻译程序是指这样一种程序，它能将用甲语言（源语言）编写的程序翻译成与之等价的用乙语言（目标语言）书写的程序。,程序翻译的方式：一是“编译”方式，二是“解释”方式。,1.1翻译程序与编译程序,1.1.2翻译程序,编译方式是一种分阶段进行的翻译方式。,翻译阶段,高级语言或汇编语言源程序,机器语言的目标程序,翻译程序,运行阶段,1.1翻译程序与编译程序,输入数据,运行结果,目标程序,运行子程序,1.1.3编译方式,编译程序,高级语言源程序,汇编语言或机器语言目标程序,编译程序,汇编程序,汇编语言源程序,机器语言目标程序,汇编程序,编译程序编译方式下的翻译程序,1.1程序的翻译编译方式,在编译方式下，源程序的执行需要分阶段。,如果目标程序是机器语言程序，则源程序的执行分为两大阶段：编译阶段和运行阶段。,如果目标程序是汇编语言程序，则源程序的执行分为三大阶段：编译阶段、汇编阶段和运行阶段。,编译方式下，生成了目标代码，且可多次执行。,编译方式的特点,1.1程序的翻译编译方式,关于编译程序的几点说明,编译程序生成的目标程序不一定是机器语言的程序，也有可能是汇编语言程序；,编译程序与具体的机器和语言有关，即任何一个具体的编译程序都是某一特定类型的计算机系统中关于某一特定语言的编译程序；,对编译程序而言，源程序是输入数据，目标程序是输出结果。,关于编译程序的几点说明,（4）编译程序实际上只可能发现并报告在静态可计算性制约下的那些错误。（5）理想的编译程序应该具有单独编译某个模块的能力，同时它不应因为源程序的一两处修改就对源程序重新编译。,完成解释工作的解释程序将按源程序中语句的动态顺序，逐句地进行分析解释，并立即予以执行。,1.1程序的翻译解释方式,1.1.4解释方式,1.编辑器2.预处理器3.编译器4.连接程序5.装入程序6.调试程序,程序设计环境,集成开发环境（IDE）,源程序解释执行的历程,计算机,解释程序,源程序（高级语言）,初始数据,计算结果,在解释方式下，并不生成目标代码，而是直接执行源程序本身。这是编译方式与解释方式的根本区别。,所谓编译过程是指将高级语言程序翻译为等价的目标程序的过程。,翻译外文资料：1、能识别出句子中的一个单词；2、分析句子的语法结构；3、根据句子的含义进行初步翻译；4、对译文进行修饰；5、写出最后的译文。,1.2编译程序的组成,翻译和编译工作的比较,编译过程,词法分析,语法分析,语义分析及中间代码生成,代码优化,目标代码生成,习惯上是将编译过程划分为5个基本阶段：,1.2编译程序的工作过程,例：一个简要的C程序Main()/*usedforillustratingcompilingprocess*/Inta,b,c,x;a=a+b*c+b*c;x=a*3-b*c;b=a+)b*(x-;,依据语言词法规则，分析由字符组成的源程序，把它识别为一个一个具有独立意义的最小语法单位，即“单词”，并识别出与其相关的属性(如是标识符，是界限符，还是数，等等)，再转换成长度上统一的标准形式(这种统一的标准形式既刻画了单词本身，又刻画了它所具有的属性，称为属性字)，以供其它部分使用。,1.2编译程序的工作过程词法分析,上述源程序通过词法分析识别出如下单词符号：基本字：main,int标识符：a,b,c,x常数：3运算符：,*,界符：(,),;,/*,*/,=长度上统一的标准形式TOKEN串TOKEN串是一个二元组：（单词类别，单词的值）其中：“单词的类别”用既已存在的一组整数值（称为单词的种别码）表示。用以区分不同种类的单词。“单词的值”是单词的机内表示形式。一般是ASCII码。,Main()/*usedforillustratingcompilingprocess*/Inta,b,c,x;a=a+b*c+b*c;x=a*3-b*c;b=a+)b*(x-;,依据语法规则，逐一分析词法分析时得到的单词，把单词串分解成各类语法单位，即确定它们是怎样组成说明和语句，以及说明和语句又是怎样组成程序的。分析时如发现有不合语法规则的地方，便将出错的位置及出错性质打印报告给程序员；如无语法错误，则用另一种中间形式给出正确的语法结构，供下一阶段分析使用。,1.2编译程序的工作过程语法分析,通过语法分析，识别出：a,b,x是这个语法单位；a+b*c+b*c组合成这样的语法单位；识别出，这样的语法单位，并检查正确性。例如，由=构成；这里发现b=a+)b*(x-的语法错误。原因是a+)b*(x-错误,Main()/*usedforillustratingcompilingprocess*/Inta,b,c,x;a=a+b*c+b*c;x=a*3-b*c;b=a+)b*(x-;,依据语言的语义规则对语法分析得到的语法结构进行静态语义检查(确定类型、类型和运算合法性检查、识别含义与相应的语义处理及其它一些静态语义检查)，并用另一种内部形式（如中间代码）表示出来，或者直接用目标语言表示出来。凡在编译时可以确定的内容称为“静态”的；凡必须推迟到程序运行时才能确定的内容称为“动态”的。,1.2编译程序的工作过程语义分析,具体说来语义分析包括两方面：（1）静态语义检查。要检查标识符是否被定义，前后的数据类型是否一致。如上述源程序中x=a*3-b*c，要查看赋值号左右的变量和表达式的类型是否一致。（2）进行语义处理。针对不同类型的语句语义处理的方式不同。对说明语句，要将说明性语句中所定义的变量名字及其有关信息送进符号表，并为之分配存储单元；对可执行语句（如赋值语句、条件语句、循环语句等），就要生成可表达语义的中间代码。,分析到说明语句inta,b,c,x;后，应把变量a,b,c的类型int填入符号表中，分析到后，将产生以下四元式序列：运算符左运算对象右运算对象工作单元注释(1)*bcT1b*cT1(2)+aT1T2a+T1T2(3)*bcT3b*cT3(4)+T2T3T4a+b*c+b*cT4(5)=T4_aT4a(6)*a3T5a*3T5(7)*bcT6b*cT6(8)_T5T6T7a*3-b*cT7(9)=T7_xT7x语义翻译工作通常穿插在语法分析过程当中，因而语义翻译程序是由一组语法子程序构成的。,a:=a+b*c+b*c;x:=a*3-b*c;b:=a+)b*(x-,依据程序的等价变换规则，尽量压缩目标程序运行所需的时间和所占的存储空间，以提高目标程序的质量。代码优化分为两类：(1)与机器有关的优化：主要涉及如何分配寄存器。这种优化是在生成目标代码时进行的。(2)与机器无关的优化：包括对中间代码的优化，局部优化和循环优化。,1.2编译程序的工作过程代码优化,上述四元式经优化得：（1）（*，b,c,T1）（2）(+,a,T1,T2)（3）(+,T1,T2,T4)（4）(=,T4,_,a)（5）(*,a,3,T5)（6）(_,T5,T1,T7)（7）(=,T7,_,x)编译程序所产生的目标代码质量的高低，主要取决于这一阶段里代码优化程序功能的强弱。,如果语义分析时把源程序表示成中间形式而不是表示成目标指令，则由本部分完成从中间形式到目标指令的转换。如果语义分析时，已直接生成目标指令，则无需另外再做代码生成工作。,目标指令可能是绝对指令代码，或可重新定位的指令代码或汇编指令代码。该阶段的工作有赖于硬件系统结构和机器指令含义。,1.2编译程序的工作过程代码生成,登记源程序中出现的每个名字以及名字的各种属性。有些名字的属性需要在各个阶段才能填入。即编译各阶段的工作都涉及到构造、查找或更新有关的符号表，编译过程的绝大部分时间是用在造表、查表和更新表格的事务上。因此，编译程序中还应包括一个表格管理程序。,1.2编译程序的工作过程表格管理,源程序中的错误有语法错误和语义错误两种。,语法错误：源程序中不符合语法(或词法)规则的错误，它们可在词法分析或语法分析时检测出来。,语义错误：源程序中不符合语义规则的错误，一般在语义分析时检测出来，有的语义错误要在运行时才能检测出来。通常包括：说明错误、作用域错误、类型不一致等等。,1.2编译程序的工作过程出错处理,1.3编译程序的结构,1.4.1遍(趟，趟程),所谓一趟或一遍是指一个编译程序在编译时刻把源程序或源程序的等价物(中间程序)从头到尾扫描一遍并做有关的加工处理，生成新的源程序的中间形式或目标程序。,根据编译程序在完成翻译任务的过程中需要对源程序或其中间等价物扫描的遍数，可以把编译程序分为单遍扫描的编译程序(只需扫描一遍)和多遍扫描的编译程序(需扫描多遍)。,1.4编译程序的组织形式,单遍扫描的编译程序,多遍扫描的编译程序,例如，可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍：从而构成一个四遍扫描的编译程序。每遍完成上述某个阶段的一部分、全部或几个阶段的工作，并将结构存入外存储器里，作为下一遍的输入。,那么一个编译程序究竟应分成几遍，这和源程序语言的结构与目标机器的特征有关。分多遍完成编译过程的优点：可以使整个编译程序的逻辑结构更清晰，能减少对主存容量的要求，使优化工作更为充分，并为可移植创造条件。缺点：遍数多势必增加读写中间文件的次数，从而消耗过多的时间。总之，对一个具体的编译器，要确定用几遍扫描来完成，需要综合考虑各种因素，从中取得最佳方案。,前端主要由与源语言有关但与目标机器无关的那些部分组成，如词法分析、语法分析、语义分析与中间代码生成及部分代码优化工作。,后端主要包括编译中与目标机器有关的那些部分，如与目标机有关的代码优化和目标代码生成等。后端不依赖于源语言而仅依赖于中间语言。,可以通过改变编译程序的后端来实现编译程序的移植。,1.4编译程序的组织形式,编译的前端和后端,如果宿主机的内存空间有限，则需要外存辅助，这种情况下，编译程序可以按照下面的方式组织。首先在内存中开辟三个覆盖区（共享区）：一个存放最大的Comp1；一个存放输入对象（扫描对象）；一个存放加工结果（部分处理结果）。然后在外存开辟编译程序的暂存区和输入对象/加工结果的存放区。并且由“编译总控程序”负责控制和调度编译程序的各遍。,编译程序组织方式,构造编译程序可以用机器言语、汇编语言和高级语言。,高级语言的自编译性：一个语言可以用来编写自己的编译程序。,1.5编译程序的构造及相关技术P5,1.5.1高级语言的自编译性,通过一系列自展途径而形成编译程序的过程。,先对语言的核心部分构造一个小小编译程序(可用低级语言实现)，再以它为工具构造一个能够编译更多语言成分的较大编译程序。如此扩展下去，越滚越大，最后形成所期望的整个编译程序。,1.5编译程序的构造及相关技术,1.5.2编译的自展技术,将一个机器（宿主机）上的一个具有自编译性的高级语言编译程序移植到另一个机器（目标机）上。,利用A机器上的高级语言L编写能在B机器上运行的高级语言L的编译程序。,1.5编译程序的构造及相关技术,1.5.3编译的移植,1.5编译程序的构造及相关技术,1.5.2编译程序的自动化,在编译程序自动化进程中，开发早且应用广泛的是词法分析程序生成器和语法分析程序生成器。词法分析程序生成器：LEX。它输入的是正规表达式，输出的是词法分析程序。LEX的基本思想是由正规表达式构造有穷自动机。语法分析程序生成器：基于LALR（1）文法的YACC（YetA