第2章 形式语言基础

1、第第2章章 形式语言基础形式语言基础 计算机处理语言，首先应考虑语言的形式化、规范化，使其具有可计算性和可操作性；这就是形式语言理论研究的问题。 形式语言诞生于1956年，由Chomsky创立。通常，语言研究至少涉及三个方面：语法、语义和语用； 形式语言的基本观点是 ： 语言是符号串之集合！ 形式语言理论研究的形式语言理论研究的基本问题基本问题是：是： 研究符号串集合的表示方法、结构特性研究符号串集合的表示方法、结构特性 以及运算规律。以及运算规律。因此：因此：【内容提要】 2.1 形式语言是符号串集合 2.2 形式语言是由文法定义的 2.3 各种语法成分的定义 2.4 两类特性文法 2.5

2、文法变换方法 2.6 形式语言的分类第第2章章 形式语言基础形式语言基础 字母表 - 元素(符号)的非空有限集合； 符号串 - 符号的有限序列； 符号串集合 - 有限个或者无限个符号串组成的集合； 规 则 - 以某种形式表达的在一定范围内共同遵守的章程和制度；这里，指符号串的组成规则。2.1 形式语言是符号串集合形式语言是符号串集合 【形式语言】是字母表上的符号按一定的规则组成的所有符号串集合；其中的每个符号串称为一个句子。【名词解释】：【名词解释】：三要素！三要素！【例【例2.1】 L1= 00,01,10,11 ; 字母表字母表1= 0,1, 句子有：句子有：00,01,10,11【注】【

3、注】 (1) b0= （空符号串）（空符号串）,b1=b,b2=bb,b3=bbb, (2) L1 为有限语言为有限语言; L2 为无限语言。为无限语言。 形式语言概念示例：形式语言概念示例：【例【例2.2】 L2= abmc,bn | m0,n0 字母表字母表2= a,b,c,句型句型1: abmc 有句子：有句子：abc, abbc, abbbc, 句型句型2: bn 有句子：有句子： , b, bb, bbb, 两个语言两个语言!1.1.连接连接：. = 如：a.b=ab符号串符号串(集合集合)的运算的运算3.3.方幂方幂： n n = = = = n-1n-1 = = n-1n-1 4

4、.4.闭包：闭包：n n个个.符号串的运算符号串的运算 设设 , , 为两个符号串，则为两个符号串，则： 的正闭包：的正闭包： + + = = 1 1| | 2 2| n n| 的星闭包：的星闭包： * * = = 0 0| | 1 1| | 2 2| n n| 0 0 = = ( (空符号串空符号串) ) 什么符号也没有的符号串什么符号也没有的符号串 ！ 1 1= = ； 2 2 = = ；2.2. 或或： | | = = 或者或者 这是一种这是一种泛指泛指！5.5.固有头，固有尾固有头，固有尾 对于每个符号串对于每个符号串s s， s s和和两者都是符号串两者都是符号串s s的前缀，的前缀

5、，后缀和子串。后缀和子串。 符号串符号串s s的固有头，固有尾：的固有头，固有尾： z=xy,xz=xy,x是是z z的头，的头，y y是是z z的尾，如果的尾，如果x x非空则非空则y y是固是固有尾，如果有尾，如果y y非空则非空则x x是固有头。是固有头。例：在例：在Z=abcZ=abc Z Z的头的头:,a,ab,abc:,a,ab,abc；其中固有头：；其中固有头：,a,ab,a,ab Z Z的尾的尾:,c,bc,abc:,c,bc,abc；其中固有尾：；其中固有尾：,c,bc,c,bc【例【例2.3】：】：(2) abc. = . abc=abc(1) abc.de= abcde(

6、4) (a|b)1 =(a|b)= a|b (a|b)* =(a|b)0 |(a|b)1 |(a|b)2 |(a|b)2 =(a|b)(a|b)=aa|ab|ba|bb 即：即：(a|b)* = (a|b)n , n0同理：同理：(a|b)+ = (a|b)n , n0 符号串运算示例符号串运算示例泛指：泛指：由由a，b组成的组成的任意符号串！任意符号串！（包括空串）（包括空串）(3) ab|cd = ab或者或者cd1. 乘积乘积： AB = xy | x A 且且 y B4.闭包闭包：A的正闭包的正闭包：A+ = A1A2AnA的星闭包的星闭包：A* = A0A1A2An 设设 A 和和

