第7章LR分析法(lly)3講述

1、第七章第七章 LR(left-right)分析法分析法考查重點(diǎn)：考查重點(diǎn)：vLR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)，LALR(1)LALR(1)項(xiàng)目集規(guī)范族的項(xiàng)目集規(guī)范族的構(gòu)造構(gòu)造，識(shí)別識(shí)別活前綴活前綴的的DFADFA的構(gòu)造的構(gòu)造，分析表的構(gòu)造分析表的構(gòu)造，及及輸入串的分析輸入串的分析。1.1.LR(0)LR(0)、SLR(1)SLR(1)、LR(1)LR(1)、LALR(1)LALR(1)文法及其關(guān)系和文法及其關(guān)系和區(qū)別區(qū)別文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c de步驟步驟符號(hào)棧符號(hào)棧輸入符號(hào)串輸入符號(hào)串

2、動(dòng)作動(dòng)作 1） # abbcde# 移進(jìn)移進(jìn) 2） #a bbcde# 移進(jìn)移進(jìn)A 3） #ab bcde# 歸約歸約(Ab) 4） #aA bcde# 移進(jìn)移進(jìn)A 5） #aAb cde# 歸約歸約(AAb) 6） #aA cde# 移進(jìn)移進(jìn) 7） #aAc de# 移進(jìn)移進(jìn)B 8） # aAcd e# 歸約歸約(Bd) 9） #aAcB e# 移進(jìn)移進(jìn)11） #S # 接受接受S10） #aAcBe # 歸約歸約(SaAcBe)分析符號(hào)串a(chǎn)bbcde是否GS的句子對(duì)輸入串a(chǎn)bbcde#的移進(jìn)-規(guī)約分析過程SaAcBe aAcde aAbcde abbcdev在步驟在步驟3中，用中，用Ab歸

3、約歸約v在步驟在步驟5中，用中，用AAb歸約歸約v問題：何時(shí)移進(jìn)？何時(shí)歸約？用哪個(gè)產(chǎn)生式問題：何時(shí)移進(jìn)？何時(shí)歸約？用哪個(gè)產(chǎn)生式歸約（如何找當(dāng)前句柄歸約）？歸約（如何找當(dāng)前句柄歸約）？ 3） #ab bcde# 歸約歸約(Ab) 5） #aAb cde# 歸約歸約(AAb) 4） #aA bcde# 移進(jìn)移進(jìn) 6） #aA cde# 移進(jìn)移進(jìn)分析：已分析過的部分在棧中的分析：已分析過的部分在棧中的前綴前綴不同，而且移進(jìn)和歸不同，而且移進(jìn)和歸約后棧中的狀態(tài)會(huì)發(fā)生變化約后棧中的狀態(tài)會(huì)發(fā)生變化我們引入一個(gè)新的我們引入一個(gè)新的狀態(tài)棧狀態(tài)棧來表示符號(hào)棧中的符號(hào)目前狀態(tài)來表示符號(hào)棧中的符號(hào)目前狀態(tài)用用LRL

4、R分析表分析表來表示不同狀態(tài)下對(duì)于各輸入符號(hào)應(yīng)采取的動(dòng)來表示不同狀態(tài)下對(duì)于各輸入符號(hào)應(yīng)采取的動(dòng)作作LR 分析器工作示意圖分析器工作示意圖步驟步驟 符號(hào)棧符號(hào)棧 輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # abbcde# 移進(jìn)移進(jìn) 0 S2 2） #a bbcde# 移進(jìn)移進(jìn) 02 S4 4） #aA bcde# 移進(jìn)移進(jìn) 023 S6 6） #aA cde# 移進(jìn)移進(jìn) 023 S5 7） #aAc de# 移進(jìn)移進(jìn) 0235 S8 9） #aAcB e# 移進(jìn)移進(jìn) 02357 S911） #S # 接受接受 01 acc對(duì)輸入串a(chǎn)bbcde#的LR分析過程 3） #ab bcde# 歸約歸約(Ab

5、) 024 r2 3 5） #aAb cde# 歸約歸約(AAb) 0236 r3 3 8） # aAcd e# 歸約歸約(Bd) 02358 r4 710） #aAcBe # 歸約歸約(SaAcBe) 023579 r1 1狀態(tài)棧狀態(tài)棧ACTIONGOTO文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dSi:移進(jìn)，并將狀態(tài)移進(jìn)，并將狀態(tài)i進(jìn)棧進(jìn)棧ri:用第用第i個(gè)產(chǎn)生式歸約，同時(shí)狀個(gè)產(chǎn)生式歸約，同時(shí)狀態(tài)棧與符號(hào)棧退出相應(yīng)個(gè)符號(hào)，態(tài)棧與符號(hào)棧退出相應(yīng)個(gè)符號(hào)，根據(jù)根據(jù)GOTO表將相應(yīng)狀態(tài)入棧表將相應(yīng)狀態(tài)入棧S8S9問題：v對(duì)于一個(gè)文法，狀態(tài)集是如何確定的？vLR分

