《形式语言概述》PPT课件.ppt

《《形式语言概述》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《形式语言概述》PPT课件.ppt（81页珍藏版）》请在三一办公上搜索。

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

2、（1）符号语言中最基本的不可再分的单位（2）符号串符号串是由字母表中的符号所组成的有穷序列。符号串由小写x,y,z表示例：某个字母表=a,b,c,z,if,then,else,main,1,2,3,4,9,0,=,=,;，则建立在上的符号串有：if(2+3=5)then a=6 else b=8;空串是不含任何符号的串，记作（3）符号串的长度符号串x中所包含的符号的个数称为符号串x的长度，记为|x|。例：字母表0，1，则|010110|=6。空串的长度为0。,（4）子字符串设有非空符号串u=xvy，其中x、v、y是符号串，且v，则称v为符号串u的子符号串。例：设字母表=a，b，c，d，+，-，

3、*，/，(，)上有符号串x=a+b*(c+d)，则a、a+b*与（c+d）等都是x的子符号串，且其长度分别为a=1、a+b*=4与(c+d)=5（5）符号串的头和尾如果z=xy是一个符号串，则x是z的头,而y是z的尾。如果y非空，则x是z的固有头，又称为真前缀；若x非空，则y是z的固有尾，又称为真后缀。例 假设字母表=a,b,c上的符号串z=abc，则、a、ab、abc都是z的头，且除abc外都是z的固有头；、c、bc、abc都是z 的尾，且除abc外都是z的固有尾。,若只对符号串的头部感兴趣，记做z=x。若只对尾部感兴趣，则记为z=x。,符号串的运算,连接（乘积）运算设 x与y是同一个字母表

4、上的两个符号串，把y的各个符号相继写在x的符号后所得到的符号串称为x与y的连接，记为xy。例：设在字母表a,b,c上有符号串 x=ab与y=cba，则z=xy=abcba。这里x=2,y=3,z=5。对于字母表上的任何符号串x，都有x=x=x注：xy!=yx符号串的方幂设x是某个字母表上的符号串，把x自身连接n次，即z=xxx（n个x），称为符号串x的n次方幂，记为z=xn。例:x=ab x3=ababab,2.1.3 符号串集合,符号串集合集合A中一切元素都是某字母表上的符号串，则称A是该字母表上的符号串的集合。字母表上的符号串的集合通常用大写字母来A、B、C、表示。例：设某个字母表a,b,

5、c,d,符号串集合A，B A=a,bc,B=abc,cd,ab,乘积两个符号串集合A和B的乘积AB定义为AB=xyxA，且yB例:设A=a,b，B=c,d,e 则AB=ac,ad,ae,bc,bd,be对于任何空集合，都有A=A=A方幂类似于符号串的方幂，可以定义符号串集合的方幂，特别地定义字母表A的方幂为：A0=，A1=A，An=An-1A(n0),符号串集合的运算,字母表的闭包与正闭包的运算闭包设有字母表A，A的闭包定义如下：A*=A0A1 A2 An,其中，An（n=0，1，2，3，）中所有的符号串的长度为n，因此字母表A的闭包 A*为字母表上一切长度为n的符号串所组成的集合。注：闭包可

6、以看作由A上符号组成的所有串的集合（包括空串）正闭包如果不允许包含空串，则得到字母表A的正闭包。A的正闭包 A+=A1 A2 An 注：正闭包可以看作由A上符号组成的所有串的集合（不包括空串）语言字母表上按照某种规则形成的某个符号串的集合，所以，语言是该字母表上正闭包的子集,例：设字母表=a,b,c,依次写出长度为1、2、3的符号串，可得到 的正闭包+：+=a,b,c,aa,ab,ac,bb,bc,aaa,aab,aac,abb,abc,baa,在+上添入空串即得*。,2.2 文法的定义及其分类,什么是文法?描述语言的语法结构的形式规则，严格地定义句子的结构，用适当条数的规则把语言的全部句子描