7、B 为两个符号串集合，则：为两个符号串集合，则：2. 和和： AB = A+B = x | x A 或或 x B 3.方幂方幂： An = AAA = AAn-1 = An-1An个个 A0 = ; A1 =A ; A2 =AA ; A3 =AAA ; .符号串集合的运算符号串集合的运算 符号串符号串(集合集合)的运算的运算 符号串集合运算示例符号串集合运算示例【例【例2.4】 设设 A=a,b,B=c,d 则则 A+B=a,b,c,d 则则 AB=xy|x A,y B=ac,ad,bc,bd【例【例2.5】 设设 A=a 则则 A* = A0A1A2An = +a+aa+aaa+ = ,a,

8、aa,aaa, =an|n0 【例【例2.6】 设设 A=a, b， A* = ? A* = A0A1A2An A0 = ; A1 = A =a, b; A2 = AA=a, ba, b=aa,ab,ba,bb; A3 = AA2=a, baa,ab,ba,bb =aaa,aab,aba,abb,baa,bab,bba,bbb; A* = x | x=(a|b)n , n0 符号串集合运算示例符号串集合运算示例( (续续) )： 推论推论：若：若 A 为任一字母表，则为任一字母表，则 A* 就是该字母就是该字母表表 上上的所有符号串的所有符号串(包括空串包括空串)的集合。的集合。2.2 形式语

9、言是由文法定义的形式语言是由文法定义的 形式语言是符号串的集合，对形式语言的描述形式语言是符号串的集合，对形式语言的描述有两种方式：有两种方式：(1) 枚举方式枚举方式：语言为有穷集合时：语言为有穷集合时 设有字母表设有字母表A=a,b,c, 有有 L1=a,aa,ab,ac, L2=c,cc(2) 使用文法使用文法：语言为无穷集合时，无法枚举：语言为无穷集合时，无法枚举 设有字母表设有字母表B=0,1, B+=0,1,00,10,11,01,000, 用用 A 表示表示B+，可以表示为，可以表示为A-0 A-1 A-A0 A-A1文法：用有穷的集合刻画无穷的集合的工具。文法：用有穷的集合刻画

10、无穷的集合的工具。 【定义】【定义】 文法文法(grammar)是是规则规则的有限集，通常可的有限集，通常可以表示为四元组：以表示为四元组： G(Z)=(VN, VT, Z, P) VN : 非终结符集非终结符集 ( 定义的对象集，如：语法成分等定义的对象集，如：语法成分等 ) ； VT : 终结符集终结符集 ( 字母表字母表 ) ； Z : 开始符号开始符号 ( 研究范畴中最大的定义对象研究范畴中最大的定义对象 ) ； P : 规则集规则集 ( 又称产生式集又称产生式集 ) ；2.2 形式语言是由文法定义的形式语言是由文法定义的每个元素每个元素2.2.1 什么是文法什么是文法 ？ Z - 或

11、者或者 A - | 注：此文法实际称为上下文无关文法注：此文法实际称为上下文无关文法 描述符号描述符号 ： -(定义为定义为/生成生成)，|(或者是或者是) 文法符号文法符号 ： Z , AVN， , (VN+VT)* 每个规则每个规则 【注意】提供了规则集，就相当给出了一个文法： S - aAc A - bA | G(S):VT= a,b,c ; Z = S ; P :VN= S,A ;G(Z)=(VN, VT, Z, P)2.2.1 什么是文法什么是文法 ？【例【例2.7】 L = abnc | n0 ，字母表：，字母表：= a,b,c； 展开：展开：L =ac,abc,abbc,abbb

12、c, 可以用右图给出的可以用右图给出的 S - aAc A - bA | 文法规则文法规则来表示来表示：2.2.2 文法是怎样定义语言的？文法是怎样定义语言的？ 则则 L(G) = x | Z x, x VT* 即：一个文法所定义的即：一个文法所定义的语言语言，就是由该文法，就是由该文法开始开始设有文法设有文法G(Z)，L(G)为为G所定义的语言；所定义的语言；利用利用推导算符推导算符 = 进行连续推导进行连续推导符号推导出符号推导出的所有的所有仅含终结符仅含终结符的所有的所有符号串符号串之之集合集合。其中的每个符号串皆称为其中的每个符号串皆称为句子句子。 = + +2.1使用文法的使用文法的

