形式語言與自動機(jī)課件——上下文無關(guān)文法

1、1College of Computer Science & Technology, BUPT 4.2 上下文無關(guān)文法的變換上下文無關(guān)文法的變換 nCFG 的簡化的簡化n消無用符號消無用符號n消消 產(chǎn)生式產(chǎn)生式n消單產(chǎn)生式消單產(chǎn)生式n對生成式形式進(jìn)行標(biāo)準(zhǔn)化對生成式形式進(jìn)行標(biāo)準(zhǔn)化2College of Computer Science & Technology, BUPT生成式的標(biāo)準(zhǔn)形式生成式的標(biāo)準(zhǔn)形式n Chomsky范式 (CNF - Chomsky Normal Form)生成式形式為ABC, Aa, A, B, CN , aT (后面將證明, 每個上下文無關(guān)文法都有一個C

2、NF文法) nGreibach范式 (GNF)生成式形式為Aa, aT , N* 意義: 對每個2型語言都可找到一個文法使產(chǎn)生式的右端都以終結(jié)符開始 中心思想:消除左遞歸.3College of Computer Science & Technology, BUPT變換算法變換算法 - 消去無用符號消去無用符號 無用符號（無用符號（useless symbol） 非生成非生成符號符號 不可達(dá)不可達(dá)符號符號 有用符號（有用符號（useful symbol） 對于對于 CFG G = (N, T, P , S )，稱符號稱符號 X N T 是是有用的有用的，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng) S X w，

3、其中其中 w T* ， , (N T )* . 稱符號稱符號 X 是是生成生成符號符號（generating symbol），當(dāng)且僅當(dāng)存在當(dāng)且僅當(dāng)存在w T* ，滿足滿足 X w. 稱符號稱符號 X 是是可達(dá)可達(dá)符號符號（reachable symbol），當(dāng)且僅當(dāng)存在當(dāng)且僅當(dāng)存在 , (N T )* ，滿足滿足 S X . 4College of Computer Science & Technology, BUPT 計算生成符號（計算生成符號（generating symbol）集集 計算可達(dá)符號（計算可達(dá)符號（reachable symbol）集集 消去非生成符號、不可達(dá)符號消去

4、非生成符號、不可達(dá)符號消去無用符號消去無用符號 消去相關(guān)產(chǎn)生式消去相關(guān)產(chǎn)生式5College of Computer Science & Technology, BUPT計算生成符號集計算生成符號集思路思路 對于對于 CFG G = (N, T, P , S )，可通過下列歸納可通過下列歸納步驟計算生成符號集合：步驟計算生成符號集合： 基礎(chǔ)基礎(chǔ) 任何終結(jié)符任何終結(jié)符 a T 都是生成符號；都是生成符號； 歸納歸納 如果有產(chǎn)生式如果有產(chǎn)生式 A ，其中其中 ( N T )* 的的每一個符號都是生成符號，則每一個符號都是生成符號，則 A 也是生成符號；也是生成符號；6College of

5、Computer Science & Technology, BUPT步驟步驟:(1) N 0 = (賦為賦為 ) N 0為有用的非終結(jié)符集為有用的非終結(jié)符集(2) N = A | A且且T* N為非終結(jié)符集合為非終結(jié)符集合(3) 如果如果N 0N 則轉(zhuǎn)則轉(zhuǎn)(4),否則轉(zhuǎn)否則轉(zhuǎn)(6)(4) N 0=N(5) N= N 0 A | A且且(TN 0)* , 轉(zhuǎn)轉(zhuǎn)(3)(6) N 1 = N小結(jié)小結(jié): 算法算法1找出能推出終結(jié)符串的非終結(jié)符作為有找出能推出終結(jié)符串的非終結(jié)符作為有用符號用符號. 算法算法1: 找出有用非終結(jié)符找出有用非終結(jié)符 7College of Computer Sci

6、ence & Technology, BUPT 一層層向外擴(kuò)展，直至最外兩層相等為止。所得集合一層層向外擴(kuò)展，直至最外兩層相等為止。所得集合即是算法即是算法1的有用符號。的有用符號。 算法算法1: 找出有用非終結(jié)符（圖示）找出有用非終結(jié)符（圖示） 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計算可達(dá)符號集計算可達(dá)符號集

7、 思路思路 對于對于 CFG G = ( N, T, P , S )，可通過下列歸可通過下列歸納步驟計算可達(dá)符號集合：納步驟計算可達(dá)符號集合： 基礎(chǔ)基礎(chǔ) S 是可達(dá)符號；是可達(dá)符號； 歸納歸納 如果如果 A 是可達(dá)符號，并且有產(chǎn)生式是可達(dá)符號，并且有產(chǎn)生式 A ，其中其中 ( N T )* ，則則 中的每一個符號都是可達(dá)中的每一個符號都是可達(dá)符號；符號；9College of Computer Science & Technology, BUPT算法步驟算法步驟: (1) N 0 = S (2) N= x | AN 0 且且Ax N 0 (N為有用符號集合為有用符號集合) (3) 如果

