第02章_文法和语言的基本知识(2)精.ppt

《第02章_文法和语言的基本知识(2)精.ppt》由会员分享，可在线阅读，更多相关《第02章_文法和语言的基本知识(2)精.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第02章_文法和语言的基本知识(2)第1页，本讲稿共71页 2.2.4 4 语法树语法树例如设有文法GE:构造句型i*i+i的语法树。首先给出句型的推导过程(最左推导)：EE+T|ET|TTT*F|T/F|FF(E)|iEE+TT+TT*F+TF*F+Ti*F+Ti*i+Ti*i+Fi*i+i第2页，本讲稿共71页2.2.4 4 语法树语法树根据推导过程构造句型i*i+i的语法树如下：EE+TEE+TT+TTT*F+TT*FF*F+TFi*F+Tii*i+Tii*i+FFi*i+ii第3页，本讲稿共71页2.2.4 4 语法树语法树 由例可知，语法树的构造过程是从文法的开始符号出发，构造一个推

2、导的过程。因为文法的每一个句型(句子)都存在一 个推导，所以文法的每个句型(句子)都存在一棵对应的语法树。第4页，本讲稿共71页EE+TE+FE+iT+iT*F+iT*i+iF*i+ii*i+i2.2.4 4 语法树语法树 对句型i*i+i，还可给出最右推导：EE+TTT*FFiiFi第5页，本讲稿共71页2.2.4 4 语法树语法树 这也就是说，一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程,包括最左(最右)推导。第6页，本讲稿共71页2.4 2.4 语法树语法树 2.子树语法树的子树是由某一结点连同所有分枝组成的部分。EE+TTT*FFiiFi第7页，本讲稿共71页2.

3、4 2.4 语法树语法树 3.简单子树语法树的简单子树是指只有单层分枝的子树。(即一步推导)EE+TTT*FFiiFi第8页，本讲稿共71页2.2.4 4 语法树语法树 句型的短语、直接短语和句柄的直观解释是：短语：子树的末端结点形成的符号串是相对于子树根的短语。直接短语：简单子树的末端结点形成的符号串是相对于简单子树根的直接短语。或者：某子树根经过1步推导而获得的短语。句柄：句型中最左直接短语。第9页，本讲稿共71页2.2.4 4 语法树语法树短语:ni*i+ini*in第一个in第二个in第三个in三个i都是直接短语n第一个i是句柄注意:i+i不是句型的短语句子i*i+iEE+TTT*FF

4、iiFi第10页，本讲稿共71页2.2.4 4 语法树语法树 前例对文法GS=(S,A,B,a,b,P,S)其中P为：可用语法树非常直观地求出句型baSb的全部短语，直接短语和句柄。SABAAa|bBBa|Sb第11页，本讲稿共71页2.2.4 4 语法树语法树 分析首先根据句型baSb的推导过程画出对 应的语法树如下：Sb为句型的相对于B的短语、直接短语baSb为句型的相对于S的短语ba为句型的相对于A的短语a句型的相对于B的短语、直接短语和句柄SABbBBbaBbaSbSABASbbBSbbaSbSABbB Sba由语法树可知第12页，本讲稿共71页2.5.2.5.1 1 文法的二义性文法

5、的二义性从前面的讨论可以看出，对于文法G中任一句型的推导序列,我们总能为它构造一棵语法树，现在我们提出一个问题：文法的某个句型是否只对应唯一的一棵语法树呢？也就是，它是否只有唯一的一个最左(最右)推导呢？第13页，本讲稿共71页2.5.2.5.1 1 文法的二义性文法的二义性 例如设有文法GE：句子i*i+i有两个不同的最左推导，对应两棵不同的语法树。EE+E|E*E|(E)|i第14页，本讲稿共71页2.5.2.5.1 1 文法的二义性文法的二义性 最左推导1EE+EE*E+Ei*E+Ei*i+Ei*i+i最左推导2EE*Ei*Ei*E+Ei*i+Ei*i+iEE*EE+EiiiEE+EE*

