第二章 高级语言及其语法描述.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,程序设计语言,编 译 原 理,主讲：张永梅,翻译程序扫描所输入的源程序，并将其转换为目标程序。,翻译程序,源程序,目标程序,源程序是用高级语言或汇编语言编写的，而目标程序则是用目标语言表示的。,汇编程序,汇编语言程序,机器语言程序,编译程序,高级语言程序,低级语言程序,汇编程序与编译程序都是,翻译程序,，主要区别是加工对,象的不同。,编译程序总框,源程序,单词符号,语法单位,中间代码,中间代码,目标代码,表,格,管,理,出,错,处,理,语法分析器,语义分析与中间代码产生器,优化器,目标代码生成器,词法分析器,编译过程阶段划分是一种典型的分法，事实上并非所有的编译程序都包括这几个阶段。,有些编译程序为了加快编译速度，,中间代码生成阶段,可以去掉。有些编译程序对优化没有要求，,优化阶段,即可省去。有些最简单的编译程序只有词法分析，语法分析，语义分析和目标代码生成，如,PL/0,语言编译程序。,一遍扫描即可完成整个编译工作的称为,一遍扫描编译程序,其结构为,：,词法分析,语法分析,语义分析及代码,生成,源程序,语法成分,返回分析结果,整理目标程序,停机,目标程序,取单词,返回单词,课程安排,内 容,讲授课时,实验课时,第一章 引 论,2,第二章 高级程序语言及其语法描述,2,第三章 词法分析,实验一 词法分析器（第,6,、,7,、,8,、,9,周）,10,8,第四章 语法分析,-,自上而下分析,8,第五章 语法分析,-,自下而上分析,实验二 语法分析器（第,13,、,14,、,15,、,16,周）,8,8,第六章 属性文法和语法制导翻译,8,第七章 语义分析及中间代码产生,8,第八章 优 化,2,合 计,48,16,第二章 高级语言及其语法描述,2.1,程序语言的定义,2.2,高级语言的一般特性,2.3,程序语言的语法描述,了解：,形式语言概述,熟悉：,语法、语义,掌握：,上下文无关文法,语法分析树与二义性,第二章 高级语言及其语法描述,作业：,2.6,，,2.7,，,2.8,，,2.9,第二章 高级语言及其语法描述,2.6,令文法,G,6,为,NDND,D0123456789,（,1,）,G,6,的语言,L(G,6,),是什么？,（,2,）给出句子,0127,、,34,和,568,的最左推导和最右推导。,2.7,写一个文法，使其语言是奇数集，且每个奇数不以,0,开头。,2.8,令文法为,ETE+TE-T,TFT*FT/F,F(E)i,（,1,）给出,i+i*i,、,i*(i+i),的最左推导和最右推导；,（,2,）给出,i+i+i,、,i+i*i,和,i-i-i,的语法树。,2.9,证明下面的文法是二义的：,SiSeSiSi,第二章 高级语言及其语法描述,常用的高级语言,FORTRAN,数值计算,COBOL,事务处理,PASCAL,结构程序设计,ADA,大型程序、嵌入式实时系统,PROLOG,逻辑程序设计,ALGOL,算法语言,C/C+,系统程序设计,JavaInternet,程序设计,第二章 高级语言及其语法描述,与机器语言或汇编语言比较,，,高级语言的优点,：,较接近于数学语言和工程语言,，,比较直观、自然和易于理解;,便于验证其正确性,，,易于改错;,编写效率高;,易于移植。,2.1,程序语言的定义,程序语言由两方面定义：,语法,语义,语用,语法是描述程序的结构，根据它可以产生正确的程序。（词法规则、语法规则）,语义是语言成分的含义，由程序执行的效果来说明。,语用是语言的实际应用。如：,x=a+b*c,一、语法,程序本质上是一定字符集上的字符串。,语法,：一组规则,，,用它可以形成和产生一个,合式(well-formed),的程序,。,一、语法,词法规则,：单词符号的形成规则,。,单词符号是语言中具有独立意义的最基本结构,。,一般包括：常数、标识符、基本字、算符、界符等。,描述工具：有限自动机,语法规则,：语法单位的形成规则,。,语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;,描述工具：上下文无关文法,Ei,EE+E,EE*E,E(E),语法规则和词法规则,定义了程序的的形式结构。定义,语法单位的意义,属于语义问题。,语义：,是指这样的规则，使用它可以定义一个程序的意义。,语义描述的方法,：属性文法的语法制导翻译方法。该方法接近形式化方法。,相同语句不同含义的例子：,Z=X+Y,可以表示整数相加和实数相加等不同的语义。,编译程序就是要从基本的单词符号和语法单位分析程序的语义。,二、语义,高级语言的分类,程序结构,数据类型与操作,初等数据类型,数据结构,抽象数据类型,语句与控制结构,2.2,高级语言的一般特性,2.2,高级语言的一般特性,高级语言分类：,过程式语言,-,命令驱动，面向语句，如,C,语言等。,函数式语言,-,从功能出发构造函数，如,LISP,等。,基于规则的语言,-,检查一定的条件，当满足条件时，则执行适当的动作，如,Prolog,语言。,面向对象的语言,-,支持封装、继承和多态性等。,2.3,程序语言的语法描述,语言特征,自然语言,(Natural Language),是人与人的通讯工具,语义,(semantics):,环境、背景知识、语气、二义性,难以形式化,计算机语言,(Computer Language),计算机系统间、人机间通讯工具,严格的语法,(Grammar),、语义,(semantics),易于形式化：严格,2.3,程序语言的语法描述,语言的描述方法,现状,自然语言：自然、方便,-,非形式化,数学语言（符号）：严格、准确,-,形式化,形式化描述,高度的抽象，严格的理论基础和方便的计算机表示。,2.3,程序语言的语法描述,语言,形式化的内容提取,语言,(Language),：满足一定条件的句子集合,句子,(Sentence),：满足一定规则的单词序列,单词,(Token),：满足一定规则的字符,(Character),串,程序设计语言,形式化的内容提取,程序设计语言,(Programming Language),：组成程序的所有语句的集合。,程序,(Program),：满足语法规则的语句序列。,语句,(Sentence),：满足语法规则的单词序列。,单词,(Token),：满足词法规则的字符串。,2.3,程序语言的语法描述,描述形式,文法,语法,语句,语句的组成规则,描述方法：,BNF,范式、语法,(,描述,),图,词法,单词,单词的组成规则,描述方法：有限自动机、正规式,形式语言与自动机理论的产生与作用,语言学家,Chomsky,最初从产生语言的角度研究语言。,1956,年，通过抽象，他将语言形式地定义为是由一个字母表中的字母组成的一些串的集合。可以在字母表上按照一定的规则定义一个文法（,Grammar,），该文法所能产生的所有句子组成的集合就是该文法产生的语言。,克林,（,Kleene,）在,1951,年到,1956,年间，,从识别语言的角度研究语言，,给出了语言的另一种描述。,克林是在研究神经细胞中，建立了自动机，他用这种自动机来识别语言：对于按照一定的规则构造的任一个自动机，该自动机就定义了一个语言，这个语言由该自动机所能识别的所有句子组成。,形式语言与自动机理论的产生与作用,1959,年，,Chomsky,通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而且,证明了文法与自动机的等价性,。,20,世纪,50,年代，人们用,巴科斯范式,（,Backus Nour Form,或,Backus Normal Form,，简记为,BNF,）成功地对高级语言,ALGOL-60,进行了描述。实际上，巴科斯范式就是上下文无关文法（,Context Free Grammar,）的一种表示形式。这一成功，使得形式语言在,20,世纪,60,年代得到了大力的发展。,2.3,程序语言的语法描述,基本概念：,：是一个有穷字母表，它的每个元素称为一个符号。,上的,字,(也叫,符号串,),：是指由,中的符号所构成的一个有穷序列。,：不包含任何符号的序列称为空符号串。,*,：表示,上所有字的集合，其中包括空符号串,。,:,不包含任何元素的集合，,=,例如:设=a,b，则,*=,a,b,aa,ab,ba,bb,aaa,.,*,的子集U和V的,连接,（,积,）定义为,UV,|,U&,V,设：,U a,aa,V b,bb,那么：,UV=ab,abb,aab,aabb,2.3,程序语言的语法描述,*,的子集U和V的,连接,（,积,）定义为,UV,|,U&,V,V自身的 n次积记为,V,n,=VVV,规定V,0,=,，令,V,*,=V,0,V,1,V,2,V,3,称V,*,是V的,闭包,;,记 V,VV,*,，称V,+,是V的,正,(,规,),闭包,。,2.3,程序语言的语法描述,2.3,程序语言的语法描述,设：,U,a,aa,那么：,U,*,=,a,aa,aaa,aaaa,U,=,a,aa,aaa,aaaa,U,U,1,U,2,U,3,U,n,称为集合,U,的,正闭包,。,U,*,U,0,U,称为集合,U,的,闭包,。,2.3.1,上下文无关文法,文法：,描述语言的语法结构的形式规则。,特点：,这些规则必须是准确的，易于理解的，而且，应当有相当强的描述能力，足以描述各种不同的结构。,例如：,-,He gave me a book.,上下文无关文法：,它所定义的语法范畴是完全独立于这种范畴可能出现的环境的。,一个上下文无关文法,G,包括四个组成部分：,一组终结符号,一组非终结符号,一个开始符号,一组产生式,2.3.1,上下文无关文法,终结符号,：,是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。,非终结符号,：,用来代表语法范畴。如：语句、表达式等。,开始符号,：,是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子”或是“程序”。,2.3.1,上下文无关文法,产生式,：,是定义语法范畴的一种书写规则。,一个产生式的形式是,A,或,A:=,A,：是非终结符号,：是由终结符号或与非终结符号组成的一个符号串。,2.3.1,上下文无关文法,例如：一个简单的算术表达式文法：,Ei,EE+E,EE*E (2-1),E(E),终结符号：,i,，,+,，*，,(,，,),非终结符号：,E,开始符号：算术表达式,E,产生式：,(2-1),2.3.1,上下文无关文法,形式化定义：,一个上下文无关文法是一个四元式（,V,T,V,N,S,）,V,T,是一个非空有限集，它的每个元素称为终结符号；,V,N,是一个非空有限集，它的每个元素称为非终结符号，,V,T,V,N,=,；,S,是一个非终结符号，称为开始符号；,SV,N,。,是一个产生式集合（有限），每个产生式的形式是,P,。,其中，,PV,N,，,（,V,T,V,N,）,。开始符号,S,至少必须在某个产生式的左部出现一次。,P,1,|,2,|,n,。,其中，,i,称为是,P,的一个候选式。读作“定义”，直竖读为“或”,它是元语言符号。,2.3.1,上下文无关文法,上下文无关文法语言：,从文法的开始符号出发，反复使用产生式，对非终结符施行替换和展开。,例子：求解文法,2-1,的语言？,E,(E),(,E+E),(i,+E),(i,+i),推导：,称,A,直接推出,，即：,A,，仅当,A,是产生式，且、,(V,T,V,N,),*,2.3.1,上下文无关文法,2.3.1,上下文无关文法,表示一个文法时，通常只给出开始符号和产生式，如上例，可表示为：,G(E),：,E,i|E+E|E*E|(E),例如：一个简单的算术表达式文法：,Ei,EE+E,EE*E (2-1),E(E),终结符号：,i,，,+,，*，,(,，,),非终结符号：,E,开始符号：算术表达式,E,产生式：,(2-1),2.3.1,上下文无关文法,定义：称,A,直接推出,，即,A,仅当,A ,是一个产生式，,且,，,(,V,T,V,N,),*,。,如果,1,2,n,，则我们称这个序列是从,1,到,n,的一个,推导,。若存在一个从,1,到,n,的推导，则称,1,可以,推导,出,n,。,对文法,G(E),：,E,i|E+E|E*E|(E),E,(E),(,E+E,)(i+E)(i+i),用 表示：从,1,出发，经过,0,步或若干步，可以推出,n,。,所以：即 或,定义：假定,G,是一个文法，,S,是开始符号。如果 ，则,称是一个,句型,。仅含终结符号的句型是一个,句子,。文法,G,所产生的句子的全体是一个,语言,，将它记为,L,(,G,),。,通常，用,表示：从,1,出发，经过一步或若干步，可以推出,n,。,例：,(i*i+i),是文法,G(E),：,E,i|E+E|E*E|(E),的一个句子。,证明：,E,(E),(,E+E,),(,E*E+E,),(i*,E+E,),(i*,i+E,),(i*,i+i,),E,，,(E),，,(,E+E,),，,(E*E+E),，,，,(i*i+i),是句型。,2.3.1,上下文无关文法,例：文法G,1,(A),：,A c|Ab,G,1,(A),的语言?,L(,G,1,)=c，cb，cbb，,以c开头，后继若干个b,L(,G,1,)=c,b,n,|,n=0,2.3.1,上下文无关文法,2.3.1,上下文无关文法,例：文法G,2,(S),：,S,AB,A aA|a,B bB|b,G,2,(S),的语言?,L(,G,2,)=a,m,b,n,|m,n,=,1,2.3.1,上下文无关文法,例：给出产生语言为a,n,b,n,|n,1,的文法。,G,3,(S),：,S,aSb,S ab,例：,ab,n,a|n1,，构造其文法。,定义,G,和,G,是两个不同的文法，若,L(G)=L(G),则,G,和,G,为,等价文法,。,G,1,Z,：,ZaBa,Bb|,bB,2.3.1,上下文无关文法,G,2,Z,：,ZaBa,Bb|,Bb,i+i*i,的不同推导,EE+E|E*E|(E)|i,E,E,+E,i+,E,i+,E,*E,i+i*,E,i+i*i,E,E+,E,E+E*,E,E+,E,*i,E,+i*i,i+i*i,E,E,*E,E+,E,*E,E,+i*E,i+i*,E,i+i*i,不做限制,施于最右,非终结符号,(,最右推导,),施于最左,非终结符号,（最左推导）,一个句型的推导往往不唯一,。,最左推导,：,任何一步,=,都是对,中的最左非终结符号进行替换的。,最右推导,：,任何一步,=,都是对,中的最右非终结符号进行替换的。,2.3.1,上下文无关文法,2.3.2,语法分析树与二义性,用一张图表示一个句型的推导,称为,语法树,。,(i*i+i),的语法树,E,(E),(,E+E,),(,E*E+E,),(i*,E+E,),(i*,i+E,),(i*,i+i,),E,(E),(,E+E,),(,E+i,),(E*,E+i,),(E*,i+i,),(i*,i+i,),一棵语法树是不同推导过程的共性抽象。,G(E),：,E,i|E+E|E*E|(E),(i*i+i),树与推导,句型推导过程,该句型语法树的生长过程,由推导构造语法树,从开始,符号,开始，,自左向右,建立,推导,序列。,由,根结点,开始，,自上而下,建立,语法树,。,2.3.2,语法分析树与二义性,如果使用最左,(,右,),推导，则一个最左,(,右,),推导与语法树一一对应。,一个句型是否只对应唯一一棵语法树？,2.3.2,语法分析树与二义性,一个句子有两棵不同的语法树。,定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个,文法是二义的,。,G(E)：,E,i|E+E|E*E|(E),是二义文法。,2.3.2,语法分析树与二义性,二义文法,G(E),：,E,i|E+E|E*E|(E),表达式,项,|,表达式,+,项,项,因子,|,项*因子,因子,(,表达式,)|i,无二义文法,G(E),：,E,T|E+T,T,F|T*F,F (E)|i,2.3.2,语法分析树与二义性,),E,F,E,F,F,T,T,T,T,i,+,*,(,E,F,i,i,E,T,F,(E),(,E+T,),(,T+T,),(T*F,+T,),(F*,F+T,),(i*,F+T,),(i*i+T),(i*i+F),(i*i+i),考虑句子,(i*i+i),2.3.2,语法分析树与二义性,上下文无关文法的限制：,文法中不含任何下面形式的产生式,PP,每个非终结符,P,必须都有用处。即：必须存在含,P,的句型，并且对于,P,不存在永不终结的回路。,2.3.2,语法分析树与二义性,2.3.3,形式语言鸟瞰,乔姆斯基（,Chomsky,）把文法分四类：,0,型、,1,型、,2,型和,3,型。,其描述能力的强度有下列关系：,0,型强于,1,型、,1,型强于,2,型、,2,型强于,3,型。,0,型文法,：,设,G=,（,V,T,V,N,S,），对每个产生式,有,（,V,N,V,T,）,*,且至少含有一个非终结符；,（,V,N,V,T,）,*,对,0,型文法的,产生式,分别施加以下第,i,条限制，就得到,i,型文法,：,每个产生式为,均满足,|,|,|;,仅,S,例外，但,S,不得出现在任何产生式的右部。,G,为任何产生式为,A,，,AV,N,，,（,V,N,V,T,）,*,。,G,的任何产生式为,(1)AB,或,A,(2)AB,或,A,其中,V,T,*,，,A,、,BV,N,。,(1),式为右线性文法；,(2),式为左线性文法。,2.3.3,形式语言鸟瞰,文法说明：,1,型文法,也称,上下文有关文法,。这种文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成空串,。,2,型文法,也称,上下文无关文法,。,3,型文法,也称线性文法，或称为,正规文法,。,2.3.3,形式语言鸟瞰,2.3.3,形式语言鸟瞰,*G,是,0,型文法，,L(G),是,0,型语言；,-,其能力相当于图灵机,(TM),*G,是,1,型文法，,L(G),是,1,型语言,;,-,其识别系统是线性界限自动机,(LBA),*G,是,2,型文法，,L(G),是,2,型语言,;,-,其识别系统是不确定的下推自动机,(PDA),*,G,是右线性文法，,L(G),是,3,型语言,G,是左线性文法，,L(G),是,3,型语言,-,其识别系统是有限自动机,(FA),2.3.3,形式语言鸟瞰,四种文法之间的关系是将产生式作进一步限制而定义的,四种文法之间的逐级“包含”关系如下：,