《編譯原理教案-lr分析.ppt》由會員分享，可在線閱讀，更多相關《編譯原理教案-lr分析.ppt（78頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、LR分析,自下而上語法分析算法之,天馬行空官方博客： ；QQ:1318241189；QQ群：175569632,復習：移進-歸約分析,天馬行空官方博客： ；QQ:1318241189；QQ群：175569632,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進,2） #a bbcde# 移進,4） #aA bcde# 移進,6） #aA cde# 移進,7） #aAc de# 移進,9） #aAcB e# 移進,11） #S

2、 # 接受,分析符號串a(chǎn)bbcde是否GS的句子,對輸入串a(chǎn)bbcde#的移進-規(guī)約分析過程,,在步驟3中，用Ab歸約 在步驟5中，用AAb歸約 問題：何時移進？何時歸約？用哪個產(chǎn)生式歸約？,3） #ab bcde# 歸約(Ab),5） #aAb cde# 歸約(AAb),4） #aA bcde# 移進,6） #aA cde# 移進,分析：已分析過的部分在棧中的前綴不同，而且移進和歸約后棧中的狀態(tài)會發(fā)生變化 我們引入一個新的狀態(tài)棧來表示符號棧中的符號目前狀態(tài) 用LR分析表來表示不同狀態(tài)下對于各輸入符號應采取的動作,,,,步驟,符號棧,輸入符號串,動作,

3、,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,11） #S # 接受 01 acc,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb

4、 cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移進，并將狀態(tài)i進棧 ri:用第i個產(chǎn)生式歸約，同時狀態(tài)棧與符號棧退出相應個符號，根據(jù)GOTO表將相應狀態(tài)入棧,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a

5、bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,11） #S # 接受 01 acc,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # a

6、Acd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移進，并將狀態(tài)i進棧 ri:用第i個產(chǎn)生式歸約，同時狀態(tài)棧與符號棧退出相應個符號，根據(jù)GOTO表將相應狀態(tài)入棧,問題： 對于一個文法，狀態(tài)集是如何確定的？ LR分析表是如何得到的？,可歸前綴與活前綴,文法GS：(1) S aAcBe1(2) A b2(3) A Ab3(4) B d4,S aAcBe1 aAcd4e1

7、 aAb3cd4e1 ab2b3cd4e1,每次歸約句型的前部分依次為：ab2aAb3aAcd4aAcBe1,規(guī)范句型的這種前部分符號串稱為可歸前綴 我們把形成可歸前綴之前包括可歸前綴在內(nèi)的所有規(guī)范句型的前綴都稱為活前綴,,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe,活前綴（Viable Prefixes）,viable:adj capable of growing and developing capable of being put into practice : workable 定義： S A 是文法G中的一個規(guī)范推導，

8、如果符號串是的前綴，則稱是G的一個活前綴。,,LR分析需要構(gòu)造識別活前綴的有窮自動機 我們可以文法的終結(jié)符和非終結(jié)符都看成有窮自動機的輸入符號，每次把一個符號進棧看成已識別過了該符號，同時狀態(tài)進行轉(zhuǎn)換，當識別到可歸前綴時，相當于在棧中形成句柄，認為達到了識別句柄的終態(tài)。,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc d

9、e# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,11） #S # 接受 01 acc,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,,ACTION,GOTO,0,1,

10、,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,,*,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,對輸入串a(chǎn)bbcde#的LR分析過程,狀態(tài)棧,,ACTION,GOTO,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,對輸入串a(chǎn)bbcde#的LR分析過程,狀

11、態(tài)棧,,ACTION,GOTO,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,狀態(tài)棧,,ACTION,GOTO,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,,,,步驟,符號棧,輸入符

12、號串,動作,,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,狀態(tài)棧,,ACTION,GOTO,,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a

13、bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,,ACTION,GOTO,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a bbcde#

14、 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,,ACTION,GOTO,*,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進

15、 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,狀態(tài)棧,,ACTION,GOTO,*,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,

16、S,a,b,A,b,c,B,e,d,8,,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236

