《计算机程序编译原理 第2章 形式语言概论课件》由会员分享，可在线阅读，更多相关《计算机程序编译原理 第2章 形式语言概论课件（25页珍藏版）》请在金锄头文库上搜索。
1、第2章形式语言概论,文法和语言形式化定义 文法的类型 语言和语法树 文法和语言的几点说明 分析方法简介 本章小结,字母表和符号串,字母表是元素的非空有穷集合，用表示。字母表中的元素称为符号。 例如：汉语的字母表中包括汉字、数字及标点符号等。 PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。 符号的有穷序列称为符号串，如compiler, string等。什么符号也不包含的符号串称为空符号表，用表示。符号串所包含的符号的个数称为符号串的长度。空符号串的长度为零。,符号串的运算,连接运算。设x, y是两个符号串，则xy称为x与y的连接。如x=cate, y=
2、nation, 则xy=catenation, 特别地，=，其中是任意符号串。 符号串的方幂。设x是符号串，则把x自身连接n次得到符号串z, 即z=xx.xx称为符号串x的方幂，写成z=xn 。 符号串集合的乘积。设A, B是两个符号串集合，则AB表示A与B的乘积，定义为 AB=xy|xA, yB。例如，A=ab,c, B=d, efg, 则AB=abd,abefg,cd,cefg。特别地，A= A =A, A=A=A=, 其中为空集。，空符号串不属于空集。 符号串集合的方幂。同一符号串集合的乘积。 符号串集合的正闭包。符号串集合A正闭包A+=A1A2. An.即A+为集合A上所有符号串的集合
3、。 符号串集合的自反闭包。符号串集合A正闭包A*=A+=A+ A+=A A*= A*A,文法,定义2.1 设VN,VT分别是非空有限的非终结符号集和终结符号集，V=VNVT, VNVT=，一个产生式是一个序偶对（，），其中 V+, V*，通常表示为： -或:=，称为产生式的左部，称为产生式的右部。 定义2.2 文法G是一个四元组，G=（VN, VT, P, S）,其中VN,VT分别是非空有限的非终结符号集和终结符号集，VNVT=，P是产生式集，S VN称为文法的识别符号或开始符号。 如果产生式集合中的产生式有共同的左部，如-， -，则可将其简写为： -|。,文法G=（VN，VT，P，S） VN
4、 =标识符，字母，数字 VT =a,b,c,x,y,z,0,1,9 P= a, z 0, 9 S= 习惯上只将产生式写出。并有如下约定： 1、第一条产生式的左部是开始符号； 2、用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符； 3、G可写成GS，其中S是开始符号；,文法例子,0型文法：对任一产生式，都有(VNVT)+， (VNVT)* 。 1型文法（上下有关文法）：对任一产生式，都有|， 仅仅 S除外。 2型文法（上下无关文法）：对任一产生式，都有VN ， (VNVT)*。 3型文法（正规文法）：任一产生式的形式都为AaB或Aa，其中A VN ，B VN
5、，a VT。,文法分类,文法举例,例2.6 1型文法G6=（VN，VT，P，S），其中VN=S，X，Y，Z，VT=x，y，z，P=SxSYZ|xYZ, xYxy, yYyy, yZyz, ZYYZ, zZzz 例2.7 2型文法G7=（VN，VT，P，S），其中VN=S，T，VT=a，b，c, d，P=SaTd, TbT|cT|b|c 例2.8 2型文法G8=（VN，VT，P，B），其中VN=B，VT=(，) ，P=B(B)|BB|( ) 例2.9 2型文法G9=（VN，VT，P，S），其中VN=S，VT=0，1 ，P=S0S1, S01 例2.10 正规文法G10=（VN，VT，P，A），其
6、中VN=A, B, C, D，VT=x, y, z ，P=AxB|yC, BzB|y|yC, CxD, DyD|x ,推导,定义2.3 G=（VN, VT, P, S），是文法G的产生式，,V*，若有v, w满足：v=, w= , 则说：v（应用规则）直接产生w 或说：w是v的直接推导 或说：w直接归约到v 记作 v w。 例 GS：S0S1， S01 直接推导： 0S10011 （v=0S1，w=0011，使用规则S01，=0，=1） S 0S1 （v=S，w=0S1，使用规则S0S1，=，= ） 0S100S11 （v=0S1，w=00S11，使用规则S0S1，=0，=1） 定义2.4 v
7、+u 若存在v =0 =1=n=u, (n0) 则称u为u的一个推导，记为v+u。 定义2.5 v*u 表示v+u 或 v=u,最左推导,定义2.6 在xUy=xuy直接推导中，若x VT*, U VN, 即U是符号串xUy中最左非终结符，则称此直接推导为最左直接推导。若一个推导的每一步直接推导都是最左直接推导，那么此推导称为最左推导。 例 G12： | a|b|c|x|y|z 0|1|2|3|4|5|6|7|8|9 aa6a69,最右推导,定义2.7 在xUy=xuy直接推导中，若y VT*, U VN, 即U是符号串xUy中最右非终结符，则称此直接推导为最右直接推导。若一个推导的每一步直接
8、推导都是最右直接推导，那么此推导称为最右推导。 最右直接推导又称为规范直接推导，最右推导又称为规范推导。 例 文法如G12. 996969a69,句型、句子和语言,定义2.8 如果符号串x是从识别符号推导出来的，即S* x，则称x是文法GS的句型。开始符号S也是文法G的句型。 定义2.9 如果符号串x是终结符号构成，即S* x，x VT*，则称x是文法GS的句子。 定义2.10 设S是文法G的开始符号，文法G的语言L（G）=u|S* u, x VT*，即文法的语言是文法的所有句子构成的集合。,文法和语言,0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语
9、言或上下文有关语言（CSL） 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）,语法树,设文法G=（VN, VT, P, S），对于文法G的任意一个句型都存在一个相应的语法树： 树中每个结点都有一个标记，该标记是VNVT中的一个符号； 树的根结点标记是文法的识别符号S； 若树的一个结点至少有一个叶子结点，则该结点的标记一定是一个非终结符； 若树的一个结点有多个叶结点，该结点的标记为A，这些叶结点的标记从左到右分别是B1，B2，.，Bn，则AB1B2BnP,文法的
10、句型都可依据其产生式来生成相应的语法树。,上下文无关文法的语法树,例: GS: EE+T|T TT*F|F F(E)|i,E E + T T * F ( E ) i E + T,句型E+(E+T)*i的语法树,叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。,产生式树,例: GS:EE+T|T, TT*F|F, F(E)|i,*,T,F,i,F,E,(,),*,T,F,i,F,E,(,),+,E,F,(a),(b),(c),(d),(e),(f),文法和语言的几点说明,(1) 文法中某些非终结符不在任何规则的右部出现，该非终
11、结符称为不可到达的； (2) 文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的（无用非终结符）； (3)可空终结符,可以用于消除左递归； (4)一个文法，如果它的一个句子有两棵或两棵以上的语法树，则称该句子具有二义性。如果一个文法含有二义性的句子，则该文法具有二义性。形如UU的产生式。会引起文法的二义性。,化简文法,例：GS 1) SBe SBe 2) BCe BAf 3) BAf AAe 4) AAe Ae 5) Ae 6) CCf 7) Df,问题：一个句型是否对应唯一的一棵语法树？,例：GZ:Z aZb Z Z Z ab,Z a Z b a b,Z a Z b Z a b,句
12、型aabb的语法树,自上而下分析方法,自上而下分析方法的基本思想是从文法的识别符号出发，看是否能够推导出待检查的符号串，如果能够推导出这个符号串，则表明此符号串是该文法的一个句型或句子，否则便不是。或者说，以文法识别符号作为根结点，看其是否能够构造一个语法树，而且此语法树的所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能够生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则便不是。 自上而下分析方法可分为：不确定的自上而下分析方法和确定的自上而下分析方法两种。不确定的自上而下分析方法可能需要回溯，因此时间花费多，效率低,自上而下的语法分析,例：文法G：S cAd
13、A ab A a识别输入串 w = cabd 是否该文法的句子,SSS cAdcAd a b 推导过程：S cAd cabd,自下而上分析方法,自下而上分析方法的基本思想是从待检查的符号串出发，看最终是否能归约（推导的逆过程）到文法的识别符号。如果能够归约到文法的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。 从待检查的符号串出发，在其中寻找一个称为句柄的子串，此句柄如果与文法中某一产生式右部相匹配，那么就用此产生式左部（一个非终结符）去替换待检查符号串的句柄，替换之后得一个新符号串，然后，对这个新符号串作同样的处理。这个过程称为归约过程。,自下而上的语法分析,例：文法
14、G：S cAd A ab A a识别输入串 w = cabd 是否该文法的句子,S AA c a b d c a b d c a b d 规约过程：S cAd cabd,句型分析的有关问题,1）如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是V，且有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？ 2）如何识别可归约的串？ 在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,产生式表,在归约过程中，采用产生式表来保存所有产生式。,小结,文法和语言形式化定义； 文法的类型，0型文法，上下相关文法，上下无关文法，正规文法； 语言和语法树，推导和规范推导、句型句子和语言、产生式树； 文法和语言的几点说明，多余规则，有害规则，二义性、可空终结符； 分析方法简介 ，自上而下和自下而上的分析方法；,