8、如果N 0N轉(zhuǎn)轉(zhuǎn)(4), 否則轉(zhuǎn)否則轉(zhuǎn)(5) (4) N 0=N; 轉(zhuǎn)轉(zhuǎn)(2) (繼續(xù)迭代下去繼續(xù)迭代下去) (5) N 0 = N N T1=NT P1由由P內(nèi)只含內(nèi)只含N中符號的生成式組成中符號的生成式組成 (即刪去了從即刪去了從S起不可達(dá)的符號起不可達(dá)的符號).算法算法2: 找出有用符號找出有用符號(從從S可達(dá)的符號可達(dá)的符號) 10College of Computer Science & Technology, BUPT一層層外擴(kuò)一層層外擴(kuò),找出從找出從S可達(dá)的所有符號可達(dá)的所有符號(含非終結(jié)符和終含非終結(jié)符和終結(jié)符結(jié)符)算法算法2: 找出從找出從S可達(dá)的符號可達(dá)的符號 （圖

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消去非生成符號及不可達(dá)符號消去非生成符號及不可達(dá)符號 例例: (書書P135 例例1) 已知已知2型文法型文法G=(S, A, B, a, P, S) P: SAB, Sa, Aa由算法由算法1: B推不出終結(jié)符串推不出終結(jié)符串, 刪除之刪除之, 并刪并刪SAB. N1=S, A, P1: Sa,

10、 Aa由算法由算法2: A不出現(xiàn)在不出現(xiàn)在S能推導(dǎo)出的句型中能推導(dǎo)出的句型中, 刪除之刪除之.并刪并刪Aa 結(jié)果為結(jié)果為G1=(S, a, Sa, S ) 應(yīng)用算法應(yīng)用算法1和算法和算法2,可刪去文法中所有無用符號可刪去文法中所有無用符號.12College of Computer Science & Technology, BUPT消去非生成符號及不可達(dá)符號消去非生成符號及不可達(dá)符號注意注意: 必須先執(zhí)行算法必須先執(zhí)行算法1,再執(zhí)行算法再執(zhí)行算法2,不能顛倒不能顛倒.否則否則,可能導(dǎo)致無用符號不會被完全刪除可能導(dǎo)致無用符號不會被完全刪除.例例:上例中上例中,若先用算法若先用算法2,得

11、得 Sa, AAB, Aa再用算法再用算法1, 得得Sa, Aa。而而Aa是多余的是多余的. 定理定理:任何非空的上下文無關(guān)語言任何非空的上下文無關(guān)語言, ,可由不存在無用符可由不存在無用符號的上下文無關(guān)語言產(chǎn)生號的上下文無關(guān)語言產(chǎn)生( (證明略證明略) )。 13College of Computer Science & Technology, BUPT消去消去 產(chǎn)生式產(chǎn)生式 目的目的 方便文法的設(shè)計方便文法的設(shè)計, 利于文法規(guī)范化利于文法規(guī)范化. 影響影響 消去消去 產(chǎn)生式產(chǎn)生式, 除了文法不能產(chǎn)生字符串除了文法不能產(chǎn)生字符串 外，不會影響到原文法相應(yīng)的語言中其它字符串外，不會影響

12、到原文法相應(yīng)的語言中其它字符串的產(chǎn)生的產(chǎn)生. 可致空符號（可致空符號（nullable symbol） 對于對于 CFG G = (N, T, P , S )，稱符號稱符號 A N 是是可致可致空空的的，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng) A . 消去消去 產(chǎn)生式及其影響，需要計算可致空符號的產(chǎn)生式及其影響，需要計算可致空符號的集合集合. 14College of Computer Science & Technology, BUPT算法算法3: 生成無生成無 文法文法定義定義: 若G的生成式中無任何產(chǎn)生式,或只有一個生成式S且S不出現(xiàn)在任何生成式的右邊,則稱G為無文法.思路思路 對于 CFG G =

13、 (N T, P , S )，可通過下列歸納步驟計算可致空符號集合： 基礎(chǔ)基礎(chǔ) 對于所有產(chǎn)生式對于所有產(chǎn)生式 A ，A 是一個可致空符號是一個可致空符號 歸納歸納 如果有產(chǎn)生式如果有產(chǎn)生式 B C1C2Ck ，其中每一個其中每一個 Ci N 是可致空符號，則是可致空符號，則 B 是一個可致空符號；是一個可致空符號；15College of Computer Science & Technology, BUPT算法算法3: 生成無生成無 文法文法算法步驟算法步驟:(1) 利用算法1, 找出N= A | AN且A=+ (找出能推導(dǎo)出的所有非終結(jié)符A)(2) 用以下兩步組成P1 如果生成式A