6、析表是如何得到的？答案答案：需要構(gòu)造識(shí)別：需要構(gòu)造識(shí)別可歸前綴可歸前綴的的有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)可歸前綴與活前綴文法文法GS：(1) S aAcBe1(2) A b2(3) A Ab3(4) B d4S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1每次歸約句型的每次歸約句型的前部分前部分依次為：依次為：ab2 /?aAb3aAcd4aAcBe1規(guī)范句型規(guī)范句型的這種前部分符號(hào)串稱為的這種前部分符號(hào)串稱為可歸前綴可歸前綴我們把形成可歸前綴之前包括可歸前綴在內(nèi)我們把形成可歸前綴之前包括可歸前綴在內(nèi)的所有規(guī)范句型的前綴都稱為的所有規(guī)范句型的前綴都稱為活前綴活前綴 ,a,ab

7、,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBe活前綴活前綴v定義：定義：S A 是文法是文法G中的一個(gè)中的一個(gè)規(guī)范推導(dǎo)規(guī)范推導(dǎo)，如果，如果符號(hào)串符號(hào)串是是的前綴，則稱的前綴，則稱是是G的一個(gè)的一個(gè)活前綴活前綴。（在在當(dāng)前句型當(dāng)前句型中，中，不不包含包含句柄句柄右邊右邊的前綴的前綴）R*RvLR分析需要構(gòu)造識(shí)別分析需要構(gòu)造識(shí)別可歸前綴可歸前綴的的有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)把文法的把文法的終結(jié)符和非終結(jié)符終結(jié)符和非終結(jié)符都看成有窮自動(dòng)機(jī)輸入都看成有窮自動(dòng)機(jī)輸入符號(hào)，每次把一個(gè)符號(hào)進(jìn)?？闯梢炎R(shí)別過了該符符號(hào)，每次把一個(gè)符號(hào)進(jìn)?？闯梢炎R(shí)別過了該符號(hào)，同時(shí)狀態(tài)進(jìn)行轉(zhuǎn)

8、換，當(dāng)識(shí)別到可歸前綴（棧號(hào)，同時(shí)狀態(tài)進(jìn)行轉(zhuǎn)換，當(dāng)識(shí)別到可歸前綴（棧中形成句柄）時(shí)，認(rèn)為達(dá)到了識(shí)別句柄的終態(tài)。中形成句柄）時(shí)，認(rèn)為達(dá)到了識(shí)別句柄的終態(tài)。注注：在在符號(hào)棧符號(hào)棧中，中，始終存放當(dāng)前句型的活前綴始終存放當(dāng)前句型的活前綴8014235769SabAbcBed*S8S9句子句子abbcde的的可可歸前綴歸前綴：ab2aAb3aAcd4aAcBe1文法文法GS：(1) S aAcBe1(2) A b2(3) A Ab3(4) B d41句子識(shí)別態(tài)i句柄識(shí)別態(tài)*如何構(gòu)造識(shí)別如何構(gòu)造識(shí)別可歸可歸前綴的有限自動(dòng)機(jī)前綴的有限自動(dòng)機(jī)v已經(jīng)有了可歸前綴如何構(gòu)造有限自動(dòng)機(jī)?v活前綴及其可歸前綴的一般計(jì)算

9、方法文法文法GS：S S0S aAcBe1A b2A Ab3B d4句子句子abbcdeabbcde的可歸前綴（的可歸前綴（正規(guī)式正規(guī)式）如下：）如下：S0S0ab2ab2aAb3aAb3aAcd4aAcd4aAcBe1aAcBe1構(gòu)造識(shí)別其活前綴及可歸前綴的有限自動(dòng)機(jī)如下構(gòu)造識(shí)別其活前綴及可歸前綴的有限自動(dòng)機(jī)如下：104387131210182591461715161110SabaAbaAcdaAcBe*1句子識(shí)別態(tài)i句柄識(shí)別態(tài)104387131210182591461715161110SabaAbaAcdaAcBe*X加上開始狀態(tài)X確定化 X13246859SabAbcBed7*識(shí)別活前綴