13、规则进行规则进行 形式语言是字母表上的符号按一定的形式语言是字母表上的符号按一定的规则规则组成的组成的 所有符号串集合。所有符号串集合。 从从开始符号出发，对符号串中的出发，对符号串中的定义对象定义对象，采，采用用推导的方法（的方法（用其规则右部替换左部用其规则右部替换左部）产生新的）产生新的符号串，如此进行，直到新符号串中不再出现定义符号串，如此进行，直到新符号串中不再出现定义的对象为止，则最终的符号串就是一个的对象为止，则最终的符号串就是一个句子。 S - aAc A - bA | 利用利用文法规则文法规则表示语言表示语言 【句子产生过程】( (= 推导算符) S S= = aAcaAc

14、= ac= ac = ac= ac S S= aAc= aAc = abAc= abAc = abc= abc = abc= abc S S= aAc= aAc = abAc= abAc= abbAc= abbAc = abbc= abbc 一个句子一个句子! !又一个句子又一个句子! ! S abS abn nc ,n0 c ,n0 = + +再一个句子再一个句子! !非终结符号非终结符号练习练习1.=a,b上的字符串集上的字符串集A=abna|n=1则该集合的文法是：则该集合的文法是：(1) A-aBa B-b|Bb|bB(2) Z-ABC A-a C-a B-bB|Bb|b(3) A-a

15、B B-ba|bB练习练习2. =a,b,c上的字符串集上的字符串集A=ancbn|n=0 该集合的文法是：该集合的文法是：A-aAb|c【例【例2.8】标识符标识符的文法的文法 【标识符标识符】指字母开头的字母、数字序列。】指字母开头的字母、数字序列。令令G(Z)=(VN, VT, Z, P)则则 VN = I(标识符标识符) , A(标识符尾标识符尾) ； VT = (字母字母) , d(数字数字) ； Z = I ; P : I - A | A - A | d A | 同理，同理，【无符号整数无符号整数】文法可写成：】文法可写成：G(N): N - d N | d其其四元组四元组也可写成

16、：也可写成：G(N)=( N, d, N, P ) 得：得： I = (|d)n , n0 令：令： I = A | A = A | d A | 求解求解文法文法所定义的语言所定义的语言(1)上面构造的标识符文法 属于正规文法I - A | A - A | d A | 先求解先求解 A: A=(|d) A , A=(|d)2 A , , A=(|d)n A 代入代入 A= 得：得： A= (|d)n , n0 I= A | 代入代入 A= (|d)n , n0正规方程式正规方程式标识符：字母开头的字母、数字序列标识符：字母开头的字母、数字序列 求解求解文法文法所定义的语言所定义的语言(2)则则

17、 L(G)的求解过程的求解过程 代代入法入法 ： Z - aAc A - bA | 【例【例2.9】 G(Z):所以所以： L(G)= abnc | n0 A = bA = bbA = = bn ,n0 Z = a A c a bn c , n0 = + +A b bn n = + + 即：即： A bn = + +，n0即：即： Z abnc ，n0 = + +则则 VN = E(算术表达式算术表达式),T(项项),F(因式因式)； VT = i(变量或常数变量或常数), + , - , * , / , ( , ) ； Z = E ; P : 【例【例2.10】简单算术表达式文法】简单算术表

18、达式文法【注】此文法定义了算术表达式的层次嵌套结构【注】此文法定义了算术表达式的层次嵌套结构: : E - T | E + T | E - T T - F | T * F | T / F F - i | ( E )令令 G(Z)= (VN, VT, Z, P) ( ( 表达式表达式 ) )表达式表达式项项因式因式文法文法E - E + E | E E | E * E | E / E | i | (E) ? 算术表达式文法应用示例：算术表达式文法应用示例： 根据根据 语言定义式语言定义式2.1， G(E): E-T |E+T |E-T T-F |T* F |T/F F-i |(E)证明证明 i*

19、(i+i-i)是文法是文法G(E)的一个的一个句子句子(即合法的即合法的算术表达式算术表达式): = + +E i*(i+i-i) 成立吗？成立吗？ E = + +E i*(i+i-i) =T =T*F =T*(E) =T*(E-T)=T*(E+T-T) =F*(E+T-T)=i*(E+T-T)= 观察推导过程，可以看观察推导过程，可以看到：一旦产生式选择错到：一旦产生式选择错了，会导致失败！了，会导致失败！=i*(i+i-i)L(G) = x | Z x , x VT* = + +合法的算术表达式是指：合法的算术表达式是指： 文法有两种基本运算：文法有两种基本运算：推导推导和和归约归约v星推

20、导星推导( ): 2.3 各种语法成分的定义各种语法成分的定义1. 直接推导直接推导( = ) : xAy = x y即：指用产生式的右部符号串即：指用产生式的右部符号串替换替换左部非终结符。左部非终结符。 加推导加推导算符算符v 加推导( ): 设设 x, y(VN+VT)*，A - P = * = *（当且仅当（当且仅当 = 1 = 2 = = ） 即：指一步或一步以上的直接推导运算。即：指一步或一步以上的直接推导运算。 （当且仅当当且仅当 =或或 = 1= 2=) 即：指零步或零步以上的直接推导运算。即：指零步或零步以上的直接推导运算。直接推导直接推导算符算符星推导星推导算符算符 = +