7、述出来，是以有穷的集合刻划无穷的集合的工具。,:=:=|:=我|你|他:=:=是|学习:=|,我是大学生的推导过程：=我=我=我是=我是=我是大学生,2.2.2 文法的形式定义(1),非终结符出现在规则的左部，用括起来，表示一定语法概念的词，用VN表示终结符语言中不可再分割的字符串（包括单个字符组成的串）用VT表示V=VN U VT开始符号表示所定义的语法范畴的非终结符又称为识别符号开始符号用S表示,2.2.2 文法的形式定义(2),重写规则也叫产生式规则，或称为生成式，是形如或:=的(,)有序对,其中,是某个字母表V+中的一个元素，是V*中的一个元素。称为规则的左部，称为规则的右部。例：AB

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

9、D1，D2，D3S 是开始符号,为N注：产生式的规则说明一点，即若A，A，A可写成A|。“|”读做“或者”。上面的产生式规则可以改写为：NL|NL|NDLa|b|cD1|2|3,2.2.3 文法的分类,乔姆斯基（Chomsky）于1956年建立形式语言的描述以来，把文法分成四种类型，即0型、1型、2型和3型文法。0型文法(短语文法)设G=（VN，VT，P，S），如果它的每个产生式是这样一种结构：(VNVT)+，且至少含有一个非终结符，而（VNVT）*，则称G是一个0型文法。0型文法又称短语文法，它的能力相当于一个图灵机。例如，A图灵机是识别0型文法的识别装置0型文法是对产生式限制最少的文法；对

10、0型文法产生式的形式作某些限制，可得到其他类型文法的定义。,1型文法（上下文有关文法）设G=（VN，VT，P，S）为一文法，若P中的每一个产生式均满足，仅仅S除外，则文法G是1型文法或上下文有关文法。所谓上下文有关文法即：=1A2，=1B2，符号串1 和2可以认为是上下文，A只有出现在上下文之间中，才可以被符号串B替代，成为=1A2=1B2因此，1型文法又称为上下文有关文法。能够识别上下文无关语言的自动机称为线性界限自动机。缩写为LBA注：1型文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成，除非是开始符号产生,2型文法（上下文无关文法）设G=(VN，VT，P，S)，若P

11、中的每个产生式满足:是一个非终结符,(VNVT)*，则此文法称为2 型文法或上下文无关文法。有时将2型文法的产生式表示为形如：A，其中AVN。也就是当用取代非终结符A时，与A所在的上下文无关。上下文无关文法有足够的能力描述现今的程序设计语言。识别上下文无关语言的自动机称为下推自动机。它是。缩写为PDA。例:2 型文法G=（VN，VT，P，N）其中，VN=N，DVT=0，1，2，3，4，5，6，7，8，9P=NNDD，D0123456789注：该文法描述的符号串的集合是整数。,3型文法（右线性文法或正规文法）对2型文法的产生式做进一步的限制，限制产生式右部是单一终结符或单一终结符跟着单一非终结符

12、，即：Aa,AaB则称该文法为3型文法，又称为右线性文法或正规文法，其中A、BVN，aVT.识别3型语言或正则语言的自动机称为有穷自动机。缩写为FA。例:3型文法 G=（VN，VT，P，S）其中，VN=S，A，BVT=0，1P=S011A0B，A1A0B，B010B注：该文法产生的是二进制整数。,2.2.4 文法举例,例：1型文法G=（VN，VT，P，A）VN=S,X,Y,Z VT=x,y,z P=S xSYZxYZxYxyyYyyyZ yzZY YZzZ zz,例：2型文法G=（VN，VT，P，E）VN=E，T，F，VT=+，*，（，），iP=EE+T|T,TT*F|T,F(E)|i 注：该