10、的確定的有限自動(dòng)機(jī)識(shí)別活前綴的確定的有限自動(dòng)機(jī)活前綴及其可歸前綴的一般計(jì)算方法活前綴及其可歸前綴的一般計(jì)算方法定義：文法定義：文法G，A VN,LC(A)= | S A , V*, VT *規(guī)范推導(dǎo)規(guī)范推導(dǎo)中在中在非終結(jié)符非終結(jié)符A左邊所有可能出左邊所有可能出現(xiàn)的符號(hào)串的集合現(xiàn)的符號(hào)串的集合(不包括句柄的活前綴不包括句柄的活前綴? )推論：若文法推論：若文法G中有產(chǎn)生式中有產(chǎn)生式B A ，則有則有LC(A) LC(B) R*文法文法GS：S S0S aAcBe1A b2A Ab3B d4由前面定義與推論知：LC(S) = LC(S) = LC(S) * LC(A) = LC(S) *a LC(

11、A) * LC(B) = LC(S) *aAc化簡(jiǎn)為：S = S = SA = Sa+A B = SaAc求解方程組可得：S = S = A = a+A B = aAcA = a|AA = a *=a這樣我們求出了每個(gè)這樣我們求出了每個(gè)非終結(jié)符非終結(jié)符在規(guī)范推導(dǎo)中用該非終結(jié)符在規(guī)范推導(dǎo)中用該非終結(jié)符的右部替換該非終結(jié)符之前，它的左部可能出現(xiàn)的的右部替換該非終結(jié)符之前，它的左部可能出現(xiàn)的所有前所有前綴綴，也就是在規(guī)范歸約過程中用句柄歸約成該非終結(jié)符之，也就是在規(guī)范歸約過程中用句柄歸約成該非終結(jié)符之前前不包括句柄的活前綴不包括句柄的活前綴。推論推論：若文法若文法G中有產(chǎn)生中有產(chǎn)生式式B A ，則有

12、則有LC(A) LC(B) 不包括句柄的活前綴不包括句柄的活前綴 + 句柄句柄 = ？ 可歸前綴？可歸前綴？ 令令 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)造識(shí)別文法活前綴的有限自動(dòng)機(jī)？總結(jié)：如何構(gòu)造識(shí)別文法活前綴的有限自動(dòng)機(jī)？ 1、根據(jù)文法算出其可歸前綴、根據(jù)文法算出其可歸前綴2、根據(jù)可

13、歸前綴，構(gòu)造識(shí)別文法活前綴的不確定有限自動(dòng)機(jī)、根據(jù)可歸前綴，構(gòu)造識(shí)別文法活前綴的不確定有限自動(dòng)機(jī)3、確定化，從而構(gòu)造出識(shí)別文法活前綴的確定的有限自動(dòng)機(jī)、確定化，從而構(gòu)造出識(shí)別文法活前綴的確定的有限自動(dòng)機(jī)參見課本參見課本P124的例子的例子LR分析器的構(gòu)造分析器的構(gòu)造 1、構(gòu)造識(shí)別文法活前綴的確定有限自動(dòng)機(jī)、構(gòu)造識(shí)別文法活前綴的確定有限自動(dòng)機(jī)根據(jù)文法算出其可歸前綴根據(jù)文法算出其可歸前綴根據(jù)可歸前綴，構(gòu)造識(shí)別文法活前綴的不確定有限自動(dòng)機(jī)根據(jù)可歸前綴，構(gòu)造識(shí)別文法活前綴的不確定有限自動(dòng)機(jī)確定化，從而構(gòu)造出識(shí)別文法活前綴的確定的有限自動(dòng)機(jī)確定化，從而構(gòu)造出識(shí)別文法活前綴的確定的有限自動(dòng)機(jī)2、根據(jù)該自動(dòng)

14、機(jī)構(gòu)造相應(yīng)的分析表、根據(jù)該自動(dòng)機(jī)構(gòu)造相應(yīng)的分析表(ACTION表、表、GOTO表表)輸出輸出狀態(tài)與符號(hào)棧狀態(tài)與符號(hào)?？偪爻绦蚩偪爻绦駻ction/Goto表表輸入符號(hào)串輸入符號(hào)串這種方法構(gòu)造識(shí)別可歸前綴的有限自動(dòng)機(jī)從理論的角度講是比較嚴(yán)格的，但實(shí)現(xiàn)起來卻很復(fù)雜!是否存在一種比較實(shí)用的方法？KISS準(zhǔn)則！準(zhǔn)則！項(xiàng)目（項(xiàng)目（item）：）：在每個(gè)產(chǎn)生式的右部適當(dāng)位置添加一個(gè)圓點(diǎn)構(gòu)成項(xiàng)目例如：產(chǎn)生式S aAcBe對(duì)應(yīng)有6個(gè)項(xiàng)目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 項(xiàng)目圓點(diǎn)的左部表示分析過程的某個(gè)時(shí)刻用該產(chǎn)生式

