形式语言与自动机课件——上下文无关文法

1、1College of Computer Science & Technology, BUPT 4.2 上下文无关文法的变换上下文无关文法的变换 nCFG 的简化的简化n消无用符号消无用符号n消消 产生式产生式n消单产生式消单产生式n对生成式形式进行标准化对生成式形式进行标准化2College of Computer Science & Technology, BUPT生成式的标准形式生成式的标准形式n Chomsky范式 (CNF - Chomsky Normal Form)生成式形式为ABC, Aa, A, B, CN , aT (后面将证明, 每个上下文无关文法都有一个C

2、NF文法) nGreibach范式 (GNF)生成式形式为Aa, aT , N* 意义: 对每个2型语言都可找到一个文法使产生式的右端都以终结符开始 中心思想:消除左递归.3College of Computer Science & Technology, BUPT变换算法变换算法 - 消去无用符号消去无用符号 无用符号（无用符号（useless symbol） 非生成非生成符号符号 不可达不可达符号符号 有用符号（有用符号（useful symbol） 对于对于 CFG G = (N, T, P , S )，称符号称符号 X N T 是是有用的有用的，当且仅当，当且仅当 S X w，

3、其中其中 w T* ， , (N T )* . 称符号称符号 X 是是生成生成符号符号（generating symbol），当且仅当存在当且仅当存在w T* ，满足满足 X w. 称符号称符号 X 是是可达可达符号符号（reachable symbol），当且仅当存在当且仅当存在 , (N T )* ，满足满足 S X . 4College of Computer Science & Technology, BUPT 计算生成符号（计算生成符号（generating symbol）集集 计算可达符号（计算可达符号（reachable symbol）集集 消去非生成符号、不可达符号消去

4、非生成符号、不可达符号消去无用符号消去无用符号 消去相关产生式消去相关产生式5College of Computer Science & Technology, BUPT计算生成符号集计算生成符号集思路思路 对于对于 CFG G = (N, T, P , S )，可通过下列归纳可通过下列归纳步骤计算生成符号集合：步骤计算生成符号集合： 基础基础 任何终结符任何终结符 a T 都是生成符号；都是生成符号； 归纳归纳 如果有产生式如果有产生式 A ，其中其中 ( N T )* 的的每一个符号都是生成符号，则每一个符号都是生成符号，则 A 也是生成符号；也是生成符号；6College of

5、Computer Science & Technology, BUPT步骤步骤:(1) N 0 = (赋为赋为 ) N 0为有用的非终结符集为有用的非终结符集(2) N = A | A且且T* N为非终结符集合为非终结符集合(3) 如果如果N 0N 则转则转(4),否则转否则转(6)(4) N 0=N(5) N= N 0 A | A且且(TN 0)* , 转转(3)(6) N 1 = N小结小结: 算法算法1找出能推出终结符串的非终结符作为有找出能推出终结符串的非终结符作为有用符号用符号. 算法算法1: 找出有用非终结符找出有用非终结符 7College of Computer Sci

6、ence & Technology, BUPT 一层层向外扩展，直至最外两层相等为止。所得集合一层层向外扩展，直至最外两层相等为止。所得集合即是算法即是算法1的有用符号。的有用符号。 算法算法1: 找出有用非终结符（图示）找出有用非终结符（图示） N N0 0 = 空= 空 N = A | A 且 T* N = A | A 且 T*A A1 1A A3 3A A2 2N= NN= N0 0B|B且(TN B|B且(TN ) )* * B B2 2B B1 18College of Computer Science & Technology, BUPT计算可达符号集计算可达符号集

7、 思路思路 对于对于 CFG G = ( N, T, P , S )，可通过下列归可通过下列归纳步骤计算可达符号集合：纳步骤计算可达符号集合： 基础基础 S 是可达符号；是可达符号； 归纳归纳 如果如果 A 是可达符号，并且有产生式是可达符号，并且有产生式 A ，其中其中 ( N T )* ，则则 中的每一个符号都是可达中的每一个符号都是可达符号；符号；9College of Computer Science & Technology, BUPT算法步骤算法步骤: (1) N 0 = S (2) N= x | AN 0 且且Ax N 0 (N为有用符号集合为有用符号集合) (3) 如果

8、如果N 0N转转(4), 否则转否则转(5) (4) N 0=N; 转转(2) (继续迭代下去继续迭代下去) (5) N 0 = N N T1=NT P1由由P内只含内只含N中符号的生成式组成中符号的生成式组成 (即删去了从即删去了从S起不可达的符号起不可达的符号).算法算法2: 找出有用符号找出有用符号(从从S可达的符号可达的符号) 10College of Computer Science & Technology, BUPT一层层外扩一层层外扩,找出从找出从S可达的所有符号可达的所有符号(含非终结符和终含非终结符和终结符结符)算法算法2: 找出从找出从S可达的符号可达的符号 （图

