Part2高级语言及其语法描述课件

,啊,啊,啊,啊,Part2,高级语言及其语法描述,授课：胡静,Part2高级语言及其语法描述,内容提要,预备知识,形式语言基础,文法和语言的定义（语法定义、语义定义）,术语和概念,文法的表示：正则表达式和语法树,文法和语言的分类,内容提要预备知识形式语言基础,预备知识,预备知识,更多的概念和一些约定,A,B,C,用来表示,非终结符,a,b,c,表示,终结符,X,Y,Z,可以用来表示,终结符或者非终结符,w,x,y,z,表示,终结符号串,表示由,终结符或非终结符构成的符号串,在产生式,A,中，,A,是产生式的左边,(,lefthand side,LHS),是产生式的右边,(righthand side,RHS),A,1,|,n,表示产生式,A,1,A,n,更多的概念和一些约定A,B,C,用来表示非终结符,符号串和符号串集合的运算,符号串和符号串集合的运算,符号串和符号串集合的运算,符号串和符号串集合的运算,Part2高级语言及其语法描述课件,Part2高级语言及其语法描述课件,将字符看做符号，则单词就是符号串，单词集合就是符号串的集合,将单词看做符号，则句子就是符号串，而所有句子的集合（语言）就是符号串的集合,Part2高级语言及其语法描述课件,文法的直观概念,文法的直观概念,Part2高级语言及其语法描述课件,规则、字母表均为有限集合,句子长度是有限的,生成的句子个数是无限的,Part2高级语言及其语法描述课件,Part2高级语言及其语法描述课件,Part2高级语言及其语法描述课件,Part2高级语言及其语法描述课件,语法树,语法（推导）树来描述一个句子的语法结构,识别符号,语法树语法（推导）树来描述一个句子的语法结构识别符号,关于文法的定义,定义,3.1,文法,G,定义为四元组（,V,N,V,T,P,S,）。,其中,V,N,为非终结符号（或语法实体，或变量）集；,V,T,为终结符号集；,P,为产生式（也称规则）的集合；,V,N,V,T,和,P,是非空有穷集。,S,称做识别符号或开始符号，是一个非终结符（,S,V,N,），至少要在一条规则中作为左部出现。,V,N,和,V,T,不含公共元素，即,V,N,V,T,=,。通常,V,表示,V,N,V,T,，,V,称为文法,G,的字母表或字汇表。,例,3.1,文法,G=,（,V,N,，,V,T,，,P,，,S,）,V,N,=S,V,T,=0,1,P=S0S1,S01,S,为开始符号,文法可以简写，只需要指出开始符号和产生式即可。,关于文法的定义定义3.1,关于文法的定义（续）,定义,3.2,如,是文法,G=(V,N,V,T,P,S),的规则,(,或说是,P,中第一个产生式,),，,和,是,V,*,中的任意符号串，若有符号串,v,，,w,满足：,v=,，,w=,，则说,v,（应用规则,）直接产生,w,，或说,w,是,v,的直接推导。,（,v=w,）,例：,GS,：,S0S1,，,S01,S,0S1 00S11 000S111 00001111,G,关于文法的定义（续）定义3.2G,关于文法的定义（续）,定义,3.3,如果存在直接推导的序列：,v=w,0,=w,1,=w,2,=w,n,=w,，,(n0),，则称,v,推导出（产生）,w,（推导长度为,n,）。记做,v=,+,w,。,定义,3.4,若有,v=,+,w,，或,v=w,，则记做,v=,*,w,。,规范推导（最右推导）,最左推导：若规则右端符号串中有两个以上的非终结符时，先推导左边的。,最右推导：若规则右端符号串中有两个以上的非终结符时，先推导右边的。,关于文法的定义（续）定义3.3,关于文法的定义（续）,定义,3.5,设,GS,是一文法，如果符号串,x,是从识别符号推导出来的，即有,S=,*,x,，则称,x,是文法,GS,的句型。若,x,只由终结符号组成，则称,x,为,GS,的句子。,定义,3.6,文法,G,所产生的语言定义为集合,x|S=,*,x,，其中,S,为文法的开始符号，且,xV,T,*,。可用,L(G),表示该集合。,例：,G,：,S0S1,，,S01,S,0S1 00S11 000S111 00001111,L(G)=0,n,1,n,|n,1,关于文法的定义（续）定义3.5,关于文法的定义（续）,定义,3.7,若,L(G1)=L(G2),，则称文法,G1,和,G2,是等价的。,例,1,：如文法,G,1,A,：,A0R,与,G,2,S,：,S0S1,等价,A01 S01,RA1,例,2,：,G,1,E:E i,与,G,2,E,：,E T|E+T,等价,E E+E T F|T*F,E E*E F,（,E,）,|i,E (E),关于文法的定义（续）定义3.7,Part2高级语言及其语法描述课件,文法的类型,Chomsky,将文法分为四种类型：,0,型文法：对任一产生式,，都有,(V,N,V,T,),+,，,(V,N,V,T,),*,1,型文法：对任一产生式,，都有,|,，仅仅,S,除外,2,型文法：对任一产生式,，都有,V,N,，,(V,N,V,T,),*,3,型文法：任一产生式,的形式都为,AaB,或,Aa,，其中,AV,N,，,BV,N,，,aV,T,。上述叫做右线性文法，另有左线性文法，二者等价。,文法的类型 Chomsky将文法分为四种类型：,文法的类型举例,1,型（上下文有关）文法,文法,GS,：,SCDAbbA,CaCABaaB,CbCBBbbB,ADaD C,BDbD D,AabD,L(G)=ww|wa,b,*,文法的类型举例1型（上下文有关）文法,文法的类型举例,2,型（上下文无关）文法,文法,GS,：,SaB|bA,Aa|aS|bAA,Bb|bS|aBB,文法,GS,：,S0A|1B|0,A0A|1B|0S,B1B|1|0,文法的类型举例2型（上下文无关）文法,文法的类型举例,定义标识符的,3,型（正规）文法,文法,GI,：,I lT,I l,T lT,T dT,T l,T d,文法的类型举例定义标识符的3型（正规）文法,文法和语言,0,型文法,0,型文法（短语文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何,0,型语言都是递归可枚举的,1,型文法（上下文有关文法）,产生式的形式为,1,A,2,1,2,，即只有,A,出现在,1,和,2,的上下文中时，才允许,取代,A,。其识别系统是线性界限自动机。,2,型文法（上下文无关文法）,产生式的形式为,A,，,取代,A,时与,A,的上下文无关。其识别系统是不确定的下推自动机。,3,型文法（正则文法）,产生的语言是有穷自动机（,FA,）所接受的集合,文法和语言0型文法,上下文无关文法,上下文无关文法有足够的能力描述现今程序设计语言的语法结构,算术表达式,语句,赋值语句,条件语句,读语句,文法,G=(E,+,*,I,(,),P,E ifthen P:E i|ifthenelse,E E+E,E E*E,E (E),上下文无关文法上下文无关文法有足够的能力描述现今程序设计语言,上下文无关文法的语法树,用于描述上下文无关文法的,句型推导,的直观方法,例,:GS:,S,aAS,A,SbA,A,SS,S,a,A,ba,S,a A S,S b A,b a,句型,aabbaa,的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,a,a,上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观,上下文无关文法的语法树,推导过程中施用产生式的,顺序,例,:GS:,S,aAS,A,SbA,A,SS,S,a,A,ba,S,a A S,S b A a,a b a,S,aASaAaaSbAaaSbbaaaabbaa,SaASaSbASaabASaabbaSaabbaa,SaASaSbASaSbAaaabAaaabbaa,上下文无关文法的语法树推导过程中施用产生式的顺序 例:G,Thanks for your time!,Questions&Answers,Part2高级语言及其语法描述课件,