14、0 C11 C2CnnP n0 且每個Ck (1kn) 均在N內(nèi) 而對于0jn, 沒有j在N內(nèi) (i也可能是終結(jié)符) 則P1應(yīng)加入 A0Y11Y22Ynn 其中Yk或是Ck或是 (即所有的可能組合) 但A不加入P116College of Computer Science & Technology, BUPT算法算法3: 生成無生成無 文法文法算法步驟（續(xù)）算法步驟（續(xù)）: 如果SN,則P1中應(yīng)加入以下生成式 S1|S S1是新的起始符 N1=NS1 如果SN, 則N1=N, S1=S 由此得出G1=( N1,T, P1,S1)17College of Computer Science

15、 & Technology, BUPT消去消去 產(chǎn)生式產(chǎn)生式例例: (書書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的構(gòu)造 由SaSbS; 加入SaSbS|abS|aSb|ab 由SbSaS; 加入SbSaS|baS|bSa|ba 但S不加入P1 由SN得出 S1 S N1= NS1 = S,S118College of Computer Science & Technology, BUPT消去消去 產(chǎn)生式產(chǎn)生

16、式 練習(xí)練習(xí) 以下產(chǎn)生式表示的文法中以下產(chǎn)生式表示的文法中，D 為可致空符號：為可致空符號： S A; A 0BD; B 0BC; B 1; C 1; D . 通過通過上述步驟，上述步驟，消去消去 產(chǎn)生式產(chǎn)生式，得到如下產(chǎn)生式集合：，得到如下產(chǎn)生式集合： S A; A 0BD; A 0B; B 0BC; B 1; C 1.19College of Computer Science & Technology, BUPT消去單產(chǎn)生式消去單產(chǎn)生式 單產(chǎn)生式單產(chǎn)生式 形如形如 A B 的產(chǎn)生式，其中的產(chǎn)生式，其中A、B 為非為非終結(jié)符終結(jié)符. 消去單產(chǎn)生式的目的消去單產(chǎn)生式的目的 可簡化某些證

17、明，減少推可簡化某些證明，減少推導(dǎo)步數(shù)導(dǎo)步數(shù), 利于文法規(guī)范化利于文法規(guī)范化. 單元偶對（單元偶對（unit pairs） 對于對于 CFG G = (N, T, P , S )， A，B N ，稱稱 (A，B) 是是單元偶單元偶 對對，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng) A B ，且該推導(dǎo)過程僅使用過單產(chǎn)生式且該推導(dǎo)過程僅使用過單產(chǎn)生式. 消去單產(chǎn)生式時，需要計算所有單元偶對的集合消去單產(chǎn)生式時，需要計算所有單元偶對的集合. 20College of Computer Science & Technology, BUPT消去單產(chǎn)生式消去單產(chǎn)生式思路思路 設(shè)設(shè) CFG G = (N, T, P , S

18、 )，對每個單元偶對對每個單元偶對 (A，B) ，在在 G1 中加入產(chǎn)生式中加入產(chǎn)生式 A ，其中其中 B 為一個非單產(chǎn)生式；從為一個非單產(chǎn)生式；從而消去而消去 G 中的單產(chǎn)生式，中的單產(chǎn)生式，得到得到 CFG G1 = (N, T, P1, S )：算法步驟算法步驟:(1) 對每個對每個AN,構(gòu)造非終結(jié)符集構(gòu)造非終結(jié)符集NA=B|A=* B ( NA是可由是可由A推出的單生成式中的非終結(jié)符集推出的單生成式中的非終結(jié)符集)。構(gòu)造方法分三步構(gòu)造方法分三步: N0=A N=C | 如果如果BC P且且B N0N0 若若N N0,則則N0=N,轉(zhuǎn)向轉(zhuǎn)向 (繼續(xù)迭代繼續(xù)迭代) 否則否則NA = N,