21、 + = + +2.3.1 文法的运算文法的运算 =. .+ + =. .+ +2. 直接归约直接归约( ) : x y xAy =. . =. .（当且仅当（当且仅当 1 1 2 2 ） =. . =. . =. . =. .v 星归约星归约( ): =. .* =. .* （当且仅当（当且仅当 =或或 1 1 2 2 ) ) =. . =. . = . . =. .即：直接归约是直接推导的即：直接归约是直接推导的逆运算逆运算，用产生式的左，用产生式的左 部非终结符替换右部符号串。部非终结符替换右部符号串。即：指零步或零步以上的直接归约运算。即：指零步或零步以上的直接归约运算。即：指一步或一

22、步以上的直接归约运算。即：指一步或一步以上的直接归约运算。直接归约直接归约算符算符加归约加归约算符算符星归约星归约算符算符v 加归约加归约( ): 2.3.1 文法的运算文法的运算 规范推导和规范归约规范推导和规范归约 实用中最常见的两种运算：l 最左推导( )每次推导皆最左非终结符优先；l 最左归约( )每次归约皆最左可归约串优先。 =+ + =. .+ +l 最右推导也称为规范推导l 最左归约也称为规范归约同一个句子可以通过不同的推导序列推导出来同一个句子可以通过不同的推导序列推导出来通常只考虑两种特殊推导，即通常只考虑两种特殊推导，即最左推导和最右推导最左推导和最右推导N1=N=ND=N

23、2=D2=1212 D2 N2 ND N N1N1 - N N - ND|D D - 0|1|2 =. =. =. =. =.最左归约是最右推导的逆过程！最左归约是最右推导的逆过程！i + i*il 给定一个符号串给定一个符号串 i+i*i ： T-F|T*F|T/F F-i |( E )G(E): E-T|E+T|E-T文法运算示例：文法运算示例： 【例【例 2.11】 算术表达式文法：算术表达式文法： =. =. =. =. =. =. =. =.2. 最左归约最左归约(从从符号串出发符号串出发)过程：过程：E = E +T= T +T= F+T= i+ T = i+T*F= i+ F *

24、F = i+i*F = i+i*i E =+ +i + i * iF+i*iT+i*iE+ i *iE+F*iE+T*iE+T*FE+TE i + i * i =. .+ +E1. 最左推导最左推导(从从开始符号出发开始符号出发)过程：过程：最左非终结符最左非终结符最左可归约串最左可归约串练习：练习：G=(S,A,a,b,P,S)S-aAS A-SbA A-SS S-a A-ba请写出句子请写出句子aabbaa的最右推导和最左推导。的最右推导和最左推导。最右推导最右推导:S=aAS=aAa=aSbAa=aSbbaa=aabbaa最左推导：最左推导：S=aAS=aSbAS=aabAS=aabba