15、歸約時(shí)句柄已識(shí)別的部分句柄已識(shí)別的部分，圓點(diǎn)右部表示待待識(shí)別的部分識(shí)別的部分?？债a(chǎn)生式A的項(xiàng)目只有一個(gè)：A由文法的產(chǎn)生式直接構(gòu)造識(shí)別活由文法的產(chǎn)生式直接構(gòu)造識(shí)別活前綴和可歸前綴的有限自動(dòng)機(jī)前綴和可歸前綴的有限自動(dòng)機(jī)l有限自動(dòng)機(jī)NFA的每一個(gè)狀態(tài)由一個(gè)項(xiàng)目構(gòu)成構(gòu)造識(shí)別活前綴的構(gòu)造識(shí)別活前綴的NFA：1 1、把文法的所有產(chǎn)生式的項(xiàng)目都引出，把文法的所有產(chǎn)生式的項(xiàng)目都引出，每個(gè)項(xiàng)目都每個(gè)項(xiàng)目都為為NFANFA的一個(gè)狀態(tài)的一個(gè)狀態(tài)2 2、確定、確定初態(tài)初態(tài)、句柄識(shí)別態(tài)句柄識(shí)別態(tài)、句子識(shí)別態(tài)句子識(shí)別態(tài)3 3、確定、確定狀態(tài)之間的轉(zhuǎn)換關(guān)系狀態(tài)之間的轉(zhuǎn)換關(guān)系若項(xiàng)目若項(xiàng)目i i為為 X X1X2.Xi-1 X

16、 X1X2.Xi-1 XiXi.Xn.Xn項(xiàng)目項(xiàng)目j j為為 X X1X2.Xi-1 X X1X2.Xi-1 XiXi Xi+1.Xn Xi+1.Xn則從狀態(tài)則從狀態(tài)i i到狀態(tài)到狀態(tài)j j連一條標(biāo)記為連一條標(biāo)記為XiXi的箭弧的箭弧若若i i為為X X A A ，k k為為A A ，則從狀態(tài)則從狀態(tài)i i畫標(biāo)畫標(biāo)記為記為 的箭弧到狀態(tài)的箭弧到狀態(tài)k k文法文法G：S EE T + E E TT int * T T int T (E)文法的項(xiàng)目有：文法的項(xiàng)目有：1、 S E2、 S E 3、 E T + E4、 E T + E5、 E T + E6、 E T + E 7、 E T8、 E T

17、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) 注意注意：初態(tài)初態(tài)句柄識(shí)別態(tài)句柄識(shí)別態(tài) 句子識(shí)別態(tài)句子識(shí)別態(tài)注意注意：拓廣文法引入的意義。（確保初態(tài)唯一）拓廣文法引入的意義。（確保初態(tài)唯一）NFA for Viable Prefixes of the ExampleT . (E)T (.E)T (E.)T (E).(E)S E.E . T+EE T.+EE T+.EE T+E.S . EE . TE T.T int.T .int

18、T .int * TT int * T.T int *.TT int.* TETE+intint*TTNFA for Viable Prefixes in Detail (1)S . ENFA for Viable Prefixes in Detail (2)S . ES E.EE . TE . T+ENFA for Viable Prefixes in Detail (3)S E.E . T+ES . EE . TT .int * TET . (E)T .intE T.TNFA for Viable Prefixes in Detail (4)T . (E)S E.E . T+ES . EE

19、 . TE T.T .intT .int * TEE T.+ETTNFA for Viable Prefixes in Detail (5)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETNFA for Viable Prefixes in Detail (6)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ENFA for Viable Prefixes in Detail (7)T . (E)T (.E)(S E.E .

20、 T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)NFA for Viable Prefixes in Detail (8)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+NFA for Viable Prefixes in Detail (9)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E

21、+E T+E.ENFA for Viable Prefixes in Detail (10)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET NFA for Viable Prefixes in Detail (11)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET T int.* TintNF

22、A for Viable Prefixes in Detail (12)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET T int.* TintT int *.T*NFA for Viable Prefixes in Detail (13)T . (E)T (.E)(S E.E . T+ES . EE . TE T.T .intT .int * TETE T.+ETT (E.)ET (E).)E T+.E+E T+E.ET T

23、int.* TintT int *.T*T int * T.T根據(jù)圓點(diǎn)所在的位置圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終圓點(diǎn)后是終結(jié)符還是非終結(jié)符結(jié)符把項(xiàng)目分為以下幾種：移進(jìn)移進(jìn)項(xiàng)目，形如 A a 待約待約項(xiàng)目，形如 A B 歸約歸約項(xiàng)目，形如 A （句柄識(shí)別態(tài)）（句柄識(shí)別態(tài)）接受接受項(xiàng)目，形如 S S （句子識(shí)別態(tài)句子識(shí)別態(tài)）初態(tài)初態(tài)項(xiàng)目，形如 S S （初態(tài)）初態(tài)）Translation to the DFAS . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. + ET int. * TT int.T (. E)E .TE .T + ET