9、示）（图示） N N0 0 = = S S N N = = x x | | A AN N 0 0 且且A Ax x N N 0 0A A1 1A A3 3A A2 2N N C C1 1C C2 211College of Computer Science & Technology, BUPT消去非生成符号及不可达符号消去非生成符号及不可达符号 例例: (书书P135 例例1) 已知已知2型文法型文法G=(S, A, B, a, P, S) P: SAB, Sa, Aa由算法由算法1: B推不出终结符串推不出终结符串, 删除之删除之, 并删并删SAB. N1=S, A, P1: Sa,

10、 Aa由算法由算法2: A不出现在不出现在S能推导出的句型中能推导出的句型中, 删除之删除之.并删并删Aa 结果为结果为G1=(S, a, Sa, S ) 应用算法应用算法1和算法和算法2,可删去文法中所有无用符号可删去文法中所有无用符号.12College of Computer Science & Technology, BUPT消去非生成符号及不可达符号消去非生成符号及不可达符号注意注意: 必须先执行算法必须先执行算法1,再执行算法再执行算法2,不能颠倒不能颠倒.否则否则,可能导致无用符号不会被完全删除可能导致无用符号不会被完全删除.例例:上例中上例中,若先用算法若先用算法2,得

11、得 Sa, AAB, Aa再用算法再用算法1, 得得Sa, Aa。而而Aa是多余的是多余的. 定理定理:任何非空的上下文无关语言任何非空的上下文无关语言, ,可由不存在无用符可由不存在无用符号的上下文无关语言产生号的上下文无关语言产生( (证明略证明略) )。 13College of Computer Science & Technology, BUPT消去消去 产生式产生式 目的目的 方便文法的设计方便文法的设计, 利于文法规范化利于文法规范化. 影响影响 消去消去 产生式产生式, 除了文法不能产生字符串除了文法不能产生字符串 外，不会影响到原文法相应的语言中其它字符串外，不会影响

12、到原文法相应的语言中其它字符串的产生的产生. 可致空符号（可致空符号（nullable symbol） 对于对于 CFG G = (N, T, P , S )，称符号称符号 A N 是是可致可致空空的的，当且仅当，当且仅当 A . 消去消去 产生式及其影响，需要计算可致空符号的产生式及其影响，需要计算可致空符号的集合集合. 14College of Computer Science & Technology, BUPT算法算法3: 生成无生成无 文法文法定义定义: 若G的生成式中无任何产生式,或只有一个生成式S且S不出现在任何生成式的右边,则称G为无文法.思路思路 对于 CFG G =

13、 (N T, P , S )，可通过下列归纳步骤计算可致空符号集合： 基础基础 对于所有产生式对于所有产生式 A ，A 是一个可致空符号是一个可致空符号 归纳归纳 如果有产生式如果有产生式 B C1C2Ck ，其中每一个其中每一个 Ci N 是可致空符号，则是可致空符号，则 B 是一个可致空符号；是一个可致空符号；15College of Computer Science & Technology, BUPT算法算法3: 生成无生成无 文法文法算法步骤算法步骤:(1) 利用算法1, 找出N= A | AN且A=+ (找出能推导出的所有非终结符A)(2) 用以下两步组成P1 如果生成式A

14、0 C11 C2CnnP n0 且每个Ck (1kn) 均在N内 而对于0jn, 没有j在N内 (i也可能是终结符) 则P1应加入 A0Y11Y22Ynn 其中Yk或是Ck或是 (即所有的可能组合) 但A不加入P116College of Computer Science & Technology, BUPT算法算法3: 生成无生成无 文法文法算法步骤（续）算法步骤（续）: 如果SN,则P1中应加入以下生成式 S1|S S1是新的起始符 N1=NS1 如果SN, 则N1=N, S1=S 由此得出G1=( N1,T, P1,S1)17College of Computer Science

15、 & Technology, BUPT消去消去 产生式产生式例例: (书书P137 例例2) G = (N, T, P, S) 其中N=S, T= a, b P: SaSbS | bSaS| 求其无文法 G1=( N1,T, P1, S1)解解: (1) S =+ N=S (2) P1的构造 由SaSbS; 加入SaSbS|abS|aSb|ab 由SbSaS; 加入SbSaS|baS|bSa|ba 但S不加入P1 由SN得出 S1 S N1= NS1 = S,S118College of Computer Science & Technology, BUPT消去消去 产生式产生