25、S=aabbaa1,4,2,5,41,2,4,5,4即：句型是由文法开始符号加推导出的任一符号串。即：句型是由文法开始符号加推导出的任一符号串。 2.3.2 句型、句子和语法树句型、句子和语法树若有若有 且且 VT*，则，则 是句子；是句子； Z =+若有若有 , 则则 是句型；是句型； Z =+2. 句子句子即：句子是由开始符号加推导出的任一即：句子是由开始符号加推导出的任一终结终结符号串。符号串。 1. 句型句型设有文法设有文法 G(Z)=(VN, VT, Z, P)，则：，则：3.语法树语法树 句型句型(句子句子)产生过程的一种树结构表示；产生过程的一种树结构表示；树根树根开始符号开始符

26、号；树叶树叶给定的给定的句型句型(句子句子)。 A x1 x2 xn 重复步骤重复步骤，直到推导过程结束为止。，直到推导过程结束为止。 置树根为开始符号；置树根为开始符号； 【语法树的构造算法】【语法树的构造算法】 若若推导推导采用了采用了产生式产生式：A - x1x2xn，则有，则有子树：子树： 如此构造的语法树，其如此构造的语法树，其全体树叶全体树叶( (自左至右自左至右) ) 恰好是给定的句型恰好是给定的句型( (句子句子) )。 E = T = T*F =F*F =(E)*F =(E+T)*F=(T+T)*F =(T/F+T)*F =(T/F+F)*F =(T/F+F)*i 句型、句子

27、和语法树示例句型、句子和语法树示例【例2.12】算术表达式文法：(1) 证明证明 (T/F+F)*i 是一个句型是一个句型(表达式型表达式型)；(2) 画出该句型的语法树。画出该句型的语法树。 E - T | E + T | E - T T - F | T * F | T / F F - i | ( E )【证】【证】即：即：E (T/F+F)*i = + + 句型句型(T/F+F)*i的语法树构造：的语法树构造：ETT * FF ( E )E + TT T / FFiE - T | E+T | E-T T - F | T*F | T/F F - i | ( E )【注】关于语法树：【注】关于

28、语法树： 子树：由某一结点子树：由某一结点连同连同所有分支所有分支组成组成的部分。的部分。 简单子树简单子树 ：仅具有：仅具有单层分支单层分支的子树。的子树。 3. 句柄句柄 - - 一个句型的一个句型的最左简单短语最左简单短语称为该句型的称为该句型的句柄句柄。2.3.3 短语、简单短语和句柄 设文法设文法G(Z),x y是一个句型，则是一个句型，则: 则则 是句型是句型 x y 关于关于A的短语的短语(A是是 的名字的名字)； = + + = + +1.1.短语短语 若若 Z xAy xZ xAy x y y Z x A y 任一任一子树子树的的树叶全体树叶全体( (具有共同具有共同祖先祖先

29、的叶节点符号串的叶节点符号串) )皆为皆为短语短语； = + +2. 简单短语简单短语 若若 Z xAy Z xAy = x x y y 则则 是句型是句型 x y 关于关于A的简单短语的简单短语(A是是 的名字的名字) ； 任一任一简单子树简单子树的的树叶全体树叶全体( (具有共同具有共同父亲父亲的叶节点符的叶节点符号串号串) )皆为皆为简单短语简单短语； (他他) (哥哥哥哥)(喜欢喜欢) (看看) 图图2.2 他哥哥喜欢看书他哥哥喜欢看书的的语法树语法树(书书) 2.3.3 短语、简单短语和句柄 【例2.13】图2.2为一个中文句型的语法树： 短 语 - 他哥哥,喜欢看,书， 喜欢看书，

30、他哥哥喜欢看书 简单短语 - 他哥哥，喜欢看，书 句 柄 - 他哥哥（最左边的简单短语!）【例2.14】图2.3为一个算术表达式(型)的语法树： 句型： E+F-T/F*i 短语: E+F-T/F*i，E+F，F，T/F*i，T/F，i 简单短语: F，T/F，i 句柄: F E E - T E + T T * F F T / F i 图图2.3 E+F-T/F*i 的语法树的语法树 2.3.3 短语、简单短语和句柄 一类典型的综合例题：一类典型的综合例题：【例【例2.15】G(S): S-aAcBe ; A-Ab|b ; B-d 给定符号串给定符号串 ：aAbcde 证明证明 = aAbcd