24、 .(E)T .int * TT .intE T + E.E T + . EE .TE .T + ET .(E)T .int * TT .intT int * .TT .(E)T .int * TT .intT int * T.T (E.)T (E).ET(intint*)EETint (intT+(T項(xiàng)目集項(xiàng)目集NFANFA確定化為確定化為DFADFA的工作量較大，我們考慮直接構(gòu)的工作量較大，我們考慮直接構(gòu)造出項(xiàng)目集作為造出項(xiàng)目集作為DFADFA的狀態(tài)，就可直接構(gòu)造的狀態(tài)，就可直接構(gòu)造DFADFA構(gòu)成識(shí)別一個(gè)文法活前綴的構(gòu)成識(shí)別一個(gè)文法活前綴的DFA項(xiàng)目集（狀態(tài)）項(xiàng)目集（狀態(tài)）的全體稱為這個(gè)

25、文法的的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族.如果I是文法G的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包CLOSURE(I)如下：a)I的項(xiàng)目都在CLOSURE(I)中b)若A B 屬于CLOSURE(I)，則每一形如B 的項(xiàng)目也屬于CLOSURE(I)c)重復(fù)b)直到CLOSURE(I)不再擴(kuò)大閉包函數(shù)閉包函數(shù)(CLOSURE)來求來求DFA一個(gè)狀態(tài)的項(xiàng)目集一個(gè)狀態(tài)的項(xiàng)目集例例文法文法GS：(1) S aAcBe(2) A b(3) A Bb(4) B d求求若若I的項(xiàng)目集的項(xiàng)目集=S .aAcBe，則，則CLOSURE(I)？若若I的項(xiàng)目集的項(xiàng)目集=S a.AcBe呢？呢？v定義轉(zhuǎn)換函

26、數(shù)如下：定義轉(zhuǎn)換函數(shù)如下：GOTO（I，X）= CLOSURE（J）其中：其中：I為包含某一項(xiàng)目集的狀態(tài)，為包含某一項(xiàng)目集的狀態(tài)，X為一文法符號(hào)為一文法符號(hào) J=任何形如任何形如A X 的項(xiàng)目的項(xiàng)目| A X 屬于屬于Iv圓點(diǎn)不在產(chǎn)生式右部圓點(diǎn)不在產(chǎn)生式右部最左邊最左邊的項(xiàng)目稱為的項(xiàng)目稱為核核，唯一，唯一的例外是的例外是S S。思考思考：GOTO（I，X）轉(zhuǎn)換函數(shù)得到的轉(zhuǎn)換函數(shù)得到的J是否一定為是否一定為核核？例例文法文法GS：(1) S aAcBe(2) A b(3) A Bb(4) B d求求若若I的項(xiàng)目集的項(xiàng)目集=S .aAcBe，則，則GOTO（I，a）=？若若I的項(xiàng)目集的項(xiàng)目集=S

27、a.AcBe，GOTO（I，A）呢？呢？使用閉包函數(shù)（使用閉包函數(shù)（CLOSURECLOSURE）和轉(zhuǎn)向函數(shù)和轉(zhuǎn)向函數(shù)( (GOTO(I,X)GOTO(I,X)構(gòu)造文法構(gòu)造文法GG的的LR(0)LR(0)的項(xiàng)目集規(guī)范族的項(xiàng)目集規(guī)范族，步驟如下，步驟如下：c)重復(fù)重復(fù)b)直到不出現(xiàn)新的項(xiàng)目集為止直到不出現(xiàn)新的項(xiàng)目集為止b)對(duì)初態(tài)集或其它所構(gòu)造的項(xiàng)目集應(yīng)用轉(zhuǎn)換函數(shù)對(duì)初態(tài)集或其它所構(gòu)造的項(xiàng)目集應(yīng)用轉(zhuǎn)換函數(shù)GOTO(I，X)= CLOSURE(J)求出求出新狀態(tài)新狀態(tài)J的項(xiàng)目集的項(xiàng)目集a)置項(xiàng)目置項(xiàng)目S S為初態(tài)集的核，然后對(duì)核求閉包為初態(tài)集的核，然后對(duì)核求閉包CLOSURE（S S）得到得到初態(tài)的項(xiàng)