17、 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,狀態(tài)棧,,ACTION,GOTO,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0

18、235 S8,9） #aAcB e# 移進 02357 S9,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,狀態(tài)棧,,ACTION,GOTO,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進

19、 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7） #aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e#

20、 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,,ACTION,GOTO,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,,,,步驟,符號棧,輸入符號串,動作,,1） # abbcde# 移進 0 S2,2） #a bbcde# 移進 02 S4,4） #aA bcde# 移進 023 S6,6） #aA cde# 移進 023 S5,7）

21、#aAc de# 移進 0235 S8,9） #aAcB e# 移進 02357 S9,11） #S # 接受 01 acc,對輸入串a(chǎn)bbcde#的LR分析過程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe # 歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,,ACTION,G

22、OTO,0,1,,4,,2,3,5,7,6,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,8,,*,如何構(gòu)造識別活前綴的有限自動機,已經(jīng)有了活前綴如何構(gòu)造有限自動機? 活前綴及其可歸前綴的一般計算方法,文法GS：S S0S aAcBe1A b2A Ab3B d4,句子abbcde的可歸前綴如下：S0ab1aAb3aAcd4aAcBe1,構(gòu)造識別其活前綴及可歸前綴的有限自動機如下：,1,,0,,4,,3,,8,,7,,13,,12,,10,,18,,2,5,9,14,,6,,,17,15,16,,,11,,10,,,,,,,,,,S,a,b,a,A,b,a,A,c,d,a,A,c

23、,B,e,*,1,,*,句子識別態(tài),i,,句柄識別態(tài),1,,0,,4,,3,,8,,7,,13,,12,,10,,18,,2,5,9,14,,6,,,17,15,16,,,11,,10,,,,,,,,,,S,a,b,a,A,b,a,A,c,d,a,A,c,B,e,*,X,加上開始狀態(tài)X,確定化,,,,,,X,1,,3,,2,4,6,8,5,,9,,,,,,,,,,,S,a,b,A,b,c,B,e,d,7,,,*,,識別活前綴的確定的有限自動機,活前綴及其可歸前綴的一般計算方法,定義：文法G，AVN, LC(A)= | S A, V*, VT * 規(guī)范推導中在非終結(jié)符A左邊所有可能出現(xiàn)的符號串

24、的集合 推論：若文法G中有產(chǎn)生式BA，則有LC(A) LC(B)*,文法GS：S S0S aAcBe1A b2A Ab3B d4,由前面的定義與推論我們知： LC(S) = LC(S) = LC(S) *LC(A) = LC(S) *a LC(A) * LC(B) = LC(S) *aAc,化簡為： S = S = SA = Sa+A B = SaAc,求解方程組可得： S = S = A = a+A B = aAc,A = a|A,A = a*=a,這樣我們求出了每個非終結(jié)符在規(guī)范推導中用該非終結(jié)符的右部替換該非終結(jié)符之前，它的左部可能出現(xiàn)的所有前綴，也就是在規(guī)范歸約過程中用句柄歸約成該非終

25、結(jié)符之前不包括句柄的活前綴。,不包括句柄的活前綴 + 句柄 = ？,可歸前綴？,令 LR(0)C(A) = LC(A)* ,文法G的可歸前綴有： LR(0)C(S S) = S*S = S LR(0)C(S aAcBe) = S*aAcBe = aAcBe LR(0)C(A b) = A*b = ab LR(0)C(A Ab) = A*Ab = aAb LR(0)C(B d) = B*d = aAcd,總結(jié)：如何構(gòu)造識別文法活前綴的有限自動機？,1、根據(jù)文法算出其可歸前綴2、根據(jù)可歸前綴，構(gòu)造識別文法活前綴的不確定有限自動機3、確定化，從而構(gòu)造出識別文法活前綴的確定的有限自動機,參見課本P12