13、文法能推出具有乘和加运算的算术表达式。,例：正规文法G=（VN，VT，P，S）其中VN=S，A，B，G，H，VT=d，+，P=SdB|+A|A|.GAdB|.GBdB|.H|dGdHHdH|d其中，d代表十进制数字。根据以上我们对文法的定义我们不难发现3型文法类是2型文法类的特殊情况，2型文法类是1型文法类的特殊情况。每一类文法都是在前一类文法的基础上加上一些限定规则而产生的。因此，四类文法产生的语言就会有如下关系：3型语言2型语言1型语言0型语言,2.2.6 文法分类的意义,一个文法实际上是某种语言的一个简明、确切的描述，它表示了该语言中所允许的一类语法结构。从一个文法能推导出多个终结符的句

14、子。但是知道了如何去构造属于某一个语言的一个合法串只是问题的一个方面。同时我们还要有能力判定一个串是否合法。也就是说，我们需要确定这个给定串的推导序列。如果从文法出发找不到这个推导序列，则该串就是非法的。程序设计语言的词法分析属于正规文法，与局部语法相关的部分属于上下文无关文法，与全局语法和语义有关的部分属于上下文有关文法。,2.3 文法产生的语言和句型的语法树,推导推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。最左（右）推导：每次使用一个规则，以其右部取代符号串的最左（右）非终结符。注：最左推导和最右推导称为规范推导：归约归约是推导的逆过程，即，从给定的

15、源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程。最左(右)归约是最右(左)推导的逆过程。注：最左归约和最右归约称为规范归约。,文法产生的语言和句型的语法树（续）,推导和规范推导推导分为三大类：直接推导、，长度为n(n1)的推导+和长度为n（n0）的推导*。直接推导如是文法G=(VN,VT,P,S)的规则（或说是P中的一产生式），,(VNVT)*，则称符号串为符号串应用产生式所得到的直接推导。记为。,推导长度大于0的推导如果对于符号串v 与w存在一个直接推导序列 u0 u1u2u3un(n0)其中u0=v与un=w,则称符号串v推导出w或称w归约到v，记作v+w，称这个直接推导

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

17、推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换，则称这种推导为最右推导。规范推导在形式语言中，最右推导常称为规范推导，由规范推导所得的句型称为规范句型。,例：给出了下列文法G:|0|1|2|3|4|5|6|7|8|9VT=0,1,2,3,4,5,6,7,8,9 VN=,判断数据2634是否是C语言合法的数据?（1）用最右推导，每次用产生式的规则替换最右边的非终结符，推导过程如下：4434346342634,（2）用最左推导，每次直接推导都替换最左边的非终结符，推导过程如下：2262632634,2.3.2 句型、句子和语言,句型设GS是一个文法，如果符号串x是从开始符号S推导得到

18、的，即有S=*x，xV+，则称符号串x是该文法G的一个句型。句子GS是一个文法，如果符号串x是从开始符号S推导得到的，即有S=+x，并且xVT，则称该符号串为该文法的一个句子。注：实质上，句子是句型的特殊情况，句子是由终结符组成，而句型是有终结符和非终结符组成。语言:GS是一个文法，文法G产生的语言L(G)=x|S=*x，并且xVT，即文法的语言是文法所有句子的集合。,句型、句子和语言（续）,文法规则的递归定义非终结符的定义中包含了非终结符自身。注：使用文法的递归定义要谨慎，要有递归出口，否则，可能永远产生不出句子。,例：字母表A=0,1文法：|0|1 再如：字母表A=0,1 0|1,2.3.

19、3 语法树,在自然语言中，句子结构可以借助一种树形表示进行分析。如下面的句子：They are students and teachers of the Physics Department。对该句子的结构进行分析，其树型结构如图2-3所示，由此可以看出，该句子是由主语、系词和表语组成，是一个语法正确的句子。,在自然语言中，可以通过树型表示直观地分析句子的结构；在形式语言中，我们提到了句型、推导的概念，在证明某个符号串是否是某个文法的句型时，采用从文法开始符号推导的方法，这个推导过程可以用语法树直观的表示出来。语法树也称为推导树，其定义如下：,给定文法G=(VN,VT,P,S)，对于G的任何句

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