28、目集初態(tài)的項(xiàng)目集舉例舉例S . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. + ET int. * TT int.T (. E)E .TE .T + ET .(E)T .int * TT .intE T + E.E T + . EE .TE .T + ET .(E)T .int * TT .intT int * .TT .(E)T .int * TT .intT int * T.T (E.)T (E).ET(intint*)EETint (intT+(T總結(jié)：構(gòu)造識(shí)別文法活前綴DFA的三種方法一、根據(jù)形式定義求出活前綴的正規(guī)表達(dá)式，一、根

29、據(jù)形式定義求出活前綴的正規(guī)表達(dá)式，然后由此正規(guī)表達(dá)式構(gòu)造然后由此正規(guī)表達(dá)式構(gòu)造NFANFA再確定化為再確定化為DFADFA二、求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)二、求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)別活前綴的別活前綴的NFANFA再確定化為再確定化為DFADFA三、使用閉包函數(shù)（三、使用閉包函數(shù)（CLOSURECLOSURE）和轉(zhuǎn)向函數(shù)和轉(zhuǎn)向函數(shù)( (GOTO(I,X)GOTO(I,X)構(gòu)造文法構(gòu)造文法G G的的LR(0)LR(0)的的項(xiàng)目集規(guī)項(xiàng)目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識(shí)別活前綴的系得到識(shí)別活前綴的DFADFALRLR（0 0

30、）項(xiàng)目集規(guī)范族的項(xiàng)目類型分為如下四種：項(xiàng)目集規(guī)范族的項(xiàng)目類型分為如下四種：1 1）移進(jìn)項(xiàng)目）移進(jìn)項(xiàng)目 A a 2 2）待約項(xiàng)目待約項(xiàng)目 A B 3 3）歸約項(xiàng)目歸約項(xiàng)目 A 4 4）接受項(xiàng)目接受項(xiàng)目 S S 一個(gè)項(xiàng)目集可能包含多種項(xiàng)目一個(gè)項(xiàng)目集可能包含多種項(xiàng)目a) 移進(jìn)和歸約項(xiàng)目同時(shí)存在。移進(jìn)和歸約項(xiàng)目同時(shí)存在。移進(jìn)移進(jìn)-歸約沖突歸約沖突b) 歸約和歸約項(xiàng)目同時(shí)存在。歸約和歸約項(xiàng)目同時(shí)存在。歸約歸約-歸約沖突歸約沖突LR(0)文法：LR(0)文法：若其文法：若其LR(0)項(xiàng)目集規(guī)范族不存在項(xiàng)目集規(guī)范族不存在移進(jìn)移進(jìn)-歸約，或歸約歸約，或歸約-歸約沖突，稱為歸約沖突，稱為LR(0)文法文法。LR

31、(0)分析表的構(gòu)造分析表的構(gòu)造vLR(0)分析表相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)DFA的狀態(tài)轉(zhuǎn)換矩陣vLR(0)分析表的構(gòu)造算法(書上p131)vLR(0)分析器的工作過程(書上p132)令包含令包含S S 的項(xiàng)目集的項(xiàng)目集Ik的下標(biāo)的下標(biāo)k為分析器的初態(tài)為分析器的初態(tài)LR(0)分析表的分析表的ACTION和和GOTO表的構(gòu)造步驟：表的構(gòu)造步驟：e) 其它填上其它填上“報(bào)錯(cuò)標(biāo)志報(bào)錯(cuò)標(biāo)志”d) 若項(xiàng)目若項(xiàng)目SS 屬于屬于Ik ，則置則置ACTIONk,# = accc) 若若GOTO (Ik,A)= Ij ，則置則置GOTOk,A=j，其中其中A為非為非終結(jié)符，終結(jié)符，j為某一狀態(tài)號(hào)為某一狀態(tài)號(hào)b)

32、 若項(xiàng)目若項(xiàng)目A 屬于屬于Ik ，則對(duì)則對(duì)a為為任何終結(jié)符或任何終結(jié)符或#，置置ACTIONk,a = rj ，j為產(chǎn)生式在文法為產(chǎn)生式在文法G中的編號(hào)中的編號(hào)a) 若項(xiàng)目若項(xiàng)目A a 屬于屬于Ik，且轉(zhuǎn)換函數(shù)且轉(zhuǎn)換函數(shù)GOTO(Ik,a)= Ij ，當(dāng)當(dāng) a為終結(jié)符時(shí)，則置為終結(jié)符時(shí)，則置ACTIONk,a為為SjS . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. + ET int. * TT int.T (. E)E .TE .T + ET .(E)T .int * TT .intE T + E.E T + . EE .TE .T +

33、 ET .(E)T .int * TT .intT int * .TT .(E)T .int * TT .intT int * T.T (E.)T (E).ET(intint*)EETint(intT+(1234567891011SLR(1)分析分析v大多數(shù)適用的程序設(shè)計(jì)語言的文法不能滿足LR(0)文法的條件，即其規(guī)范族中會(huì)有含有沖突的項(xiàng)目集（狀態(tài)）v如果解決這種沖突？v直覺：對(duì)于有沖突的狀態(tài)，向前查看一個(gè)符號(hào)，以確定采用的動(dòng)作文法文法G：(0) S S(1) S rD (2) D D,i(3) D iLR(0)LR(0)分析表分析表思考思考: S,存在此句型？存在此句型？思考思考:1 1）為

34、什么引入）為什么引入FOLLOWFOLLOW2 2）I I3 3中沖突如何解決的？中沖突如何解決的？3 3）若有）若有S S S,rS,r 如何如何 ? ?一個(gè)LR(0)規(guī)范族中含有如下的項(xiàng)目集（狀態(tài)）IkIk = X b , A , B 若一個(gè)文法的LR(0)分析表中所含有的動(dòng)作沖突都能用上述方法解決，則稱這個(gè)文法是SLR(1)文法文法,所構(gòu)造的分析表為SLR(1)分析表分析表，使用SLR(1)分析表的分析器為SLR(1)分析器分析器。狀態(tài)狀態(tài)k k面臨某輸入符號(hào)面臨某輸入符號(hào)x x1) 1) 若若x x=b=b，則移進(jìn)則移進(jìn)2) 2) 若若x x FOLLOW(A), FOLLOW(A),

