第2章 形式语言概述精选PPT.ppt

《第2章 形式语言概述精选PPT.ppt》由会员分享，可在线阅读，更多相关《第2章 形式语言概述精选PPT.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 形式语言概述形式语言概述第1页，此课件共81页哦本章学习目标本章学习目标u形式语言由Chomsky于1956年提出，主要讨论语言和文法的数学机制数学机制以及语言和文法的分类分类。形式语言的形成和发展，对编译原理和技术产生了重要的影响。本章主要内容是:文法和语言的形式定义文法的分类句型的分析和语法树第2页，此课件共81页哦 字母表字母表u字母表是元素的非空有穷有穷集合，字母表中的元素称为符号符号，因此字母表也称为符号表符号表。高级语言如C语言的字母表是由字母、数字、特殊符号和一些专用符号构成。字母表可以用表示例：=a,b，=0,1，=0,1，2，3，4，5，6，7，8，9，=a,b,

2、c,z,if,then,else,main,1,2,3,4,9,0,=,=,0)符号串集合的运算符号串集合的运算第9页，此课件共81页哦u字母表的闭包与正闭包的运算闭包设有字母表A，A的闭包定义如下：A*=A0A1 A2 An,其中，An（n=0，1，2，3，）中所有的符号串的长度为n，因此字母表A的闭包 A*为字母表上一切长度为n的符号串所组成的集合。注：注：闭包可以看作由A上符号组成的所有串的集合（包括空串）正闭包如果不允许包含空串，则得到字母表A的正闭包。A的正闭包 A+=A1 A2 An 注：注：正闭包可以看作由A上符号组成的所有串的集合（不包括空串）语言字母表上按照某种规则形成的某个

3、符号串的集合，所以，语言是该字母表上正闭包的子集正闭包的子集第10页，此课件共81页哦例：例：设字母表=a,b,c,依次写出长度为1、2、3的符号串，可得到的正闭包+：+=a,b,c,aa,ab,ac,bb,bc,aaa,aab,aac,abb,abc,baa,在+上添入空串即得*。第11页，此课件共81页哦2.2 文法的定义及其分类文法的定义及其分类u什么是文法文法?描述语言的语法结构的形式规则形式规则，严格地定义句子的结构，用适当条数的规则把语言的全部句子描述出来，是以有穷有穷的集合刻划无穷无穷的集合的工具。:=:=|:=我|你|他:=:=是|学习:=|我是大学生的推导过程：=我 =我 =

4、我是 =我是 =我是大学生第12页，此课件共81页哦2.2.2 文法的形式定义文法的形式定义(1)u非终结符出现在规则的左部，用括起来，表示一定语法概念的词，用VN表示u终结符语言中不可再分割的字符串（包括单个字符组成的串）用VT表示V=VN U VTu开始符号表示所定义的语法范畴的非终结符又称为识别符号开始符号用S表示第13页，此课件共81页哦2.2.2 文法的形式定义文法的形式定义(2)u重写规则也叫产生式规则产生式规则，或称为生成式生成式，是形如或:=的(,)有序对,其中,是某个字母表V+中的一个元素，是V*中的一个元素。称为规则的左部左部，称为规则的右部。例例：AB读作“A定义为B”，

5、也就是说它是一条关于A的规则（产生式）。u文法文法G是一个四元组，G=（VN，VT，P，S），），其中，VN、VT分别是非空有限的非终结符号集和终结符号集，VNVT=，P是产生式的集合，SVN为文法的识别符号或开始符号。第14页，此课件共81页哦u例：例：在程序设计语言中，假设我们定义标识符的命名规则为字母a、b、c开头的，字母a、b、c和数字1、2、3的序列。命名规则为：abc123第15页，此课件共81页哦u我们一般用大写字母代表左边的非终结符，设N代表，D代表，L代表，则定义标识符的文法是：G=(VN，VT，P，S)其中，VN=N，L，D,VT=a,b,c,1,2,3P为产生式的规则：N