31、e 是一个句型；是一个句型； 画出句型画出句型 的语法树；的语法树； 指出指出 中的短语、简单短语和句柄。中的短语、简单短语和句柄。【题解】【题解】 S=aAcBe=aAbcBe= aAbcde 语法树如右图：语法树如右图： 短语、简单短语和句柄短语、简单短语和句柄: : S S a A c B e a A c B e A b d A b d 短语短语: aAbcde ,Ab , d 简单短语简单短语: Ab , d 句柄：句柄：Ab练习：练习：G=(E,T,F,+,*,i,(,),P,E)P为为E-T|E+T , T-F|T*F , F-(E)|i句型句型(T+i)*i+F的语法树的语法树E

32、ET+TFT*FFi(E)+ETTFi短语短语: (T+i)*i+F T+i (T+i) (T+i)*i i F T i简单短语简单短语: i，F，T，i句柄：句柄：TG2(S): S - b S | a - 直接右递归直接右递归文法。文法。2.4 两种特性文法两种特性文法 2.4.1 递归文法 设有文法：设有文法：G(Z)=(VN,VT,Z,P)【定义】【定义】 设设 AVN，x, y(VN+VT)*，则，则; 若若 A xAy，称文法具有，称文法具有递归性递归性; = + +特别地特别地： 若若 A - A ，称文法具有，称文法具有直接左递归性直接左递归性； A - A ，称文法具有，称文

33、法具有直接右递归性直接右递归性。 递归文法是定义无限语言的工具递归文法是定义无限语言的工具 递归文法定义的语言有无限个句子递归文法定义的语言有无限个句子如：如：G1(S): S - S b | a - 直接左递归直接左递归文法；文法； 递归文法示例递归文法示例【例【例2.16】G(Z)： Z - aAbB | cZ A - bBc | B - BbAc |a Z - cZ 直接右递归性直接右递归性； B - BbAc 直接左递归性直接左递归性； A =bBc = bBbAcc 即即 A A 具有递归性具有递归性 ( 且且 又称为又称为A具有自嵌套性具有自嵌套性) 可以统称文法可以统称文法G(Z

34、)具有递归性。具有递归性。 = + +2.4.2 二义性文法【定义】【定义】 若文法中存在这样的句型，它具有若文法中存在这样的句型，它具有两棵两棵不同的语法树不同的语法树，则称该文法是，则称该文法是二义性二义性文法。文法。【例【例2.17】 算术表达式的另一种文法：算术表达式的另一种文法： 句型句型 i+i*i 有两棵不有两棵不 同的语法树同的语法树(右图右图)： G(E) 是二义性文法。是二义性文法。G(E)：E - E+E | E*E | (E) | i ;i (变量或常数变量或常数) E E E E E + E E E + E E * * E E i E i E * * E E + E

35、i E E + E i i i i i i i i i 二义性文法会引起歧义，二义性文法会引起歧义，应尽量避免之！应尽量避免之！文法二义性的消除文法二义性的消除【方法【方法1 1】不改变文法的原有规则】不改变文法的原有规则, ,加进一些非形加进一些非形 式的规定。式的规定。【方法【方法2 2】构造一个】构造一个等价的无二义性文法等价的无二义性文法，将排除，将排除 二义性的规则合并到文法中二义性的规则合并到文法中 加进运算符的优先顺序和结合规则加进运算符的优先顺序和结合规则 对对G(E)，规定，规定*优于优于+，*和和+服从左结合服从左结合G(E) - G (E) : E - E+T | T T