35、 則用產(chǎn)生式則用產(chǎn)生式 A A 進(jìn)行歸約進(jìn)行歸約3 3) ) 若若x x FOLLOW(B), FOLLOW(B), 則用產(chǎn)生式則用產(chǎn)生式 B B 進(jìn)行歸約進(jìn)行歸約4) 4) 此外，報(bào)錯(cuò)此外，報(bào)錯(cuò)若有：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b = “改進(jìn)的改進(jìn)的”SLR(1)分析：分析：對(duì)所有所有非終結(jié)符都求出其FOLLOW集合，這樣只有歸約項(xiàng)目歸約項(xiàng)目?jī)H對(duì)面臨輸入符號(hào)包含在該歸約項(xiàng)目左部非終結(jié)符的FOLLOW集合中，才采取用該產(chǎn)生式歸約的動(dòng)作。FOLLOW(SFOLLOW(S）= # = # SLR(1)SLR(1)分析表分析表文法文法G

36、：(0) S S(1) S rD (2) D D,i(3) D iFOLLOW(DFOLLOW(D）= #= #， LR(0)LR(0)分析表分析表1) 若項(xiàng)目A a 屬于Ik，且轉(zhuǎn)換函數(shù)GOTO(Ik,a)= Ij ，當(dāng)a為終結(jié)符時(shí)，則置ACTIONk,a為Sj2) 若項(xiàng)目A 屬于Ik ，則對(duì)a FOLLOW(A)時(shí)，置ACTIONk,a = rj ，j為產(chǎn)生式在文法G中的編號(hào)3) 若GOTO (Ik,A)= Ij ，則置GOTOk,A=j，其中A為非終結(jié)符，j為某一狀態(tài)號(hào)4) 若項(xiàng)目SS 屬于Ik ，則置ACTIONk,# = acc5) 其它填上“報(bào)錯(cuò)標(biāo)志”改進(jìn)的改進(jìn)的SLR(1)分析表

37、的分析表的ACTION表和表和GOTO表的構(gòu)造步驟：表的構(gòu)造步驟：v仍有許多文法構(gòu)造的仍有許多文法構(gòu)造的LR(0)LR(0)項(xiàng)目集規(guī)范族存在項(xiàng)目集規(guī)范族存在的動(dòng)作沖突不能用的動(dòng)作沖突不能用SLR(1)SLR(1)方法解決方法解決LR(1)分析分析v若項(xiàng)目集若項(xiàng)目集 A A B B 屬于屬于I I時(shí)，則時(shí)，則 B B 也屬于也屬于I Iv把把FIRST(FIRST( ) )作為用產(chǎn)生式歸約的搜索符（稱為作為用產(chǎn)生式歸約的搜索符（稱為向前搜向前搜索符索符），作為用產(chǎn)生式），作為用產(chǎn)生式B B 歸約時(shí)查看的符號(hào)集合（用歸約時(shí)查看的符號(hào)集合（用以代替以代替SLR(1)SLR(1)分析中的分析中的FOL

38、LOWFOLLOW（B B）集），并把此集），并把此搜索搜索符號(hào)的集合也放在相應(yīng)項(xiàng)目的后面符號(hào)的集合也放在相應(yīng)項(xiàng)目的后面，這種處理方法即為，這種處理方法即為LR(1)LR(1)方法方法說明說明：為什么引入為什么引入FIRST(FIRST( ) )？FIRST(FIRST( ) )與與FOLLOWFOLLOW（B B）的關(guān)系）的關(guān)系LR(1)LR(1)項(xiàng)目項(xiàng)目與與LR(0)LR(0)項(xiàng)目的不同？項(xiàng)目的不同？ 心，展望字符集心，展望字符集? ? 思考思考：1 1） S S S S， ? ? 2 2）若）若 A A B B ，a a ，則，則 A A B B ，？ 3 3）若）若 A A BbBb，

39、a a ，則，則 B B ，？ 4 4）若）若 A A B B，a a ，則，則 B B ，？ 5 5）若）若 A A B B ，a a ，則，則 B B ，？ LR(1)項(xiàng)目集族的構(gòu)造：項(xiàng)目集族的構(gòu)造：(1)針對(duì)初始項(xiàng)目針對(duì)初始項(xiàng)目SS,#求閉包求閉包(2)再用轉(zhuǎn)換函數(shù)逐步求出整個(gè)文法的再用轉(zhuǎn)換函數(shù)逐步求出整個(gè)文法的LR(1)項(xiàng)目集族。項(xiàng)目集族。構(gòu)造構(gòu)造LR（1）項(xiàng)目集的項(xiàng)目集的閉包函數(shù)閉包函數(shù)a)Ia)I的項(xiàng)目都在的項(xiàng)目都在CLOSURE(I)CLOSURE(I)中中b)b)若若AA B B ，aa屬于屬于CLOSURE(I)CLOSURE(I)， B B 是文法的產(chǎn)生是文法的產(chǎn)生式，式，

40、 V V* *，b b FIRST(FIRST( a),a),則則BB ,b,b也屬于也屬于CLOSURE(I)CLOSURE(I)c)c)重復(fù)重復(fù)b)b)直到直到CLOSURE(I)CLOSURE(I)不再擴(kuò)大不再擴(kuò)大轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)的構(gòu)造的構(gòu)造 GOTOGOTO（I I，X X）= CLOSURE= CLOSURE（J J） 其中：其中：I I為為LR(1)LR(1)的項(xiàng)目集的項(xiàng)目集，X X為一文法符號(hào)為一文法符號(hào) J=J=任何形如任何形如AA X X , ,a a 的項(xiàng)目的項(xiàng)目| | AA X X ,a,a 屬于屬于II文法文法G：(0) S S (1) S aAd (2) S bAc

