《编译原理》第,章概述及高级语言

.,编译原理,曹琼联系方式：电话-Mail:caosfile,.,C语言程序,voidmain()intx,y,z;x=3;y=2;z=x+y;,movax,3movx,axmovax,2movy,axmovax,xmovbx,yaddax,bxmovz,ax.,汇编语言程序,300302304306308,.,为什么要学习编译原理？,更深刻地理解与运用高级程序设计语言。大型程序设计与软件工程的经典实例。理论与实践相结合的典范。为解决实际问题提供一种新的有效途径,.,语言种类ProgramminglanguagesScriptsDomain-specificlanguagesSQL,HTML,XML,.,语言参与者,.,学习本课程的目的和任务,加深对编程语言设计和实现的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用，提升自身的编程能力掌握编译程序的基本结构，掌握常用的编译技术和方法，将编译原理的理论和方法应用于一般的软件设计中培养团队协作能力,.,本课程的特点,(1)本课程理论性很强，学习时需要很强的逻辑思维能力(2)涉及的算法复杂，要深入地理解这些算法很困难(3)整个编译程序的构造方法非常精妙，就像一部走时精确的时钟，很多齿轮、部件协调地运转，以驱动指针准确地旋转；编译程序也是如此，一边扫描源程序，一边经过各个部件的运算，准确地输出为目标语言。(4)编译原理课程各个部分之间的独立性很强，包括词法分析、语法分析、存储的组织与分配、中间语言、语法制导翻译、代码生成与优化这几大部分。词法分析和语法分析是其中的重点，语言分析也是难点，需要掌握比较复杂的算法逻辑；其他部分相对来说知识性更强一些。各部分之间的方法也互相独立，在学习时，便于逐个击破。(5)考试考查的内容相对来说是很稳定的，绝大多数题目的解法都非常机械。,.,学习方法,(1)尽可能地掌握编译原理的思想，要站得高一点，尽可能理解算法的思想，而不是背固定的算法。应该尽力理解为什么要这样做，逐渐在头脑中建立起编译器的整体概念，而不是零零散散的一些算法。(2)很多题目的解法比较固定，要熟练掌握相应的具体方法。(3)多做习题,对于编译这样的学科，题目的规模很大，步骤繁多，而且前面的步骤一旦出错，后面都错。(4)要扎扎实实地牢记重要算法，配合大量的习题进行练习，达到拿到题目就可以动手做的地步。(5)一边学习，一边总结，关键是找差异：同一问题可以用多种方法来求解，不同方法适用于不同的文法，对文法的限制和要求，相应的表格的构造、使用等，各个方面的差异都要关注。(6)亲自动手实现书上的一些算法,完成实验指导书上给出的一个简单的编译程序，或者编译程序的一部分，这样能更灵活地掌握编译程序构造的精髓。,.,考核方法,平时成绩、作业完成：10%要求上课不迟到早退,不旷课,有事请假上课带笔和草稿本,记好笔记要求用大作业本,不能交单张纸,独立完成实验：20%要求程序可运行,并有相关设计和使用说明期末考试：70%闭卷形式,.,参考资料,编译原理（龙书）Alfred.Aho等第二版机械工业出版社程序设计语言编译方法肖军模第三版大连理工大学出版社编译原理吕映芝清华大学出版社编译原理技术与工具人民邮电出版社,.,编译技术的发展,1954年至1957年间，IBM的JohnBackus带领一个小组开发FORTRAN语言及其编译器。花了18个人年，非常辛苦。几乎与此同时，NoamChomsky开始自然语言结构的研究。Chomsky的研究导致了根据语言文法(grammar，结构规则)的难易程度以及识别它们所需的算法来为语言分类。在60年代和70年代进行的分析问题(parsingproblem，用于限定上下文无关语言的识别的有效算法)的研究，相当完善地解决了语言的识别的问题，现在它已是编译理论的一个标准部分。有穷自动机(finiteautomata)和正则表达式(regularexpression)与乔姆斯基的3型文法相对应。对它们的研究与乔姆斯基的研究几乎同时开始，并且引出了表示程序设计语言的单词的符号方式。接着又深化了生成有效的目标代码的方法，这就是最初的编译器，它们被一直使用至今。人们通常将其误称为优化技术(optimizationtechnique)，但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性，因此实际上应称作代码改进技术(codeimprovementtechnique)。当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器的自动构造。Lex与Yacc。在70年代后期和80年代早期，大量的项目都关注于编译器其他部分的生成自动化，这其中就包括了代码生成。这些尝试并未取得多少成功。,.,编译器设计最近的发展,与复杂的程序设计语言的发展结合在一起。如用于函数语言编译的Hindley-Milner类型检查的统一算法。编译器已成为基于窗口的交互开发环境(IDE)的一部分，IDE的标准并没有多少，但已对标准的窗口环境进行了开发。近年来对此进行了大量研究，但是基本的编译器设计近20年来没有多大的改变，现在正迅速地成为计算机科学课程中的中心一环。由多处理机的发展以及对并行处理的要求，最近的研究方向是并行编译。随着嵌入式应用的迅速增长，推动了交叉编译技术的发展；对系统芯片设计方法和关键EDA技术的研究，也带动了专用语言VHDL等及其编译技术的不断深化。,.,第一章引论,什么是编译程序编译过程概述编译程序的结构编译阶段的组合编译程序的构造方法,.,重点掌握：编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。,.,机器语言(machinelanguage)C70600000002汇编语言(assemblerlanguage)MOVX,2高级语言(high-levellanguage)X=2,为什么要使用编译器？,.,1.1什么叫编译程序,编译程序（Compiler）将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。功能,编译程序,源程序,目标程序,计算机运行,输入数据,结果,.,解释程序,解释程序（Interpreter）将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。功能,解释程序,源程序,输入数据,结果,.,操作系统汇编语言,编译程序所处的层次,计算机硬件,.,计算机中的语言层次和转换关系,.,1.1什么叫编译程序,翻译程序：能够将某种语言写的程序转换成另一种语言的程序，而且后者与前者在逻辑上是等价的。编译程序：是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序解释程序：接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。诊断编译程序、优化编译程序、交叉编译程序,.,对编译程序的一些说明,编译程序实质上是一个翻译程序，要注意等价变换本课程的任务就是讲解在这个转换过程中所涉及到的一些理论和方法，最后，使用这些理论和方法，自己编写一个小的编译器转换是一个总体的功能，要抓住总体结构，逐层细分，写编译器时要体现软件工程中软件设计的原则，自顶向下，逐层分解。编译器要完成的转换任务相当复杂，实现编译器时必须分步骤分阶段实现。分阶段实现的好处是能够简化程序的设计，当然也可以不分阶段实现。,.,与编译程序相关的程序解释程序(Interpreter)汇编程序(assembler)连接程序(linker)连接系统函数与系统资源装入程序(loader)重定位(relocation)预处理器(Preprocessor)编辑器(editor)Debugger,Profiler,ProjectManager,.,3、什么是编译原理编译原理是讨论编译程序设计的基本理论、基本概念、基本方法,.,1.2编译过程概述,1、逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成每个阶段把源程序从一种表示变换成另一种表示,.,按照词法分析、语法分析、语义分析等这种方式来划分阶段的原因是：每个阶段的复杂程度不同，所依据的理论基础不同，实现时采用的方法也不同。主要是方便理解和实现。划分阶段的依据是什么？每个阶段所实现的功能相对独立。,.,第一阶段：词法分析,任务:从左到右扫描源程序，识别出每个单词附加任务：a、滤掉空格b、识别单词单词符号是语言的基本组成成分词法分析的工作主要依据语言的词法规则，描述词法规则的有效工具是正规式和有限自动机。单词的种类：（1）标识符（2）关键字（char、int、if、else、switch、while、for等）（3）运算符（即运算符号+、*、/、,例:,.,第二阶段：语法分析,任务:在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。根据规则判定：赋值语句：标识符：表达式表达式：标识符、常数是表达式；表达式的运算也是表达式例：识别符号串id1:=int1+id2*id3+id2*id3（即result:=5B*CB*C）是一个赋值语句，而int1+id2*id3+id2*id3（5B*CB*C）是一个表达式,.,语法分析所依据的是语言的语法规则，表示语法规则的工具是上下文无关文法,用下推自动机实现。,id1:=int1+id2*id3+id2*id3,.,第三阶段：语义分析和中间代码生成,任务：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)。静态语义审查变量定义类型匹配类型转换例：C:=A*B(检查C与、类型)中间代码的翻译中间代码有多种形式，如：四元式:(运算符，运算对象1，运算对象2，结果),.,例：对赋值语句：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,.,第四阶段：代码优化,任务：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。代码的优化依据的是程序的等价变换规则。,.,第五阶段：目标代码的生成,任务：把中间代码(或经优化的中间代码)变换成特定机器上的低级语言代码。依赖于机器的硬件系统结构和机器指令的含义目标代码可以是：绝对指令代码、可重定位的指令代码、汇编指令代码,.,1.3编译程序的结构,由左图可以看出，词法分析是实现编译器的基础，语法分析是实现编译器的关键。因此按照这个顺序来实现编译器每一步的实现都依赖于一定的理论基础。数学，尤其是离散数学是程序设计方法学的理论基础,.,1.3编译程序的结构(续),几个概念符号表：登记源程序中出现的名字以及名字的各种属性遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成,.,为什么生成中间代码,.,1.3编译程序的结构(续),(1)记号(token)当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。,编译程序中的主要数据结构:,.,编译程序中的主要数据结构,(2)语法树（syntaxtree）如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。,.,(3)符号表（symboltable）这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分析程序将增加数据类型和其他信息；优化阶段和代码生成阶段也将利用由符号表提供的信息选出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。,编译程序中的主要数据结构:,.,(4)常数表（literaltable）常数表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也十分重要。但是，在其中却无需删除，这是因为它的数据全程应用于程序而且常量或字符串在该表中只出现一次。,编译程序中的主要数据结构:,.,(5)中间代码（intermediatecode）根据中间代码的类型（例如三元式代码）和优化的类型，该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允许简单重组的表示。,编译程序中的主要数据结构:,.,(6)临时文件（temporaryfile）计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足够信息用以处理翻译）解决了。,编译程序中的主要数据结构:,.,1.4构造编译程序,一般生成编译程序的方法有：1.直接用机器语言编写编译程序2.用汇编语言编写编译程序注：编译程序核心部分常用汇编语言编写3.用高级语言编写编译程序注：这是普遍采用的方法4.自编译5.用编译工具自动生成:LEX(词法分析)与YACC(用于自动产生LALR分析表)6.移植（同种语言的编译程序在不同类型的机器之间移植）,.,1.4构造编译程序(续),构造编译程序要掌握以下几方面的内容：源语言：理解其结构和含义目标语言：必须清楚硬件的系统结构和指令的格式等编译方法,.,.,编译技术的应用,语言的结构化编辑器:Turbo-Edit、editplus和Ultraedit等语言程序的调试工具语言程序的测试工具高级语言之间的转换工具交叉编译程序,.,作业1：,将13题写在作业本上，思考第5题。1.什么是编译程序？2.编译过程分哪些阶段？各阶段的功能和任务是什么?3.写出C语言中字符集、单词、数据类型、各种表达式、语句和程序的组成4.自学2.5节5.设计一种计算机语言，该语言可以用来解决实际问题，比如，该语言的应用等。,.,第二章程序语言的语法描述(P25),掌握：上下文无关文法基本概念推导、句型、句子、语言语法树文法的二义性理解：文法的语言生成过程,.,以C和PASCAL为例复习高级语言1语言的基本字符集的定义(字母,数字,界符)2单词集的定义3数据类型的定义4表达式的定义5语句的定义6程序定义PASCAL和C的主要区别,.,程序语言定义的基本概念,1.字母表：是元素的有穷非空集合2.符号：字母表中的每个元素，因此字母表也称为符号集。不同的语言可以有不同的字母表，例如英文的字母表中26个字母、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号组成。符号是该语言能识别的符号，字母表是该语言能识别的所有符号的全体（字符集）。,.,基本概念(续),3.符号串:由字母表中的符号组成的任何有穷序列称为符号串，例如001110是字母表=0，1上的符号串.字母表A=a,b,c上的一些符号串有：a,b,c,ab,aaca等。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。符号串STR表示“由符号S、T和R，并按此顺序组成.,.,基本概念(续),4.符号串的运算a.字符串的连接：字符串称为字符串和的连接符号串的长度:符号串中符号的个数，例如:某符号串中有m个符号,则称其长度为m，表示为x=m，如001110的长度是6。空符号串:即不包含任何符号的符号串，用表示，其长度为0，即=0。用*表示上所有的符号串的全体(长度为0，1，2，)。,.,集合的运算b.*的子集U、V的积：UV=|U&V长度相加即:集合UV中的符号串是由U和V的符号串连接而成。c.集合的方幂：n个相同符号连接Vn=VVVV.V规定V0=d.闭包、正则闭包的运算,.,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,使用*表示上的一切符号串（包括）组成的集合。称为的闭包。上的除外的所有符号串组成的集合记为+。称为的正闭包。,U=aa,bbV=00,11则UV=?V=0,1V*=?V+=?,.,文法,文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合文法是被用来精确而无歧义地描述语言的句子的构成方式.文法描述语言的时候不考虑语言的含义。,.,引例,例1：有如下规则(表示由组成)|我大学生是|现要求根据如上规则得出句子：我是大学生=我是大学生,.,句子“我是大学生”也可以如下图示分析,在有规则的情况下，每一次用上述规则的右边去替换左边，得到“我是大学生”是符合上述规则的句子,.,上下文无关文法的形式定义,由四部分组成：终结符号：是组成该语言的最基本的符号，是不可再分的基本符号,如保留字、标识符等。非终结符号：规则中用尖括号括起来的符号，表示一些语法成分，可以推导出其他的语法成分,表示一定符号串的集合，是一个类，如表达式。开始符号：规则中的一个特殊的非终结符号，语言中的句子都从它开始推导,如程序、句子产生式：定义语法成分的规则，其中：,.,文法的形式定义(续),一个文法G抽象地表示为四元组G=（Vn,Vt,P,S）其中Vn表示非终结符号Vt表示终结符号，VnVt=(字母表)，VnVt=S是开始符号，P是产生式，形如：(V+且至少含有一个非终结符号，V*),.,上例中：G=（Vn,Vt,P,）Vn=（，）Vt=(我，是，大学生)P=,|我大学生是|,.,产生式的形式为：A,左部符号，非终结符,右部，可以含有非终结符和终结符,又称为一条规则有时一个产生式不足以描述该语法范畴，就用多个产生式，如算术表达式的描述为：(递归定义)EE+EEE*EEi相同左部的一个右部又称一个候选式,.,上下文无关文法所定义的语法成分独立于它可能出现的环境，即不考虑上下文。,.,算术表达式的文法定义,变量是表达式表达式+表达式是表达式表达式*表达式是表达式(表达式)是表达式,EE+EEE*EE(E)Ei,EE+E|E*E|(E)|i,.,上下文无关文法产生句子的方法:从文法的开始符号出发,反复连续使用产生式,对左边的非终结符进行替换和展开例：表达式定义规则,EE+EEE*EE(E)Ei,(i+i),E=(E)=(E+E)=(i+E)=(i+i),.,推导:连续使用产生式右部去替换左部某个非终结符的过程,得到的连续序列称为一个推导。直接推导：又称一步推导(用符号=表示),就是用某条规则的右部去替换该规则的左部,.,几个概念的形式定义,直接推导:如果是文法G=（Vn,Vt,P,S）的产生式，和是*中的任意符号，若有符号串v,w满足：v=,w=,则说v直接产生w，(w是v的直接推导)记作：v=w例：S01,0S0=0010(直接推导,)如果存在v=w0=w1=w2.=Wn=w(n0)，则称v推导出w（长度为n），记作v=w(至少一步)若有=w或v=w，则记作v=w(0步或若干步),*,+,.,例3:G=(E,i,+,*,(,),P,E)(1.1)P：EE+E|E*E|(E)|i表达式(i)和(i+i)*i的推导：,E(E)(i)EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i,EE0步推导E(i+i)*i6步推导E(i+i)*i6步推导E(E)直接推导,.,句型：设(s)是一文法，如果符号串x是从开始符号推导出来的，即有s=x,则称x是文法G(s)的一个句型。即:任何由开始符推导出来的符号串都是句型。句子：若x仅由终结符号组成，则称x为G(S)的句子,*,练习文法G：SaAcB|BdAAaB|cBbScA|b写出句型aAcbBdcc和句子acabcbbdcc的推导过程。,.,文法G所产生的语言定义为：L(G)=x|S=x,其中S为文法的开始符号，xVt*。即:一个文法G可以推导出的所有句子构成的一个集合,就确定了一个语言。,*,.,例2.1(P30)考虑文法G1:它定义了什么语言。,SbAAaA|a,推导过程：S=bA=baS=bA=baA=baa.S=bA=baA=baa,归纳得：L(G1)=ban|n1,.,练习：文法(A,B,S,a,b,c,P,S)SAc|aBAabBbc写出(G)的全部元素,L(G)=abc,.,例2.2(P30)考虑文法G2:它定义的语言是：,SABAaA|aBbB|b,L(G2)=ambn|m,n1,.,思考：构造一个文法G3使得：,L(G3)=anbn|n1,SaSbSab,a,b的个数相同,则文法G3为：,.,文法等价：若文法G1和文法G2所产生的语言相同，即L(G1)=L(G2)，则称文法G1和文法G2等价。,.,例：有如下两个文法，判断它们是否等价？G1=（S，0，S，S0S，S0）G2=（S，0，S，SS0，S0）,S0S0S00S0S00S0000,L(G1)=0n|n1,对于G2：,对于G1：,SS0S000000,L(G2)=0n|n1,G1G2，但L(G1)=L(G2)，文法G1和G2等价,.,例3:G=(E,i,+,*,(,),P,E)P：EE+E|E*E|(E)|i表达式(i+i)*i的推导过程：(1)EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i(2)EE*EE*i(E)*i(E+E)*i(E+i)*i(i+i)*i,得到一个语言，是通过利用所有的产生式推导出所有可能的句子，构成一个集合。但是一个句型到另一个句型(句子)的推导过程不是唯一的。,.,最左推导:在整个推导过程中,任何一步推导=都是对中最左边的非终结符进行替换。最右推导:,在推导之前确定推导的顺序，是对句子进行确定性分析所必须的,例3：G=(E,i,+,*,(,),P,E)P：EE+E|E*E|(E)|i(i+i)*i的最左推导过程：EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i最右推导过程：EE*EE*i(E+E)*i(E+i)*i(i+i)*i,.,用语法树表示上下文无关文法的推导,语法树：推导的形式化表示，有助于理解句子语法结构的层次每个结点都有一个标记，该标记属字母集中的一个符号，根由开始符号标记。当某个非终结符被它的某个候选式所替换时，就产生相应的下一层的结点，候选式中自左至右的每个符号对应一个新的结点，并标记它，画出其与父结点之间的连线。,.,例：对文法G=(E,i,+,*,(,),P,E)P：EE+E|E*E|(E)|i句子(i+i)*i的语法树：,在语法树的推导过程中的任何时刻，没有后代的端末结点自左至右排列起来就是一个句型一棵语法树表示了一个句型很多可能的不同推导过程。(包括最左推导和最右推导),.,例3：G=(E,i,+,*,(,),P,E)P：EE+E|E*E|(E)|i句子(i*i+i)的语法树：(1)E(E)(E+E)(E*E+E)(i*E+E)(i*i+i),(2)E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i),