26、4的例子,LR分析器的構(gòu)造,1、構(gòu)造識別文法活前綴的確定有限自動機2、根據(jù)該自動機構(gòu)造相應的分析表(ACTION表、GOTO表),總控程序,Action/Goto表,,,,,輸入符號串,,輸出,,,狀態(tài)與符號棧,,這種方法構(gòu)造識別可歸前綴的有限自動機從理論的角度講是比較嚴格的，但實現(xiàn)起來卻很復雜 是否存在一種比較實用的方法？,由文法的產(chǎn)生式直接構(gòu)造識別活前綴和可歸前綴的有限自動機 項目（item）：在每個產(chǎn)生式的右部適當位置添加一個圓點構(gòu)成項目 例如：產(chǎn)生式S aAcBe對應有6個項目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be

27、4 S aAcB e 5 S aAcBe 有限自動機的每一個狀態(tài)由一個項目構(gòu)成,項目圓點的左部表示分析過程的某個時刻用該產(chǎn)生式歸約時句柄已識別的部分，圓點右部表示待識別的部分。 構(gòu)造識別活前綴的NFA：1、把文法的所有產(chǎn)生式的項目都引出，每個項目都為NFA的一個狀態(tài)2、確定初態(tài)、句柄識別態(tài)、句子識別態(tài)3、確定狀態(tài)之間的轉(zhuǎn)換關系*若項目i為 X X1X2...Xi-1 Xi...Xn項目j為 X X1X2...Xi-1 Xi Xi+1...Xn則從狀態(tài)i到狀態(tài)j連一條標記為Xi的箭弧*若i為X A，k為A ，則從狀態(tài)i畫標記為 的箭弧到狀態(tài)k,文法G：S EE T + E E TT in

28、t * T T int T (E),文法的項目有：1、 S E2、 S E 3、 E T + E4、 E T + E5、 E T + E6、 E T + E 7、 E T8、 E T 9、T int * T10、T int * T11、T int * T12、T int * T ,13、 T int 14、 T int 15、 T (E) 16、 T ( E)17、 T (E )18、 T (E) ,NFA for Viable Prefixes of the Example,T . (E),T (.E),T (E.),T (E).,(,E,),S E.,E . T+E,E T.+E

29、,E T+.E,E T+E.,S . E,E . T,E T.,T int.,T .int,T .int * T,T int * T.,T int *.T,T int.* T,e,e,e,e,E,e,T,e,e,e,E,+,e,int,int,*,T,e,e,e,e,e,T,e,NFA for Viable Prefixes in Detail (1),S . E,NFA for Viable Prefixes in Detail (2),S . E,NFA for Viable Prefixes in Detail (3),S E.,E . T+E,S . E,E . T,e,E,e,NFA

30、 for Viable Prefixes in Detail (4),T . (E),S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,E,e,e,e,T,NFA for Viable Prefixes in Detail (5),T . (E),S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,E,e,e,e,e,e,e,T,NFA for Viable Prefixes in Detail (6),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E

31、 T.,T .int,T .int * T,e,e,E,e,e,e,e,e,e,T,NFA for Viable Prefixes in Detail (7),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,T (E.),E,NFA for Viable Prefixes in Detail (8),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e

32、,e,T,E T.+E,T,T (E.),E,T (E).,),NFA for Viable Prefixes in Detail (9),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,NFA for Viable Prefixes in Detail (10),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e

33、,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,e,e,E T+E.,E,NFA for Viable Prefixes in Detail (11),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,e,e,E T+E.,E,T int.,int,NFA for Viable Prefixes in Detail (12),T

34、 . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,e,e,E T+E.,E,T int.,int,T int.* T,int,T int *.T,*,NFA for Viable Prefixes in Detail (13),T . (E),T (.E),(,S E.,E . T+E,S . E,E . T,E T.,T .int,T .int * T,e,e,e,e,E,e,e,e,e,e,e,

35、T,E T.+E,T,T (E.),E,T (E).,),E T+.E,+,e,e,E T+E.,E,T int.,int,T int.* T,int,T int *.T,*,根據(jù)圓點所在的位置和圓點后是終結(jié)符還是非終結(jié)符把項目分為以下幾種： 移進項目，形如 A a 待約項目，形如 A B 歸約項目，形如 A 接受項目，形如 S S ,Translation to the DFA,S . E E . T E .T + E T .(E) T .int * T T .int,S E .,E T. E T. + E,T int. * T T int.,T (. E) E .T E .T + E

