chap3-文法和语言.ppt

2020年6月1日,授课教师：张雁,1,教学纲要,教学目标与要求掌握文法和语言的形式定义掌握文法的类型掌握上下文无关文法及其语法树了解句型分析的方法掌握句柄、短语等概念,2020年6月1日,授课教师：张雁,2,教学纲要,教学的重点和难点文法和语言的形式化定义文法的分类二义性文法的判断判断句型的短语、直接短语和句柄语言和文法之间的转换教学时间4学时作业,2020年6月1日,授课教师：张雁,3,文法和语言,3.0计算机语言3.1文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型的分析3.6.1自上而下的分析方法3.6.2自下而上的分析方法3.6.3句型分析的有关问题3.7有关文法实用中的一些说明,2020年6月1日,授课教师：张雁,4,3.0计算机语言（一）,计算机语言的组成结构,2020年6月1日,授课教师：张雁,5,3.0计算机语言（二）,计算机语言的共同点语法：语句的组成规则描述方法：BNF范式、语法描述图词法：单词的组成规则描述方法：BNF范式、正规式单词：具有语义的最小字符串（可区分的）,2020年6月1日,授课教师：张雁,6,3.0计算机语言（三）,语言的描述方法叙述性方法自然语言（非形式化描述）记号方法数学方法（形式化描述）保证描述清晰准确形式化描述的作用理论基础和抽象分析方法,2020年6月1日,授课教师：张雁,7,3.1文法的直观概念,自然语言是由无穷多个句子所组成，我们可用一些规则（语法）来定义句子的组成结构。以汉语为例，参看教材32页形如上述规则对汉语句子的语言描述就称为文法。推导符号=使用一条规则，代替=左边的某个符号,产生=右端的符号串,2020年6月1日,授课教师：张雁,8,3.2符号和符号串（一）,字母表：元素（符号）的非空有穷集合。Ex机器语言：由符号“0”和“1”组成的字母表,=0，1ASCII字符集；汉语的字母表中包括汉字、数字及标点符号C字母表为：=AZ,az,09,+,-,*,/,:,;，.，,(,),2020年6月1日,授课教师：张雁,9,符号和符号串（二）,符号：字母表中的元素。（通常用大写字母表示）符号串：字母表中的符号组成的任意有穷序列。（小写字母）长度：符号的个数|001101|=6空符号串：|=0符号串的头和尾：z=xyx是z的头，y是z的尾若y，称x是z的固有头或真前缀若x，称y是z的固有头或真后缀子串:删去一个前缀和一个后缀逆转：将符号串中的符号按相反次序写出而得到的符号串。,2020年6月1日,授课教师：张雁,10,符号和符号串（三）,Ex:符号串z=banana长度：banana=6前缀：e,b,ba,ban,bana,banan,banana真前缀:e,b,ba,ban,bana,banan后缀：banana,anana,nana,ana,na,a,e真后缀:anana,nana,ana,na,a,e子串:banana,anana,banan,anan,e逆转（用z表示）：ananab,2020年6月1日,授课教师：张雁,11,符号和符号串（四）,符号串集合的运算1.连接eg.x=aby=cdexy=abcde|xy|=5特例：x=x=x2.方幂An=AAA=AAn-1=An-1AEx:x=ba,x1=ba,x2=baba,x3=bababa,xn=(ba)n,2020年6月1日,授课教师：张雁,12,符号和符号串（五）,3.乘积AB=xy|(xA)(yB)eg:A=a,b,B=c,dAB=ac,ad,bc,bd4.+(符号串集合的正闭包）:由字母表A上的符号组成的所有串(不包括空串)的集合。+=12nExample:A=a,bA+a,b,aa,ab,ba,bb,aaa,aab,aba,abb,2020年6月1日,授课教师：张雁,13,符号和符号串（六）,5.*（符号串集合的闭包）：字母表A的各次方幂之并。其含义是由A上符号组成的所有串的集合（包括空串)*=0+=+=*=*=*ExampleA=a,bA*,a,b,aa,ab,ba,bb,aaa,aab,aba,abb,2020年6月1日,授课教师：张雁,14,3.3文法和语言的形式定义（一）,文法的形式定义1.规则（产生式）规则是一个有序对（，），表示为：或:=V+，V*(其中V为字母表）为规则的左部，为规则的右部。,2020年6月1日,授课教师：张雁,15,文法和语言的形式定义（二）,2.文法G的形式定义（定义3.1)文法是规则的非空集合，表示为四元组（VN,VT,P,S)VN：非终结符号（规则左部出现的符号）VT：终结符（规则中不属于VN的符号）VNVTVNV：产生式（规则）的集合：识别符号（开始符号，至少应在一条规则中作为左部出现。句子的语法有四部分：终结符号集，非终结符号集，语法规则，开始符号。,2020年6月1日,授课教师：张雁,16,文法和语言的形式定义（三）,Example:终结符号集VT=我,你,他,王明,大学生,英语,是,学习非终结符号集VN=，语法规则集P=，开始符号S=注：习惯约定351）2）3）Eg:P32,2020年6月1日,授课教师：张雁,17,文法的写法,G=(S,A，a,b，P，S)其中P：SaAbAabAaAbAG：SaAbAabAaAbAGS：AabAaAbASaAbGS：Aab|aAb|SaAb,2020年6月1日,授课教师：张雁,18,文法和语言的形式定义（五）,推导与归约-推导是使用产生式的右部取代左部的过程称为推导-归约是将左部取代右部的过程称为归约。推导的分类-直接推导-推导-广义推导-最左推导-最右推导,2020年6月1日,授课教师：张雁,19,文法和语言的形式定义（六）,1.直接推导（定义3.2）产生式右部代替左部当是文法的一个产生式，且、（TN）*，称是的直接推导，记为=例：EE*Ei+E=i+E*E,2020年6月1日,授课教师：张雁,20,文法和语言的形式定义（七）,2.推导（长度为n的推导）定义3.3如果存在直接推导的序列：v=w0=w1=w2=wn=w(n0)，称v推导出（产生）w（推导长度n）或称w归约到v。记为v=+w（一步或多步）定义3.4广义推导若有v=+w或v=w，则记为v=*w（零步或多步）,2020年6月1日,授课教师：张雁,21,文法和语言的形式定义（八）,3.句型和句子（定义3.5）设GS是一文法，若符号串x是从开始符号S推导出来的，即有S=*x，则称x是文法GS的句型。若x仅由终结符组成，即xVT*，则称x为GS的句子4.语言（定义3.6）L(GS)=x|S=*x，xVT*为文法G所产生的语言。NOTE:句子是仅由终结符组成的句型，所以，一个符号串不是句型，则一定不是句子。而若某一符号串不是句子，它还可能是句型，关键在于它能否由开始符号推出。,2020年6月1日,授课教师：张雁,22,文法和语言的形式定义（九）,ExampleGS:SaAbABcA|BBidt|S=aAb=aBcAb=aidtcAb=aidtcBcAbS=aAb=aBcAb=aidtcBcAb=aidtccAb=aidtccAb=aidtccBb=aidtccb=aidtccbS=aAb=aBb=ab=ab,2020年6月1日,授课教师：张雁,23,文法和语言的形式定义（十）,考虑一个文法G(0,1,S,S，P),其中P：S0S1|01结果为：L(GS)=0n1n|n1,S=01句型S,01句子01,S=01=0011句型S,0S1,0011句子0011,S=0S1=00S11=03S13=.=0n-11n-1=0n1n,2020年6月1日,授课教师：张雁,24,文法和语言的形式定义（十一）,等价文法定义3.若L(G1)=L(G2)，则称文法G1和G2是等价的,L(GS)=L(GA)GS和GA等价,2020年6月1日,授课教师：张雁,25,文法和语言的形式定义（十二）,NOTE:文法等价是指从两个文法得到的语言句子在结构上是等价的，而含义上不一定等价。结论：一个语言所对应的文法不唯一。,2020年6月1日,授课教师：张雁,26,文法和语言的形式定义（十三）,递归产生式递归：同一操作或一组操作的连续重复。递归产生式：左部和右部出现了相同非终结符的产生式。递归产生式的形式左递归产生式UU右递归产生式UU自嵌入产生式UU,2020年6月1日,授课教师：张雁,27,文法和语言的形式定义（十四）,递归文法直接递归：文法中有递归产生式。间接递归：经若干步推导，出现递归。例:UVxVUy|z对如下的推导：UVxUyx，出现递归递归文法的用处用于定义无限语言(递归语言)总结语言无限，一定存在递归。语言有限，一定不存在递归。,2020年6月1日,授课教师：张雁,28,文法和语言的形式定义（十五）,ExampleGS:SaB|bBBa|b,S=aB=aa,S=aB=ab,S=bB=ba,S=bB=bb,L(GS)=aa,ab,ba,bb,2020年6月1日,授课教师：张雁,29,文法和语言的形式定义（十六）,文法G的作用以有限的规则描述无限的语言现象有限：产生式集合终结符集合非终结符集合无限：由开始符号导出的句子,2020年6月1日,授课教师：张雁,30,3.3Example（一）,给出文法，得出对应的语言例:G:|0|1|2|3|9,2020年6月1日,授课教师：张雁,31,Example（二）,解：分析过程如下：DNS1位数0|1|9DNNSSS0S|1S|9S2位数DNNSNSSSSS0SS|9SS3位数L(GD)=V+V=0,1,，9,2020年6月1日,授课教师：张雁,32,Example（三）,例:GS：SaA|aAaS解：分析过程如下：SaSaAaaSaaaSaAaaSaaaAaaaaSaaaaaL(GS)=a2n+1|n=0,2020年6月1日,授课教师：张雁,33,3.4文法的类型（一）,Chomsky根据对规则施加不同的限制，将文法和语言分为四类0型文法（短语文法）形如V+,V*产生的语言：0型语言（递归可枚举）推论：0型语言图灵机（Turing）说明：对规则无限制,2020年6月1日,授课教师：张雁,34,3.4文法的类型（二）,1型文法（上下文有关）满足：|（除S）产生的语言：1型语言（上下文有关）2型文法(上下文无关)满足VN,V*限制:无需考虑在上下文中的出现情况产生的语言:2型语言(上下文无关),2020年6月1日,授课教师：张雁,35,3.4文法的类型（三）,3型文法(正则文法)1.右线性文法a或aBB,VN,aVT2.左线性文法a或BaB,VN,aVT限制:一个文法中的规则全部是1或全部是2的形式产生语言:正则语言(3型语言),2020年6月1日,授课教师：张雁,36,文法的类型（四）,2020年6月1日,授课教师：张雁,37,3.4文法的类型（五）,3型,2型,1型,0型,2020年6月1日,授课教师：张雁,38,3.4文法的类型（六）,文法分类的意义程序设计语言的词法规则属于正规文法语法和与语义的规则采用上下文无关文法,2020年6月1日,授课教师：张雁,39,3.5上下文无关文法及其语法树（一）,语法树1.语法树的定义设文法G=(VN,VT,P,S),则满足以下条件的树称为一棵语法树：1）每个结点都有一个标记M，MV；2）根的标记为S；3）若一个结点至少有一后继结点，则该结点上的标记必为VN;4)若一个标记为A的结点，有标记依次（从左到右）的次序为A1,A2,Ak为其后继结点，则必有AA1A2Ak一定是P中的一个产生式。,2020年6月1日,授课教师：张雁,40,上下文无关文法及其语法树（二）,语法树用于直观地描述推导过程例G=(S,A,a,b,P,S),其中P:SaAS|aASbA|SS|ba,2020年6月1日,授课教师：张雁,41,上下文无关文法及其语法树（三）,用树的形式表示句子的结构树根：开始符号中间结点：非终结符叶结点：终结符每个推导对应一个中间结点及其儿子,2020年6月1日,授课教师：张雁,42,上下文无关文法及其语法树（四）,2.语法树与推导1）语法树的画法从开始符出发，向下画一个分枝，表示第一个直接推导；再从VN符号往下画分枝，表示即将进行的直接推导直至全部推导都在树上表示出来。Eg:P41NOTE:语法树表示了在推导过程中施用了哪个产生式和施用在哪个非终结符上，它并没有表明施用产生式的顺序。,2020年6月1日,授课教师：张雁,43,上下文无关文法及其语法树（五）,2）推导在推导的任何一步=，、是句型，都是对中的最左（最右）的VN进行替换，则称其为最左（右）推导。最右推导称为规范推导，由规范推导所得的句型称为规范句型。语法树和推导之间的对应关系每一棵语法树至少存在一个推导与之对应，每一个推导都存在一棵语法树。,2020年6月1日,授课教师：张雁,44,上下文无关文法及其语法树（六）,例如：已知文法GS，P：SaAS|aASbA|SS|ba，对字符串aabbaa，根据推导过程得到的语法树如下：,2020年6月1日,授课教师：张雁,45,上下文无关文法及其语法树（七）,结论两种推导的结果相同，推导的步数相同，只是中间句型不完全相同。对于任何上下文无关文法，从其开始符号出发可推导的句子集合与推导期间选择非终结符进行扩展的顺序是无关的。,2020年6月1日,授课教师：张雁,46,上下文无关文法及其语法树（八）,注意：语法树的顺序性例如：PSaAS|aASbA|SS|ba，上图的推导过程正确，下图的推导过程是错误的。原因是语法树的一个分枝的顺序是按产生式右部的顺序排列的。,2020年6月1日,授课教师：张雁,47,上下文无关文法及其语法树（九）,二义性1.ExampleP412.定义如果文法G中的某个句子存在两棵以上的语法树，则称该句子是二义性的。若一个文法含有二义性的句子，则称该文法是二义的。3.排除文法的二义性在语义上加限制重新构造一个无二义性的文法NOTE:不存在一个算法，能在有限步骤内，确切判定任给的一个文法是否为二义的。,2020年6月1日,授课教师：张雁,48,3.5上下文无关文法及其语法树（十）,判别文法是否具有二义性的方法只要判别文法是否定义有这样的句子：该句子对应着两棵语法树，或者说有两个不同的最右（左）推导。eg:文法GPPPaP|PbP|cP|Pe|f考虑句子fbfbf，它对应了两棵不同的语法树所以该文法是二义性文法。,2020年6月1日,授课教师：张雁,49,3.6句型的分析（一）,句型的分析1.定义识别一个符号串是否为某文法的句型，是某个推导的构造过程。2.分析算法（分析程序）完成句型分析的算法（程序）3.分析算法的分类自上而下自下而上,2020年6月1日,授课教师：张雁,50,句型的分析（二）,自上而下的分析方法1.基本思想从文法开始符开始，作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。2.ExampleP43,2020年6月1日,授课教师：张雁,51,句型的分析（三）,自下而上的分析方法1.基本思想从输入的符号串开始，以它作为语法树的末端结点符号串，逐步进行“归约”，直至归约到文法的开始符号。2.ExampleP43,2020年6月1日,授课教师：张雁,52,句型的分析（四）,句型分析的有关问题1.存在的问题1）自上而下分析方法中的主要问题假定要被代替的最左VN是V，且有n条产生式V1|2|n，如何确定用哪个右部去替代V以后章节将介绍：回溯的方法来解决2）自下而上分析方法每一步如何确定“可归约串”（“句柄”）,2020年6月1日,授课教师：张雁,53,3.6句型的分析（五）,2.定义“规范归约”中的“句柄”短语GS中，w=是它的一个句型，若有：S=*A且A=+称是句型相对于非终结符A的短语。简单句型A=称是句型的简单短语句柄句型的最左简单短语3.ExampleP44,2020年6月1日,授课教师：张雁,54,3.6句型的分析（六）,E,E,+,T,T,*,F,F,i1,i2,i3,求短语、简单短语和句柄,2020年6月1日,授课教师：张雁,55,3.6句型的分析（七）,语法树与简单短语语法树子树的末端结点符号即是语法树所描述句型（相对于子树的根）的短语，简单子树（只有父子两代或此子树的高度为1）的末端结点符号即是简单短语，最左简单子树的末端结点符号串是句柄。eg:GEEE+T|E-T|TTT*F|T/F|FF(E)|I求出句型(F+i)-T*(E-T)的短语、简单短语和句柄。,2020年6月1日,授课教师：张雁,56,3.6句型的分析（八）,Answer短语：F,I,F+i,(F+i),E-T,(E-T),T*(E-T),(F+i)-T*(E-T)简单短语为：F,i,E-T句柄为:F,2020年6月1日,授课教师：张雁,57,3.7有关文法实用中的一些说明（一）,文法的实用限制1.文法中不含形如UU的产生式2.文法中不包含多余规则（产生式）1）不含有不可达的VN；2）不含有不可终止的VN3.保证任一终结符A在句子推导中出现，满足以下条件：1）A必须在某句型中出现；2）从A能推导出终结符号串t。,2020年6月1日,授课教师：张雁,58,3.7有关文法实用中的一些说明（二）,上下文无关文法中的规则形如A，其中AVN的规则（产生式）称为规则（产生式）。规则并不影响文法所产生的语言的类型。结论：若L是上下文有关语言、上下文无关语言或正规语言，则