21、，则称该文法具有二义性。例:设文法GS：Sif B then S|if B then S else S|i：=E给出符号串if B then if B then S else S的语法树。语法树的结构如图2-5所示。从上面的语法图我们可以看出，字符串if B then if B then S else S能够画出两棵语法树，所以该文法是一个二义性文法。,在语言中，为了避免二义性的文法，往往对文法加以一定的限制，限制条件语句then之后不允许再是条件语句从语义解释方面限制条件语句中的else只能与其前面的、还没有和其他else配对的then配对。,Sif B then S|if B then S

22、 else S|i：=E符号串if B then if B then S else S,2二义性文法的证明,要判定一个文法是否是二义性文法，或它是否产生一个先天二义性的上下文无关语言，是个递归不可解的。即不存在一个算法，它能在有限的步骤内，确切的判断出某个给定的文法是否是一个二义性文法。我们要证明一个文法是否是一个二义性文法，就是找到该文法的一个句型特例，能够画出这个句型的两棵语法树，该文法就是二义性文法。,例2.25 文法G=（E，+，*，I,(,)，P，E）其中P为：Ei EE+EEE*EE(E)证明该文法是二义性文法，并将该文法改为等价的非二义性文法（等价的文法是指产生的语言相等的文法）

23、?,【证明】取句型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+TTF|T*FF（E）|i,2.3.5 文法产生的语言,例2.26 设G=（VN，VT，P，S），VN=S,B,E，VT=a,b,c，P由下列产生式组成：SaSBESaBEEBBEaBabbBbbbEbeeEee（1）问该文法是Chomsky哪一类型的文法？（2）它生成的语言是什么？,（1）答根据文法分类定义，由于文法中存在产生式，其左

24、部由长度大于1的符号串构成，如产生式“EBBE”，显然不符合Chomsky 的2型和3型文法的定义。该文法产生式左部串的长度均小于等于右部串的长度，符合1型文法的定义，所以该文法是上下文有关文法。,（2）根据如下推导：对于每一个n1，我们将号产生式使用n-1次，得到推导序列：S an-1S(BE)n-1，然后使用产生式(2)一次，得到：S an(BE)n，然后从an(BE)n.继续推导，总是对EB使用产生式的右部进行替换，而最终在得到的串中，所有的B都限于所有的E。设n=3，aaBEBEBEaaaBBEEBEaaaBBEBEEaaaBBBEEE。即有：S anBnEn.接着，使用产生式(4)一

25、次,得到SanbBn-1En，然后使用产生式n-1 次得到：S anbnEn，然后使用产生式一次，使用产生式n-1次，得到：S anbnen 因此该文法产生的语言是L(G)=anbnen|n1。,例：设有上下文无关文法如下：GS：SABAUTUa|aUTb|bTBc|cC将文法的产生式代入产生如下文法：GS：SUTBUa|aUTb|bTBc|cC,考察文法，用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)

26、=(aibjck|i1,j1,k1)=a+b+c+,语言产生文法(1),例：设L1=a2nbn|n=1 且a,b VT试构造生成L1的文法G1设 n=1，L1=aab n=2，L1=aaaabb n=3，L1=aaaaaabbb 所以得：S aaSb S aab,例：构造一个上下文无关文法G，使其描述的语言L(G)是能够被5整除的无符号整数集合。能够被5整除的整数其结构特点是，末位数一定是0或5。所以，只要保证生成的整数末位数字是0或5即可。据此，构造描述能被5整除的无符号整数集合的文法如下：GS：SN0|N5NDN|D0|1|2|3|4|5|6|7|8|9,语言产生文法(3),例:写出一个上

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