36、 T .(E) T .int * T T .int,E T + E.,E T + . E E .T E .T + E T .(E) T .int * T T .int,T int * .T T .(E) T .int * T T .int,T int * T.,T (E.),T (E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,T,項目集,,構(gòu)成識別一個文法活前綴的DFA項目集（狀態(tài)）的全體稱為這個文法的LR(0)項目集規(guī)范族 NFA確定化為DFA的工作量較大，我們考慮直接構(gòu)造出項目集作為DFA的狀態(tài)，就可直接構(gòu)造DFA 通過閉包函數(shù)(CLOSURE

37、)來求DFA一個狀態(tài)的項目集,如果I是文法G的一個項目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：a)I的項目都在CLOSURE(I)中b)若A B屬于CLOSURE(I)，則每一形如B 的項目也屬于CLOSURE(I)c)重復b)直到CLOSURE(I)不再擴大 定義轉(zhuǎn)換函數(shù)如下：GOTO（I，X）= CLOSURE（J）其中：I為包含某一項目集的狀態(tài)，X為一文法符號 J=任何形如AX 的項目| A X 屬于I,圓點不在產(chǎn)生式右部最左邊的項目稱為核，唯一的例外是S S。因此用GOTO（I，X）轉(zhuǎn)換函數(shù)得到的J為轉(zhuǎn)向后狀態(tài)所含項目集的核 使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GOTO

38、(I,X))構(gòu)造文法G的LR(0)的項目集規(guī)范族，步驟如下： a)置項目S S為初態(tài)集的核，然后對核求閉包CLOSURE（S S）得到初態(tài)的項目集b)對初態(tài)集或其它所構(gòu)造的項目集應用轉(zhuǎn)換函數(shù)GOTO(I，X)= CLOSURE(J)求出新狀態(tài)J的項目集c)重復b)直到不出現(xiàn)新的項目集為止,S . E E . T E .T + E T .(E) T .int * T T .int,S E .,E T. E T. + E,T int. * T T int.,T (. E) E .T E .T + E T .(E) T .int * T T .int,E T + E.,E T + . E E .T

39、E .T + E T .(E) T .int * T T .int,T int * .T T .(E) T .int * T T .int,T int * T.,T (E.),T (E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,T,總結(jié)：構(gòu)造識別文法活前綴DFA的三種方法,一、根據(jù)形式定義求出活前綴的正規(guī)表達式，然后由此正規(guī)表達式構(gòu)造NFA再確定化為DFA 二、求出文法的所有項目，按一定規(guī)則構(gòu)造識別活前綴的NFA再確定化為DFA 三、使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GOTO(I,X))構(gòu)造文法G的LR(0)的項目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立

40、狀態(tài)之間的連接關系得到識別活前綴的DFA,LR（0）項目集規(guī)范族的項目類型分為如下四種： 1）移進項目 A a 2）待約項目 A B 3）歸約項目 A 4）接受項目 S S 一個項目集可能包含多種項目 a) 移進和歸約項目同時存在。移進-歸約沖突 b) 歸約和歸約項目同時存在。歸約-歸約沖突 LR(0)文法：若其LR(0)項目集規(guī)范族不存在移進-歸約，或歸約-歸約沖突，稱為LR(0)文法。,LR(0)分析表的構(gòu)造,LR(0)分析表相當于識別活前綴的有限自動機DAF的狀態(tài)轉(zhuǎn)換矩陣 LR(0)分析表的構(gòu)造算法 書上p130, 倒數(shù)4行， A 改為 A a LR(0)分析器的工作過程,令