6、L，NNL，NND，La，Lb，Lc，D1，D2，D3S是开始符号,为N注注：产生式的规则说明一点，即若A，A，A可写成A|。“|”读做“或者”。上面的产生式规则可以改写为：NL|NL|NDLa|b|cD1|2|3第16页，此课件共81页哦2.2.3 文法的分类文法的分类u乔姆斯基（Chomsky）于1956年建立形式语言的描述以来，把文法分成四种类型，即0型、1型、2型和3型文法。u0型文法(短语文法)设G=（VN，VT，P，S），如果它的每个产生式是这样一种结构：(VNVT)+，且至少含有一个非终结符，而（VNVT）*，则称G是一个0型文法型文法。0型文法又称短语文法短语文法，它的能力相当

7、于一个图灵机。例如，Au图灵机图灵机是识别0型文法的识别装置u0型文法是对产生式限制最少的文法；对0型文法产生式的形式作某些限制，可得到其他类型文法的定义。第17页，此课件共81页哦u1型文法（上下文有关文法）设G=（VN，VT，P，S）为一文法，若P中的每一个产生式均满足，仅仅S除外，则文法G是1型文法或上下文有关文法型文法或上下文有关文法。所谓上下文有关文法即：=1A2，=1B2，符号串1和2可以认为是上下文，A只有出现在上下文之间中，才可以被符号串B替代，成为=1A2=1B2因此，1型文法又称为上下文有关文法。能够识别上下文无关语言的自动机称为线性界限自动机线性界限自动机。缩写为LBA注

8、注：1型文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成，除非是开始符号产生第18页，此课件共81页哦u2型文法（上下文无关文法）设G=(VN，VT，P，S)，若P中的每个产生式满足:是一个非终结符非终结符,(VNVT)*，则此文法称为2 型文法或上下文无关文法型文法或上下文无关文法。有时将2型文法的产生式表示为形如：A，其中AVN。也就是当用取代非终结符A时，与A所在的上下文无关。上下文无关文法有足够的能力描述现今的程序设计语言。识别上下文无关语言的自动机称为下推自动机下推自动机。它是。缩写为PDA。u例例:2型文法G=（VN，VT，P，N）其中，VN=N，DVT=0，

9、1，2，3，4，5，6，7，8，9P=NNDD，D0123456789注：注：该文法描述的符号串的集合是整数。第19页，此课件共81页哦u3型文法（右线性文法或正规文法）对2型文法的产生式做进一步的限制，限制产生式右部是单一终结符或单一终结符跟着单一非终结符，即：Aa,AaB则称该文法为3型文法型文法，又称为右线性文法或正规文法右线性文法或正规文法，其中A、BVN，aVT.识别3型语言或正则语言的自动机称为有穷自动机有穷自动机。缩写为FA。u例例:3型文法G=（VN，VT，P，S）其中，VN=S，A，BVT=0，1P=S011A0B，A1A0B，B010B注：注：该文法产生的是二进制整数。第2

10、0页，此课件共81页哦2.2.4 文法举例文法举例u例：例：1型文法G=（VN，VT，P，A）VN=S,X,Y,ZVT=x,y,zP=S xSYZ xYZxYxyyYyyyZ yzZY YZzZ zzu例例：2型文法G=（VN，VT，P，E）VN=E，T，F，VT=+，*，（，），iP=EE+T|T,TT*F|T,F(E)|i注注：该文法能推出具有乘和加运算的算术表达式。第21页，此课件共81页哦u例：例：正规文法G=（VN，VT，P，S）其中VN=S，A，B，G，H，VT=d，+，P=SdB|+A|A|.GAdB|.GBdB|.H|dGdHHdH|d其中，d代表十进制数字。u根据以上我们对文

11、法的定义我们不难发现3型文法类是2型文法类的特殊情况，2型文法类是1型文法类的特殊情况。每一类文法都是在前一类文法的基础上加上一些限定规则而产生的。因此，四类文法产生的语言就会有如下关系：3型语言2型语言1型语言0型语言第22页，此课件共81页哦2.2.6 文法分类的意义文法分类的意义u一个文法实际上是某种语言的一个简明、确切的描述，它表示了该语言中所允许的一类语法结构。从一个文法能推导出多个终结符的句子。但是知道了如何去构造属于某一个语言的一个合法串只是问题的一个方面。同时我们还要有能力判定一个串是否合法。也就是说，我们需要确定这个给定串的推导序列。如果从文法出发找不到这个推导序列，则该串就