28、）的分析方法。,2.4.1 自上向下的分析方法,基本思想 自上而下的分析方法就是从识别符号出发，看是否能推导出待检查的符号串，如果能推导出这个符号串，则表明此符号串是该文法的句型或句子，否则就不是。或者说，以文法的识别符号作为根结点，看是否能构造出一个语法树，而且此语法树所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则就不是。,例 设文法GS：SaAbc|aBAbaBbeB|d输入串：abed，识别该串是否是该文法的一个句子?方法：从文法的识别符号S开始出发，选择它的一个产生式SaAbc 得到直接推导S aAbc

29、以识别符S作为根结点，构造语法树，如下图2-7所示,SaAbc|aBAbaBbeB|d,abed?,2分析过程,符号串aAbc与待检查的符号串abed的第一个符号相匹配。由于符号串aAbc的第2个符号是非终结符，因此需要对它进行替换。A只有一个产生式Aba。以其右部替换A，得推导SaAbcababc得到语法树，如图2-7（b）所示。符号串ababc与待查符号串abed的第2个符号相匹配，但与第3个符号不相匹配，匹配失败。此时，需要退回到非终结符 A，重新选择S另外的产生式，再做试探。这种选择的过程称之为回溯。,选择S的另外一条产生式的规则SaB，得到直接推导SaB，得到语法树2-7（c），再选

30、取其中的一条产生式BbeB，得到推导SaBabeB，得到语法树如图（d），将Bd代入即可得到该字符串abed。,3存在问题,自上而下分析方法是从文法的识别符号开始，选择相应的产生式规则进行推导。但在推导过程中会出现回溯现象。我们把出现回溯的分析称为不确定的自顶上下分析方法。这种方法花费时间多，效率低，编程实现时复杂，如果对文法加以限制，就可以避免回溯，这就出现了我们后面要提到的LL(1)分析方法,2.4.2 确定的自上而下的分析方法,例:设文法GSSaBc|bCdBeB|fCdC|c试检查符号串aefc是不是该文法的句子?,识别符S有两条产生式，它们的右部首符号分别是终结符a和b。待检查符号串

31、aefc的首符号是a，所以从识别符S出发，只能选择其产生式SaBc得到直接推导SaBc得到语法树如图2-8（a）所示。其中，非终结符B有两条产生式，它们右部首符号分别是终结符e与f，而待检查的符号串aefc的第2个符号是终结符e，所以选择B的产生式BeB得到推导SaBcaeBc，得到语法树如图2-8（b）所示。,由于待检查的符号串aefc的第3个符号是终结符f，因而对句型aeBc中的非终结符B选择其产生式Bf的推导SaBcaeBcaefc得到语法树如图2-8（c）所示。如此推导出的符号串aefc，语法树的叶子结点序列是aefc，与待检查的符号串aefc相匹配。,SaBc|bCdBeB|fCdC

32、|c,aefc?,例:若有文法GSSAp|BqAaAcABbBdB当输入串W=ccap，那么试图推出输入串的推导过程为：SApcApccApccap很容易构造相应语法树，如图2-9所示。,2.4.3 自下而上的分析方法,基本思想自下而上的分析方法的基本思想是从待检查的符号串出发，看最终是否能归约到文法的识别符号。如果能归约到文法的开始的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。,例2.33 若有文法GSScAdAabAa识别输入串w=cabd是否是该文法的句子。首先从输入串开始，扫描cabd，从中寻找一个子串，该子串与某一产生式的右端相匹配。子串a和子串ab都是合格

33、的，假若我们选用了ab，用产生式的左端A去替代它，即把ab归约到A，得到串cAd。构造一个直接推导cAdcabd，即从cabd叶子开始向上构造语法树，接下去在得到的串cAd中又找到了子串cAd与产生式的右端相匹配，则用S替代cAd，或称将cAd归约到S，得到了又一直接推导ScAd，形成了最终的语法树。分析过程如图2-10所示。,2存在问题,在自上向下的分析中，假定要被代换的最左非终结符的符号是V，且有n条规则：V1|2|3|n，那么如何确定用哪个右部去替换V？有一种解决方法是从各种可能的选择中挑选一种，并希望它是正确的。如果发现它是错误的，我们必须退回，再试着进行另外的选择，这种方式称为回溯。