19、轉(zhuǎn)向轉(zhuǎn)向(2). (已得到了完整的已得到了完整的NA)21College of Computer Science & Technology, BUPT消去單產(chǎn)生式消去單產(chǎn)生式算法步驟（續(xù)）算法步驟（續(xù)）:(2) 構(gòu)造構(gòu)造P1:如果如果B P且不是單生成式且不是單生成式, 則對于則對于BNA的所有的所有A,把把A加入到加入到P1中中(即對每個即對每個B NA (意味著意味著A=+ B)的非單生成式的非單生成式B P, 直接將直接將與與NA的的A連接連接, 構(gòu)成新產(chǎn)生式構(gòu)成新產(chǎn)生式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 的簡化的簡化 小結(jié)小結(jié) 設(shè)設(shè) CFG G = (V, T, P , S )，可以通過下列步驟對可以通過下列步驟對 G 進(jìn)行簡化進(jìn)行簡化： （1）消除消除 G 中的中的 產(chǎn)生式產(chǎn)生式； （2）消除消除 G 中的單元產(chǎn)生式；中的單元產(chǎn)生式； （3）消除消除 G 中的中的 無用符號無用符號. 結(jié)論結(jié)論 設(shè)設(shè) CFG G 的語言至少包含一個非的語言至少包含一個非 的字符串，通的字符串，通 過過上述步驟上述步驟從從 G 構(gòu)造構(gòu)造 G1 ，則

21、有則有 L(G1)= L(G) - . 注意注意 以上簡化步驟的次序以上簡化步驟的次序.23College of Computer Science & Technology, BUPT消去單產(chǎn)生式消去單產(chǎn)生式 （例）（例）例例: 設(shè)設(shè) 2型文法型文法G = (S,A,B, ( , ) , + , * , a, P, S) P: SS+A|A AA*B|B B(S)|a 構(gòu)造無單生成式的文法構(gòu)造無單生成式的文法G1 解解: (1) 構(gòu)造構(gòu)造NS , NA , NB N0=S N = C | BC P且且B N0N0 = AS = A, S N0N N0 = N = A,S 繼續(xù)轉(zhuǎn)繼續(xù)轉(zhuǎn)

22、N=BA,S=B,A,S N0N N0 = N =B,A,S 繼續(xù)轉(zhuǎn)繼續(xù)轉(zhuǎn) 有有N=B,A,S= N0 NS= B, A, S 同理可得同理可得: NA=A,B, NB=B 24College of Computer Science & Technology, BUPT消去單產(chǎn)生式消去單產(chǎn)生式 （續(xù)續(xù)） (2) 構(gòu)造構(gòu)造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代替這兩條產(chǎn)生式代替這兩條產(chǎn)生式)

23、又又 B(S) P, B NS 將將S（S）加到加到P1中中. 又又 Ba P, B NS 將將Sa加到加到P1中中.25College of Computer Science & Technology, BUPT消去單產(chǎn)生式消去單產(chǎn)生式 （續(xù)續(xù)）同理同理: 對對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中中. 結(jié)果結(jié)果: 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是循環(huán)文法是循環(huán)文法27College of Computer Science & Technology, BUPT生成式的代換生成式的代換定義定義: 2型文法中所有形如型文法中所有形如A的生成式稱為的生成式稱為A生成式生成

25、式.引理引理1: 對對A的的A生成式可進(jìn)行變換生成式可進(jìn)行變換設(shè)設(shè) 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中生成式產(chǎn)生的語言相等中生成式產(chǎn)生的語言相等,證明從略。證明從略。28College of Computer Science & Technology, BUPT生成式的代換生成式的代換例例: 設(shè)文法設(shè)文法G G有有Sa S S |bSa S S |

26、b B B 應(yīng)用引理應(yīng)用引理1,1,設(shè)設(shè)=a B=S, =S, =S B Ba S S a S S | | b b 即即 r1 r2替換替換SaSS|bSaSS|b有有G1的產(chǎn)生式為的產(chǎn)生式為: Sa Sa aSSaSS S|a S|ab bS | bS | b r1 r229College of Computer Science & Technology, BUPT生成式的代換生成式的代換其句子其句子aabbbaabbb的推導(dǎo)樹為的推導(dǎo)樹為 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: 消除直接左遞歸消除直接左遞歸 設(shè)設(shè)G = (N, T, P, S), P中有中有A生成式生成式 AA1 | A2 | | Am |1 |2 | |n其中其中i的第一個字符不是非終結(jié)符的第一個字符不是非終結(jié)符A (可以是其它非終結(jié)符可以是其它非終結(jié)符)可構(gòu)成可構(gòu)成G1= (NA, T, P1, S), A為新引入的非終結(jié)符為新引入的非終結(jié)符 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消除直接左遞歸對推導(dǎo)樹的影響消除直接左遞歸對推導(dǎo)樹的影響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 消左遞歸消左遞歸? 以后的句法分析算法不適用于左遞歸以后的句法分析算法不適用于左遞歸, ,會引起死循環(huán)。會引起死循環(huán)。 對于給定的對于給定的2型文法型文法, 該文法不存在無用符號該文法不存在無用符號, 無循環(huán)且是無循環(huán)且是無無生成式的文法生成式的文法, 為了消除為了消除G中可能存在的左遞歸中可能存在的左遞歸, 構(gòu)成一構(gòu)成一個等效的無左遞歸的文法個等效的無左遞歸的文法G1, 可用算法可用算法5。 算法算法5在原