6、Eiii第15页，本讲稿共71页2.5.2.5.1 1 文法的二义性文法的二义性 如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义性的。或者说，若一个文法中存在某个句子，它有两个不同的最左(最右)推导，则这个文法是二义性的。EE+E|E*E|(E)|i第16页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除 1.不改变文法中原有的语法规则,仅加进一些非形式的语法规定。EE+EE*Eiii第17页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除2.构造一个等价的无二义性文法。即 把排除二义性的规则合并到原有文法中,改写原有的文法。例

7、如，对于上例文法GE，将运算符的优先顺序和结合规则：*优先于;、*左结合加到原有文法中,可构造出无二义性文法如下：第18页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除则句子i*i+i只有唯一一棵语法树：EE+T|TTT*F|FF(E)|iEE+TTT*FFiiFi第19页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除 例2定义某程序语言条件语句的文法G为:试证明该文法是二义性的并消除之。分析该文法的句子ifbifbAelseA对应下面两棵不同的语法树：SifbS|ifbSelseS|A(其它语句）第20页，本讲稿共71页2.5.2.5.2

8、2 文法二义性的消除文法二义性的消除 所以该文法是二义的。SifbSbSSifAelseASbSSifAelseAifbSSifbS|ifbSelseS|A句子ifbifbAelseA第21页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除 消除文法的二义性可采用下面两种方法：1.不改变已有规则，仅加进一非形式的语法规定：else与前面最接近的不带else的if相对。SifbSbSSifAelseA文法G的句子ifbifbAelse只对应唯一的一棵语法树，消除了二义。第22页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除2.改写文法G为GSS1

9、|S2S1ifbS1elseS1|AS2ifbS|ifbS1elseS2G:SifbS|ifbSelseS|A(其它语句）G:第23页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除这是因为通过分析，得知引起二义性的原因是:ifelse 语句的 if 后可是if型，因此改写文法时规定:if else之间只能是ifelse语句或其他语句。第24页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除SS1|S2S1ifbS1elseS1|AS2ifbS|ifbS1elseS2ifbSbifAelseASS2S1S1S1对改写后的文法，句子ifbifbAe

10、lseA只对应唯一的一棵语法树。第25页，本讲稿共71页通常我们只说文法的二义性,而不说语言的二义性,这是因为可能有两个不同的文法G和G，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G),即这两个文法所产生的语言是相同的。2.5.2.5.2 2 文法二义性的消除文法二义性的消除 应该指出的是文法的二义性和语言的二义性是两个不同的概念。第26页，本讲稿共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除 将一个语言说成是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。例如L=aibjck|i=j或j=k且i,j,k1便是这种语言。第27页，

11、本讲稿共71页2.6 2.6 文法和语言的分类文法和语言的分类 著名的语言学家乔姆斯基(Chomsky)将文法和语言分为四大类，即0型、1型、2型、3型。划分的依据是对文法中的规则施加不同的限制。第28页，本讲稿共71页2.6 2.6 文法和语言的分类文法和语言的分类 0型文法（无限制文法）若文法G=(VN,VT,P,S)中的每条规则是这样一种结构：而且中至少含一个非终结符,则称G是0型文法。(VNVT)+,(VNVT)*0型文法描述的语言是0型语言。0型文法没有加任何限制条件，又称为无限制性文法，相应的语言称为无限制性语言。0型语言由图灵机识别。第29页，本讲稿共71页2.6 2.6 文法和

12、语言的分类文法和语言的分类 例如，有0型文法G=(VN,VT,P,S)其中：VN=A,B,S,VT=0,1其描述的0型语言为L0(GS)=P:S0AB1B0BSA|01A1SB1A0S0B第30页，本讲稿共71页2.6 2.6 文法和语言的分类文法和语言的分类 1型文法（上下文有关文法）1型文法也称为上下文有关文法，相应的语言又称为上下文有关语言。若文法G=(VN,VT,P,S)中的每一条规则的形式为A,其中：,(VNVT)*,AVN,则称G是1型文法。1型文法描述的语言是1型语言。1型语言由线性界限自动机识别。(VNVT)+第31页，本讲稿共71页2.6 2.6 文法和语言的分类文法和语言的

13、分类 例如，有1型文法G=(VN,VT,P,S)其中：VN=S,A,B,VT=a,b,cP:SaSAB|abBBABABAAAAAABbAbbbBbccBcc其描述的1型语言为L1(GS)=anbncn|n1第32页，本讲稿共71页2.6 2.6 文法和语言的分类文法和语言的分类 2型文法（上下文无关文法）2型文法又称上下文无关文法，其产生的 语言又称为上下文无关的语言。若文法G=(VN,VT,P,S)中的每一条规则的形式为A,其中：AVN,(VNVT)*则称G是2型文法。2型文法描述的语言是2型语言。2型语言由下推自动机识别。第33页，本讲稿共71页例如前面描述算术表达式的文法GE:EE+E

14、|E*E|(E)|i2.6 2.6 文法和语言的分类文法和语言的分类 第34页，本讲稿共71页其描述的语言为L2(GS)=x|xa,b+且x中a和b的个数相同例如，有2型文法G=(VN,VT,P,S)其中：VN=S,A,B,VT=a,bP=SaB|bAAa|aS|bAABb|bS|aBB2.6 2.6 文法和语言的分类文法和语言的分类 第35页，本讲稿共71页2.6 2.6 文法和语言的分类文法和语言的分类 3型文法（正规文法）右线性文法和左线性文法都称为3型文法。若文法G=(VN,VT,P,S)中的每一条规则的形式为AaB或Aa,其中：A,BVN,aVT*,则称G是右线性文法。若文法G=(V

15、N,VT,P,S)中的每一条规则的形式为ABa或Aa,其中：A,BVN,aVT*,则称G是左线性文法。3型文法描述的语言是3型语言。3型语言由有穷自动机识别。3型文法也称正规文法。正规文法产生的语言称为正规语言。第36页，本讲稿共71页例如，用左线性正规文法和右线性正规文法定义标识符2.6 2.6 文法和语言的分类文法和语言的分类 用I代表标识符;l代表任意一个字母;d代表任意一个数字;则定义标识符的文法为：左线性文法:P:Il|Il|Id右线性文法:P:Il|lTTl|d|lT|dT第37页，本讲稿共71页例如，用左线性正规文法和右线性正规文法定义无符号整数2.6 2.6 文法和语言的分类文

16、法和语言的分类 用N代表无符号整数;d代表任意一个数字；则定义的无符号整数文法为：左线性文法:P:NNd|d右线性文法:P:NdN|d第38页，本讲稿共71页2.6 文法分类总结 0 0型文法：型文法：左部：左部：V VN N和和V VT T组成组成(可以由多个可以由多个V VN N多个多个V VT T组成组成,但至少一个但至少一个V VN N)右部：右部：V VN N和和V VT T组成组成(可以由多个可以由多个V VN N多个多个V VT T组成组成)。1 1型文法：型文法：左部：左部：V VN N和和V VT T组成组成(可以由多个可以由多个V VN N多个多个V VT T组成组成,且至

17、少一个且至少一个V VN N)右部：右部：V VN N和和V VT T组成组成(可以由多个可以由多个V VN N多个多个V VT T组成组成)。|左部左部|=|=|右部右部|第39页，本讲稿共71页2.6 文法分类总结 2 2型文法：左部：只有一个型文法：左部：只有一个V VN N 。右部：右部：V VN N和和V VT T组成组成(可以由多个可以由多个V VN N多个多个V VT T组成组成)。3 3型文法：左部：只有一个型文法：左部：只有一个V VN N 。右部：最多一个右部：最多一个V VN N ，且在最左或最右。，且在最左或最右。第40页，本讲稿共71页2.6 2.6 文法和语言的分类

18、文法和语言的分类 由上述四类文法的定义可知,从0型文法到3型文法,是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法,而由它们所定义的语言类是依次缩小的，有 L0 L1 L2 L3。第41页，本讲稿共71页2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 文法是用来描述程序设计语言的，在 实际应用中需要对文法加一些限制条件。1.文法中不能含有形如AA的规则。这种规则我们称之为有害规则。对文法的实用限制有以下两点：第42页，本讲稿共71页2.7 2.7 有关文法的实用限制和变

19、换有关文法的实用限制和变换 2.文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：(1)某条规则A的左部符号A不在所属文法的任何其他规则右部出现，即在推导文法的所有句子中始终都不可能用到的规则。(2)对文法中的某个非终结符A，无法从它推出任何终结符号串来。第43页，本讲稿共71页2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 例如设有文法GS:P:SBdAAd|dBCd|AeCCeDe删除多余规则后的文法变换为:P:SBdAAd|dBAe第44页，本讲稿共71页2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 若程序设计语言的文法含有多余规则，其中

20、必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。第45页，本讲稿共71页作业P第46页，本讲稿共71页本章重点介绍了语言的语法结构的形式描述、语法树以及文法的二义性,主要内容有：1.设计一个文法定义一个已知的语言(1)文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。从文法定义可知,文法对于程序设计者来说，文法给出了语言的精确定义和描述。本章小结本章小结本小结花时45分钟第47页，本讲稿共71页(2)分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。(4)若语言是无穷集合,设计该语言的文法一定是递归的。本

21、章小结本章小结(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。第48页，本讲稿共71页分析根据语言句子的结构特征，设计出相应规则例1.给出语言L2=anbm|mn1的文法P2:SABL2=ab,abb,abbb,aabb,aabbb,aabbbb,aaabbb,aabbbb，AaAb|abBbB|本章小结本章小结第49页，本讲稿共71页分析根据语言句子的结构特征，设计出相应规则例2.给出语言L1=a2n+1|n0的文法P1:AaB|aP1：AaAa|a 或或L1=a,aaa,aaaaa,aaaaaaa,aaaaaaaaa，Baa|aBa本章小结本章小结第50页，本讲稿共7

22、1页本章小结本章小结分析根据语言句子的结构特征，设计出相应规则例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第51页，本讲稿共71页本章小结本章小结L4=0,2,4,6,8,10,12,14,16,18,20,22,24,26,例4.写一个文法,使其语言是正偶数的集合,每个偶数不以0开头。P4:NE|AEN0|2|4|6|8|BN或或分析不以0开头的偶数集合中串的结构特征:AD|ADE0|2|4|6|8D1|2|3

23、|9D0|1|2|3|9B1|2|3|9|B0P4:第52页，本讲稿共71页本章小结本章小结A0A1|P:S1S0|0A1|例5.给出语言L=1n0m1m0n|n,m0的文法。分析根据语言句子的结构特征,设计出相应规则L=,01,0011,10,1100,1010,100110,110100,11001100第53页，本讲稿共71页本章小结本章小结P:Sa|0S0|1S1例6.给出语言L=WaWt|W0|1*,Wt 表示W的逆的文法。分析根据语言句子的结构特征，设计出相应规则L=a,0a0,1a1,01a10,10a01,00a00,11a11,101a101,110a011,100a001,

24、W=,0,1,01,10,00,11,101,110,100,111,第54页，本讲稿共71页本章小结本章小结2.已知一个文法，确定该文法所定义的语言。(2)给定一个文法，可根据语言和推导定义推导出文法的句子，从而确定出该文法所定义的语言。(1)文法所定义的语言L(GS)=x|Sx且xVT*第55页，本讲稿共71页本章小结本章小结自然语言描述。例如,L=x|xa,b+且x中a,b个数相同式子描述。例如L=a2nbb|n0。正规式描述。(3)语言可用第56页，本讲稿共71页本章小结本章小结例1文法GA=(A,a,b,AbA|a,A)所生成的语言是什么？分析AbAbbAbbbAbnAbnaL(GA

25、)=bna|n0第57页，本讲稿共71页本章小结本章小结例2文法GN为:NND|DD0|1|2|3|4|5|6|7|8|9(1)GN所生成的语言是什么？(2)给出句子0127的最左、最右推导。第58页，本讲稿共71页本章小结本章小结L(GN)=|0,1,2,9+=|为可带前导0的正整数=|为数字串最左推导:NNDN7ND7N27ND27N127D1270127最右推导:NNDNDDNDDDDDDD0DDD01DD012D0127NND|DD0|1|2|3|4|5|6|7|8|9第59页，本讲稿共71页本章小结本章小结例3.已知文法GS=(A,B,a,b,c,d,P,S),其中P为:分析SABa

26、AbBa2Ab2Ban-1Abn-1BanbnBanbncBdanbnc2Bd2anbncm-1Bdm-1anbncmdmL(GS)=anbncmdm|n,m1该文法所生成的语言是什么？AaAb|abBcBd|cdSAB第60页，本讲稿共71页本章小结本章小结3.求句型的短语、直接短语和句柄(1)短语、直接短语和句柄是对某句型而言的。(2)短语总是句型的某个子串，它对应子树未端结点形成的符号串。(3)直接短语是某条规则右部，它对应简单子树未端结点形成的符号串。(4)最左边的直接短语是句柄。第61页，本讲稿共71页本章小结本章小结例1已知文法GE：证明 E+T*F是它的一个句型,指出这个句型的短

27、语直接短语和句柄。EE+TE+T*F短语:E+T*F、T*FE+T*F是它的一个句型。画出该句型的语法树:句柄:T*F直接短语:T*FETFT+E*EE+T|E-T|TTT*F|T/F|TT(E)|i第62页，本讲稿共71页本章小结本章小结例2已知文法GS：试找出符号串(a)和(A(SaA)(b)的短语直接短语和句柄(如果有的话)。S(AS)|(b)A(SaA)|(a)符号串(a)不是文法的句型，因此它没有短语直接短语和句柄。分析S(AS)(a)S)(a)/第63页，本讲稿共71页本章小结本章小结S(AS)(A(AS)(A(A(b)(A(SaA)(b)符号串(A(SaA)(b)是文法的句型，画

28、出该句型的语法树如下图：S(AS)|(b)A(SaA)|(a)第64页，本讲稿共71页本章小结从句型的语法树求 短语:(A(SaA)(b)(SaA)(b)(SaA)(b)直接短语：(SaA)、(b)句柄：(SaA)SA(S)A(S)(S aA)b(S(AS)|(b)A(SaA)|(a)对于句型(A(SaA)(b)第65页，本讲稿共71页本章小结本章小结4文法二义性的判断一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左（最右）推导，则该文法是二义性的。第66页，本讲稿共71页本章小结本章小结例1设有文法GS:SiSeS|iS|i试证明文法GS有二义性。分析因为对文法的句子iiiei有

29、如下两棵不同的语法树与之对应，所以该文法是二义的第67页，本讲稿共71页本章小结本章小结SiSeS|iS|i句子 iiiei对应下面两颗语法树：SSie SiSiiSiSiSie Si第68页，本讲稿共71页本章小结本章小结NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|91.试证明文法GN有二义性。2.此文法所描述的语言是什么？3.试写出另一文法G使L(G)=L(G)且G是无二义性的。例2设有文法GN:第69页，本讲稿共71页本章小结本章小结分析因为对文法的句子10有两棵不同的语法树与之对应，所以该文法是二义的NES0D1NE01NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9第70页，本讲稿共71页本章小结本章小结该文法所描述的语言是所有无符号偶数的集合(可以0开头)。改写后的文法GS为:NSE|ESSD|DE0|2|4|6|8D0|1|2|3|4|5|6|7|8|9NSE|ESSD|DE0|2|4|6|8|10D0|1|2|3|4|5|6|7|8|9第71页，本讲稿共71页