12、是非法的。u程序设计语言的词法分析属于正规文法，与局部语法相关的部分属于上下文无关文法，与全局语法和语义有关的部分属于上下文有关文法。第23页，此课件共81页哦2.3 文法产生的语言和句型的语法树文法产生的语言和句型的语法树u推导推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。最左（右）推导：每次使用一个规则，以其右部取代符号串的最左（右）非终结符。注注：最左推导和最右推导称为规范推导规范推导：u归约归约是推导的逆过程，即，从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程。最左(右)归约是最右(左)推导的逆过程。注注：最左归约和最右归

13、约称为规范归约规范归约。第24页，此课件共81页哦文法产生的语言和句型的语法树（续）文法产生的语言和句型的语法树（续）u推导和规范推导推导分为三大类：直接推导直接推导、，长度为n(n1)的推导+和长度为n（n0）的推导*。u直接推导如是文法G=(VN,VT,P,S)的规则（或说是P中的一产生式），,(VNVT)*，则称符号串为符号串应用产生式所得到的直接推导直接推导。记为。第25页，此课件共81页哦u推导长度大于0的推导如果对于符号串v与w存在一个直接推导序列u0u1u2u3un(n0)其中u0=v与un=w,则称符号串v推导出推导出w或称w归约归约到v，记作v+w，称这个直接推导序列是长度为

14、n的推导。u推导长度大于等于0的推导如果对于符号串v和w，v=w或v=w，则记作v*w，称符号串v广广义推导义推导到符号串w，或称w广义归约广义归约到v。第26页，此课件共81页哦u例：例：根据文法，考虑以C语言中的无正负号整数作为识别符号的文法。|0|1|2|3|4|5|6|7|8|9VT=0,1,2,3,4,5,6,7,8,9VN=,判断数据2634是否是C语言合法的数据?给出数据2634的推导。4434346342634由此可见，2634是C语言的合法数据。每一步推导都是直接推导。可以表示为=2634第27页，此课件共81页哦u最左推导 如果在推导的任何一步，其中、是句型，都是对中的最左

15、非终结最左非终结符符进行替换，则称这种推导为最左推导最左推导。u最右推导 如果在推导的任何一步，其中、是句型，都是对中的最右非终结最右非终结符符进行替换，则称这种推导为最右推导最右推导。u规范推导在形式语言中，最右推导常称为规范推导规范推导，由规范推导所得的句型称为规范句型规范句型。第28页，此课件共81页哦u例：例：给出了下列文法G:|0|1|2|3|4|5|6|7|8|9VT=0,1,2,3,4,5,6,7,8,9VN=,判断数据2634是否是C语言合法的数据?（1）用最右推导，每次用产生式的规则替换最右边的非终结符，推导过程如下：4434346342634第29页，此课件共81页哦（2）

16、用最左推导，每次直接推导都替换最左边的非终结符，推导过程如下：2262632634第30页，此课件共81页哦2.3.2 句型、句子和语言句型、句子和语言u句型句型设GS是一个文法，如果符号串x是从开始符号S推导得到的，即有S=*x，xV+，则称符号串x是该文法G的一个句型句型。u句子句子GS是一个文法，如果符号串x是从开始符号S推导得到的，即有S=+x，并且xVT，则称该符号串为该文法的一个句子句子。注注：实质上，句子是句型的特殊情况，句子是由终结符终结符组成，而句型是有终结符有终结符和非终结符非终结符组成。u语言语言:GS是一个文法，文法G产生的语言L(G)=x|S=*x，并且xVT，即文法

17、的语言是文法所有句子的集合。第31页，此课件共81页哦句型、句子和语言（续）句型、句子和语言（续）u文法规则的递归定义非终结符的定义中包含了非终结符自身。注：使用文法的递归定义要谨慎，要有递归出口，否则，可能永远产生不出句子。u例：字母表A=0,1文法：|0|1u再如：字母表A=0,10|1第32页，此课件共81页哦2.3.3 语法树语法树u在自然语言中，句子结构可以借助一种树形表示进行分析。如下面的句子：TheyarestudentsandteachersofthePhysicsDepartment。u对该句子的结构进行分析，其树型结构如图2-3所示，由此可以看出，该句子是由主语、系词和表语

