编译原理第二章高级语言及其语法描述

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 高级语言及其语法描述,2.1 程序语言的定义(描述),2.2 高级语言的一般特性,2.3 程序语言的语法描述,2.1 程序语言的定义,语法：,语言的语法是指这样的一组规则，用它可以产生和形成一个合式的程序。,例如：变量的标示符要以非数字开头,语法分为词法规则和语法规则。,词法规则：,指单词符号的形成规则，单词符号包括：各种类型常数、标示符、算符和界符等。,词法分析工具：正规式和有限自动机理论。,语法规则：,是语法单位的形成规则。,语法单位包括：表达式、语句、子程序、函数等。,语法规则描述工具：上、下文无关文法。,语义：,是指这样的规则，使用它可以定义一个程序的意义。,语义描述的方法：属性文法的语法制导翻译方法。该方法接近形式化方法。,相同语句不同含义的例子：,Z=X+Y,可以表示整数相加和实数相加等不同的语义。,编译程序就是要从基本的单词符号和语法单位分析程序的语义。,2.2 高级语言的一般特性,高级语言分类：,过程式语言-命令驱动、面向语句，如C语言等。,函数式语言-从功能出发构造函数，如LISP等。,基于规则的语言-检查一定的条件，当他满足，则执行适当的动作，如Prolog语言。,面向对象的语言-支持封装、继承和多态性等。,2.3 程序语言的语法描述,基本概念：,：是一个有穷字母表，它的每个元素称为一个符号。,上的字（符号串）：是指由中的符号所构成的一个有穷序列。,：不包含任何符号的序列称为空字。,：表示上所有字的集合，其中包括空字。,:不包含任何元素的集合 =,集合运算：,集合的积运算：UV=|U&V,V,n,=VVV：其中V,0,=,集合的或运算：UV=|U ORV,集合的闭包运算：V,=V,0,V,1,V,2,V,3,集合的正规闭包：V,+,=VV,2.3.1,上下文无关文法,文法：,描述语言的语法结构的形式规则。,特点：,这些规则必须是准确的，易于理解的，而且，应当有相当强的描述能力，足以描述各种不同的结构。,例如：,-,上、下文无关文法：,它所定义的语法范畴是完全独立于这种范畴可能出现的环境的。,一个上、下文无关文法G包括四个组成部分：,一组终结符号,一组非终结符号,一个开始符号,一组产生式,终结符号：,是组成语言的基本符号，在程序语言中就是以前屡次提到的单词符号，如基本字、标识符、常数、算符和界符等。,非终结符号：,用来代表语法范畴。如：语句A、表达式B等。,开始符号：,是一个特殊的非终结符号，它代表所定义的语言中我们最终感兴趣的语法范畴，这个语法范畴通常称为“句子”或是“程序”。,产生式：,是定义语法范畴的一种书写规则。,一个产生式的形式是A或A:=,A：是非终结符号,：是由终结符号或与非终结符号组成的一个符号串。,例如：一个简单的算术表达式文法：,Ei,EE+E,EE*E (2-1),E(E),终结符号：i,非终结符号：E,开始符号：算术表达式,产生式：(2-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-1的语言？,E,(E),(,E+E),(i,+E),(i,+i),推导：,称,A直接推出，即：A，仅当A,是产生式，且、(V,T,V,N,),*,如果,1,1,n,，则称序列是一个推导；称,1,可推出,n,；,表示经一步或若干步可推出,表示经0步或若干步推出,假定G是一个文法，S是它的开始符号。如果有:,则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。L(G),=,|,S,*,&V,T,*,最左推导：,任何一步=都是对中的最左非终结符进行替换的。,最右推导：,任何一步=都是对中的最右非终结符进行替换的。,例2.1、例2.2、例2.3,2.3.2 语法分析树与二义性,语法树定义：,句型推导的树形表示称为语法树。,E,E,E(根),(,),i,*,+,E,E,E,i,i,文法二义性：,文法存在某个句子对应两颗不同的语法树，则称这个文法是二义性文法。,例如：,E,E,E(根),(,),i,*,+,E,E,E,i,i,E,E,E(根),(,),i,+,*,E,E,E,i,i,二义性文法特点：,文法的二义性和语言的二义性不同，不同的文法可以有相同的语言，即L(G)=L(G*)，其中G是二义性文法。,文法的二义性证明是NP-Hard问题。,上、下文无关文法的限制：,文法中不含任何下面形式的产生式 PP,每个非终结符P必须都有用处。即：必须存在含P的句型，并且对于P不存在永不终结的回路。,无二义性文法推导举例：,文法：,E看作“表达式”，T看作“项”，F看作“因子”，则上述文法可以表示为：,表达式-项|表示式+项,项-因子|项*因子,因子-(表达式)|i,表达式,项,因子,(表达式),(表达式+项),(项+项),(项*因子+项),(因子*因子+项),(i*因子+项),(i*i+因子),(i*i+i),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)式左线,性文法,文法说明：,1型文法也称上、下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成空串。例如，假若A是1型文G的一个产生式，和都不空，则非终结符A只有在和这样的一个上下文环境中才可以把它替换为。,2型文法也称上、下文无关文法。,3型文法也称线性文法，或称为正规文法。,文法应用举例,例1：判断文法S,aSb|ab,的类型，并推断文法语言。,由于S aSb|ab与a、b无关，则是上下文无关文法。,S aSb|ab，有S,aSb aaSbb a,n,Sb,n,，,文法对应的语言为：L,2,=a,n,b,n,|n1,例2现有文法如下：,语句if条件 then 语句|,if条件 then 语句 else 语句|,其它语句,试判断文法的二义性和类型？,由文法可以推导出下面的二义性句型,If C,1,then if C,2,then S,1,else S,2，,其中 else 不知与那,个then 匹配,，,所以它是二义性文法。,由于替换仅在右侧进行，且不考虑条件，所以它上下、文无关的正规文法。,某些语言是上、下文无关语言、但有些语言却无法用上、下无关文法描述。,有些语言即不是一个上、下文无关语言，但也不是一个上下有关语言。,作业：第6题、第8题。,