编译原理课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,CompilerPrinciples,*,编译原理课件,1,CompilerPrinciples,第一讲 引论,课程信息,编译程序概述,高级语言的语法描述,1.,课程信息,一、课程名称：编译原理,基本内容是介绍编译程序构造的基本原理、方法和技术，包括词法分析、语法分析、语义分析与中间代码产生、代码优化及目标代码产生等。简言之，就是介绍如何将源程序翻译成目标代码程序。,3,CompilerPrinciples,二、课程性质：,专业基础课，必修,编译程序（器）出现于上世纪,50,年代后期（第一个高级语言,1958,年）,60,年代,70,年代是研究高峰期,60,年代中期开始在高校中开设课程,80,年代开始作为计算机科学与技术专业的必修基础课程,4,CompilerPrinciples,5,CompilerPrinciples,三、课程特点,：,充分体现了计算学科中抽象、理论和设计三个学科形态,该课程涉及多门课程的内容综合运用，,涉及面广，内容庞杂，学习艰难,程序设计语言、计算机体系结构、语言理论及算法等,数据结构、离散数学,该课程涉及的原理、方法和技术具有十分普遍的意义,每一个计算机科学与技术工作者的职业生涯中反复用到，“享用一辈子”,这儿接受的训练很难在其他地方获得，如：抽象与形式化方法、局部与全局优化方法、构造技术、证明方法等,6,CompilerPrinciples,四、学习该课程的意义,编译程序是计算机系统不可缺少的重要组成部分,对程序设计语言的设计与实现能有更深刻的理解,对程序设计语言有关理论有所了解,从宏观上把握程序设计语言,掌握了编译原理后，就不能再说：“某语言未学过，所以不会”,有助于快速理解、定位和解决程序调试与运行中出现的问题,7,CompilerPrinciples,编译方法与技术有着广泛应用,安全技术、程序理解、软件逆向工程、应用软件与软件工具开发、软件测试与验证等,编译课程蕴含着计算学科中解决问题的思路、抽象和方法，这些与高等数学一样，使你“享用一辈子”,课程所涉及的内容至今非常活跃,自然语言的翻译,软件移植,网络安全,形式化方法,形式语义学等,8,CompilerPrinciples,鉴于以上所述，作为计算机科学与技术专业的学生必须学习和掌握编译原理这门课程，当然由于其综合性、处理问题的复杂性等，学习起来有一定难度，这就需要艰苦奋斗的精神和良好的学习方法,9,CompilerPrinciples,五、学习方法,编译程序的构造是一个庞大而复杂的系统工程，无论是概念还是理论、方法，对初学者来说许多都是新的，学习起来会感到困难大一些，这一点必须有充分认识，为此建议学习方法上注意以下几点：,10,CompilerPrinciples,课前预习，课堂认真听讲，课后复习加深理解，特别要经常有意识地将前后内容联系起来融会贯通。,因为编译程序是一个庞大的程序系统，讲解过程必须“分而治之”（,这也是人们处理复杂问题的基本方法,），这就要求大家在学习过程中，始终以处理过程为主线，把前后联系起来考虑。,11,CompilerPrinciples,理论联系实际亲自动手，构造一个演示性编译程序，至少要完成扫描器和语法分析器，以及语法制导翻译产生中间代码,（,课程设计,）,认真完成作业，进一步巩固并加深理解所学知识,特别要下功夫认真学习如何从实际问题进行抽象并形式化，最终建立实际问题的模型（上升为理性认识），并借助模型进一步设计实现，这将对你能力的提高大有益处,12,CompilerPrinciples,六、教材,程序设计语言编译原理（第3版）国防工业出版社 陈火旺等,内容详实丰富，理论与技术相结合,较为全面介绍了编译程序构造的基本原理、方法与技术,厚度适中,大多数院校一直采用，硕士入学考试参考书,所谓教材，实为第一参考书而已,13,CompilerPrinciples,七、参考书目,1.编译原理,第2版,赵建华等,译，, A.V.Aho,M.S.Lam,Rav,i,Sethi, J.D.Ullman著，机械工业出版社,，2009,；,2.编译原理,课程设计,王雷等著，,机械工业出版社,，2005,；,八、,期末总评,平时成绩：,1,0%,课程设计,：,2,0%,期终考试：70%,14,CompilerPrinciples,15,CompilerPrinciples,2.,编译程序概述,一、翻译程序,（,Translator,）,能够把一种语言程序（称为源语言程序）转换成,逻辑上等价的,另一种语言程序（称为目标语言程序）的程序,16,CompilerPrinciples,任何非机器语言程序都需要翻译程序,翻译程序的工作就是进行等价变换（映射）,两个程序逻辑上等价是指对相同输入得到相同的输出,翻译程序,解释,程序,汇编,程序,编译,程序,17,CompilerPrinciples,汇编程序,(Assembler),把汇编语言程序转变为机器语言程序的翻译程序,解释程序,(Interpreter),把源程序作为输入接收，边解释边执行的翻译程序,源,程,序,数,据,解,释,程,序,结,果,18,CompilerPrinciples,编译程序,将高级语言程序转变为低级语言程序的翻译程序,源,程,序,编译,程,序,目,标,程,序,19,CompilerPrinciples,20,CompilerPrinciples,编译程序又可根据用途和侧重点的不同，进一步分类为：,诊断编译程序,(Diagnostic Compiler),专门用于帮助程序开发和调试的编译程序,优化编译程序,(Optimizing Compiler),着重于提高目标代码效率的编译程序,交叉编译程序,(Cross Compiler),能够产生不同于其宿主机机器代码的编译程序,可变目标编译程序,(Retargetable complier),无须重写与机器无关部分就能改变目标机的,编译程序,21,CompilerPrinciples,二、与编译程序相关的程序,本讲义只介绍编译程序（器）构造的基本原理、方法与技术，但在一个完整的语言开发（或称程序设计）环境中，除了编译器这一主要工具外，还需要其他一些工具，如编辑器、连接器、装入程序等。现代计算机系统常将这些相互独立的程序设计工具集成起来，构成一个集成化的程序开发环境，以提高程序设计效率和程序的质量。如,Turbo C,、,Visual C+,等语言环境都是集成化的程序设计环境。而,Ada,语言的集成环境是这方面的典型代表。,22,CompilerPrinciples,如Ada语言的集成环境是一个分层的程序开发环境,编,译,程,序,M,APS,E,编,辑,程,序,连,接,程,序,宿,主,机,O,S,A,P,S,E,工,具,界,面,用,户,界,面,KAPSE,调试程序,配置管理程序,命令解释程序,其他工具,23,CompilerPrinciples,这儿要强调的是：尽管本课程只介绍编译的基本理论、方法和技术，但这些基本理论、方法与技术对其他工具的构造同样起作用！,24,CompilerPrinciples,编辑器,(Editor),完成源程序输入、编辑并产生标准文件（如,ASCII,文件）的程序。,近来已与编译器和其他程序捆绑进一个交互开发环境,IDE,中,尽管这样的编辑器仍生成标准文件，但会转向正被讨论的程序设计语言的格式或结构（称为基于结构的），且已包含了编译器的某些操作；因此在程序编写时而不是编译时就可得知错误，甚至也可调用编译器,25,CompilerPrinciples,预处理程序,(Preprocessor),在真正翻译开始之前产生编译程序的输入的程序,处理宏及注释：宏是被经常使用的较长结构的缩写,处理文件包含：把头文件包含到程序正文中（如,C,的文件包含,include ,）,“理解”预处理器：把现代控制流和数据结构机制添加到比较老式的语言中,语言扩充：通过大量的内部宏定义来增强语言的能力，如,Equel,语言是一种嵌套在,C,语言中的数据库查询语言,26,CompilerPrinciples,连接程序,(Linker),又称为连接编辑器。将分别在不同的目标文件中编译（或汇编）的代码、所用标准库函数的代码以及操作系统提供的资源（如存储分配程序及输入,/,输出设备）收集到一个可直接执行的文件中的程序,装配程序,(Loader),完成程序的装入和连接编辑两项功能。 装入过程包括读入可重定位机器代码、修改可重定位地址、并将修改后的指令和数据放到内存的适当位置。 装入程序使得可执行代码更加灵活,27,CompilerPrinciples,调试程序,(Debugger),可在被编译了的程序中判定执行错误的程序,它经常与编译程序一起放在,IDE,中,运行一个带有调试程序的程序与直接执行不同，这是因为调试程序保存着所有的或大多数源代码信息，它可以在预先指定的位置（断点,BreakPoint,）暂停执行，并提供有关信息（已调用的函数、变量名的当前值等）,28,CompilerPrinciples,其他有关的还有,描述器,(Profiler),执行中搜集目标程序行为统计的程序,项目管理程序,(Project Manager),如,Unix,系统中的,SCCS,（源代码控制系统）和,RCS,（修正控制系统）和汇编程序等,综上所述可给出一个“语言处理系统”的图示：,29,CompilerPrinciples,我们这个课只介绍编译程序这一部分,30,CompilerPrinciples,三、编译过程与编译程序结构,1.,编译过程：,输入 输出,（高级语言源程序） （低级语言目标程序,）,编译程序工作过程如下：,识别出一个个的单词,分析句子的语法结构,分析句子的语义并进行初步翻译,对初步翻译进行优化,整理出目标程序,对以上过程进一步整理可得如下编译程序结构总框：,编译程序,31,CompilerPrinciples,2.编译程序总框：,词法分析器,语法分析器,语义分析与中间代码产生器,优化器,目标代码生成器,单词符号,语法单位,中间代码,中间代码,出,错,处,理,表,格,管,理,源程序,目标代码,32,CompilerPrinciples,3.,五个阶段简介,第一阶段：词法分析,依据语言构词规则，识别出一个个单词（符号）,单词种类,保留字：,for if while,算符： ,界符： ， ；（）, ,标识符：,a1 a2 pi,常数：,9 1024 4.8 6E6,无穷性,有穷性,思考：识别有穷集合 VS 识别无穷集合,33,CompilerPrinciples,词法分析工作由,词法分析器（或称扫描器）完成。,扫描器输出为等长度的单词符号（二元式）流。,例：,P,o,s,i,t,i,o,n,=,i,n,i,t,i,a,l,+,r,a,t,e,*,6,0,词,法,分,析,（,扫,描,器,）,保,留,字,表,(06,Position),(11,),(06,initial),(12,),(06,rate),(13,),(07,60的二进制),34,CompilerPrinciples,第二阶段：语法分析,依据语言的语法规则，把扫描器提供的单词符号串分解成各种语法单位（范畴），如“短语”、“子句”、“句子”乃至“程序”。同时进行语法检查，以确定输入串是否正确，该工作是由语法分析器完成的。,如：Position=initial+rate*60 是一个“赋值表达式”（C语言中）,Position,=,表达式,表达式,表达式,+,表达式,标识符,表达式,*,表达式,initial,标识符,常数,rate,60,标识符,35,CompilerPrinciples,第三阶段：语义分析与中间代码产生,针对各类不同的语法范畴，按语言的语义规则进行语义分析和初步翻译工作，产生某种中间语言形式的中间代码（即一种结构简单，含义明确的记号系统）。该阶段工作通常包括两个方面的工作：,对每种语法范畴进行静态语义检查，包括：,变量是否定义过,类型是否正确,是否用了,0,作除数, ,36,CompilerPrinciples,将语法范畴翻译成某种形式的中间代码，如四元式：,Op,ARG1,ARG2,Result,rate,60,T1,initial,T1,T2,=,T2,Position,37,CompilerPrinciples,第四阶段：优化,对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出高效（节省时、空）的目标代码，这一任务是由优化器来完成的,根据优化的范围不同，可分为：局部优化，循环优化和全局优化,一个循环优化的例子：,38,CompilerPrinciples,1,K,I,M,J,100,K,J,N,10,K,T1,1,K,I,T1,M,J,100,K,10,K,T2,M,10,M,J,T2,N,N,10,N,K,1,K,K,1,K,循环,For(k=1;k=100;k+) M=I+10*k; N=J+10*k;,优化前用了两个临时工作单元(T1,T2),优化后没有用临时单元,优化前循环体中要做300次加、200次乘， 优化后循环体内只做300次加,39,CompilerPrinciples,第五阶段：目标代码生成,把中间代码翻译成目标代码,显然这阶段要依赖于硬体系统结构和指令系统,涉及存贮分配、寄存器调度,这一阶段工作是由代码生成器完成的,说明：,以上各阶段（或称工序）并不是截然分开 的，尤其编译程序结构十分复杂、体积相当庞大，所以有时人们把几个阶段的工作有机地组合在一起、穿插进行，构成遍。,40,CompilerPrinciples,遍（,Pass,）：对源程序或源程序的中间代码从头到尾扫描一次并做相应处理加工,分遍的好处是结构清晰、节省内存（每遍都从外存获取前一遍的结果作为开始，工作结果仍记入外存，每遍几乎可使用全部内存）,分不分遍、如何分遍要视具体情况,计算机内存容量、源语言的繁简、从事编译程序设计人员的情况等,41,CompilerPrinciples,如,某,PL/0编译程序的结构,词法分析程序,语法语义分析程序,代码生成程序,PL/0源程序,目标程序,表格,管理,程序,出错,处理,程序,42,CompilerPrinciples,4.前端与后端,：概念上讲，编译程序的五个阶段可进一步划分为前端和后端：,前端：主要由与源语言有关而与目标机无关的部分组成，包括词法分析、语法分析、语义分析和中间代码产生。代码优化一般也包含在前端。,后端：主要由与目标机有关的部分组成，包括目标代码生成和与目标机有关的优化等。,43,CompilerPrinciples,源,程,序,词法分析,语法分析,语义分析和中间代码产生,中,间,语,言,中间代码优化,目标代码生成,目标代码优化,目,标,语,言,前端,后端,44,CompilerPrinciples,划分前端和后端，就可以仅改写后端而生成不同目标机上的目标程序，当然也可考虑对不同语言仅稍加改变前端而产生相同的中间代码，经同一后端生成相同目标机的目标代码。就目前来说，针对相同中间代码适应不同目标机的工作较多，如Ada语言的APSE(Ada程序设计环境)中使用的Diana中间代码，Java语言定义的虚拟机代码Bytecode中间语言，都是定义良好的中间语言。,45,CompilerPrinciples,Java,的传统环境,Java源程序,(.java),编译环境,Java编译器,Java字节码,(.class),Java 字节码,（本地或,网络传输）,运行环境,类加载程序,字节码验证,Java类库,Java解释器,即时编译器,Java虚拟机,硬件,46,CompilerPrinciples,5.,表格与表格管理,表格记录源程序中的各类有用信息,名字、函数、标号、过程、数值等,每个阶段的工作都要与表格打交道：查、填、改等,表格的结构与处理方法：统一的大表与分类的小表,统一大表,名字栏为主栏（关键字栏），信息栏又分成若干子栏,种属、类型等,NAME,INFORMATION,47,CompilerPrinciples,分类小表：每类一张表，如：,符号名表,(SNT),常数表,(CT),3.1415926,48,X,哑元 实型,A,数组 整型,48,CompilerPrinciples,DO,编号(03),L1,入口地址,Swap,二目子程序,入口地址,入口表(ENT),标号表(LBT),基本字表,(KWT),49,CompilerPrinciples,6.出错处理：,这是编译程序的又一重要组成部分，因为编译的各个阶段都有可能发现源程序中的错误。一旦发现这样或那样的错误，就应把错误的性质及位置报告给用户，并且使编译能继续下去。,思考：,如何准确地报告错误,如何从错误中恢复过来,50,CompilerPrinciples,四、编译程序的构造过程,1.,需求分析，确定语言文本,(1),确定语言的种类：,按语言范型分类，当今大多数程序语言可分为四类：,过程式,(,强制式语言,),：命令驱动，面向语句，如,FORTRAN,、,PASCAL,、,Ada,及,C,等,函数式,(,应用式,),语言：功能驱动，面向函数，如,LISP,、,SNOBOL,及,ML,等,逻辑式,(,基于规则的,),语言：依据条件进行逻辑推演，如,Prolog,等,OO,语言：支持封装性、继承性、多态性及动态聚束等，以对象为运行单位，如,Smalltalk,、,Java,、,C+,等,51,CompilerPrinciples,通过用户提供的应用范围，决定采用何种语言。,例如：,偏重于科学计算的则选用,Fortran,；,偏重于符号处理的则选用,Lisp,或,Snobol,；,偏重于事务处理的则选用,Cobol,或数据库管理语言；, ,52,CompilerPrinciples,(2),深刻理解语言的结构、语法及语义,这就是说不仅仅是用程序设计语言编几个程序的问题，而是要在语法和语义方面下一些功夫。具体说来有以下几个方面：,程序语言的定义：,任何程序语言都是某个确定的字符集上的符号按照一定规则组成的有穷序列。,这里所谓的规则是从两个方面来谈的：,语法规则：用于形成和产生一个正确的程序的,一组规则。,语义规则：用于定义程序意义的一组规则。,53,CompilerPrinciples,例如：,从语法的角度看，标识符和名字是一个东西，都是以字母开头的字母数字串；但从语义的角度看，标识符是一个没有任何意义的字符序列，而名字却有确定的意义和属性，而且具有一定的作用域和定义域，即有局部和全部之分。,又如：,程序从语法角度看，是一些语法范畴构成的如下层次结构：,54,CompilerPrinciples,程序,分程序或子程序（过程、函数等）,语句,表达式,数据引用,算符,函数调用,而从语义的角度来说，程序是描述一定的数据结构及其处理过程。,55,CompilerPrinciples,程序结构：,现代高级语言程序通常由若干子程序段（过程、函数等）构成，许多语言还引入了类、程序包等更高级的结构。,例如，,Fortran,、,C,程序是块结构的；,Pascal,程序是过程嵌套的；,Algol,既有分程序嵌套，又有过程嵌套；,Java,与,C+,是面向对象的，它们很重要的方面是类和继承的概念，同时支持多态性和动态聚束等特性；而在,Ada,中引入了程序包，它可以把数据和操作代码封装在一起，支持数据抽象。,（详见教材,P,15-18,）,56,CompilerPrinciples,语言的基本成分：,包括数据类型、表达式、语句、过程或函数等，这些在学习语言课时都已经学过了，但从编译的角度出发，应如何了解这些基本成分呢？,初等数据类型：牵扯到存储空间的问题；,结构数据类型：牵扯到下标、维数、存放方式、,分配时间,-,动态与静态等；,表达式：牵扯到运算分量、运算符、形成规则、,运算顺序等；,语句：顺序、控制、循环等；,过程与参数传递：传地址、传值、传名、得结果,等；,存储管理：静态存储分配、动态存储分配；,57,CompilerPrinciples,2.,由程序设计环境确定编译程序构造的方式和方法,最早是直接使用机器语言或汇编语言,现在一般使用高级语言,Pascal,或,C,语言好处：,编译方式还是解释方式,便于阅读、理解和移植,提高程序设计效率,易于查错和修改,58,CompilerPrinciples,任何一个编译程序至少要涉及三种语言：源语言（,S,）、目标语言（,T,）和编译程序实现语言（,I,），可用如下,T,型图来表示三者之间的关系：,S,T,I,59,CompilerPrinciples,Ada,语言,A,代码,Ada,语言,A,代码,C,C,A,代码,A,代码,A,代码,用C语言编写Ada编译程序,如若A机上已经有了一个用A机器语言（称A代码）实现的C语言编译程序，则可用C语言作为工具编写Ada语言的编译程序。这样Ada语言的编译程序经过C语言编译程序编译后就可得到A代码的Ada语言编译程序。可图示如下：,60,CompilerPrinciples,现在常用构造编译程序的方式除高级语言实现外，经常还用：,自展（自编译）：类似于滚雪球。先确定一个非常简单的核心L,0,，用低级语言写出其编译程序C,0,。再把L,0,扩充为L,1,，,，,并用L,0,来编写L,1,的编译程序。如此逐渐扩展下去，可得到一个系统编程语言族：而L,k,便是我们要编译的语言，其编译程序C,k,可用L,k-1,编写。这种滚雪球式的自展方法可大大减少开发工作量。,61,CompilerPrinciples,交叉编译：在机器,A,上产生机器,B,的目标代码 ，这种编译程序称为交叉编译。这儿,A,称宿主机，,B,称为目标机。这种情况一般是宿主机上有丰富的工具软件，而,B,机上没有任何高级语言可用。图示为：,C,B,代码,C,B,代码,C,C,B,代码,B,代码,A,代码,62,CompilerPrinciples,移植：如果一个程序能比较容易地从一台机器上搬到另一台机器上运行，则称其为可移植的，移植一个程序的工作量要远小于开发它的工作量才有意义。 显然一个编译程序要可移植，则其前端与后端的界面要清晰、简单，这样仅需改写后端即可。改写后亦可通过交叉编译的方法得到。,63,CompilerPrinciples,编译程序生成器：根据语言要求、设计实现的算法，能自动产生编译程序的工具软件。可图示为：,64,CompilerPrinciples,3.,确定编译方法：,本课程要介绍若干方法，但不可能全采用，只能根据语言特点采用其中一种或二种,4.,总体设计：,分不分遍、分几遍、前端与后端接口并画出总框,5.,详细设计：,进一步细划总框,6.,实现及调试：,采用何种方式实现、分调与连调等,65,CompilerPrinciples,本节目的：,为语言的语法描述寻求形式化工具,工具就是对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）,形式化工具就是将形式语言抽象地定义为一个数学系统。,“,形式,”,是指这样的事实：语言的所有规则是以什麽符号串能出现的方式来陈述。,3.,高级语言的语法描述,66,CompilerPrinciples,本节主要内容,预备知识,上下文无关,文法及其语言的形式定义,文法的等价性,语法树及文法二义性,文法的类型,语法分析的一些思考,67,CompilerPrinciples,一、预备知识,1.,文法的直观概念,当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷多个句子的语言来讲，存在着如何给出它有穷表示的问题。,以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明,(,或者定义,),句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语。,例如：,68,CompilerPrinciples,“我是大学生”是汉语的一个句子,对该句子我们可以通过下列一组规则描述：,句子=主语谓语,主语=代词名词,代词=,我,你,他,名词=,王明,大学生,工人,英语,谓语=动词直接宾语,动词=,是,学习,直接宾语=代词名词,有了这组规则以后，可按如下方式导出句子：,先找=左端的带有句子的规则，并将它用,=右端的符号串代替，于是表示成：,69,CompilerPrinciples,句子,主语,谓语,然后在得到的串,主语,谓语,中，选取,主语,或,谓语,，再用相应规则的,=,右端代替之。比如，选取了,主语,，并采用规则,主语,=,代词,，那么得到：,主语,谓语,代词,谓语,依此类推，句子“我是大学生”的全部导出过程是：,句子,主语,谓语,代词,谓语,我,谓语,我,动词,直接宾语,我是,直接宾语,我是,名词,我是大学生,70,CompilerPrinciples,“,我是大学生,”,的构成符合上述规则，而,“,我大学生是,”,不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据。换句话说，这些规则看成是一种元语言，用它描述汉语，仅仅涉及汉语句子的结构描述。,这里,“,”,读作,“导出”,或,“派生出”。,而,“,:=”,（,通常又简记为,“,”,）,读作“,定义为,”或“由,组成”，而每一条规则又称作是,产生式,或重写式。这样的一种描述形式就称作是,BNF,（,Backus-Naur Form,）。,71,CompilerPrinciples,例,：,赋值表达式可描述为,=,|,a1,|,b123,|,salary,|,stu_age,18,|123|4,.,5|,+ |- |* |/,72,CompilerPrinciples,2.,语言概述,语言,是由句子组成的集合。,汉语,-,所有符合汉语语法的句子的全体。,英语,-,所有符合英语语法的句子的全体。,程序设计语言,-,所有符合该语言语法的程序的全体。,每个句子构成的规则,研究语言 每个句子的含义,每个句子和使用者的关系,73,CompilerPrinciples,研究程序设计语言,每个程序构成的规则,每个程序的含义,每个程序和使用者的关系,语言研究的三个方面,:,语法,(Syntax) -,表示构成语言句子的各个记号之,间的组合规则,语义,(Semantics) -,表示各个记号的特定含义。,（各个记号和记号所表示的对象之间的关系）,语用,(Pragmatics) -,表示在各个记号所出现的行,为中，它们的来源、使用和影响。,74,CompilerPrinciples,每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。,语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,75,CompilerPrinciples,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。该数学系统称为,文法,。“形式”是指这样的事实：,语言的所有规则描述什麽符号串以什么方式出现,。形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。,76,CompilerPrinciples,3.,有关定义和记号,回顾,符号：,可以相互区别的记号（元素）。,字母表,：,符号（元素）的非空有穷集合。,符号串(字)：,由字母表,中的符号组成的任何有穷序列称为该字母表上的符号串。,空字,(,没有,符号的符号串)是,上的符号串；,若x是,上的符号串,a是,的元素,则xa是,上,的符号串 ；,y是,上的符号串,当且仅当它可以由,和,导出。,例如： =a,b,a,b,aa,ab,aabba,都,是,上的符号串,77,CompilerPrinciples,符号串s的前缀：,符号串s的任何首部。,如:,、,b、ba、都是符号串banana的前缀.,符号串s的后缀：,符号串s的任何尾部。,如:,、,a、na、都是符号串banana的后缀.,符号串s的子串：,从s中删去一个前缀和一个后缀得到的符号串.,如:ana是符号串banana的一个子串.,符号串s的真前缀：,x,s且x,的,任何前缀x。,s的真后缀，真子串,可以类似地定义,。,78,CompilerPrinciples,符号串的运算：,符号串的长度,：符号串中符号的个数,.,符号串,s,的长度,记为,|s|,。,的长度为,0,连接,：符号串,x,、,y,的连接,是把,y,的符号写在,x,的符号,之后得到的符号串,xy,如,x=ab,y=cd,则,xy=abcd,又如,a = a,方幂,：符号串自身连接,n,次得到的符号串,a,n,定义为,aaaa,n,个,a,a,0,=,a,1,=a, a,2,=aa ,79,CompilerPrinciples,符号串集合,：若集合,A,中所有元素都是某字母表,上的符号串，则称,A,为字母表,上的符号串集合。,符号串集合,A,和,B,的乘积,：,AB =,xy|xA,且,yB,若 集合,A=,ab,cde,B =,0,1,则,AB =,ab1,ab0,cde0,cde1,的闭包：,上的一切符号串（包括,）组成的集合，记为,*,。,的正闭包：,上的,除,外,的所有符号串组成的集合，记为,+,。,80,CompilerPrinciples,例：,=a,b,*,=,a,b,aa,ab,ba,bb,aaa,aab,+,=a,b,aa,ab,ba,bb,aaa,aab,81,CompilerPrinciples,语言：,由句子构成的集合。换言之,字母表,上,的一个语言是,上的一些符号串的集合,(,字母表,上,的每个语言是,*,的一个子集)。,例如：,字母表,=a,b,*,=,a,b,aa,ab,ba,bb,aaa,aab,集合,ab,aabb,aaabbb,a,n,b,n,或表示为,w|w,*,且,w=a,n,b,n,n1为,字母表,上,的一个语言。,集合,a,aa,aaa,或,表示为,w|w,*,且,w=a,n,n1 为,字母表,上,的一个语言。,是一个语言，,即, 也,是一个语言,。,82,CompilerPrinciples,二、上下文无关,文法及其语言的形式定义,1.,如何来描述一种语言？,如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示；,如果语言是无穷的，找出语言的有穷表示。,语言的有穷表示有两个途径：,生成方式,：语言中的每个句子可以用严格定义的规则来构造。,识别方式,：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，要麽永远继续下去。,83,CompilerPrinciples,文法是从生成方式描述语言的，而自动机则是从识别的角度来描述语言的。本节仅介绍有关文法的概念。,前面关于“,我是大学生,”及“,赋值表达式,”的例子中，涉及到如下的概念：,所表示的是一个,类,概念，通常称作,语法范畴,或语法变量，如果用一个符号来代替,也称为,非终结符,(nonterminal)。所有规则中的非终结符构成了一个非空有穷集，记为,V,N,。,上述两例中的,“,句子,”,及,“,赋值表达式,”,显然是,最大的语法范畴,，也是我们最感兴趣的非终结符，通常称作开始符号，记为,S,。,“,大学生,”,、,“,我,”,、,“,是,”,、,“,a,”,、,“,+,”,等表示的是一个,具体概念,，用一个符号来表示，则称为,终结符,(terminal)。所有这样的符号同样构成了一个非空有穷集，记为,V,T,。,我、8等称作,产生式,(production)。所有产生式的集合显然是有穷的，记为P。,这样我们可以将文法抽象为如下的一个数学系统：,84,CompilerPrinciples,2.,文法的形式定义,一个文法G定义为一个四元式(,V,N, V,T, S ,P,),其中：,V,N,为非终结符号的非空有穷集；,V,T,为终结符号的非空有穷集，,V,N,V,T,=,；,P,为产生式的集合；,产生式,也称,重写规则或生成式,，形如,A,，其中：,A,V,N,(,V,N,V,T,),*,。,A,称为产生式的左部，,称作产生式的右部。,S,称作识别符号或开始符号，S,V,N,且,至少要在一条产生式中作为左部出现。,V,N,V,T,中的符号统称为文法符号。,85,CompilerPrinciples,例1 文法G=（V,N,，V,T,， S ， P ）,V,N,= S , V,T,= 0, 1 ,P= S,0S1, S,01 ,S为开始符号,例2 文法G=（V,N,，V,T,， S ， P ）,V,N,=，,V,T,=a,b,c,x,y,z,0,1,9,P=,a, ,z,0,9,S=,86,CompilerPrinciples,文法的写法,. G,：,SaA,b,Aab,AaA,b,A,. GS,：,SaS,b,Aab AaA,b,A,.,GS,：,SaS,b,Aab |aA,b,|,元,符号：, ,= |,习惯表示：,大写英文字母：非终结符,/,集合,字母表中靠前的小写英文字母：终结符,字母表中靠后的小写英文字母：字符串,87,CompilerPrinciples,上下文无关文法：它所定义的语法范畴是完全独立于这种范畴所能出现的环境。,程序设计语言的词：a+b/3 a10),，则记为,v ,+,w,，,v,推导,出,w,，或,w,归约,到,v,。若有,v ,+,w,，,或,v=w,，则记为,v ,*,w,。,例：,G,：,S,0S1,，,S,01,S,0S1,0S1 00S11,00S11 000S111,000S111 00001111,S,0S1 00S11 000S111 00001111,S,+,00001111,S,*,S 00S11,*,00S11,90,CompilerPrinciples,(3),最左（最右）推导,最左（最右）推导,：在推导的任何一步,，都是对,中的最左（右）非终结符进行替换。,最右推导被称为,规范推导,。也就是说，规范推导具有最右性。,规范推导的逆过程称为,规范规约,。也就是说，规范规约具有最左性。,由规范推导所得的句型称为,规范句型。,91,CompilerPrinciples,4.,句型、句子,句型：,有文法,G,，若,S,*,x,，,x,(V,N,V,T,),*,则称,x,是文法,G,的句型。,句子：,有文法,G,，若,S,*,x,，且,x,V,T,*,，则称,x,是文法,G,的句子。,例,1,：,G,：,S,0S1,，,S,01,S,0S1 00S11 000S111 00001111,G,的句型,:S,0S1 ,00S11 ,000S111,00001111,G,的句子,:,00001111,01,92,CompilerPrinciples,例2：G,E,：,EE+T|T TT*F|F F(E)|a,这个文法都能推导出什么,句子,？,E,E+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a,用符号a，+，*，( 和,),构成的算术表达式,思考：写出一个不同的文法，同样能够产生这些句子,93,CompilerPrinciples,5.,语言的定义,由文法,G,生成的语言记为,L(G),它是文法,G,的所有句子的集合。,L(G)=x|S,+,x, S,为开始符号,且,x V,T,*,例,1 G,：,S0S1,，,S01,L(G)=0,n,1,n,|n1,例,2,文法,GS,：,（,1,）,SaSBE,（,2,）,SaBE,（,3,）,EBBE,（,4,）,aBab,（,5,）,bBbb,（,6,）,bEbe,（,7,）,eEee,L（G）= a,n,b,n,e,n,| n1 ,这个文法生成,什么,语言,？,这个文法与前面见过的文法有什么不同？,94,CompilerPrinciples,S,a S BE (,S,aSBE),a aBEBE (,S,aBE),aabEBE,( aB,ab ),aabBEE,( EB,BE ),aabbEE,（bB,bb),aabbeE,（bE,be),aabbee,（eE,ee),类似推导可以看出a,b,e在句子中出现的顺序及个数满足L(G),当然要进一步说明：,G,生成的每个,句子,都在,L(G),中,L(G),中的每个,句子,确实能被,G,生成,95,CompilerPrinciples,使用产生式,(1) n-1,次，得到推导序列：,S,*,a,n-1,S(BE),n-1,，然后使用产生式,(2),一次，得到：,S,*,a,n-1,S(BE),n-1,a,n,(BE),n,。然后从,a,n,(BE),n,继续推导，总是对,EB,使用产生式,(3),的右部进行替换，而最终在得到的串中，所有的,B,都先于所有的,E,。例如，若,n=3,aaaBEBEBE,aaaBBEEBE,aaaBBEBEE,aaaBBBEEE,。,即有：,S,*,a,n,B,n,E,n,再使用产生式,(4),一次，得到,S,*,a,n,bB,n-1,E,n,，然后使用产生式,(5) n-1,次得到：,S,*,a,n,b,n,E,n,，进而使用产生式,(6),一次，使用产生式,(7) n-1,次，最后得到：,S,*,a,n,b,n,e,n,。,也能证明，对于,n1,，串,a,n,b,n,e,n,是唯一形式的终结符号串。,96,CompilerPrinciples,三、文法的等价性,1.,定义：,若,L(G,1,)=L(G,2,),，则称文法,G,1,和,G,2,是等价的。,如文法,G,1,A,：,A0R,与,G,2,S,：,S0S1,等价,A01 S01,RA1,因为,L,（,G,1,）,=L,（,G,2,）,=0,n,1,n,n1,。,97,CompilerPrinciples,2.,关于文法等价变换的几个定理,(1),对任一,文法,G1,都可以构造文法,G2,，使得,L(G1)=L(G2),，,但,G2,的开始符号不出现在任何产生式的右部。,例,1,：,G1: EE+EE*E(E)i,G2: SE EE+EE*E(E)i,具体做法：加一条,单个非产生式,SE,即可,。,(2),对任一文法,G1,都可以构造文法,G2,，使得,L(G1)=L(G2),，,但,G2,的每个非终结符都能导出一个终结符号串。,可给出如下证明：,98,CompilerPrinciples,证明：,令,=AAtG1&,t,V,T,+,；,递归扩充：,=,WWx&x(V,T,),+,由于G1的非终结符号是有穷的，上述过程一定是收敛的；,从G1的V,N,中删除不包含在,中的非终结符，并从其产生式集中删除其左部或右部中包含不属于,中的符号的产生式，这样得到的文法即为所要的G2。,99,CompilerPrinciples,例：G1A: ABeddD Bb,DEaADDB EDaEb,=B,=BA=A,B,到此为止；,于是D,E及相关D,E的产生式均可删除，得到： G2A: ABed Bb,可以证明L(G1)=L(G2)。,类似还可以给出如下定理：,(3)对任一文法,G1,都可以构造文法,G2,，使得,L(G1),=,L(G2)，,但,G2,的每个非终结符都出现在某一句型中。,证明？,100,CompilerPrinciples,(4)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2中不含,单个非产生式,。如：,G1A:,A,B,dD G2A:,A,dDbc,B,A,Cb,D,dDa,C,B,c,D,dDa,(5)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2中不含,空产生式,。,形如 E,的产生式称为空产生式,。,(6)对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，但G2中不含有,左递归,。,形如 EE+T的产生式称为左递归的,。,递归哪里去了,101,CompilerPrinciples,四、语法树和文法二义性,1.,语法树：,语法树是了解句子语法结构的一种辅助工具。树根即为开始符号所标记的结点。随着推导的展开，某个非终结符被它的产生式右部所替换时，则产生出下一代新结点。每个新结点和其父结点间都有一条连线。,于是，可给出如下的定义：,102,CompilerPrinciples,设,G=( V,N,V,T, S, P),为一,CFG,，若一棵树满足下列,4,个条件，则此树称作,G,的语法树,(,推导树,)(,派生树）：,1.,每个结点都有一个标记，此标记是,V,的一个符号,2.,根的标记是,S,3.,若一结点,n,至少有一个它自己除外的子孙，并且有标记,A,，则肯定,A,V,N,4.,如果结点,n,有标记,A,其直接子孙结点从左到右的次序是,n,1,，,n,2,，,，,n,k,，其标记分别为,A,1,，,A,2,，,，,A,k,，那么,AA,1,A,2,，,，,A,k,一定是,P,中的一个产生式,语法树的结果：,从左到右读出叶子的标记而构成的串谓之句型。,103,CompilerPrinciples,给定文法,G=(,V,N,V,T,P,S,),，对于,G,的任何句型都能构造与之关联的语法树,(,推导树,),。,定理：,G,为上下文无关文法，,对于,，有,S,*,，当且仅当,文法,G,有以,为结果的一棵语法树,(,推导树,),这里对该定理不作证明。,104,CompilerPrinciples,例如：文法,GE:,EE+EE*E(E)i,显然,(i+i)*i,是该文法产生的一个句子，它的推导过程可以用右边的语法树来描述。,子树,与,简单子树,只有单层分支的子树,代次,2,1,3,4,5,E,E,*,E,(,E,),