36、 - T*F | F F - (E) | i ;练习：判断下面的文法是否具有二义性？练习：判断下面的文法是否具有二义性？S-aB|bAB-bS|aBB|bA-aS|bAA|aaabbab最左推导最左推导S=aB=aaBB=aabB=aabbS=aabbaB=aabbabS=aB=aaBB=aabSB=aabbAB=aabbaB=aabbab所以该文法有二义性！所以该文法有二义性！2.5.1 文法的等价性 2.5 文法的等价变换文法的等价变换即：即：文法的等价性是指它们所定义的语言是一样的。文法的等价性是指它们所定义的语言是一样的。【定义】【定义】 设设G1、G2是两个文法，若是两个文法，若L(

37、G1)=L(G2)， 则称则称G1与与G2等价，记作等价，记作G1G2。【例【例2.18】 G1：S - aS|a G2：S - Sa|a L(G1)=a, aa, aaa, =an | n1 L(G2)=a, aa, aaa, =an | n1 L(G1)=L(G2) 即即 G1G2 【结论】【结论】一个语言，其描述文法并不唯一。一个语言，其描述文法并不唯一。练习：下面两个文法是否等价？练习：下面两个文法是否等价？G1: S-0S1 , S-01G2: A-0R , A-01 , R-A1 L1=0n1n|n=1;L2=0n1n|n=1;所以等价！所以等价！2.5.2 文法变换方法文法变换方

38、法 在实际工作中，人们总是希望定义一种语言的文法尽可能地简单。 另外，某些常用的语法分析技术也会对文法提出一定的要求或限制。 因此，有时需要对文法进行必要的改写。改写后的文法要与原文法等价通常称为文法变换。 这里重点介绍三类变换： BNF（巴科斯范式）表示法：巴科斯范式）表示法： 删除删除产生式；产生式； 必选项法；必选项法； 可选项法；可选项法； 重复可选项法。重复可选项法。 删除无用的产生式（文法的化简）；删除无用的产生式（文法的化简）； 文法的化简是指消除如下文法的化简是指消除如下无用产生式无用产生式： 1. A-A 形式的产生式形式的产生式(自定己自定己)； 2. 不能从其推导出终结符

39、号串的产生式不能从其推导出终结符号串的产生式(不终结不终结)； 3. 在推导中永不使用的产生式在推导中永不使用的产生式(不可用不可用)。 文法的化简文法的化简 删除删除不终结不终结产生式算法：产生式算法：(1) 构造构造能能推导出终结符号串的非终结符集推导出终结符号串的非终结符集VVT: 若有若有 A- 且且 VT* ;则令则令 AVVT ； 若有若有 B- 且且 (VT+ VVT)* ;则令则令 BVVT ; 重复步骤重复步骤，直到，直到VVT不再扩大为止。不再扩大为止。(2) 删除不在删除不在VVT中的所有非终结符中的所有非终结符( (连同其产生式连同其产生式) )。例题：例题：对文法化简

40、：对文法化简：S-Bab|cCB-b|bSC-DaD-Cb|CDaVVT=B,SS-BabB-b|bSC,D为什么没有入选？为什么没有入选？因为它们不能推出终极符因为它们不能推出终极符 删除删除不可用不可用产生式算法：产生式算法：(1) 构造可用构造可用的非终结符集的非终结符集 VUS: 首先令首先令 ZVUS ; (Z 为文法为文法开始符号开始符号) = + +(2) 删除不在删除不在VUS中的所有非终结符中的所有非终结符(连同其产生式连同其产生式)。【例【例2.19】化简下述文法：】化简下述文法： G(S): S - Be | Ec A - Ae | e | A B - C e | AfC

41、 - Cf ; D - f ; G - b 若有若有 Z A ，则，则 令令 AVUS ; 重复步骤重复步骤，直到，直到VUS不再扩大为止。不再扩大为止。 = + +文法的化简文法的化简例题：化简文法例题：化简文法S-aSab|bABA-bB|aB-aA|bC-abB|baAD-Cbc|abcVVT=A,B,C,D,SVUS=S,A,BS-aSab|bABA-bB|aB-aA|b 文法化简示例文法化简示例l 化简步骤：G(S): S - Be | Ec G(S): S - Be | Ec A - Ae | e | A A - Ae | e | A B - C e | AfB - C e | A

42、fC - Cf ; D - f ; G - bC - Cf ; D - f ; G - b 删除删除 A - A ;2. 删除删除不终结不终结产生式产生式: VVT= A,D,G,B,S ; 应删除应删除 C,E(连同其产生式连同其产生式)得：得： G(S): S - Be ; A - Ae | e ; B - Af ;D - f ; G - b ;3. 删除删除不可用不可用产生式产生式: VUS= S,B,A ; 应删除应删除 D,G(连同其产生式连同其产生式) 整理后得：整理后得：G(S):A - Ae | eB - AfS - Be 删除删除 产生式产生式【算法】【算法】1. 首先构造可

