《文法和语言》PPT课件.ppt

1,第四章文法和语言,本章目的为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具-形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述,2,本章知识点(内容),引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明,3,文法的直观概念和语言概述,当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用第2章所介绍的EBNF来表示这种句子的构成规则：,4,“我是大学生”。是汉语的一个句子,句子=主语谓语主语=代词名词代词=我你他名词=王明大学生工人英语谓语=动词直接宾语动词=是学习直接宾语=代词名词,5,有了一组规则以后，按照如下方式用它们导出句子：开始去找=左端的带有句子的规则并把它由=右端的符号串代替，这个动作表示成：句子主语谓语，然后在得到的串主语谓语中，选取主语或谓语，再用相应规则的=右端代替之。比如，选取了主语，并采用规则主语=代词，那么得到：主语谓语代词谓语，重复做下去，句子：“我是大学生”的全部动作过程是：句子主语谓语代词谓语我谓语我动词直接宾语我是直接宾语我是名词我是大学生,6,“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。,7,英语句子,sentencesubjectThis|Computers|Iverb-phrase|adverbneververbis|run|am|tellobjectthe|a|noununiversity|world|cheese|liesThisisauniversity.Computersruntheworld.Iamthecheese.Inevertelllies.,8,语言概述,语言是由句子组成的集合，是由一组符号所构成的集合。汉语-所有符合汉语语法的句子的全体英语-所有符合英语语法的句子的全体程序设计语言-所有该语言的程序的全体每个句子构成的规律研究语言每个句子的含义每个句子和使用者的关系,9,研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax语义Semantics语用Pragmatics,10,语法-表示构成语言句子的各个记号之间的组合规律语义-表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用-表示在各个记号所出现的行为中，它们的来源、使用和影响。,11,每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。,12,如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,13,有关定义和记号回顾,符号：可以相互区别的记号（元素）。字母表：符号（元素）的非空有穷集合。符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串2.若x是上的符号串,a是的元素,则xa是上的符号串3.y是上的符号串,当且仅当它可以由1和2导出。例如：=a,b,a,b,aa,ab,aabba都是上的符号串,14,有关定义和记号回顾,符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串.如：b是符号串banana的一个前缀.符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串.如:nana是符号串banana的一个后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串.如:ana是符号串banana的一个子串.,15,对于每个符号串s，s和两者都是符号串s的前缀，后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串x,相应地，是s的前缀，后缀或子串，并且sx符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。的长度为0连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd有a=a方幂：符号串自身连接n次得到的符号串an定义为aaaan个aa1=a,a2=aa则a0=,16,符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积定义为AB=xy|xA且yB若集合A=ab,cdeB=0,1则AB=ab1,ab0,cde0,cde1使用*表示上的一切符号串（包括）组成的集合。*称为的闭包。上的除外的所有符号串组成的集合记为+。+称为的正闭包。,17,例：=a,b*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,18,有关定义和记号,语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。例如：字母表=a,b,*=,a,b,aa,ab,ba,bb,aaa,aab,集合ab,aabb,aaabbb,anbn,或表示为w|w*且w=anbn,n1为字母表上的一个语言。集合a,aa,aaa,或表示为w|w*且w=an,n1为字母表上的一个语言。是一个语言。即是一个语言。,19,给出语言上的有关运算,设L是（上的）一个语言,M是（上的）一个语言,语言L和M的并，交，差，补是一个语言。语言L和M的并为LM，是一个语言:w|wisinLorisinM如：L1=a,b,y,zM1=1,28,9L1M1=a,b,y,z，1,28,9语言L和M的连接是一个语言，记为LMLM=st|sL且tM如：L1M1=a1,b1,y1,z1,a2,b2a9z9有L=L=L。L的n次连接Ln=LL.L,20,语言上的运算,语言L的闭包记为L*，L*=L0L1L2.L0=，Ln=LLn-1=Ln-1L,n1语言L的正闭包记为L+，L+=L1L2L3.L+=LL*=L*LL*=L+如：L1=a,b,y,zM1=1,28,9（L1M1）=a,b,y,z，1,28,9（L1M1）*=a,b,y,z，1,28,9，aa,1a,xyz,6789st.L1（L1M1）*=所有字母打头的字母和数字符号串,21,文法和语言的形式定义,如何来描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要麽能停止并回答“不是”，（要麽永远继续下去。）,22,文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.,23,定义,文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。VN和VT不含公共的元素，即VNVT=用V表示VNVT，称为文法G的字母表或字汇表规则，也称重写规则、产生式或生成式，是形如或=的(，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称作规则的右部。,24,Defineagrammar,AgrammarGisdefinedasa4-tuple(VN，VT，P，S)VNisasetofnonterminalsVTisasetofterminalsPisasetofproductions，eachproductionconsistsofaleftside,anarrow(or:=),andarightsideSisadesignationofoneofthenonterminalsasthestartsymbolV=VNVTisthealphabetofG,25,文法的定义,例文法G=（VN，VT，P，S）VN=S,VT=0,1P=S0S1,S01S为开始符号,例文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a,b,c,x,y,z,0,1,9P=a,z0,9S=,27,文法的写法1G：SaAbAabAaAbA2GS：AabAaAbASaSb3GS：Aab|aAb|SaSb,元符号:=|习惯表示大写字母：终结符小写字母：非终结符SABAAx|yBz,29,推导的定义,直接推导“”是文法G的产生式，若有v,w满足：v=,w=,其中V*,V*则称v直接推导到w,记作vw也称w直接归约到v例：G：S0S1，S010S100S1100S11000S111000S11100001111S0S1,30,.VAR;BEGINREAD()END.VARA;BEGINREAD()END.,31,推导的定义,若存在vw0w1.wn=w,(n0)则记为v=+w，v推导出w，或w归约到v若有v=+w，或v=w，则记为v=*w,32,例：G：S0S1，S010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S=+00001111S=*S00S11=*00S11,33,WhatareDerivations,Derivationisawaythatagrammardefinesalanguage.IntheprocessofderivationaproductionistreatedasarewritingruleinwhichthenonterminalontheleftsideisreplacedbythestringontherightsideoftheproductionAproductionuvisusedbyreplacinganoccurrenceofubyv.Formally,ifweapplyaproductionpPtoastringofsymbolswinVtoyieldanewstringofsymbolszinV,wesaythatzderivedfromwusingp,writtenasfollows:w=pz.Wealsouse:w=zzderivesfromw(productionunspecified)w=*zzderivesfromwusingzeroormoreproductionsw=+zzderivesfromwusingoneormoreproductions,34,句型、句子的定义,句型有文法G，若S=*x，则称x是文法G的句型。句子有文法G，若S=*x，且xVT*，则称x是文法G的句子。例：G：S0S1，S01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子00001111,01,35,例：GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号a，+，*，(和)构成的算术表达式,36,文法，语言的定义,由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)=x|S=*x，其中S为文法的开始符号，且xVT*例：G：S0S1，S01L(G)=0n1n|n1,例文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL（G）=anbnen|n1,38,SaSBE(SaSBE)aaBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE（bBbb)aabbeE（bEbe)aabbee（eEee)G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成,39,使用产生式(1)n-1次，得到推导序列：S=*an-1S(BE)n-1，然后使用产生式(2)一次，得到：S=*an-1S(BE)n-1an(BE)n。然后从an(BE)n继续推导，总是对EB使用产生式(3)的右部进行替换，而最终在得到的串中，所有的B都先于所有的E。例如，若n=3,aaaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S=*anBnEn接着，使用产生式(4)一次，得到S=*anbBn-1En，然后使用产生式(5)n-1次得到：S=*anbnEn，最后使用产生式(6)一次，使用产生式(7)n-1次，得到：S=*anbnen也能证明，对于n1，串anbnen是唯一形式的终结符号串,40,文法的等价,若L（G1）=L（G2），则称文法G1和G2是等价的。如文法G1A：A0R与G2S：S0S1等价A01S01RA1,41,文法的类型,通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式，都有(VNVT)+，(VNVT)*1型文法：对任一产生式，都有|，仅仅S除外2型文法：对任一产生式，都有VN，(VNVT)*3型文法：任一产生式的形式都为AaB或Aa，其中AVN，BVN，aVT,42,Ahierarchyofgrammars,Type0:freeorunrestrictedgrammarsThesearethemostgeneral.ProductionsareoftheformuvwherebothuandvarearbitrarystringsofsymbolsinV,withunon-null.Therearenorestrictionsonwhatappearsontheleftorright-handsideotherthantheleft-handsidemustbenon-empty.Type1:context-sensitivegrammarsProductionsareoftheformuXwuvwwhereu,vandwarearbitrarystringsofsymbolsinV,withvnon-null,andXasinglenonterminal.Inotherwords,Xmaybereplacedbyvbutonlywhenitissurroundedbyuandw.(i.e.inaparticularcontext).,43,Type2:context-freegrammarsProductionsareoftheformXvwherevisanarbitrarystringofsymbolsinV,andXisasinglenonterminal.WhereveryoufindX,youcanreplacewithv(regardlessofcontext).Type3:regulargrammarsProductionsareoftheformXaorXaYwhereXandYarenonterminalsandaisaterminal.Thatistheleft-handsidemustbeasinglenonterminalandtheright-handsidecanbeeitherasingleterminalbyitselforwithasinglenonterminal.Thesegrammarsarethemostlimitedintermsofexpressivepower.,44,文法的类型,例：1型（上下文有关）文法文法GS：SCDAbbACaCABaaBCbCBBbbBADaDCBDbDDAabD,45,文法的类型,例：2型（上下文无关）文法文法GS：SABABS|0BSA|1,46,3型文法,GS：S0A|1B|0A0A|1B|0SB1B|1|0,GI：IlTIlTlTTdTTlTd,47,文法的类型,0型文法,四种文法之间的逐级“包含”关系,3型文法,48,文法和语言,0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）,49,文法和语言,四种文法之间的关系是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。,50,根据形式语言理论,文法和识别系统间有这样的关系,0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法（上下文有关文法）：产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。,51,带a0a1a2a3a4a5a6a7a8an-1an,有限控制器,磁头,任何能用图灵机描述的计算都能机械实现，任何能在现代计算机上实现的计算都能用图灵机描述,52,2型文法（上下文无关文法CFG）：产生式的形式为A，取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合,53,3型文法产生的语言是有穷自动机（FA）所接受的集合.,定理设G=（VN，VT，P，S）是3型文法，则存在一个有穷自动机M=(K,f,A,Z)，使得L(M)=L(G)有穷自动机NFAM这样构造：=VTK=VNN,N为一个新状态,它不在VN中A=SZ=N对G中的形如DtB的产生式,t为终结符或,有f(D,t)=B；对G中形如Dt的产生式，t为终结符或,有f(D,t)=N;对VT中的每一个a,有f(N,a)=,54,G：SaA|bBAbB|aD|aBaA|bD|bDaD|bD|a|b,B,A,S,a,a,a,b,b,b,a,b,D,a,b,a,b,55,定理已知一有穷自动机M=(K,f,A,Z),存在有一个3型文法G=（VN，VT，P，S）,使得L(G)=L(M)G的定义：VT=VN=KS=A若f(D,t)=B，则DtB在P中若f(D,t)=B，且B在Z中，则Dt在P中,56,G：SaA|bBAbB|aD|aBaA|bD|bDaD|bD|a|b,B,A,S,a,a,a,b,b,a,b,b,57,正规文法和正规式对上的正规式r,存在一个RG=(VN,VT,P,S)：L(G)=L(r),初始，VT=,SVN，生成正规产生式Sr(R.1)对形如Ar1r2的正规产生式：Ar1BBr2BVN(R2)对形如Arr1的正规产生式：ArBAr1BrBBr1BVN(R3)对形如Ar1r2的正规产生式:Ar1Ar2不断应用R做变换，直到每个产生式右端至多有一个VN,58,例r=a(ad),Sa(ad)SaAA(ad)A(ad)BAB(ad)BBGs:SaAAVT=a,dAaBVN=S,A,BAdBBaBBdBB,59,正规文法和正规式对G=(VN,VT,P,S),存在一个=VT上的正规式r:L(r)=L(G),AxB,ByA=xyAxAyA=xyAxyA=xy,60,正规文法和正规式,Gs:SaA|aAaAadAdA(ad)A(ad)A(ad)(ad)S=a(ad)(ad)a=a(ad)(ad)=a(ad)R=a(ad),61,上下文无关文法及其语法树,上下文无关文法有足够的能力描述程序设计语言的语法结构语法树-句型推导的直观表示,62,例文法G=(E,+,*,i,(,),P,E)其中P为：Ei,EE+E,EE*E,E(E)E表示算术表达式,i表示程序的“变量”，该文法定义了由变量，+，*,(和)组成的算术表达式的语法结构，即：变量是算术表达式；若E1和E2是算术表达式，则E1+E2，E1*E2和(E1)也是算术表达式描述一种简单赋值语句的产生式：赋值语句i=E描述条件语句的产生式：条件语句if条件then语句if条件then语句else语句,63,句型、推导,GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a,64,规范推导规范句型,最左（最右）推导：在推导的任何一步，其中、是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型,65,语法树,设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：从左到右读出叶子的标记而构成的行谓之,66,语法树-句型推导的直观表示,给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树(推导树)定理：G为上下文无关文法，对于，有S=*，当且仅当文法G有以为结果的一棵语法树(推导树),67,构造语法树,GE：EE+T|TTT*F|FF(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a,EEE+TE+TTEE+TTF,68,EE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*aT+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*Fa+F*Fa+F*aa+a*a,EE+TTT*FFFaaa看不出句型中的符号被替代的顺序,69,上下文无关文法的语法树的用处,用于描述上下文无关文法句型推导的直观方法,例:GS:SaASASbAASSSaAba,SaASSbAaaba,句型aabbaa的语法树（推导树）,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记连接成的文法符号串，为GS的句型。也把该推导树称为该句型的语法树。,70,上下文无关文法的语法树,推导过程中施用产生式的顺序,例:GS:SaASASbAASSSaAba,SaASSbAaaba,SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa,71,一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?,72,例：GE:EiEE+EEE*EE(E),EE+EE*Eiii,EE*EiE+Eii,句型i*i+i的两个不同的最左推导：推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i,73,二义文法,若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件,74,文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。二义文法改造为无二义文法GE:EiGE：ET|E+TEE+ETF|T*FEE*EF（E）|iE(E)规定优先顺序和结合律如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。,75,句型的分析,句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,76,句型的分析算法分类,分析算法可分为：自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析法：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。,77,两种方法反映了两种语法树的构造过程。,自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树,78,自上而下的语法分析,例：文法G：ScAdAabAa识别输入串w=cabd是否为该文法的句子,SSScAdcAdab推导过程：ScAdcAdcabd,79,自下而上的语法分析,例：文法G：ScAdAabAa识别输入串w=cabd是否该文法的句子,SAAcabdcabdcabd规约过程构造的推导：cAdcabdScAd,80,(1)ScAd(2)Aab(3)Aa识别输入串w=cabd是否为该文法的句子自上而下的语法分析,若ScAd后选择(3)扩展A，ScAdcad那将会？w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。,ScAda,81,(1)ScAd(2)Aab(3)Aa识别输入串w=cabd是否为该文法的句子自下而上的语法分析,对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么最终就达不到归约到S的结果，因而也无从知道cabd是一个句子,cabdcAbda,82,句型分析的有关问题,1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：BA1|A2|An，那么如何确定用哪个右部去替代B？2）在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,83,刻画“可归约串”,文法GS句型的短语S=*A且A=+，则称是句型相对于非终结符A的短语句型的直接短语若有A，则称是句型相对于非终结符A的直接短语句型的句柄一个句型的最左直接短语称为该句型的句柄,84,例i*i+i例：i*i+i的短语、直接短语和句柄,EE+TTFT*Fi3短语：i1*i2+i3，i1*i2，Fi2i1，i2，i3。i1直接短语：i1，i2，i3。句柄：i1,GE：EE+T|TTT*F|FF(E)|i句型：i*i+i,85,左递归规则-,GS:SSaSbL=ban|n0W=baaaSbSSaSa,86,左递归关于非终结符P的规则,直接左递归若PP|、V*且不以P开头一般左递归若P=*PSAaASb,87,消除左递归,消除直接左递归形如：PP|非，不以P打头改写为：PQQQ|,88,消除左递归,例:EE+T|TTT*F|FF(E)|aGE:(1)ETE(2)E+TE(3)E(4)TFT(5)T*FT(6)T(7)F(E)(8)Fa,89,消除一般左递归要求文法:1.无回路(A(=+(A)2.无空产生式,（1）.以某种顺序将文法非终结符排列A1,A2An（2）fori:=1tondobeginforj:=1toi-1do用Ai-1|2r|kr替代形如Ai-Ajr的规则,其中Aj-1|2|k是关于Aj的全部产生式;消除Ai规则的直接左递归;end;（3）化简由2得到的文法,90,化简文法文法实用中的一些说明,文法中不含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则文法中不含有不可到达和不可终止的非终结符1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。,91,对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1.A必须在某句型中出现即有S=*A，其中，属于V*2.必须能够从A推出终结符号串t来即A=*t，其中tVT*,92,化简文法,例：GS：1)SBe2)BCeD为不可到达3)BAfC为不可终止4)AAe5)Ae6)CCf7)Df产生式2），6），7）为多余规则应去掉。,93,上下文无关文法中的规则,上下文无关文法中某些规则可具有形式A，称这种规则为规则因为规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现两种定义的唯一差别是句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果语言L有一个有穷的描述，则L1=L也同样有一个有穷的描述，并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L和L-分别是上下文有关语言、上下文无关语言和正规语言。,94,思考,本章目的为语言的语法描述寻求工具,以便：对源程序给出精确无二义的语法描述。（严谨、简洁、易读）根据语言文法的特点来进行语法分析从描述语言的文法可以自动构造出可用的分析程序制导语义翻译1.什麽是文法,什麽是它的语言?2.我们为什麽关注上下文无关文法?3.语法分析方法的分类?,95,本章小结,1.本章出现的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念.语法分析有关内容在后面章节会详细讨论.2.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的“形式”的含义只涉及语言的语法不涉及语言的语义.3.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。,本章小结考察本章知识点最典型的题目是1.已知文法GA，写出它定义的语言描述如：GA:A0B|1CB1|1A|0BBC0|0A|1CC答案:GA定义的语言由0、1符号串组成，串中0和1的个数相同.2.给出语言描述，构造文法.如：构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案1:GEEE+T|TTT*F|FF(E)|a答案2:GEEE+E|E*E|(E)|a,97,相关术语的回顾（英文版）,上下文无关文法Acontextfreegrammar(grammarforshort)consistsofterminals,nonterminals,astartsymbol,andproductions.Terminalsarethebasicsymbolsfromwhichstringsareformed.Nonterminalsaresyntacticvariablesthatdenotesetsofstringsthathelpdefinethelanguagegeneratedbythegrammar.Inagrammar,onenonterminalisdistinguishedasthestartsymbol,andthesetofstringsitdenotesisthelanguagedefinedbythegrammar.Theproductionsofagrammarspecifythemannerinwhichtheterminalsandnonterminalscanbecombinedtoformstring.,98,句型句子和语言,GivenagrammarGwithstartsymbolS,wecanusethe=*relationtodefineL(G),thelanguagegeneratedbyG.StringsinL(G)maycontainonlyterminalsymbolsofG.WesayastringofterminalswisinL(G)ifandonlyifS=*w.ThestringwiscalledasentenceofG.IfS=*,whermaycontainnonterminalsthenwesaythatisasententialformofG,99,验证文法生成的语言,AproofthatagrammarGgeneratesalanguageLhastwoparts:wemustshowthateverystringgeneratedbyGisinL,andcoverselythateverystringinLcanindeedbegeneratedbyG.,100,语法树和推导,Aparsetreemaybeviewedasagraphicalrepresentationforaderivationthatfiltoutthechoiceregardingreplacementorder.Theleavesoftheparsetreearelabeledbynonterminalsorterminalsand,readfromlefttoright,theyconstituteasententialform,calledtheyieldorfrontierofthetree.,101,句型分析，语法分析,Parsingistheprocessofdetermingifastringoftokencanbegeneratedbyagrammar.Mostparsingmethodsfallintooneoftwoclasses,calledthetop-downandbottom-upmethods.Thesetermsrefertotheorderinwhichnodesintheparsetreeareconstructed.Intheformer,constructionstartsattherootandproceedstowardstheleaves,while,inthelater,constructionstartsattheleavesandproceedstowardstheroot.,102,二义性,Agrammarthatproducesmorethanoneparsetreeforsomesetenceissaidtobeambiguous.Putanotherway,anambiguousgrammarisonethatproducesmorethanoneleftmostormorethanrightmostderivationforthesamesentence.Sometimesanambiguousgrammarcanberewrittentoeliminatetheambiguity.Forexmplesuitablegrammarsforexpressioncanoftenbeconstructedusingassociativityandprecedenceinformation,asintheslide74,103,消除左递归规则,AgrammarisleftrecursiveifithasanonterminalAsuchthatthereisaderivationA=+Aforsomestring.Aleft-recursiveproductionislike:AAinwhichtheleftmostsymbolontherightsideisthesameasthenonterminalontheleftside.ThegeneralcaseisthatanonterminalAwithtwoproductionsAA|whereandaresequencesofterminalsandnonterminalsthatdonotstartwithA.AndtheleftrecursivepairofproductionsAA|couldreplacedbythenon-left-recursiveproductions:AAAA|HereAisanewnonterminal.TheproductionAAisrightrecursive.,104,练习,1.写一文法，使其语言是偶正整数的集合。要求：允许0打头(2)不允许0打头2.证明下述文法G表达式是二义的。表达式=a|(表达式)|表达式运算符表达式运算符=+|-|*|/3.令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。,105,练习,4.给出生成下述语言的上下文无关文法：（1）anbnambm|n，m=0(2)1n0m1m0n|n，m=05.给出生成下述语言的三型文法：(1)anbm|n,m=1(2)anbmck|n,m,k=06.给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0,