41、(3) S aec (4) S bed (5) A eI0=S S, #,S aAd, #,S bAc, #,S aec, #,S bed, #I1= GOTO(I I0 0,S) =S S , #I2 = GOTO(I I0,a) =S a Ad, #,S a ec, #,A e, dI3 = GOTO(I I0,b)=S b Ac, #,S b ed, #,A e, cI4 = GOTO(I I2,A)= S aA d, #I5 = GOTO(I2,e)= S ae c, #,A e , dI6 = GOTO(I3,A)=S bA c, #I7 = GOTO(I3,A)=S be d, #

42、,A e , cI8 = GOTO(I4,d)=S aAd , #I9 = GOTO(I5,c)=S ae c , #I10 = GOTO(I6,c)= S bAc , #I11 = GOTO(I7,d)=S bed , #查看查看I I5 5 ，I I7 7中的沖突，中的沖突，體會(huì)體會(huì)LR(1)LR(1)如何解決？如何解決？LR(1)項(xiàng)目集族項(xiàng)目集族=?構(gòu)造構(gòu)造LR(0)分析表分析表構(gòu)造構(gòu)造SLR(1)分析表分析表構(gòu)造構(gòu)造LR(1)分析表分析表LR(1)分析表的構(gòu)造1) 若項(xiàng)目若項(xiàng)目A a ,b屬于屬于Ik，且轉(zhuǎn)換函數(shù)且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij ，當(dāng)當(dāng)a為終結(jié)符時(shí)，則置為終結(jié)符時(shí)，則

43、置ACTIONk,a為為Sj2) 若項(xiàng)目若項(xiàng)目A ,a屬于屬于Ik ，則則置置ACTIONk,a = rj ，j為產(chǎn)生式在文法為產(chǎn)生式在文法G中的編號(hào)中的編號(hào)3) 若若GO(Ik,A)= Ij ，則置則置GOTOk,A=j，其中其中A為為非終結(jié)符，非終結(jié)符，j為某一狀態(tài)號(hào)為某一狀態(tài)號(hào)4) 若項(xiàng)目若項(xiàng)目SS ,#屬于屬于Ik ，則置則置ACTIONk,# = acc5) 其它填上其它填上“報(bào)錯(cuò)標(biāo)志報(bào)錯(cuò)標(biāo)志”vLR(1)LR(1)項(xiàng)目集的構(gòu)造對(duì)某些項(xiàng)目集的構(gòu)造對(duì)某些同心集的分裂同心集的分裂可能可能使?fàn)顟B(tài)數(shù)目劇烈的增長使?fàn)顟B(tài)數(shù)目劇烈的增長文法G：(0) S S(1) B aB (2) S BB(3)

44、 B bI0:S S, #S BB, #B aB, a/bB b, a/bI1:S S , #I2:S B B, #B a B, #B b, #I5:S B B , #I6:B a B, #B aB, #B b, #I9:B a B , #I4:B b , a/bI3:B a B, a/bB aB, a/bB b, a/bI8:B a B , a/bI7:B b , #SBbbBbbaaaaBBLR(1)項(xiàng)目集和轉(zhuǎn)換函數(shù)分析可發(fā)現(xiàn)I3和I6 ， I4和I7 ， I8和I9分別為同心集I3:B a B, a/bB aB, a/bB b, a/bI6:B a B, #B aB, #B b, #I4:B b , a/bI7:B b , #I8:B a B , a/bI9:B a B , #I3,6:B a B, a/b/#B aB, a/b/#B b, a/b/#I4,7:B b , a/b/#I8,9:B a B , a/b/#合并為合并為合并為合并為合并為合并為LALR(1)分析分析v對(duì)對(duì)LR(1)項(xiàng)目集規(guī)范族合并同心集，若項(xiàng)目集規(guī)范族合并同心集，若合并同合并同心集后不產(chǎn)生新的沖突心集后不產(chǎn)生新的沖突，