16、式 练习练习 以下产生式表示的文法中以下产生式表示的文法中，D 为可致空符号：为可致空符号： S A; A 0BD; B 0BC; B 1; C 1; D . 通过通过上述步骤，上述步骤，消去消去 产生式产生式，得到如下产生式集合：，得到如下产生式集合： S A; A 0BD; A 0B; B 0BC; B 1; C 1.19College of Computer Science & Technology, BUPT消去单产生式消去单产生式 单产生式单产生式 形如形如 A B 的产生式，其中的产生式，其中A、B 为非为非终结符终结符. 消去单产生式的目的消去单产生式的目的 可简化某些证

17、明，减少推可简化某些证明，减少推导步数导步数, 利于文法规范化利于文法规范化. 单元偶对（单元偶对（unit pairs） 对于对于 CFG G = (N, T, P , S )， A，B N ，称称 (A，B) 是是单元偶单元偶 对对，当且仅当，当且仅当 A B ，且该推导过程仅使用过单产生式且该推导过程仅使用过单产生式. 消去单产生式时，需要计算所有单元偶对的集合消去单产生式时，需要计算所有单元偶对的集合. 20College of Computer Science & Technology, BUPT消去单产生式消去单产生式思路思路 设设 CFG G = (N, T, P , S

18、 )，对每个单元偶对对每个单元偶对 (A，B) ，在在 G1 中加入产生式中加入产生式 A ，其中其中 B 为一个非单产生式；从为一个非单产生式；从而消去而消去 G 中的单产生式，中的单产生式，得到得到 CFG G1 = (N, T, P1, S )：算法步骤算法步骤:(1) 对每个对每个AN,构造非终结符集构造非终结符集NA=B|A=* B ( NA是可由是可由A推出的单生成式中的非终结符集推出的单生成式中的非终结符集)。构造方法分三步构造方法分三步: N0=A N=C | 如果如果BC P且且B N0N0 若若N N0,则则N0=N,转向转向 (继续迭代继续迭代) 否则否则NA = N,

19、转向转向(2). (已得到了完整的已得到了完整的NA)21College of Computer Science & Technology, BUPT消去单产生式消去单产生式算法步骤（续）算法步骤（续）:(2) 构造构造P1:如果如果B P且不是单生成式且不是单生成式, 则对于则对于BNA的所有的所有A,把把A加入到加入到P1中中(即对每个即对每个B NA (意味着意味着A=+ B)的非单生成式的非单生成式B P, 直接将直接将与与NA的的A连接连接, 构成新产生式构成新产生式A加入到加入到P1中中)(3) 得到得到G1=( N1, T1, P1, S)N N0 0 = A= AB B

20、1 1B B2 2N NA AC C1 1C C2 222College of Computer Science & Technology, BUPTCFG 的简化的简化 小结小结 设设 CFG G = (V, T, P , S )，可以通过下列步骤对可以通过下列步骤对 G 进行简化进行简化： （1）消除消除 G 中的中的 产生式产生式； （2）消除消除 G 中的单元产生式；中的单元产生式； （3）消除消除 G 中的中的 无用符号无用符号. 结论结论 设设 CFG G 的语言至少包含一个非的语言至少包含一个非 的字符串，通的字符串，通 过过上述步骤上述步骤从从 G 构造构造 G1 ，则

21、有则有 L(G1)= L(G) - . 注意注意 以上简化步骤的次序以上简化步骤的次序.23College of Computer Science & Technology, BUPT消去单产生式消去单产生式 （例）（例）例例: 设设 2型文法型文法G = (S,A,B, ( , ) , + , * , a, P, S) P: SS+A|A AA*B|B B(S)|a 构造无单生成式的文法构造无单生成式的文法G1 解解: (1) 构造构造NS , NA , NB N0=S N = C | BC P且且B N0N0 = AS = A, S N0N N0 = N = A,S 继续转继续转

22、N=BA,S=B,A,S N0N N0 = N =B,A,S 继续转继续转 有有N=B,A,S= N0 NS= B, A, S 同理可得同理可得: NA=A,B, NB=B 24College of Computer Science & Technology, BUPT消去单产生式消去单产生式 （续续） (2) 构造构造P1对对NS= S,A,B SS+A P且不是单生成式且不是单生成式, 且且S NS 于是，将于是，将SS+A加到加到P1中中. 又又 AA*B P, A NS 将将SA*B加到加到P1中中.( SA, AA*B 直接用直接用SA*B代替这两条产生式代替这两条产生式)