18、组成，是一个语法正确的句子。第33页，此课件共81页哦句子主语系词表语代词Theyare名词student连接词and名词teacher定语前置词冠词名词ofthePhysics名词Department图2-3句子结构第34页，此课件共81页哦u在自然语言中，可以通过树型表示直观地分析句子的结构；在形式语言中，我们提到了句型句型、推导推导的概念，在证明某个符号串是否是某个文法的句型句型时，采用从文法开始符号推导的方法，这个推导过程可以用语法树直观的表示出来。语法树语法树也称为推导树推导树，其定义如下：第35页，此课件共81页哦u给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关

19、联的语法树，这棵树满足下列四个条件：（1）每个结点都有一个标记，此标记是V的一个符号。（2）根的标记是S。（3）若一结点n至少有一个它自己除外的子孙，并且有 标记A，则A肯定在VN中。（4）如果结点n的直接子孙，从左到右的次序是结点n1,n2,n3.nk，其标记分别为A1，A2，A3，AK。那么AA1A2A3AK一定是P中的一个产生式。第36页，此课件共81页哦u例例:设文法GS：EE+T|TTT*F|FF(E)|i证明符号串E+(E+T)*i是文法的句型?第37页，此课件共81页哦EE+Ti*FF()TE+ET第38页，此课件共81页哦2.3.4 二义性文法及其他二义性文法及其他u二义性文法

20、一个文法，如果它的一个句子或句型有两棵两棵或两棵两棵以上的语法树，则称此句子具有二义性二义性。如果一个文法含有二义性的句子，则称该文法具有二义性。例例:设文法GS：SifBthenS|ifBthenSelseS|i：=E给出符号串ifBthenifBthenSelseS的语法树。语法树的结构如图如图2-5所示。从上面的语法图我们可以看出，字符串ifBthenifBthenSelseS能够画出两棵语法树，所以该文法是一个二义性文法。第39页，此课件共81页哦u在语言中，为了避免二义性的文法，往往对文法加以一定的限制，限制条件语句then之后不允许再是条件语句从语义解释方面限制条件语句中的else

21、只能与其前面的、还没有和其他else配对的then配对。第40页，此课件共81页哦SifB thenSifB thenelseSSSifBthenelseSSifBthenSSif B then S|if B then S else S|i：=E符号串if B then if B then S else S第41页，此课件共81页哦2二义性文法的证明二义性文法的证明u要判定一个文法是否是二义性文法，或它是否产生一个先天二义性的上下文无关语言，是个递归不可解的。即不存在一不存在一个算法个算法，它能在有限的步骤内，确切的判断出某个给定的文法是否是一个二义性文法。u我们要证明一个文法是否是一个二义性

22、文法，就是找到该文法的一个句型特例句型特例，能够画出这个句型的两棵语法树，该文法就是二义性文法。第42页，此课件共81页哦u例例2.25 文法G=（E，+，*，I,(,)，P，E）其中P为：EiEE+EEE*EE(E)证明该文法是二义性文法，并将该文法改为等价的非二义性文法（等价的文法是指产生的语言相等的文法）?第43页，此课件共81页哦u【证明】取句型i*i+i，写出该句型的两个不同的推导。画出推导的两棵不同的语法树。推导1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i推导的两棵语法树如图2-6所示。将文法改为非二义性文法为：ET|E+

23、TTF|T*FF（E）|i第44页，此课件共81页哦EEE+E*EiiiEEEE*E*Eiii第45页，此课件共81页哦2.3.5 文法产生的语言文法产生的语言u例例2.26 设G=（VN，VT，P，S），VN=S,B,E，VT=a,b,c，P由下列产生式组成：SaSBESaBEEBBEaBabbBbbbEbeeEee（1）问该文法是Chomsky哪一类型的文法？（2）它生成的语言是什么？第46页，此课件共81页哦u（1）答根据文法分类定义，由于文法中存在产生式，其左部由长度大于1的符号串构成，如产生式“EBBE”，显然不符合Chomsky的2型和3型文法的定义。该文法产生式左部串的长度均小于

