第02章_文法和语言的基本知识(2)优秀PPT.ppt-淘文阁

资源描述

《第02章_文法和语言的基本知识(2)优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第02章_文法和语言的基本知识(2)优秀PPT.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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*FF

3、iiFi现在学习的是第7页，共71页2.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是句柄注意:

4、i+i不是句型的短语句子i*i+iEE+TTT*FFiiFi现在学习的是第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由语法树可知

5、现在学习的是第12页，共71页2.5.2.5.1 1 文法的二义性文法的二义性从前面的讨论可以看出，对于文法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最左

6、推导2EE*Ei*Ei*E+Ei*i+Ei*i+iEE*EE+EiiiEE+EE*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 文法二义性的消除文法二

7、义性的消除2.构造一个等价的无二义性文法。即把排除二义性的规则合并到原有文法中,改写原有的文法。例如，对于上例文法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对应

8、下面两棵不同的语法树：SifbS|ifbSelseS|A(其它语句）现在学习的是第20页，共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除所以该文法是二义的。SifbSbSSifAelseASbSSifAelseAifbSSifbS|ifbSelseS|A句子ifbifbAelseA现在学习的是第21页，共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除消除文法的二义性可采用下面两种方法：1.不改变已有规则，仅加进一非形式的语法规定：else与前面最接近的不带else的if相对。SifbSbSSifAelseA文法G的句子ifbifbAelse只对应唯一的一棵

9、语法树，消除了二义。现在学习的是第22页，共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除2.改写文法G为GSS1|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|S2S1

10、ifbS1elseS1|AS2ifbS|ifbS1elseS2ifbSbifAelseASS2S1S1S1对改写后的文法，句子ifbifbAelseA只对应唯一的一棵语法树。现在学习的是第25页，共71页通常我们只说文法的二义性,而不说语言的二义性,这是因为可能有两个不同的文法G和G，而且其中一个是二义性的，另一个是无二义性的,但却有L(G)=L(G),即这两个文法所产生的语言是相同的。2.5.2.5.2 2 文法二义性的消除文法二义性的消除应该指出的是文法的二义性和语言的二义性是两个不同的概念。现在学习的是第26页，共71页2.5.2.5.2 2 文法二义性的消除文法二义性的消除将一个语

11、言说成是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。例如L=aibjck|i=j或j=k且i,j,k1便是这种语言。现在学习的是第27页，共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型文法

12、描述的语言是0型语言。0型文法没有加任何限制条件，又称为无限制性文法，相应的语言称为无限制性语言。0型语言由图灵机识别。现在学习的是第29页，共71页2.6 2.6 文法和语言的分类文法和语言的分类例如，有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,其中：,(VN

13、VT)*,AVN,则称G是1型文法。1型文法描述的语言是1型语言。1型语言由线性界限自动机识别。(VNVT)+现在学习的是第31页，共71页2.6 2.6 文法和语言的分类文法和语言的分类例如，有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)中的

15、类文法和语言的分类 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型文法也称正规文法。正规文法产生的语言称为正规语言。现在学习的是第36页，共71页例如，用左线性正规文法和右线性正规文法定义标识符2.6 2.6 文法和语言的分类文法和语言的分类用I代表标识符;l代表任意一个字母;d代表任意一个数

17、和V VT T组成组成(可以由多个可以由多个V VN N多个多个V VT T组成组成)。1 1型文法：型文法：左部：左部：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组成组成)。|左部左部|=|=|右部右部|现在学习的是第39页，共71页2.6 文法分类总结 2 2型文法：左部：只有一个型文法：左部：只有一个V VN N 。右部：右部：V VN N和和V VT T组成组成(可以由多个可以由多个V VN N

18、多个多个V VT T组成组成)。3 3型文法：左部：只有一个型文法：左部：只有一个V VN N 。右部：最多一个右部：最多一个V VN N ，且在最左或最右。，且在最左或最右。现在学习的是第40页，共71页2.6 2.6 文法和语言的分类文法和语言的分类由上述四类文法的定义可知,从0型文法到3型文法,是逐渐增加对规则的限制条件而得到的，因此每一种正规文法都是上下文无关的文法，每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是0型文法,而由它们所定义的语言类是依次缩小的，有L0L1L2L3。现在学习的是第41页，共71页2.7 2.7 有关文法的实用限制和变换有关文法的实

