第三章文法和语言.ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三 文法 语言
- 资源描述:
-
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章文法和语言,本章目的为语言的语法描述寻求工具,以便:,对源程序给出精确无二义的语法描述。(严谨、简洁、易读),根据语言文法的特点来指导语法分析的过程,从描述语言的文法可以自动构造出可用的分析程序,制导语义翻译,1,文法和语言,预备知识,文法和语言的形式定义,文法的类型,上下文无关文法及其语法树,上下文无关文法的句型分析,有关文法实用中的一些说明,有关文法的一些关系,2,预备知识-语言概述,语言是由句子组成的集合,是由一组记号所构成的集合。,汉语-所有符合汉语语法的句子的全体,英语-所有符合英语语法的句子的全体,程序设计语言-所有该语言的程序的全体,每个句子构成的规律,研究语言 每个句子的含义,每个句子和使用者的关系,3,预备知识-语言概述,研究程序设计语言,每个程序构成的规律,每个程序的含义,每个程序和使用者的关系,语言研究的三个方面,语法 Syntax,语义 Semantics,语用 Pragmatics,4,预备知识-语言概述,语法-表示构成语言句子的各个记号之间的组合规律,语义-表示按照各种表示方法所表示的各个记号的特定含义。(各个记号和记号所表示的对象之间的关系),语用-,表示在各个记号所出现的行为中,它们的来源、使用和影响。,5,预备知识-有关定义和记号,符号:可以相互区别的记号(元素)。,字母表,:符号(元素)的非空有穷集合。,符号串:由字母表,中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串,(,没有,符号的符号串)是,上的符号串 2.若x是,上的符号串,a是,的元素,则xa是,上的符号串 3.,y是,上的符号串,当且仅当它可以由1和2导出。,例如:=a,b ,a,b,aa,ab,aabba,都,是,上的符号串,8,预备知识-有关定义和记号,符号串s的前缀:移走符号串s尾部的零个或多于零个符号得到的符号串.如:b是符号串banana的一个前缀.,符号串s的后缀:删去符号串s头部的零个或多于零个符号得到的符号串.如:nana是符号串banana的一个后缀.,符号串s的子串:从s中删去一个前缀和一个后缀得到的符号串.如:ana是符号串banana的一个子串.,9,对于每个符号串s,s和,两者,都,是符号串s的前缀,后缀和子串。,符号串s的真前缀,真后缀,真子串:任何非空符号串 x,相应地,是s的前缀,后缀或子串,并且 s,x,符号串的运算,符号串的长度:符号串中符号的个数.符号串s的长度记为|s|。,的长度为0,连接:符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a=a,方幂:符号串自身连接n次得到的符号串 a,n,定义为 aaaa n个a a,1,=a,a,2,=aa则a,0,=,10,符号串集合:若集合A中所有元素都是某字母表,上的符号串,则称A为字母表,上的符号串集合。,两个符号串集合A和B的乘积定义为 AB=,xy|xA且yB,若 集合A=,ab,cde,B=,0,1,则 AB=,ab1,ab0,cde0,cde1,使用,*表示,上的一切符号串(包括,)组成的集合。,*,称为的闭包,。,上的,除,外,的所有符号串组成的集合记为,+,。,+,称为的正闭包,。,11,例:=a,b,*,=,a,b,aa,ab,ba,bb,aaa,aab,+,=a,b,aa,ab,ba,bb,aaa,aab,12,语言:字母表,上,的一个语言是,上的一些符号串的集合,(上,的每个语言是,*,的一个子集)。,例如:=a,b,*,=,a,b,aa,ab,ba,bb,aaa,aab,集合,ab,aabb,aaabbb,a,n,b,n,或w|w,*,且w=a,n,b,n,n,1为,字母表,上,的一个语言。,集合,a,aa,aaa,或w|w,*,且w=a,n,n,1 为,字母表,上,的一个语言。,是一个语言。,即,是一个语言。,13,语言,上,的运算,设L是(,上的)一个语言,M是(,上的)一个语言,语言,L和M的并,交,差,补,是一个语言。,如,语言,L和M的并为 LM,,是一个语言:,w|w is in L or is in M 如:,L1,=a,b,y,z M1=1,28,9,L1M,1=a,b,y,z,1,28,9,语言,L和M的连接,是一个语言,记,为 LM,LM=,st|s,L,且 t,M,如:,L1M1,=a1,b1,y1,z1,a2,b2a9z9,有,L,=,L=L。L的n次连接L,n=,LL.L,14,语言,上,的运算,语言,L的,闭包,记,为 L*,L*=L,0,L,1,L,2,.L,0,=,,L,n,=L,L,n-1,=,L,n-1,L,n1,语言,L的正,闭包,记,为 L,+,,L,+,=L,1,L,2,L,3,.L,+,=LL*=L*L,L*=L,+,如:,L1,=a,b,y,z M1=1,28,9 (,L1M,1)=a,b,y,z,1,28,9,(,L1M,1),*,=a,b,y,z,1,28,9,,aa,1a,xyz,6789st.,L1,(,L1M,1),*,=所有字母打头的字母和数字符号串,15,语言的描述,如何来描述一种语言?,如果语言是有穷的(只含有有穷多个句子),可以将句子逐一列出来表示,如果语言是无穷的,找出语言的有穷表示。两个途经:生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。识别方式(自动机):用一个过程,当输入的一任意串属于语言时,该过程经有限次计算后就会停止并回答“是”,若不属于,要麽能停止并回答“不是”,(要麽永远继续下去。),16,文法,数学系统,一个形式数学系统,可由下列基本成分来刻画:一组基本符号,一组形成规则,一组公理,一组推理规则。,17,文法和语言的形式定义,文法的定义,推导的定义,句型、句子、语言的定义,18,文法的定义,文法G定义为四元组(V,N,,V,T,,P,S),V,N,:非终结符集,V,T,:终结符集,P:产生式(规则)集合,S:开始符号,V,N,V,T,=,,S,V,N,V=,V,N,V,T,,称为文法G的文法,符号集合,19,规则的定义,规则(重写规则、产生式或生成式),是形如,或=的(,)有序对,且V,+,,V,*,。,称为规则的左部(,或生成式,的左部)。,称为规则的右部(,或生成式,的右部)。,20,文法的定义,例3.1 文法G=(V,N,,V,T,,P,S),V,N,=S,V,T,=0,1,P=S,0S1,S,01,S为开始符号,21,文法的定义,习惯上只将产生式写出。并有如下约定:,第一条产生式的左部是开始符号,用尖括号括起的是非终结符,否则为终结符。或者大写字母表示非终结符,小写字母表示终结符,G可写成GS,S是开始符号,G:S,a,A,b,A,ab,A,a,A,b,A,GS:A,ab,A,a,A,b,A,S,a,S,b,缩写形式,GS:A,ab,|,a,A,b,|,S,a,S,b,注意:,元,符号和源符号,22,例3.2 文法G=(V,N,,V,T,,P,S),V,N,=标识符,字母,数字,V,T,=a,b,c,x,y,z,0,1,9,P=,a,z,0,9,S=,23,推导的定义,直接推导,“”,是文法G的产生式,若有v,w满足:,v=,w=,其中V,*,V,*,则称v直接推导到w,记作 v,w,或w,直接归约到v,例:G:,S,0S1,S,01,S,0S1 00S11 000S111 00001111,.,.VAR;BEGIN READ()END.VAR A;BEGIN READ(A)END.,24,推导的定义,若存在v w,0,w,1,.w,n,=w,(n0),则称v w,v推导出w,或w归约到v,若有v w,或v=w,,则记为v w,25,文法的句型、句子的定义,句型,有文法G,若S x,则称x是文法G的句型。,句子,有文法G,若S x,且x,V,T,*,,则称x是文法G的句子。,例:G:,S,0S1,S,01,S,0S1 00S11 000S111 00001111,26,例:G,E,:,EE+T|T TT*F|F F(E)|aE,E+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a表示一切能用符号a,+,*,(和,)构成的算术表达式,27,文法,语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)=x|S x,其中S为文法的开始符号,且x,V,T,*,例:G:,S,0S1,S,01,L(G)=0,n,1,n,|n,1,28,例3.3 文法GS:,(1)S,aSBE,(2)S,aBE,(3)EB,BE,(4)aB,ab,(5)bB,bb,(6)bE,be,(7)eE,ee,L(G)=a,n,b,n,e,n,|n,1,29,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),G,生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,30,已知语言描述,写出文法,例:若语言由0、1符号串组成,串中0和1的个数相同,构造其文法。A,0B|1CB,1|1A|0BBC,0|0A|1CC,已知文法,写出语言描述,例:G,E,:,EE+T|T TT*F|F F(E)|a,31,语法 Syntax 语义 Semantics,偶正整数的集合,0,2,4,2n,dd.0(2,4,6,8),32,文法的等价,若L(G,1,)=L(G,2,),则称文法G,1,和G,2,是等价的。,如文法,G,1,A:A0R 与G,2,S:S0S1 等价,A01 S01,RA1,33,文法的类型,通过对产生式施加不同的限制,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,34,文法的类型,例:1型(上下文有关)文法,文法GS:S,aSBE,S,aBE,EB,BE,aB,ab,bB,bb,bE,be,eE,ee,35,文法的类型,例:1型(上下文有关)文法,文法GS:SCDAbbA,CaCABaaB,CbCBBbbB,ADaD C,BDbD D,AabD,L(G)=ww|wa,b,*,36,文法的类型,例:2型(上下文无关)文法,文法GS:S,aB|bA,A,a|aS|bAA,B,b|bS|aBB,文法GS:S,0A|1B|0,A,0A|1B|0S,B,1B|1|0,37,文法的类型,例:定义标识符的3型(正规)文法,文法GI:I,lT,I,l,T,lT,T,dT,T,l,T,d,38,文法和语言,0型文法产生的语言称为0型语言,1型文法或上下文有关文法(,CSG,),产生的语言称为,1,型语言,或上下文有关,语言(CSL),2型文法或上下文无关文法(,CFL,),产生的语言称为2型语言,或上下文无关,语言(CF L),3型文法或正则(正规)文法(,RG,),产生的语言称为3型语言,正则(正规),语言(RL),39,文法和语言,四种文法之间的关系 是将产生式做进一步限制而定义的。,语言之间的关系依次:有不是上下文有关语言的0型语言,有不是上下文无关语言的1型语言,有不是正则语言的上下文无关语言。,40,文法和识别系统,0型文法(短语文法)的能力相当于图灵机,可以表征任何递归可枚举集,而且任何0型语言都是递归可枚举的,1型文法(上下文有关文法):产生式的形式为,1,A,2,1,2,,即只有A出现在,1,和,2,的上下文中时,才允许取代A。其识别系统是线性界限自动机。,41,带 a,0,a,1,a,2,a,3,a,4,a,5,a,6,a,7,a,8 ,a,n-1,a,n,有限控制器,磁头,图灵机,42,文法的类型,2型文法(上下文无关文法、CFG):产生式的形式为,A,取代A时与A的上下文无关。其识别系统是不确定的下推自动机。,3型文法(正规文法、右线性文法):产生的语言是有穷自动机(FA)所接受的集合,43,上下文无关文法及其语法树,上下文无关文法有足够的能力描述现今程序设计语言的语法结构,算术表达式,语句,赋值语句,条件语句,读语句,44,算术表达式,上下文无关文法表示,文法,G=(E,+,*,I,(,),P,E,P:E i,E E+E,E E*E,E (E),45,条件语句,上下文无关文法表示,ifthen|ifthenelse,46,上下文无关文法的语法树,用于描述上下文无关文法的,句型推导,的直观方法,例:GS:,S,aAS,A,SbA,A,SS,S,a,A,ba,S,a A S,S b A a,a b a,句型aabbaa的语法树(推导树),叶子结点:树中没有子孙的结点。从左到右读出推导树的叶子标记,所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,47,上下文无关文法的语法树,给定文法G,对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树满足下列4个条件:,1、每个结点都有一个V中的符号作标记,2、根的标记是开始符号S,3、若一结点n至少有一个它自己除外的子孙,并且n有标记A,则A,V,N,4、如果结点n的直接子孙,从左到右的次序是结点n,1,n,2,n,k,,其标记分别为A,1,A,2,A,k,,那么A,A,1,A,2,A,k,一定是P中的一个产生式,48,上下文无关文法的语法树,定理:G为上下文无关文法,,对于,,有S,,当且仅当,文法G有以,为结果的一棵推导树。,49,上下文无关文法的语法树,推导过程中施用产生式的,顺序,例: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,50,最左(最右)推导:在推导的任何一步,,其中、是句型,都是对,中的最左(右)非终结符进行替换,最右推导被称为规范推导。,由规范推导所得的句型称为规范句型,51,问题:一个句型是否对应唯一的一棵语法树?,52,例:GE:E i,E E+E,E E*E,E (E),E,E+E,E*E i,i i,E,E*E,i E+E,i i,句型 i*i+i 的两个不同的最左推导:,推导1:E,E+E E*E+E i*E+E i*i+E i*i+i,推导2:E E*E i*E i*E+E i*i+E i*i+i,53,二义文法,若一个文法存在某个句子对应两棵不同的语法树,则称这个文法是,二义,的。或者,若一个文法存在某个句子有两个不同的最左(右)推导,则称这个文法是,二义,的。,产生某上下文无关语言的每一个文法都是二义的,则称此语言是,先天二义,的。,54,二义文法,判定任给的一个上下文无关文法是否二义,或它是否产生一个先天二义的上下文无关语言,这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。,二义文法改造为无二义文法,GE:E i GE:E T|E+T,E E+E T F|T*F,E E*E F (E)|i,E (E),规定优先顺序和结合律,55,句型的分析,句型分析,就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。,在语言的编译实现中,把完成句型分析的程序称为,分析程序,或,识别程序,。分析算法又称,识别算法,。,从左到右的分析算法,,即总是从左到右地识别输入符号串,首先识别符号串中的最左符号,进而依次识别右边的一个符号。,56,句型的分析,分析算法可分为:,自上而下分析法,:从文法的开始符号出发,反复使用各种产生式,寻找与输入符号匹配的推导。,自下而上分析法,:从输入符号串开始,逐步进行归约,直至归约到文法的开始符号。,两种方法反映了两种不同的语法树的构造过程,57,自上而下的语法分析,例:文法G:S,cAd A,ab A,a识别输入串w=cabd是否该文法的句子,SSS,cAdcAd,a b,推导过程:S,cAd,cabd,58,自下而上的语法分析,例:文法G:S,cAd A,ab A,a识别输入串w=cabd是否该文法的句子,S,AA,c a b d c a b d c a b d,规约过程:S,cAd,cabd,59,句型分析的有关问题,1)如何选择使用哪个产生式进行推导?,假定要被代换的最左非终结符号是V,且有n条规则:V,A1|A2|An,那么如何确定用哪个右部去替代V?,2)如何识别可归约的串?,在自下而上的分析方法中,在分析程序工作的每一步,都是从当前串中选择一个子串,将它归约到某个非终结符号,该子串称为“可归约串”,60,句型分析,短语、直接短语、句柄的定义:文法GS,,S,A,且A b则称b是句型,b,相对于非终结符A的短语。若有A,b则称b是句型,b,相对于该规则A,b的直接短语。一个句型的最左直接短语称为该句型的句柄。,61,句型分析,E,F T,T F,F,i,1,*i,2,+i,3,短语:,直接短语:,句柄:,GE:EE+T|T TT*F|F F(E)|i,句型:i*i+i,62,有关文法实用中的一些说明,有关文法的实用限制,上下文无关文法中的,规则,63,有关文法的实用限制,文法中不得含有,有害规则,和,多余规则,有害规则:形如U,U的产生式。会引起文法的二义性,多余规则:指文法中任何句子的推导都不会用到的规则,1)文法中某些非终结符不在任何规则的右部出现,该非终结符称为不可到达,2)文法中某些非终结符,由它不能推出终结符号串来,称为不可终止的,64,有关文法的实用限制,对于文法GS,为了保证任一非终结符A在句子推导中出现,必须满足如下两个条件:1,),A必须在某句型中出现。2,),必须能从A推出终结符号串t来。即1)文法GS,对 某两个符号串,和:,S,A,2)A t,tV,T,65,化简文法,例:GS,1),S,Be,S,Be,2,),B,Ce,B,Af,3,),B,Af,A,Ae 4,),A,Ae A,e,5,),A,e 6,),C,Cf,7,),D,f,66,上下文无关文法中的,规则,具有形式A,的规则称为,规则,其中A,V,N,某些著作和讲义中限制这种规则的出现。因为,规则会使有关文法的一些讨论和证明变得复杂,两种定义的唯一差别是,句子在不在语言中。,67,上下文无关文法中的,规则,如果语言L有一个有穷的描述,则L,也同样有一个有穷描述。并且可以证明,若L是上下文有关语言、上下文无关语言或正规语言,则,L,和,L-,分别是上下文有关语言、上下文无关语言和正规语言,68,上下文无关文法中的,规则,定理3.1 文法G,任一P中的产生式,A,,都有,A,V,N,,,(,V,N,V,T,),*,(,即可能为),则L(G)也能这样一种文法产生,任一产生式,A,,只有如下两种形式:,A,V,N,,,(,V,N,V,T,),+,(,即)或者 S且 S不出现在任何产生式右边,69,上下文无关文法中的,规则,定理3.2G是上下文有关文法,则存在另一个上下文有关文法G,1,,L(G)=L(G,1,),且G,1,的开始符号不出现在G,1,的任何产生式的右边。若G为上下文无关文法或正规文法,类似结论成立。,70,有关文法的一些关系,一般来说,一个集合上的(二目)关系就是某一性质,此性质对集合中的任意两个有序符号来说,或者满足,或者不满足。所定义的符号,和 是符号串之间的两个关系。,我们习惯采用中缀表示法表示关系,即如果在集合中的两个元素c和d之间满足某一关系,我们就记作cRd。,71,R,+,,R*,集合A上的一关系R,a,b,c是A的元素。若 cRc,称R为自反的.若由aRb能得到 bRa 则称R为对称的。若由aRb和 bRc能得到 aRc 则称R为传递的。,给定任一关系R,我们定义一个新的关系 R,+,,称为R的传递闭包。aR,1,b,aRb aR,+,b c:aRc且 cR,i-1,b,i1,R*,称为R的自反传递闭包,72,FIRST集和FOLLOW集,设G=(,V,N,V,T,S,P)是上下文无关文法,FIRST(,)=a|,a,aV,T,V,*,若,则规定FRIST(,)。,FOLLOW(A)=a,S,A,且a FRIST(,),,V,*,,,V,+,若S u A,且,,则#FOLLOW(A)。,73,1.若X,V,则FIRST(X)=X.,2.若X,V,N,且有产生式X,a,则把a加入到FIRST(X)中;若X,也是一条产生式,则把,也加到FIRST(X)中.,3.若X,Y是一个产生式且Y,V,N,则把FIRST(Y)中的所有非,元,素都加到FIRST(X)中;若X,Y,1,Y,2,Y,K,是一个产生式,Y,1,Y,2,Y,(i-1),都是非终结符,而且对于任何j,1,j,i,-1,FIRST(Y,j,)都含有,(即Y,1,.Y,(i-1),),则把FIRST(Y,j,)中的所有非,元素都加到FIRST(X)中;特别是,若所有的FIRST(Y,j,j=1,2,K)均含有,则把,加到FRIST(X)中.,74,FOLLOW,1.对于文法的开始符号S,置#于FOLLOW(S)中;,2.若,B 是一个产生式,则把,FIRST(),加至,FOLLOW(B)中;,3.若,B是一个产生式,或,B是,一个产生式而,(即,FIRST()),,则把FOLLOW(A),加至FOLLOW(B)中,75,作业,3。8练习 题5,8,9,14,16,验证,L(G),是匹配的括号串 G:,S,(S)S|,76,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


第三章文法和语言.ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14638922.html