24、等于右部串的长度，符合1型文法的定义，所以该文法是上下文有关文法。第47页，此课件共81页哦u（2）根据如下推导：对于每一个n1，我们将号产生式使用n-1次，得到推导序列：San-1S(BE)n-1，然后使用产生式(2)一次，得到：San(BE)n，然后从an(BE)n.继续推导，总是对EB使用产生式的右部进行替换，而最终在得到的串中，所有的B都限于所有的E。设n=3，aaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：SanBnEn.接着，使用产生式(4)一次,得到SanbBn-1En，然后使用产生式n-1次得到：SanbnEn，然后使用产生式一次，使用产生式n-1

25、次，得到：Sanbnenu因此该文法产生的语言是L(G)=anbnen|n1。第48页，此课件共81页哦u例例：设有上下文无关文法如下：GS：SABAUTUa|aUTb|bTBc|cCu将文法的产生式代入产生如下文法：GS：SUTBUa|aUTb|bTBc|cC第49页，此课件共81页哦u考察文法，用L(S)，L(U)，L(T)和L(B)分别表示从终结符S，U，T和B出发推导出的符号串的集合，不难发现：L（U）=ai|i1=a+L（T）=bj|j1=a+L（B）=ck|k1=a+由于有SUTB，则有：L（S）=L(U)L(T)L(B)=(aibjck|i1,j1,k1)=a+b+c+第50页，

26、此课件共81页哦语言产生文法语言产生文法(1)例例：设L1=a2nbn|n=1且a,bVT试构造生成L1的文法G1设n=1，L1=aabn=2，L1=aaaabbn=3，L1=aaaaaabbb所以得：SaaSbSaab第51页，此课件共81页哦u例：例：构造一个上下文无关文法G，使其描述的语言L(G)是能够被5整除的无符号整数集合。能够被5整除的整数其结构特点是，末位数一定是0或5。所以，只要保证生成的整数末位数字是0或5即可。据此，构造描述能被5整除的无符号整数集合的文法如下：GS：SN0|N5NDN|D0|1|2|3|4|5|6|7|8|9语言产生文法语言产生文法(3)第52页，此课件共

27、81页哦u例例:写出一个上下文无关文法G，使得L(G)=anbmcmdn|n0，m1分析该语言的特点，可以看出，a和d的个数是一样的，b和c的个数是一样的。m的取值范围从1开始，所以至少有一个bc，n的最小值为0。写出文法为：SaSd|AAbAc|bc第53页，此课件共81页哦2.4 句型分析与句柄句型分析与句柄u对于上下文无关文法，语法树是句型推导过程的几何表示；是进行句型分析极好的工具。所谓句型分析句型分析就是识别一个符号串是否是某一个文法的句型。进一步说就是给定一个符号串时，按照某文法的规则为该符号串构造推导或语法树，以此来识别它是文法的一个句型。对于上下文无关文法，其句型分析方法有两大

28、类，一类是自上而下的分析方法（又称自顶向下自顶向下），另一类是自下而上（自底向上自底向上）的分析方法。第54页，此课件共81页哦2.4.1 自上向下的分析方法自上向下的分析方法u基本思想自上而下的分析方法就是从识别符号出发，看是否能推导出待检查的符号串，如果能推导出这个符号串，则表明此符号串是该文法的句型或句子，否则就不是。或者说，以文法的识别符号作为根结点，看是否能构造出一个语法树，而且此语法树所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则就不是。第55页，此课件共81页哦u例例 设文法GS：SaAbc|aB

29、AbaBbeB|d输入串：abed，识别该串是否是该文法的一个句子?u方法：从文法的识别符号S开始出发，选择它的一个产生式SaAbc得到直接推导uSaAbc以识别符S作为根结点，构造语法树，如下图2-7所示第56页，此课件共81页哦SaAbcba图2-7自上而下的推导过程SaAbcSaBSaBBebSaBebBd（a）（b）（c）（d）（e）SaAbc|aBAbaBbeB|dabed?第57页，此课件共81页哦2分析过程分析过程u符号串aAbc与待检查的符号串abed的第一个符号相匹配。由于符号串aAbc的第2个符号是非终结符，因此需要对它进行替换。A只有一个产生式Aba。以其右部替换A，得推