43、以推出空串的非终结符集：首先构造可以推出空串的非终结符集：V 若有若有 A- ; 则则 令令 AV ; 若有若有 B-A1 An 且全部且全部 AiV ;则令则令 BV ; 重复步骤重复步骤，直到，直到V 不再扩大为止。不再扩大为止。2. 删除删除 G(Z)中的中的 A - 形式的产生式；形式的产生式； 假定文法假定文法G(Z); L(G)3. 依次改写依次改写G(Z)中的产生式中的产生式 B - X1 X2 Xn :若有若有 Xi V 则用则用 (Xi| ) 替换之替换之(一个分裂为两个一个分裂为两个)； 若有若有 j 个个 Xi V ，则一个产生式将分裂为则一个产生式将分裂为2j个个! 删

44、除删除 产生式示例：产生式示例：(1) 求解求解 V = A,B (2) 删除删除 产生式产生式 得：得：S-aAbc|bS ；A-dABe ； B-A|b(3) 改写改写 右部含有右部含有 V 中元素的产生式：中元素的产生式： S-a(A| )bc S-aAbc|abc A-d(A| )(B| )e A-dABe|dBe|dAe|de B-(A| ) B-A含有含有V 元素元素的产生式的产生式 综合综合 G(S) ： S-aAbc|abc|bS A-dABe|dBe|dAe|de B-A|b【例【例2.20】G(S): S-aAbc|bS A-dABe| ; B-A|b练习：消空串练习：消空

45、串S-aBSS-bB-cSB-=S-a(B| )S S-b B-cS=S-aBS|aS S-b B-cS令令 ( | ) = 或者或者 1.必选项法（圆括号法） BNF（巴科斯范式）表示法（巴科斯范式）表示法必选其中之一！必选其中之一！例如：有例如：有 A - a |a 也可写成：也可写成： A - aA；A- | 【注】此法又称【注】此法又称提公因子法，提公因子法，利用此法可以解决：利用此法可以解决： 具有相同左部的各产生式首符号不同！具有相同左部的各产生式首符号不同！ 基本思想基本思想：扩展文法，引进新的：扩展文法，引进新的描述符号描述符号： ( ) 圆括号；圆括号； 方括号；方括号； 花

46、括号花括号可变换成可变换成: A - a( | ) 也可写成：也可写成： S - S; S - |令令 = 或者或者 2. 可选项法（方括号法） 例如：例如： S - | 可选也可不选！可选也可不选！例如例如 条件语句文法：条件语句文法： S - if (B) S 可变换成：可变换成： S - S - if (B) S else S可变换成：可变换成： S - if (B) S else S S(语句语句)，B(布布尔表达式尔表达式)或：或： S - if (B) S S ; S- else S| BNF（巴科斯范式）表示法（巴科斯范式）表示法3. 重复可选项法（花括号法） 例如：例如： A

47、- A| 令令 = 或或 或或 或或 可变换为：可变换为： A - 通过递推方法，可得：通过递推方法，可得： A= A= A= A= * 有有 A - 或或 A A ; A -A| 也可写成：也可写成： A A ; A -A| 验证：验证：【注】此方法常用来消除文法的【注】此方法常用来消除文法的直接左递归直接左递归！ BNF（巴科斯范式）表示法（巴科斯范式）表示法 产生式形式为：产生式形式为： A - u 2.6 形式语言的分类形式语言的分类 Chomsky 把形式语言分为把形式语言分为四类四类，分别由四类文，分别由四类文法定义；四类文法的区别在于法定义；四类文法的区别在于产生式的形式不同产生式的形式不同：(2) 1 型语言型语言 由由 1型文法型文法定义定义(1) 0 型语言型语言 由由 0型文法型文法定义定义又称又称 无限制文法无限制文法！ 产生式形式为：产生式形式为： - (VNVT)* 且至少有一个非终结符且至少有一个非终结符(VNVT)* 又称又称 上下文有关文法上下文有关文法！A VN, , (VNVT)* , u (VNVT)+A只有在只有在 和和 这样的上下文环境中才能换成这样的上下文环境中才能换成u2.6 形式语言的分类形