23、又又 B(S) P, B NS 将将S（S）加到加到P1中中. 又又 Ba P, B NS 将将Sa加到加到P1中中.25College of Computer Science & Technology, BUPT消去单产生式消去单产生式 （续续）同理同理: 对对NA= A, B AA*B P且非单生成式且非单生成式, A NA 将将AA*B加到加到P1中中. B(S)|aP且非单生成式且非单生成式, B NA 将将A(S)|a加到加到P1中中. 同理同理: 对对NB=B 将将B(S)|a加到加到P1中中. 结果结果: P1为为 SS+A|A*B|(S)|a AA*B|(S)|a B(

24、S)|a26College of Computer Science & Technology, BUPT消除递归消除递归递归的定义递归的定义:在在2型文法中型文法中若存在若存在 A=+A, AN，则称则称G是递归文法。是递归文法。若存在若存在 A=+ A G是左递归文法是左递归文法若存在若存在 A=+A G是右递归文法是右递归文法若存在若存在 A=+ A G是循环文法是循环文法27College of Computer Science & Technology, BUPT生成式的代换生成式的代换定义定义: 2型文法中所有形如型文法中所有形如A的生成式称为的生成式称为A生成式生成

25、式.引理引理1: 对对A的的A生成式可进行变换生成式可进行变换设设 G = (N,T,P,S)AB是是P中的生成式中的生成式, BN,(NT)*Br1| r2| rk是是P中的中的B生成式生成式可生成可生成G1 = (N1,T, P1,S)P1中的生成式是将中的生成式是将P中的中的AB用用Ar1|rk取代取代.证明思路证明思路: P1和和P中生成式产生的语言相等中生成式产生的语言相等,证明从略。证明从略。28College of Computer Science & Technology, BUPT生成式的代换生成式的代换例例: 设文法设文法G G有有Sa S S |bSa S S |

26、b B B 应用引理应用引理1,1,设设=a B=S, =S, =S B Ba S S a S S | | b b 即即 r1 r2替换替换SaSS|bSaSS|b有有G1的产生式为的产生式为: Sa Sa aSSaSS S|a S|ab bS | bS | b r1 r229College of Computer Science & Technology, BUPT生成式的代换生成式的代换其句子其句子aabbbaabbb的推导树为的推导树为 b bS Sa a S S S Sa a S S S Sb bS S a a a a S S S S S Sb bb bb bb b即将子树根S

27、用下一层的直接后代代替了. 30College of Computer Science & Technology, BUPT消除直接左递归消除直接左递归 引理引理2: 消除直接左递归消除直接左递归 设设G = (N, T, P, S), P中有中有A生成式生成式 AA1 | A2 | | Am |1 |2 | |n其中其中i的第一个字符不是非终结符的第一个字符不是非终结符A (可以是其它非终结符可以是其它非终结符)可构成可构成G1= (NA, T, P1, S), A为新引入的非终结符为新引入的非终结符 G1中的中的P1为，将为，将P中的中的A生成式用以下生成式取代生成式用以下生成式取

28、代 A1|2|n|1A|2A|nA A1|2|m|1A|2A|mA证明思路证明思路: G和和G1二者的正则式都是二者的正则式都是(1+2+n)(1+m)* 31College of Computer Science & Technology, BUPT消除直接左递归消除直接左递归 （例）（例）例例: (书书P142 例例4 4) SS +A | A, AA* *B | B, B(S) | a 1 1 1 1可变换为可变换为 SA A | AS S+A | +A S AB B | BA A* *B B | * *B A B (S)(S)| a 32College of Computer

29、Science & Technology, BUPT消除直接左递归对推导树的影响消除直接左递归对推导树的影响A AA A i i1 1A A i ik kA A i i2 2. . . . A A A Ai ik k A A i ik k- -1 1 A A . . . .i i2 2 A A i i1 1A A G中局部 ：33College of Computer Science & Technology, BUPT消除左递归的算法消除左递归的算法Why 消左递归消左递归? 以后的句法分析算法不适用于左递归以后的句法分析算法不适用于左递归, ,会引起死循环。会引起死循环。 对于给定的对于给定的2型文法型文法, 该文法不存在无用符号该文法不存在无用符号, 无循环且是无循环且是无无生成式的文法生成式的文法, 为了消除为了消除G中可能存在的左递归中可能存在的左递归, 构成一构成一个等效的无左递归的文法个等效的无左递归的文法G1, 可用算法可用算法5。 算法算法5在原