30、导SaAbcababc得到语法树，如图2-7（b）所示。u符号串ababc与待查符号串abed的第2个符号相匹配，但与第3个符号不相匹配，匹配失败。此时，需要退回到非终结符A，重新选择S另外的产生式，再做试探。这种选择的过程称之为回溯回溯。第58页，此课件共81页哦u选择S的另外一条产生式的规则SaB，得到直接推导SaB，得到语法树2-7（c），再选取其中的一条产生式BbeB，得到推导SaBabeB，得到语法树如图（d），将Bd代入即可得到该字符串abed。第59页，此课件共81页哦3存在问题存在问题u自上而下分析方法是从文法的识别符号开始，选择相应的产生式规则进行推导。但在推导过程中会出现回

31、溯回溯现象。我们把出现回溯的分析称为不确定不确定的自顶上下分析方法。这种方法花费时间多，效率低，编程实现时复杂，如果对文法加以限制，就可以避免回溯，这就出现了我们后面要提到的LL(1)分析方法第60页，此课件共81页哦2.4.2 确定的自上而下的分析方法确定的自上而下的分析方法u例例:设文法GSSaBc|bCdBeB|fCdC|c试检查符号串aefc是不是该文法的句子?第61页，此课件共81页哦u识别符S有两条产生式，它们的右部首符号分别是终结符a和b。待检查符号串aefc的首符号是a，所以从识别符S出发，只能选择其产生式SaBc得到直接推导SaBc得到语法树如图2-8（a）所示。其中，非终结

32、符B有两条产生式，它们右部首符号分别是终结符e与f，而待检查的符号串aefc的第2个符号是终结符e，所以选择B的产生式BeBu得到推导SaBcaeBc，得到语法树如图2-8（b）所示。第62页，此课件共81页哦u由于待检查的符号串aefc的第3个符号是终结符f，因而对句型aeBc中的非终结符B选择其产生式Bf的推导SaBcaeBcaefc得到语法树如图2-8（c）所示。u如此推导出的符号串aefc，语法树的叶子结点序列是aefc，与待检查的符号串aefc相匹配。第63页，此课件共81页哦SaBcSaBceBSaBceBf图2-8语法树SaBc|bCdBeB|fCdC|caefc?第64页，此课

33、件共81页哦u例例:若有文法GSSAp|BqAaAcABbBdB当输入串W=ccap，那么试图推出输入串的推导过程为：SApcApccApccap很容易构造相应语法树，如图2-9所示。第65页，此课件共81页哦SApSApcASApcAcASApcAcAa图2-9语法树（a）（b）（c）（d）第66页，此课件共81页哦2.4.3 自下而上的分析方法自下而上的分析方法u基本思想自下而上的分析方法的基本思想是从待检查的符号串出发，看最终是否能归约到文法的识别符号。如果能归约到文法的开始的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。第67页，此课件共81页哦u例例2.33

34、若有文法GSScAdAabAa识别输入串w=cabd是否是该文法的句子。u首先从输入串开始，扫描cabd，从中寻找一个子串，该子串与某一产生式的右端相匹配。子串a和子串ab都是合格的，假若我们选用了ab，用产生式的左端A去替代它，即把ab归约到A，得到串cAd。u构造一个直接推导cAdcabd，即从cabd叶子开始向上构造语法树，接下去在得到的串cAd中又找到了子串cAd与产生式的右端相匹配，则用S替代cAd，或称将cAd归约到S，得到了又一直接推导ScAd，形成了最终的语法树。分析过程如图2-10所示。第68页，此课件共81页哦图2-10自下而上构造语法树cabdcabdAcabdAS第69

35、页，此课件共81页哦2存在问题存在问题u在自上向下的分析中，假定要被代换的最左非终结符的符号是V，且有n条规则：V1|2|3|n，那么如何确定用哪个右部去替换哪个右部去替换V？有一种解决方法是从各种可能的选择中挑选一种，并希望它是正确的。如果发现它是错误的，我们必须退回，再试着进行另外的选择，这种方式称为回溯回溯。第70页，此课件共81页哦u在自下向上的分析方法中，在分析程序工作的每一步中，都从当前串中选择一个子串，将它归约到某个非终结符号，我们暂且把这个子串称为“可归约串”。出现的问题是如何确定这个如何确定这个“可归约串可归约串”？比如在上例中，我们在对输入串cabd的分析中，如果不是选择a

