编译原理第02章文法和语言的基本知识.ppt

第二章文法和语言的基本知识,字母表和符号串,文法和语言的形式定义,短语、直接短语和句柄,语法树和文法的二义性,文法和语言的分类,2.0概述,对程序设计语言的描述是从语法、语义和语用三个因素来考虑。,语法是对语言结构的定义。,语用则是从使用的角度去描述语言。,语义是描述了语言的含义。,2.0概述,例如赋值语句s2*3.1416*r*(r+h)的非形式化的描述为：,语法：赋值语句由一个变量，后随一个赋值号“”，再在其后面跟一个表达式构成。,语义：首先计算语句右部表达式的值，再将结果送给左部变量中。,语用：赋值语句可用来计算和保存表达式的值。,形式语言理论是用来对程序设计语言三要素进行形式化描述的方法。,2.1字母表和符号串,元素的非空有穷集合。,例如，=a,b,c是字母表,1.字母表,程序设计语言的字母表=x|xASCII字符=0,1,字母表中的元素称为符号或称为字符。,例如，前述例子中,2.符号（字符）,a、b、c是字母表中的符号；,0、1是字母表中的符号。,2.1字母表和符号串,例如，设有字母表=a,b,c,符号的有穷序列称为符号串。,符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成。,则有符号串a，b，ab，ba，cba，abc,3.符号串（字）,2.1字母表和符号串,说明:,不包含任何符号的符号串,称为空符号串，用表示。,符号串中符号的顺序是很重要的。,ab和ba是字母表上的两个不同的符号串。,空符号串由0个符号组成，其长度|=0,2.1字母表和符号串,2.2符号串的运算,设x和y是符号串，则串xy称为它们的连结。,则XYabc10a，YX10aabc,注意：对任意一个符号串x，,1.符号串的连结,例如，设Xabc，Y10a,我们有xxx,2.2符号串的运算,2.符号串集合的乘积,设A和B是符号串的集合,则A和B的乘积定义为：,集合的乘积是满足于xA,yB的所有符号串xy所构成的集合。,AB=xy|xA,yB,A=A=A,2.2符号串的运算,例如：,设A=aa,b,B=c,d,则AB=aac,aad,bc,bd,所以,对任意集合A,有:,2.2符号串的运算,区分：是符号串,不是集合表示由空符号串所组成的集合空集合=。,2.2符号串的运算,3.符号串的幂运算,设x是符号串,则x的幂运算定义为：,x0=,x1=x,x2=xx,x3=xxx,注意：x01,2.2符号串的运算,例如,设xabc则,x0=,x1=abc,x2=xx=abcabc,2.2符号串的运算,4.符号串集合的幂运算,设A是符号串的集合，则集合A的幂运算定义为：,A0=,A1=A,A2=AA,2.2符号串的运算,例如，设A=a,b，则,A0=,A1=A=a,b,A2=AA=aa,ab,ba,bb,A3=AAA=A2A,=aaa,aab,aba,abb,baa,bab,bba,bbb,2.2符号串的运算,5.集合A的正闭包A与闭包A*,设A是符号串的集合，则A的正闭包A和A的闭包A*的定义为:,A+=A1A2An,A*=A0A1A2An,=A+,2.2符号串的运算,例如，设A=a,b,则：,A+=a,b,aa,ab,ba,bb,aaa,aab,A*=,a,b,aa,ab,ba,bb,aaa,aab,即：闭包为集合中元素的任意组合。闭包比正闭包多含一个空符号串。,2.3文法和语言的形式定义,用A表示+,A0,A1,AA0,AA1,+=123,=0,1,00,10,11,01,000,100,2.3.1文法的形式定义,规则是一个符号与一个符号串的有序对（A,），通常写作：,A（或A),1.规则也称产生式,规则的作用是告诉我们如何用规则中的符号串生成语言中的序列。,2.3.1文法的形式定义,例如，前述例中一组规则,描述的语言序列只可能是由0和1组成的符号串。,A0,A1,AA0,AA1,2.3.1文法的形式定义,规则中符号非终结符号：出现在规则左部能派生出符号或符号串的那些符号，用大写字母表示或用尖括号把非终结符号括起来。例如，上例中的A。终结符号：不属于非终结符号的那些符号，通常用小写字母表示。例如，上例中的0和1。,2.3.1文法的形式定义,规则的非空有穷集合，通常表示成四元组,VN是规则中非终结符号的集合。,VT是规则中终结符号的集合。,P是文法规则的集合。,2.文法,G=VN,VT,P,S,2.3.1文法的形式定义,S是一个非终结符号，称为文法的开始符号或文法的识别符号，它至少要在一条规则中作为左部出现。由它开始，识别出我们所定义的语言。,由文法定义可知，文法是对语言结构的定义和描述，文法四大要素中关键是规则的集合。,2.3.1文法的形式定义,缩写为：A1|2|n,A1,A2,An,对于若干个左部相同的规则，如,i称为A的一个候选式。,2.3.1文法的形式定义,我们约定：,第一条规则的左部是识别符号。,对文法G不用四元式显示表示，仅只将规则写出。,2.3.1文法的形式定义,G=(VN，VT，P，S),VN=A,VT=0，1,P:A0|1|A0|A1,S=A,前例中描述+的文法是:,2.3.1文法的形式定义,求其VN、VT,SAAB|ifAthenAelseABC|B+C|+CCD|C*D|*DDx|(A)|-D,设文法G产生式为:,2.3.2推导和归约,推导：从文法开始符号开始，通过产生式的右部取代左部的过程，最终产生句子。,规约：从给定源语言的句子开始，通过产生式的左部取代右部的过程，最终到达开始符号。,由终结符组成的字符串,2.3.2推导和归约,最左推导，每次使用一个规则以其右部取代符号串的最左非终结符,最右推导也称为规范推导，最左规约又称为规范规约。,最右推导，每次使用一个规则以其右部取代符号串的最右非终结符,注：推导和规约的每一步只能用一个产生式进行替换。,2.3.2规范推导和规范归约,例设有文法GS:,请给出句子101001的最右、最左推导。,SAB,AA0|1B,B0|S1,2.3.2规范推导和规范归约,S,AB,AS1,AAB1,AA01,A1B01,A1001,1B1001,101001,句子101001的最右推导为:,SAB,AA0|1B,B0|S1,2.3.2推导和归约,句子101001的最左推导为：,SAB,AA0|1B,B0|S1,S,AB,1BB,10B,10S1,10AB1,101BB1,1010B1,101001,2.3.2语言的形式定义,(1)形式上的区别，推导用“”表示，规则用“”表示。,(2)对文法G中任何规则A，我们有A，即推导的依据是规则。,注意推导和规则的区别：,即表示从0出发，经一步或若干步可推导出n。,2.3.2语言的形式定义,如果存在一个推导序列：,则可表示为,012n,2.3.2语言的形式定义,例如设有文法GE=(E,T,F,i,+,*,(,),P,E),对i+i*i有如下推导序列:,我们可记为,其中P为：EE+T|T,TT*F|F,F(E)|i,E,E+T,T+T,F+T,i+T,i+T*F,i+F*F,i+i*F,i+i*i,2.3.2语言的形式定义,广义推导,我们有：,对上例EE+T|TTT*F|FF(E)|i,2.3.2语言的形式定义,4.句型和句子,设有文法GS（S是文法G的开始符号）,2.3.2语言的形式定义,例1设有文法GS：,我们有:,GS的句型：01、0S1、00S11和000111GS的句子:01和000111,S01|0S1,2.3.2语言的形式定义,例2设有文法GE：,试证明符号串(i*i+i)是文法GE的一个句子。,EE+E|E*E|(E)|i,2.3.2语言的形式定义,EE+E|E*E|(E)|i,E,(E),(E+E),(E*E+E),(i*E+E),(i*i+E),(i*i+i),（2）L(G)是VT*的子集。即属于VT*的符号串x不一定属于L(G)。,2.3.2语言的形式定义,5语言,文法GS产生的所有句子的集合称为文法G所定义的语言,记为L(GS)：,由语言定义可知：,（1）一旦文法给定，语言也就确定。,2.3.2语言的形式定义,例3设有文法GS：S01|0S1,求该文法所描述的语言是什么？,由文法推出语言,2.3.2语言的形式定义,S,0S1,00S11,0n-1S1n-1,0n1n,可见，此文法定义的语言为,L(GS)=0n1n|n1,S01|0S1,2.3.2语言的形式定义,例4设有文法GS：S0S|1S|,该文法所定义的语言是什么？,由该文法所确定的语言为,L(GS)=,0,1,00,01,10,11,=x|x0,1*,2.3.2语言的形式定义,例5设有文法GA：,该文法所定义的语言是什么？,AyBBxB|x,L(GA)=yxn|n1,2.3.2语言的形式定义,该文法所定义的语言是什么？,例6文法G:(S,A,B,a,b,c,P,S)P:SABAaA|BbBc|bc,L(G)=anbmcm,n=0,m=1,2.3.2语言的形式定义,该文法所定义的语言是什么？,例7文法G:(S,A,B,a,b,c,P,S)P:SaSABSabBBAABbAbbbBbccBcc,L(G)=anbncn,n1,2.3.2语言的形式定义,由文法确定语言的方法：从文法的开始符号出发，反复使用规则替换、展开非终结符，找出句子的规律，用式子或自然语言描述出来。,2.3.3文法的形式定义,例1设字母表=a,b，试设计一个文法，描述语言L=a2n,b2n|n1,由语言构造文法,2.3.3文法的形式定义,当n1L=aa,bb,L=aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,即语言L是由偶数个a，偶数个b这样的符号串组成的集合。,L=a2n,b2n|n1,当n2L=aaaa,bbbb,当n3L=aaaaaa,bbbbbb,2.3.3文法的形式定义,因此，定义语言L的文法,G=(VN，VT，P，S),其中：,VN=A,B,D,VT=a,b,P=Aaa,S=A,Baa,Dbb|bbD,|bb|bbD,注意:VTaa,bb,|aaB,|aaB,2.3.3文法的形式定义,问题:描述该语言的文法是否唯一呢？,显然，G不同于G。由此可见，对于一个给定的语言，描述该语言的文法是不唯一的。,P:AB|D,Baa|aBa,Dbb|bDb,等价文法:若G和G是两个不同的文法，如果它们描述的语言相同，那么，称G和G为等价文法。,2.3.3文法的形式定义,描述上例语言的文法是否G？,2.3.3文法的形式定义,G=(A,a,b,P,A),P=Aaa|bb|Aaa|Abb,2.3.3文法的形式定义,例2试设计一个表示所有标识符的文法,用I代表标识符；L代表字母；D代表数字;则定义标识符的文法为：,标识符的结构:,2.3.3文法的形式定义,G=(VN，VT，P，S),其中：,VN=I,L,D,VT=a,b,c,x,y,z,0,1,2,9,P=IL,S=I,La|b|c|x|y|z,D0|1|2|3|9,|IL,|ID,2.3.3文法的形式定义,用I代表标识符；L代表字母；D代表数字；T代表字母数字串；则定义标识符的文法还可写为：,2.3.3文法的形式定义,P:IL|LTTL|D|LT|DTLa|b|c|x|y|zD0|1|2|3|9,2.3.3文法的形式定义,若将定义标识符的文法设计成：,其中VN，VT，S同上,G=(VN，VT，P，S),P=IL|ID,La|b|c|x|y|z,D0|1|2|3|9,2.3.3文法的形式定义,该文法不能定义ab，abc仅由字母串组成的标识符，缩小了所定义语言的范围。,P=IL|ID,La|b|c|x|y|z,D0|1|2|3|9,2.3.3文法的形式定义,例3用文法定义一个含、*的算术表达式，定义用下述自然语言描述：变量是一个表达式；若E1和E2是算术表达式,则E1E2、E1*E2、(E1)也是算术表达式。,2.3.3文法的形式定义,定义算术表达式的文法为：,G=(E,i,+,*,(,),P,E),P为：Ei|E+E|E*E|(E),i,i+i,i*i,i+i*i,(i+i),注意：是符号串的集合,2.3.3文法的形式定义,例4设字母表=a,b,试设计一个文法，描述语言L=abna|n0,所以定义语言的文法为：,G=(A,B,a,b,P,A),P=AaBaBBb|,L=aa,aba,abba,2.3.3文法的形式定义,例5设字母表=(,),试设计一个文法描述语言L=(n)n|n0,P:S|(S),定义语言的文法为：,2.3.4递归规则与文法的递归性,递归规则,如果文法中有规则AA称为规则左递归。,如果文法中有规则AA称为规则右递归。,如果文法中有规则AA称为规则递归。,2.3.4递归规则与文法的递归性,文法的递归性,2.3.4递归规则与文法的递归性,例1文法中有如下规则：,这三条规则都不是递归规则，但有,UVx,VUy|z,UVxUyx,则该文法是左递归的。,2.3.4递归规则与文法的递归性,例2考虑文法GA：,由于该文法无递归性，由它所描述的语言是有穷的。该文法描述的语言为:,AaB|bB,Ba|b,L(GA)=aa,ab,ba,bb,文法递归的意义：,2.3.4递归规则与文法的递归性,例3考虑文法GN1,该文法有直接左递归规则NND,则称该文法为左递归文法或说文法左递归，其定义的语言为0,1,2+。,N1N,NND|D,D0|1|2,2.3.4递归规则与文法的递归性,在文法中使用递归规则，使得我们能用有限的规则去定义无穷集合的语言。,若不用递归规则，则NND需要用ND|DD|DDD|即无穷多条规则来定义由数字0,1,2组成的所有无符号整数。,2.4语法树,推导和语法树,1.语法树,对句型的推导过程给出一种图形表示,这种表示称为语法树，也称推导树。,2.4语法树,例如设有文法GE:,构造句型i*i+i的语法树。,推导过程(最左推导)：,EE+T|ET|T,TT*F|T/F|F,F(E)|i,EE+TT+TT*F+TF*F+Ti*F+Ti*i+Ti*i+Fi*i+i,2.4语法树,根据推导过程构造句型i*i+i的语法树如下：,EE+T,E,E,+,T,T+T,T,T*F+T,T,*,F,F*F+T,F,i*F+T,i,i*i+T,i,i*i+F,F,i*i+i,i,2.4语法树,因为文法的每一个句型(句子)都存在一个推导，所以文法的每个句型(句子)都存在一棵对应的语法树。,EE+TE+FE+iT+iT*F+iT*i+iF*i+ii*i+i,2.4语法树,对句型i*i+i，还可给出最右推导：,2.4语法树,这也就是说，一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程,包括最左(最右)推导。,2.4语法树,2.子树,语法树的子树是由某一结点连同其所有分枝组成的部分。,2.4语法树,3.简单子树,语法树的简单子树是指只有单层分枝的子树。(即一步推导),2.4语法树,句型的短语、直接短语和句柄的直观解释是：,短语：子树的末端结点形成的符号串是相对于子树根的短语。,直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。或者：某子树根经过1步推导而获得的短语。,句柄：句型中最左直接短语。,2.4语法树,短语:,i*i+i,i*i,第一个i,第二个i,第三个i,三个i都是直接短语,第一个i是句柄,注意:i+i不是句型的短语,句子i*i+i,2.4语法树,前例对文法GS=(S,A,B,a,b,P,S),其中P为：,求出句型baSb的全部短语，直接短语和句柄。,SAB,AAa|bB,Ba|Sb,2.4语法树,句型baSb的推导过程如下：,Sb为句型的相对于B的短语、直接短语,baSb为句型的相对于S的短语,ba为句型的相对于A的短语,a为句型的相对于B的短语、直接短语和句柄,SABbBBbaBbaSb,SABASbbBSbbaSb,由语法树可知,2.5.1文法的二义性,文法的某个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左(最右)推导呢？,例如设有文法GE：,句子i*i+i有两个不同的最左推导，对应两棵不同的语法树。,EE+E|E*E|(E)|i,2.5.1文法的二义性,最左推导1EE+EE*E+Ei*E+Ei*i+Ei*i+i,最左推导2EE*Ei*Ei*E+Ei*i+Ei*i+i,2.5.1文法的二义性,如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义性的。,EE+E|E*E|(E)|i,2.5.2文法二义性的消除,1.不改变文法中原有的语法规则,仅加进一些非形式的语法规定。,2.5.2文法二义性的消除,2.构造一个等价的无二义性文法。即把排除二义性的规则合并到原有文法中,改写原有的文法。,例如，对于上例文法GE，将运算符的优先顺序和结合规则：*优先于;、*左结合加到原有文法中,可构造出无二义性文法如下：,2.5.2文法二义性的消除,则句子i*i+i只有唯一一棵语法树：,EE+T|T,TT*F|F,F(E)|i,2.5.2文法二义性的消除,例2定义某程序语言条件语句的文法G为:,试证明该文法是二义性的并消除之。,分析该文法的句子ifbifbAelseA对应下面两棵不同的语法树：,SifbS,|ifbSelseS,|A(其它语句）,2.5.2文法二义性的消除,所以该文法是二义的。,SifbS|ifbSelseS|A,句子ifbifbAelseA,2.5.2文法二义性的消除,消除文法的二义性可采用下面两种方法：,不改变已有规则，仅加进一非形式的语法规定：else与前面最接近的不带else的if配对。,文法G的句子ifbifbAelseA只对应唯一的一棵语法树，消除了二义。,2.5.2文法二义性的消除,2.改写文法G为G,SS1|S2,S1ifbS1elseS1|A,S2ifbS|ifbS1elseS2,G:,SifbS,|ifbSelseS,|A(其它语句）,G:,2.5.2文法二义性的消除,这是因为通过分析，得知引起二义性的原因是:ifelse语句的if后可以是if句型，因此改写文法时规定:ifelse之间只能是ifelse语句或其他语句。,2.5.2文法二义性的消除,SS1|S2,S1ifbS1elseS1|A,S2ifbS|ifbS1elseS2,对改写后的文法，句子ifbifbAelseA只对应唯一的一棵语法树。,通常我们只说文法的二义性,而不说语言的二义性,这是因为可能有两个不同的文法G和G，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G),即这两个文法所产生的语言是相同的。,2.5.2文法二义性的消除,应该指出的是文法的二义性和语言的二义性是两个不同的概念。,2.5.2文法二义性的消除,将一个语言说成是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。例如L=aibjck|i=j或j=k且i,j,k1便是这种语言。,2.6文法和语言的分类,著名的语言学家乔姆斯基(Chomsky)将文法和语言分为四大类，即0型、1型、2型、3型。划分的依据是对文法中的规则施加不同的限制。,2.6文法和语言的分类,0型文法（无限制文法）,若文法G=(VN,VT,P,S)中的每条规则是这样一种结构：,而且中至少含一个非终结符,则称G是0型文法。,(VNVT)+,(VNVT)*,0型文法描述的语言是0型语言。,0型文法没有加任何限制条件，又称为无限制性文法，相应的语言称为无限制性语言。,0型语言由图灵机识别。,2.6文法和语言的分类,例如，有0型文法G=(VN,VT,P,S),其中：VN=A,B,S,VT=0,1,其描述的0型语言为L0(GS)=,P:S0AB,1B0,BSA|01,A1SB1,A0S0B,2.6文法和语言的分类,1型文法（上下文有关文法）,1型文法也称为上下文有关文法，相应的语言又称为上下文有关语言。,若文法G=(VN,VT,P,S)中的每一条规则的形式为A,其中：,(VNVT)*,AVN,则称G是1型文法。,1型文法描述的语言是1型语言。,1型语言由线性界限自动机识别。,(VNVT)+,2.6文法和语言的分类,例如，有1型文法G=(VN,VT,P,S),其中：VN=S,A,B,VT=a,b,c,P:SaSAB|abB,BABA,BAAA,AAAB,bAbb,bBbc,cBcc,其描述的1型语言为L1(GS)=anbncn|n1,2.6文法和语言的分类,2型文法（上下文无关文法）,2型文法又称上下文无关文法，其产生的语言又称为上下文无关的语言。,若文法G=(VN,VT,P,S)中的每一条规则的形式为A,其中：,AVN,(VNVT)*,则称G是2型文法。,2型文法描述的语言是2型语言。,2型语言由下推自动机识别。,例如前面描述算术表达式的文法GE:,EE+E|E*E|(E)|i,2.6文法和语言的分类,其描述的语言为L2(GS)=x|xa,b+且x中a和b的个数相同,例如，有2型文法G=(VN,VT,P,S),其中：VN=S,A,B,VT=a,b,P=SaB|bA,Aa|aS|bAA,Bb|bS|aBB,2.6文法和语言的分类,2.6文法和语言的分类,3型文法（正规文法）,右线性文法和左线性文法都称为3型文法。,若文法G=(VN,VT,P,S)中的每一条规则的形式为AaB或Aa,其中：,A,BVN,aVT*,则称G是右线性文法。,若文法G=(VN,VT,P,S)中的每一条规则的形式为ABa或Aa,其中：,A,BVN,aVT*,则称G是左线性文法。,3型文法描述的语言是3型语言。,3型语言由有穷自动机识别。,3型文法也称正规文法。正规文法产生的语言称为正规语言。,例如，用左线性正规文法和右线性正规文法定义标识符,2.6文法和语言的分类,用I代表标识符;l代表任意一个字母;d代表任意一个数字;则定义标识符的文法为：,左线性文法:P:Il|Il|Id,右线性文法:P:Il|lTTl|d|lT|dT,例如，用左线性正规文法和右线性正规文法定义无符号整数,2.6文法和语言的分类,用N代表无符号整数;d代表任意一个数字；则定义无符号整数的文法为：,左线性文法:P:NNd|d,右线性文法:P:NdN|d,2.6文法分类总结,0型文法：左部：VN和VT组成(可以由多个VN多个VT组成,但至少一个VN)右部：VN和VT组成(可以由多个VN多个VT组成)。1型文法：左部：VN和VT组成(可以由多个VN多个VT组成,且至少一个VN)右部：VN和VT组成(可以由多个VN多个VT组成)。|左部|=|右部|,2.6文法分类总结,2型文法：左部：只有一个VN。右部：VN和VT组成(可以由多个VN多个VT组成)。3型文法：左部：只有一个VN。右部：最多一个VN，且在最左或最右。,2.6文法和语言的分类,从0型文法到3型文法,是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法。四类文法描述语言的关系：L0L1L2L3。,2.7有关文法的实用限制和变换,1.文法中不能含有形如AA的规则。这种规则我们称之为有害规则。,对文法的实用限制有两点：,2.7有关文法的实用限制和变换,2.文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：,(1)某条规则A的左部符号A(除S外)不在所属文法的任何其他规则右部出现。,(2)对文法中的某个非终结符A，无法从它推出任何终结符号串来。,2.7有关文法的实用限制和变换,例如设有文法GS:,P:SBd,AAd|d,BCd|Ae,CCe,De,删除多余规则后的文法变换为:,P:SBd,AAd|d,BAe,2.7有关文法的实用限制和变换,若程序设计语言的文法含有多余规则，其中必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。,作业,第1章,1、编译过程包括哪几个主要阶段及每个阶段的功能。,第2章,1、写一上下文无关文法G，它能产生配对的圆括号串（如：(),(),()()等，甚至包括0对括号）2、已知文法G：EE+T|E-T|TTT*F|T/F|FF(E)|i（1）给出i+i*i,i*(i-i)的最左推导，最右推导以及语法树。（2）i-i+i哪个算符优先。,第2章,3、文法G:EET+|TTTF*|FFFP|PPE|i（1）试证明符号串TET+*i是G的一个句型(要求画出语法树).（2）写出该句型的所有短语,直接短语和句柄.4、已知文法G：SiSeS|iS|i，该文法是二义文法吗？为什么？,本章重点介绍了语言的语法结构的形式描述、语法树以及文法的二义性,主要内容有：,1.设计一个文法定义一个已知的语言,(1)文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。,从文法定义可知,文法对于程序设计者来说，文法给出了语言的精确定义和描述。,本章小结,本小结花时45分钟,(2)分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。,(4)若语言是无穷集合,设计该语言的文法一定是递归的。,本章小结,(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。,分析根据语言句子的结构特征，设计出相应规则,例1.给出语言L2=anbm|mn1的文法,P2:SAB,L2=ab,abb,abbb,aabb,aabbb,aabbbb,aaabbb,aabbbb，,AaAb|ab,BbB|,本章小结,分析根据语言句子的结构特征，设计出相应规则,例2.给出语言L1=a2n+1|n0的文法,P1:AaB|a,P1：AaAa|a,或,L1=a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，,Baa|aBa,本章小结,本章小结,分析根据语言句子的结构特征，设计出相应规则,例3.给出语言L3=anbmck|n,m,k0的文法,P3:AaA|bB|cC|,P3:AaA|B,或,L3=,a,aa,aaa,b,bb,bbb,c,cc,ccc,ab,abb,bc,bcc，,CcC|,BbB|cC|,CcC|,BbB|C,本章小结,L4=0,2,4,6,8,10,12,14,16,18,20,22,24,26,例4.写一个文法,使其语言是正偶数的集合,每个偶数不以0开头。,P4:NE|AE,N0|2|4|6|8|BN,或,分析不以0开头的偶数集合中串的结构特征:,AD|AD,E0|2|4|6|8,D1|2|3|9,D0|1|2|3|9,B1|2|3|9|B0,P4:,本章小结,A0A1|,P:S1S0|0A1|,例5.给出语言L=1n0m1m0n|n,m0的文法。,分析根据语言句子的结构特征,设计出相应规则,L=,01,0011,10,1100,1010,100110,110100,11001100,本章小结,P:Sa|0S0|1S1,例6.给出语言L=WaWt|W0|1*,Wt表示W的逆的文法。,分析根据语言句子的结构特征，设计出相应规则,L=a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,W=,0,1,01,10,00,11,101,110,100,111,本章小结,2.已知一个文法，确定该文法所定义的语言。,(2)给定一个文法，可根据语言和推导定义推导出文法的句子，从而确定出该文法所定义的语言。,本章小结,自然语言描述。例如,L=x|xa,b+且x中a,b个数相同,式子描述。例如L=a2nbb|n0。,正规式描述。,(3)语言可用,本章小结,例1文法GA=(A,a,b,AbA|a,A)所生成的语言是什么？,分析AbAbbAbbbAbnAbna,L(GA)=bna|n0,本章小结,例2文法GN为:,NND|DD0|1|2|3|4|5|6|7|8|9,(1)GN所生成的语言是什么？,(2)给出句子0127的最左、最右推导。,本章小结,L(GN)=|0,1,2,9+,=|为可带前导0的正整数,=|为数字串,最左推导:,NNDN7ND7N27ND27N127D1270127,最右推导