41、包含S S 的項目集Ik的下標k為分析器的初態(tài) LR(0)分析表的ACTION和GOTO表的構(gòu)造步驟如下： a) 若項目A a屬于Ik，且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij ，當a為終結(jié)符時，則置ACTIONk,a為Sjb) 若項目A 屬于Ik ，則對a為任何終結(jié)符或#，置ACTIONk,a = rj ，j為產(chǎn)生式在文法G中的編號c) 若GO(Ik,A)= Ij ，則置GOTOk,A=j，其中A為非終結(jié)符，j為某一狀態(tài)號d) 若項目SS 屬于Ik ，則置ACTIONk,# = acce) 其它填上“報錯標志”,S . E E . T E .T + E T .(E) T .int * T T .i

42、nt,S E .,E T. E T. + E,T int. * T T int.,T (. E) E .T E .T + E T .(E) T .int * T T .int,E T + E.,E T + . E E .T E .T + E T .(E) T .int * T T .int,T int * .T T .(E) T .int * T T .int,T int * T.,T (E.),T (E).,E,T,(,int,int,*,),E,E,T,int,(,(,int,T,+,(,1,2,3,4,5,6,7,8,9,10,11,SLR(1)分析,大多數(shù)適用的程序設計語言的文法不能滿

43、足LR(0)文法的條件，即其規(guī)范族中會有含有沖突的項目集（狀態(tài)） 如果解決這種沖突？ 直覺：對于有沖突的狀態(tài)，向前查看一個符號，以確定采用的動作,文法G：(0) S S(1) S rD (2) D D,i(3) D i,I0:S SS rD,I2: S rDD D,iD i,I3: S rD D D ,i,I4: D i ,I5: D D,i,I1: S S ,I6: D D,i ,,,,,,,,S,r,i,D,,,i,LR(0)分析表,I3: S rD D D ,i,向前查看一個符號，看其是否是S的后跟符號（FOLLOW(S)）,若否則移進，是則歸約。,SLR(1)分析表,一個LR(0)

44、規(guī)范族中含有如下的項目集（狀態(tài)）II = X b , A , B 若有：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b = 狀態(tài)I面臨某輸入符號a1) 若a=b，則移進2) 若aFOLLOW(A), 則用產(chǎn)生式 A 進行歸約3) 若aFOLLOW(B), 則用產(chǎn)生式 B 進行歸約4) 此外，報錯 若一個文法的LR(0)分析表中所含有的動作沖突都能用上述方法解決，則稱這個文法是SLR(1)文法,“改進的”SLR(1)分析： 對所有非終結(jié)符都求出其FOLLOW集合，這樣只有歸約項目僅對面臨輸入符號包含在該歸約項目左部非終結(jié)符的FOL

45、LOW集合中，才采取用該產(chǎn)生式歸約的動作。 改進的SLR(1)分析表的ACTION表和GOTO表的構(gòu)造步驟：a) 若項目A a屬于Ik，且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij ，當a為終結(jié)符時，則置ACTIONk,a為Sjb) 若項目A 屬于Ik ，則對a為任何終結(jié)符或#，且滿足aFOLLOW(A)時，置ACTIONk,a = rj ，j為產(chǎn)生式在文法G中的編號c) 若GO(Ik,A)= Ij ，則置GOTOk,A=j，其中A為非終結(jié)符，j為某一狀態(tài)號d) 若項目SS 屬于Ik ，則置ACTIONk,# = acce) 其它填上“報錯標志”,仍有許多文法構(gòu)造的LR(0)項目集規(guī)范族存在的動作沖突不

46、能用SLR(1)方法解決,LR(1)分析,若項目集AB屬于I時，則B也屬于I 把FIRST()作為用產(chǎn)生式歸約的搜索符（稱為向前搜索符），作為用產(chǎn)生式B歸約時查看的符號集合（用以代替SLR(1)分析中的FOLLOW集），并把此搜索符號的集合也放在相應項目的后面，這種處理方法即為LR(1)方法,LR(1)項目集族的構(gòu)造：針對初始項目SS,#求閉包后再用轉(zhuǎn)換函數(shù)逐步求出整個文法的LR(1)項目集族。 1）構(gòu)造LR（1）項目集的閉包函數(shù)a)I的項目都在CLOSURE(I)中b)若A B，a屬于CLOSURE(I)， B 是文法的產(chǎn)生式，V*，bFIRST(a),則B ,b也屬于CLOSURE(I)c