36、b，用产生式，而是选择a，用产生式将a归约到A，那么最终就达不到S的结果，也就不知道cabd是一个句子。因此在归约时，ab是“可归约串”而不是a。如何求“可归约串”成为自下而上进行分析的关键。下面我们用“句柄句柄”的概念来描述“可归约串可归约串”。第71页，此课件共81页哦3句柄的概念句柄的概念 u（1）形式化定义令G是一文法，S是文法的开始符号，是文法的一个句型。如果有：S=*A且A=+则称是句型相对于非终结符A的短语短语。特别地，如有A则称是句型相对于规则A的直接短语。一个句型的最左句型的最左直接短语称为该句型的句柄直接短语称为该句型的句柄。u（2）求一个句型的句柄给定某个句型，要求出该句

37、型的句柄，比较直观的方法就是画出该句型的语法树。该语法树的一棵子树子树的叶子结点（从左到右）组成的符号串便是这个句型关于子树根结点的一个短语短语。第72页，此课件共81页哦u语法树的一棵简单子树（只有单层子树）的叶子结点简单子树（只有单层子树）的叶子结点组成的符号串是这个句型关于简单子树根结点的一个直接短语。语法树的最左的简单子树叶子结点组成的符号串就是这个句型的句柄。第73页，此课件共81页哦例例:已知文法GS：S(R)|a|RTTS,T|S求句型=(a,(T),(S,T)的短语，直接短语和句柄？u【解答】观察该语法树，共有10个非叶子结点，10棵子树。因此有短语aT(T)S,T(S,T)(

38、T),(S,T)a,(T),(S,T)(a,(T),(S,T)第74页，此课件共81页哦S(R)S，TaT，ST(R)TS(R)S，T图2-11语法树第75页，此课件共81页哦2.4.4 文法的存储文法的存储u一个文法的语法图由该文法所有非终结符的定义图组成。每个非终结符号的定义图是一个结构型数据。写成高级语言的结构型数据形式，则为：typestruc=boxesboxes=recordname:array110ofchar;def:struc;nextp:struc;、rights:struc;end;第76页，此课件共81页哦u“名字名字”是用某种内部形式表示的终结符号或非终结符号的名字。

39、u“定义定义”是一个指针，对于非终结符号，它指向其第一个侯选式侯选式结构图的开始位置。对于终结符号，它为0u“下一个侯选式下一个侯选式”是一个指针，指向相同左部的下一个侯选式的开始位置。若无侯选式，则它为0；u“右部后继右部后继”是一个指针，指向同一个右部的下一个符号。u另用一个一维数组记录所有的非终结符号定义图的开始地址。u也就是说，这个数组的每个元素都是一个指针，分别指向相应的非终结符号的第一个候选式的定义图。u例2.35（p31）名字定义下一个侯选式右部后继第77页，此课件共81页哦u例例2.35文法EEAT|TTTMF|FF（E）|iA+|M*|/u按照上面的存储结构，画出文法的存储结

40、构如图2-12所示：第78页，此课件共81页哦小小 结结u文法是形式语言的一个十分重要的基本概念。文法可定义为一个四元组，文法G=（VN，VT，P，S），其中，VN是一个非终结符集，VT是一个终结符集，P是一个产生式集，S是文法的开始符号。uChomsky将文法分为0型，1型，2型和3型文法。程序设计语言的词法规则属于3型文法（正规文法），程序设计语言的语法和语义部分一般是采用2型文法来描述。第79页，此课件共81页哦u对于一个文法，我们需要研究它的句型句型，句子句子和语言语言。要识别一个符号串是不是一个文法的句子，需要对它进行语法分析。分析方法有两类，一类是自上而下分析法，另一类是自下而上的分析方法。u为了进行语法分析，需要事先将产生式存储在计算机中。可以为文法建立一个产生式表，把文法的所有的产生式都放在这个产生式表中。为了在分析过程中能迅速查找到相应的产生式，还可以建立一个目录表。第80页，此课件共81页哦作业作业uP363,4,5,6,7,10uftp:/219.222.171.9user:chenqians无密码第81页，此课件共81页哦