形式語(yǔ)言與自動(dòng)機(jī)課件——上下文無(wú)關(guān)文法

1、1College of Computer Science & Technology, BUPT 4.2 上下文無(wú)關(guān)文法的變換上下文無(wú)關(guān)文法的變換 nCFG 的簡(jiǎn)化的簡(jiǎn)化n消無(wú)用符號(hào)消無(wú)用符號(hào)n消消 產(chǎn)生式產(chǎn)生式n消單產(chǎn)生式消單產(chǎn)生式n對(duì)生成式形式進(jìn)行標(biāo)準(zhǔn)化對(duì)生成式形式進(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 (后面將證明, 每個(gè)上下文無(wú)關(guān)文法都有一個(gè)C

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

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

4、非生成符號(hào)、不可達(dá)符號(hào)消去無(wú)用符號(hào)消去無(wú)用符號(hào) 消去相關(guān)產(chǎn)生式消去相關(guān)產(chǎn)生式5College of Computer Science & Technology, BUPT計(jì)算生成符號(hào)集計(jì)算生成符號(hào)集思路思路 對(duì)于對(duì)于 CFG G = (N, T, P , S )，可通過(guò)下列歸納可通過(guò)下列歸納步驟計(jì)算生成符號(hào)集合：步驟計(jì)算生成符號(hào)集合： 基礎(chǔ)基礎(chǔ) 任何終結(jié)符任何終結(jié)符 a T 都是生成符號(hào)；都是生成符號(hào)； 歸納歸納 如果有產(chǎn)生式如果有產(chǎn)生式 A ，其中其中 ( N T )* 的的每一個(gè)符號(hào)都是生成符號(hào)，則每一個(gè)符號(hào)都是生成符號(hào)，則 A 也是生成符號(hào)；也是生成符號(hào)；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é)符作為有用符號(hào)用符號(hào). 算法算法1: 找出有用非終結(jié)符找出有用非終結(jié)符 7College of Computer Sci

6、ence & Technology, BUPT 一層層向外擴(kuò)展，直至最外兩層相等為止。所得集合一層層向外擴(kuò)展，直至最外兩層相等為止。所得集合即是算法即是算法1的有用符號(hào)。的有用符號(hào)。 算法算法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計(jì)算可達(dá)符號(hào)集計(jì)算可達(dá)符號(hào)集

7、 思路思路 對(duì)于對(duì)于 CFG G = ( N, T, P , S )，可通過(guò)下列歸可通過(guò)下列歸納步驟計(jì)算可達(dá)符號(hào)集合：納步驟計(jì)算可達(dá)符號(hào)集合： 基礎(chǔ)基礎(chǔ) S 是可達(dá)符號(hào)；是可達(dá)符號(hào)； 歸納歸納 如果如果 A 是可達(dá)符號(hào)，并且有產(chǎn)生式是可達(dá)符號(hào)，并且有產(chǎn)生式 A ，其中其中 ( N T )* ，則則 中的每一個(gè)符號(hào)都是可達(dá)中的每一個(gè)符號(hào)都是可達(dá)符號(hào)；符號(hào)；9College of Computer Science & Technology, BUPT算法步驟算法步驟: (1) N 0 = S (2) N= x | AN 0 且且Ax N 0 (N為有用符號(hào)集合為有用符號(hào)集合) (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中符號(hào)的生成式組成中符號(hào)的生成式組成 (即刪去了從即刪去了從S起不可達(dá)的符號(hào)起不可達(dá)的符號(hào)).算法算法2: 找出有用符號(hào)找出有用符號(hào)(從從S可達(dá)的符號(hào)可達(dá)的符號(hào)) 10College of Computer Science & Technology, BUPT一層層外擴(kuò)一層層外擴(kuò),找出從找出從S可達(dá)的所有符號(hào)可達(dá)的所有符號(hào)(含非終結(jié)符和終含非終結(jié)符和終結(jié)符結(jié)符)算法算法2: 找出從找出從S可達(dá)的符號(hào)可達(dá)的符號(hào) （圖

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消去非生成符號(hào)及不可達(dá)符號(hào)消去非生成符號(hào)及不可達(dá)符號(hào) 例例: (書(shū)書(shū)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,可刪去文法中所有無(wú)用符號(hào)可刪去文法中所有無(wú)用符號(hào).12College of Computer Science & Technology, BUPT消去非生成符號(hào)及不可達(dá)符號(hào)消去非生成符號(hào)及不可達(dá)符號(hào)注意注意: 必須先執(zhí)行算法必須先執(zhí)行算法1,再執(zhí)行算法再執(zhí)行算法2,不能顛倒不能顛倒.否則否則,可能導(dǎo)致無(wú)用符號(hào)不會(huì)被完全刪除可能導(dǎo)致無(wú)用符號(hào)不會(huì)被完全刪除.例例:上例中上例中,若先用算法若先用算法2,得

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

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

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

14、0 C11 C2CnnP n0 且每個(gè)Ck (1kn) 均在N內(nèi) 而對(duì)于0jn, 沒(méi)有j在N內(nèi) (i也可能是終結(jié)符) 則P1應(yīng)加入 A0Y11Y22Ynn 其中Yk或是Ck或是 (即所有的可能組合) 但A不加入P116College of Computer Science & Technology, BUPT算法算法3: 生成無(wú)生成無(wú) 文法文法算法步驟（續(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)生式例例: (書(shū)書(shū)P137 例例2) G = (N, T, P, S) 其中N=S, T= a, b P: SaSbS | bSaS| 求其無(wú)文法 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 為可致空符號(hào)：為可致空符號(hào)： S A; A 0BD; B 0BC; B 1; C 1; D . 通過(guò)通過(guò)上述步驟，上述步驟，消去消去 產(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)生式的目的 可簡(jiǎn)化某些證

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

18、 )，對(duì)每個(gè)單元偶對(duì)對(duì)每個(gè)單元偶對(duì) (A，B) ，在在 G1 中加入產(chǎn)生式中加入產(chǎn)生式 A ，其中其中 B 為一個(gè)非單產(chǎn)生式；從為一個(gè)非單產(chǎn)生式；從而消去而消去 G 中的單產(chǎn)生式，中的單產(chǎn)生式，得到得到 CFG G1 = (N, T, P1, S )：算法步驟算法步驟:(1) 對(duì)每個(gè)對(duì)每個(gè)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且不是單生成式且不是單生成式, 則對(duì)于則對(duì)于BNA的所有的所有A,把把A加入到加入到P1中中(即對(duì)每個(gè)即對(duì)每個(gè)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ǎn)化的簡(jiǎn)化 小結(jié)小結(jié) 設(shè)設(shè) CFG G = (V, T, P , S )，可以通過(guò)下列步驟對(duì)可以通過(guò)下列步驟對(duì) G 進(jìn)行簡(jiǎn)化進(jìn)行簡(jiǎn)化： （1）消除消除 G 中的中的 產(chǎn)生式產(chǎn)生式； （2）消除消除 G 中的單元產(chǎn)生式；中的單元產(chǎn)生式； （3）消除消除 G 中的中的 無(wú)用符號(hào)無(wú)用符號(hào). 結(jié)論結(jié)論 設(shè)設(shè) CFG G 的語(yǔ)言至少包含一個(gè)非的語(yǔ)言至少包含一個(gè)非 的字符串，通的字符串，通 過(guò)過(guò)上述步驟上述步驟從從 G 構(gòu)造構(gòu)造 G1 ，則

21、有則有 L(G1)= L(G) - . 注意注意 以上簡(jiǎn)化步驟的次序以上簡(jiǎn)化步驟的次序.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)造無(wú)單生成式的文法構(gòu)造無(wú)單生成式的文法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對(duì)對(duì)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ù)）同理同理: 對(duì)對(duì)NA= A, B AA*B P且非單生成式且非單生成式, A NA 將將AA*B加到加到P1中中. B(S)|aP且非單生成式且非單生成式, B NA 將將A(S)|a加到加到P1中中. 同理同理: 對(duì)對(duì)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: 對(duì)對(duì)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)生的語(yǔ)言相等中生成式產(chǎn)生的語(yǔ)言相等,證明從略。證明從略。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)樹(shù)為的推導(dǎo)樹(shù)為 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即將子樹(shù)根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的第一個(gè)字符不是非終結(jié)符的第一個(gè)字符不是非終結(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消除直接左遞歸消除直接左遞歸 （例）（例）例例: (書(shū)書(shū)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消除直接左遞歸對(duì)推導(dǎo)樹(shù)的影響消除直接左遞歸對(duì)推導(dǎo)樹(shù)的影響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ì)引起死循環(huán)。會(huì)引起死循環(huán)。 對(duì)于給定的對(duì)于給定的2型文法型文法, 該文法不存在無(wú)用符號(hào)該文法不存在無(wú)用符號(hào), 無(wú)循環(huán)且是無(wú)循環(huán)且是無(wú)無(wú)生成式的文法生成式的文法, 為了消除為了消除G中可能存在的左遞歸中可能存在的左遞歸, 構(gòu)成一構(gòu)成一個(gè)等效的無(wú)左遞歸的文法個(gè)等效的無(wú)左遞歸的文法G1, 可用算法可用算法5。 算法算法5在原