34、,在自下向上的分析方法中，在分析程序工作的每一步中，都从当前串中选择一个子串，将它归约到某个非终结符号，我们暂且把这个子串称为“可归约串”。出现的问题是如何确定这个“可归约串”？比如在上例中，我们在对输入串cabd 的分析中，如果不是选择ab，用产生式，而是选择a，用产生式将a归约到A，那么最终就达不到S的结果，也就不知道cabd是一个句子。因此在归约时，ab是“可归约串”而不是a。如何求“可归约串”成为自下而上进行分析的关键。下面我们用“句柄”的概念来描述“可归约串”。,3句柄的概念,（1）形式化定义令G是一文法，S是文法的开始符号，是文法的一个句型。如果有：S=*A且A=+则称是句型相对于

35、非终结符A的短语。特别地，如有A则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。（2）求一个句型的句柄给定某个句型，要求出该句型的句柄，比较直观的方法就是画出该句型的语法树。该语法树的一棵子树的叶子结点（从左到右）组成的符号串便是这个句型关于子树根结点的一个短语。,语法树的一棵简单子树（只有单层子树）的叶子结点组成的符号串是这个句型关于简单子树根结点的一个直接短语。语法树的最左的简单子树叶子结点组成的符号串就是这个句型的句柄。,例:已知文法GS：S(R)|a|RTTS,T|S求句型=(a,(T),(S,T)的短语，直接短语和句柄？,【解答】观察该语法树，共有10个非叶

36、子结点，10棵子树。因此有短语aT(T)S,T(S,T)(T),(S,T)a,(T),(S,T)(a,(T),(S,T),2.4.4 文法的存储,一个文法的语法图由该文法所有非终结符的定义图组成。每个非终结符号的定义图是一个结构型数据。写成高级语言的结构型数据形式，则为：type struc=boxes boxes=record name:array110 of char;def:struc;nextp:struc;、rights:struc;end;,“名字”是用某种内部形式表示的终结符号或非终结符号的名字。“定义”是一个指针，对于非终结符号，它指向其第一个侯选式结构图的开始位置。对于终结符

37、号，它为0“下一个侯选式”是一个指针，指向相同左部的下一个侯选式的开始位置。若无侯选式，则它为0；“右部后继”是一个指针，指向同一个右部的下一个符号。另用一个一维数组记录所有的非终结符号定义图的开始地址。也就是说，这个数组的每个元素都是一个指针，分别指向相应的非终结符号的第一个候选式的定义图。例2.35（p31）,例2.35文法EEAT|TTTMF|FF（E）|iA+|M*|/按照上面的存储结构，画出文法的存储结构如图2-12所示：,小 结,文法是形式语言的一个十分重要的基本概念。文法可定义为一个四元组，文法G=（VN，VT，P，S），其中，VN是一个非终结符集，VT是一个终结符集，P是一个产

38、生式集，S是文法的开始符号。Chomsky 将文法分为0 型，1型，2型和3型文法。程序设计语言的词法规则属于3型文法（正规文法），程序设计语言的语法和语义部分一般是采用2型文法来描述。,对于一个文法，我们需要研究它的句型，句子和语言。要识别一个符号串是不是一个文法的句子，需要对它进行语法分析。分析方法有两类，一类是自上而下分析法，另一类是自下而上的分析方法。为了进行语法分析，需要事先将产生式存储在计算机中。可以为文法建立一个产生式表，把文法的所有的产生式都放在这个产生式表中。为了在分析过程中能迅速查找到相应的产生式，还可以建立一个目录表。,作业,P36 3,4,5,6,7,10ftp:/219.222.171.9 user:chenqians 无密码,