19、用限制和变换文法是用来描述程序设计语言的，在实际应用中需要对文法加一些限制条件。1.文法中不能含有形如AA的规则。这种规则我们称之为有害规则。对文法的实用限制有以下两点：现在学习的是第42页，共71页2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换 2.文法中不能有多余规则。所谓多余规则是指文法中出现以下两种规则：(1)某条规则A的左部符号A不在所属文法的任何其他规则右部出现，即在推导文法的所有句子中始终都不可能用到的规则。(2)对文法中的某个非终结符A，无法从它推出任何终结符号串来。现在学习的是第43页，共71页2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和

20、变换例如设有文法GS:P:SBdAAd|dBCd|AeCCeDe删除多余规则后的文法变换为:P:SBdAAd|dBAe现在学习的是第44页，共71页2.7 2.7 有关文法的实用限制和变换有关文法的实用限制和变换若程序设计语言的文法含有多余规则，其中必定有错误存在，因此检查文法中是否含有多余规则对我们来说是很重要的。现在学习的是第45页，共71页作业P现在学习的是第46页，共71页本章重点介绍了语言的语法结构的形式描述、语法树以及文法的二义性,主要内容有：1.设计一个文法定义一个已知的语言(1)文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一

21、个语言的结构。从文法定义可知,文法对于程序设计者来说，文法给出了语言的精确定义和描述。本章小结本章小结本小结花时45分钟现在学习的是第47页，共71页(2)分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。(4)若语言是无穷集合,设计该语言的文法一定是递归的。本章小结本章小结(3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。现在学习的是第48页，共71页分析根据语言句子的结构特征，设计出相应规则例1.给出语言L2=anbm|mn1的文法P2:SABL2=ab,abb,abbb,aabb,aabbb,aabbbb,aaabbb,aabbbb，AaAb|abBbB|本

23、，共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|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,11

24、001100现在学习的是第53页，共71页本章小结本章小结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,现在学习的是第54页，共71页本章小结本章小结2.已知一个文法，确定该文法所定义的语言。(2)给定一个文法，可根据语言和推导定义推导出文法的句子，从而确定出该文法所定义的语言。(1)文法所定义的语言L(GS)=x|Sx且x

25、VT*现在学习的是第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)=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+

26、=|为可带前导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为:分析SABaAbBa2Ab2Ban-1Abn-1BanbnBanbncBdanbnc2Bd2anbncm-1Bdm-1anbncmdmL(GS)=anbncmdm|n,m1该文法所生成的语言是什么？AaAb|abBcBd|cdSAB现在学习的是第60页，共71页本章小

27、结本章小结3.求句型的短语、直接短语和句柄(1)短语、直接短语和句柄是对某句型而言的。(2)短语总是句型的某个子串，它对应子树未端结点形成的符号串。(3)直接短语是某条规则右部，它对应简单子树未端结点形成的符号串。(4)最左边的直接短语是句柄。现在学习的是第61页，共71页本章小结本章小结例1已知文法GE：证明 E+T*F是它的一个句型,指出这个句型的短语直接短语和句柄。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页本章小结本章小

28、结例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)是文法的句型，画出该句型的语法树如下图：S(AS)|(b)A(SaA)|(a)现在学习的是第64页，共71页本章小结从句型的语法树求短语:(A(SaA)(b)(SaA)(b)(SaA)(b)直接短语：(SaA)、(b)句柄：(SaA)SA(S)A

29、(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有如下两棵不同的语法树与之对应，所以该文法是二义的现在学习的是第67页，共71页本章小结本章小结SiSeS|iS|i句子iiiei对应下面两颗语法树：SSie SiSiiSiSiSie Si现在学习的是第68页，共7

30、1页本章小结本章小结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页

展开阅读全文