47、)重復b)直到CLOSURE(I)不再擴大 2)轉(zhuǎn)換函數(shù)的構(gòu)造GOTO（I，X）= CLOSURE（J）其中：I為LR(1)的項目集，X為一文法符號 J=任何形如AX ,a的項目| A X ,a屬于I,I0: S S, # S aAd, # S bAc, # S aec, # S bed, #,文法G：(0) S S(1) S aAd (2) S bAc(3) S aec(4) S bed(5) A e,I1: S S , #,I2: S a Ad, # S a ec, # A e, d,I3: S b Ac, # S b ed, # A e, c,I4: S aA d, #,I

48、5: S ae c, # A e , d,I6: S bA c, #,I7: S be d, # A e , c,I8: S aAd , #,I9: S ae c , #,I10: S bAc , #,I11: S bed , #,查看I5 ，I7中的沖突，體會LR(1)如何解決,LR(1)分析表的構(gòu)造,1) 若項目A a,b屬于Ik，且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij ，當a為終結(jié)符時，則置ACTIONk,a為Sj 2) 若項目A ,a屬于Ik ，則對a為任何終結(jié)符或#，置ACTIONk,a = rj ，j為產(chǎn)生式在文法G中的編號 3) 若GO(Ik,A)= Ij ，則置GOTOk,A=j，

49、其中A為非終結(jié)符，j為某一狀態(tài)號 4) 若項目SS ,#屬于Ik ，則置ACTIONk,# = acc 5) 其它填上“報錯標志”,LR(1)項目集的構(gòu)造對某些同心集的分裂可能使狀態(tài)數(shù)目劇烈的增長,文法G：(0) S S(1) B aB (2) S BB(3) B b,I0: S S, # S BB, # B aB, a/b B b, a/b,I1: S S , #,I2: S B B, # B a B, # B b, #,I5: S B B , #,I6: S a B, # B aB, # B b, #,I9: B a B , #,I4: B b , a/b,I3: B a

50、B, a/b B aB, a/b B b, a/b,I8: B a B , a/b,I7: B b , #,,,,,,,,,,,,S,B,b,b,,,,B,b,b,a,a,a,a,B,B,LR(1)項目集和轉(zhuǎn)換函數(shù),分析可發(fā)現(xiàn)I3和I6 ， I4和I7 ， I8和I9分別為同心集,I3: B a B, a/b B aB, a/b B b, a/b,I6: S a B, # B aB, # B b, #,I4: B b , a/b,I7: B b , #,I8: B a B , a/b,I9: B a B , #,I3,6: S a B, a/b/# B aB, a/b/# B

51、b, a/b/#,I4,7: B b , a/b/#,I8,9: B a B , a/b/#,,合并為,,合并為,,合并為,LALR(1)分析,對LR(1)項目集規(guī)范族合并同心集，若合并同心集后不產(chǎn)生新的沖突，則為LALR(1)項目集。,合并同心集的幾點說明,同心集合并后心仍相同，只是超前搜索符集合為各同心集超前搜索符的和集 合并同心集后轉(zhuǎn)換函數(shù)自動合并 LR(1)文法合并同心集后也只可能出現(xiàn)歸約-歸約沖突，而沒有移進-歸約沖突 合并同心集后可能會推遲發(fā)現(xiàn)錯誤的時間，但錯誤出現(xiàn)的位置仍是準確的,合并同心集后,,,二義性文法在LR分析中的應用,對于某些二義文法，可以人為地給出優(yōu)先性和結(jié)合性的規(guī)定，從而可以構(gòu)造出比相應非二義性文法更優(yōu)越的LR分析器,LR(0),SLR(1),LR(1),LR(k),LALR(1),LR(0) SLR(1): 生成的LR(0)項目集如有沖突，則根據(jù)非終結(jié)符的FOLLOW集決定 LR(1)、LR(k): 項由 心與向前搜索符組成，搜索符長度為1或k LALR(1): 對LR(1)項目集規(guī)范族合并同心集,作業(yè),p152, 第6,11,18題,