第6講LR分析法

1、1第六講第六講 LR分析法分析法 LR分析概述分析概述 LR(0)分析分析 SLR(1)分析分析 LR(1)分析分析 LALR(1)分析分析 二義性文法在二義性文法在LR分析中的應(yīng)用分析中的應(yīng)用2 復(fù)習(xí)：移進(jìn)復(fù)習(xí)：移進(jìn)- -歸約分析歸約分析3文法文法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)串動(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）

2、#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 abbcde4 在步驟在步驟3中，用中，用Ab歸約歸約 在步驟在步驟5中，用中，用AAb歸約歸約 問題：何時(shí)移進(jìn)？何時(shí)歸約？用哪個(gè)產(chǎn)生問題：何時(shí)移進(jìn)？何時(shí)歸約？用哪個(gè)產(chǎn)生式歸約？式歸約？5 3） #ab bcde# 歸約歸約(Ab) 5） #aAb cde# 歸約

3、歸約(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)；用用LRLR分析表分析表來表示不同狀態(tài)對(duì)各輸入符號(hào)應(yīng)采取的動(dòng)作。來表示不同狀態(tài)對(duì)各輸入符號(hào)應(yīng)采取的動(dòng)作。6LR分析器工作過程示意圖分析器工作過程示意圖總控程序總控程序ACTION表表GOTO表表S0S1#X1.Sn.XnSP輸出輸出a1 a2 ai # an 輸入串輸入串

4、狀態(tài)棧狀態(tài)棧 符號(hào)棧符號(hào)棧LR分析表分析表7步驟步驟 符號(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ì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3 5） #aAb cde# 歸約歸約(AAb) 023

5、6 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)入棧S8S98問題問題： 對(duì)于一個(gè)文法，狀態(tài)集是如何確定的？對(duì)于一個(gè)文法，狀態(tài)集是如何確定的？ LRLR分析表是如何得到的？分析表是如何

6、得到的？9可歸前綴與活前綴可歸前綴與活前綴文法文法GS：(1) S aAcBe1(2) A b2(3) A Ab3(4) B d4S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1每次歸約句型的每次歸約句型的前部分前部分依次為：依次為：ab2aAb3aAcd4aAcBe1規(guī)范句型的這種前部分符號(hào)串稱為規(guī)范句型的這種前部分符號(hào)串稱為可歸前綴可歸前綴把形成可歸前綴之前包括可歸前綴在內(nèi)的所把形成可歸前綴之前包括可歸前綴在內(nèi)的所有規(guī)范句型的前綴都稱為有規(guī)范句型的前綴都稱為活前綴活前綴 ,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,a

7、AcBe10活前綴（活前綴（Viable Prefixes）定義：定義：S A 是文法是文法G中的一個(gè)規(guī)范推中的一個(gè)規(guī)范推導(dǎo)，如果符號(hào)串導(dǎo)，如果符號(hào)串是是的前綴，則稱的前綴，則稱是是G的一個(gè)的一個(gè)活前綴活前綴。R*R11 LR分析需要構(gòu)造識(shí)別分析需要構(gòu)造識(shí)別活前綴活前綴的的有窮自動(dòng)機(jī)有窮自動(dòng)機(jī) 把文法的終結(jié)符和非終結(jié)符都看成有窮自把文法的終結(jié)符和非終結(jié)符都看成有窮自動(dòng)機(jī)的輸入符號(hào)，每次把一個(gè)符號(hào)進(jìn)棧看動(dòng)機(jī)的輸入符號(hào)，每次把一個(gè)符號(hào)進(jìn)棧看成已識(shí)別過了該符號(hào)，同時(shí)狀態(tài)進(jìn)行轉(zhuǎn)換，成已識(shí)別過了該符號(hào)，同時(shí)狀態(tài)進(jìn)行轉(zhuǎn)換，當(dāng)識(shí)別到可歸前綴時(shí)，相當(dāng)于在棧中形成當(dāng)識(shí)別到可歸前綴時(shí)，相當(dāng)于在棧中形成句柄，認(rèn)為達(dá)

8、到了識(shí)別句柄的終態(tài)。句柄，認(rèn)為達(dá)到了識(shí)別句柄的終態(tài)。12步驟步驟 符號(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ì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3 5） #aAb cde# 歸約歸約(AA

9、b) 0236 r3 3 8） # aAcd e# 歸約歸約(Bd) 02358 r4 710） #aAcBe # 歸約歸約(SaAcBe) 023579 r1 1狀態(tài)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*13步驟步驟 符號(hào)棧符號(hào)棧 輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # abbcde# 移進(jìn)移進(jìn) 0 S2對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程狀態(tài)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*14步驟步驟 符號(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)移

10、進(jìn) 02 S4 對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程狀態(tài)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*15步驟步驟 符號(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 對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3狀態(tài)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*16步驟步驟 符號(hào)棧符號(hào)棧 輸入符號(hào)串輸入符號(hào)串動(dòng)作動(dòng)作 1） # abbcde# 移進(jìn)移進(jìn) 0 S2 2） #a b

11、bcde# 移進(jìn)移進(jìn) 02 S4 4） #aA bcde# 移進(jìn)移進(jìn) 023 S6對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3狀態(tài)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*17步驟步驟 符號(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對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3 5） #aA

12、b cde# 歸約歸約(AAb) 0236 r3 3狀態(tài)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*18步驟步驟 符號(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對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3 5） #aAb cde# 歸約歸約(AAb) 0236 r3 3狀態(tài)棧狀態(tài)棧ACTIONGOTO*014235

13、769SabAbcBed819步驟步驟 符號(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對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3 5） #aAb cde# 歸約歸約(AAb) 0236 r3 3狀態(tài)棧狀態(tài)棧ACTIONGOTO*014235769SabAbcBed820步驟步驟 符號(hào)棧符

14、號(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對(duì)輸入串對(duì)輸入串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)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*21

15、步驟步驟 符號(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 S9對(duì)輸入串對(duì)輸入串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)棧

16、狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*22步驟步驟 符號(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 S9對(duì)輸入串對(duì)輸入串a(chǎn)bbcde#的的LR分析過程分析過程 3） #ab bcde# 歸約歸約(Ab) 024 r2 3 5） #aAb cde# 歸約歸約(AAb) 0236 r3 3

17、8） # aAcd e# 歸約歸約(Bd) 02358 r4 710） #aAcBe # 歸約歸約(SaAcBe) 023579 r1 1狀態(tài)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*23步驟步驟 符號(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

18、對(duì)輸入串對(duì)輸入串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 710） #aAcBe # 歸約歸約(SaAcBe) 023579 r1 1狀態(tài)棧狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*24如何構(gòu)造識(shí)別活前綴的有限自動(dòng)機(jī)如何構(gòu)造識(shí)別活前綴的有限自動(dòng)機(jī) 已經(jīng)有了活前綴如何構(gòu)造有限自動(dòng)機(jī)已經(jīng)有了活前綴如何構(gòu)造有限自動(dòng)機(jī)? ? 活前綴及其可歸前綴的一般計(jì)算方法活前綴及其可歸前綴的一般計(jì)算方法25

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

20、cBed7*識(shí)別活前綴的確定的有限自動(dòng)機(jī)識(shí)別活前綴的確定的有限自動(dòng)機(jī)27項(xiàng)目（項(xiàng)目（item）：）：在每個(gè)產(chǎn)生式的右部適當(dāng)位置在每個(gè)產(chǎn)生式的右部適當(dāng)位置添加一個(gè)圓點(diǎn)構(gòu)成添加一個(gè)圓點(diǎn)構(gòu)成項(xiàng)目項(xiàng)目例如：產(chǎn)生式例如：產(chǎn)生式S aAcBe對(duì)應(yīng)有對(duì)應(yīng)有6個(gè)項(xiàng)目個(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)的項(xiàng)目圓點(diǎn)的左部左部表示分析過程的某個(gè)時(shí)刻用該產(chǎn)表示分析過程的某個(gè)時(shí)刻用該產(chǎn)生式歸約時(shí)生式歸約時(shí)句柄已識(shí)別的部分句柄已識(shí)別的部分，圓點(diǎn)，圓點(diǎn)右部右部表示表示待待識(shí)別的部分識(shí)別的部分。空產(chǎn)生式空產(chǎn)生式A的項(xiàng)目

21、只有一個(gè)：的項(xiàng)目只有一個(gè)：A28由文法的產(chǎn)生式直接構(gòu)造識(shí)別活由文法的產(chǎn)生式直接構(gòu)造識(shí)別活前綴和可歸前綴的有限自動(dòng)機(jī)前綴和可歸前綴的有限自動(dòng)機(jī)l有限自動(dòng)機(jī)有限自動(dòng)機(jī)NFA的每一個(gè)狀態(tài)由一個(gè)的每一個(gè)狀態(tài)由一個(gè)項(xiàng)目項(xiàng)目構(gòu)成構(gòu)成29構(gòu)造識(shí)別活前綴的構(gòu)造識(shí)別活前綴的NFA：1、把文法的所有產(chǎn)生式的項(xiàng)目都引出，每個(gè)項(xiàng)目把文法的所有產(chǎn)生式的項(xiàng)目都引出，每個(gè)項(xiàng)目 都為都為NFA的一個(gè)狀態(tài)的一個(gè)狀態(tài)2、確定、確定初態(tài)初態(tài)、句柄識(shí)別態(tài)句柄識(shí)別態(tài)、句子識(shí)別態(tài)句子識(shí)別態(tài)3、確定、確定狀態(tài)之間的轉(zhuǎn)換關(guān)系狀態(tài)之間的轉(zhuǎn)換關(guān)系*若項(xiàng)目若項(xiàng)目i為為 X X1X2.Xi-1 Xi.Xn項(xiàng)目項(xiàng)目j為為 X X1X2.Xi-1 Xi

22、 Xi+1.Xn則從狀態(tài)則從狀態(tài)i到狀態(tài)到狀態(tài)j連一條標(biāo)記為連一條標(biāo)記為Xi的箭弧的箭弧*若若i為為X A ，k為為A ，則從狀態(tài)則從狀態(tài)i畫標(biāo)畫標(biāo)記為記為 的箭弧到狀態(tài)的箭弧到狀態(tài)k30文法文法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 9、T int * T10、T int * T11、T int * T12、T int * T 13、 T int 14、 T int 15、 T (E) 16、 T

23、( E)17、 T (E )18、 T (E) 31NFA 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 .intT .int * TT int * T.T int *.TT int.* TETE+intint*TT32Translation to the DFAS . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. + ET int. * TT int.T (.

24、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項(xiàng)目集項(xiàng)目集33NFANFA確定化為確定化為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)目集（

25、狀態(tài)）項(xiàng)目集（狀態(tài)）的全體稱為這個(gè)文法的的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族.34如果如果I I是文法是文法G G的一個(gè)項(xiàng)目集，定義和構(gòu)造的一個(gè)項(xiàng)目集，定義和構(gòu)造I I的閉包的閉包CLOSURE(I)CLOSURE(I)如下：如下：a)Ia)I的項(xiàng)目都在的項(xiàng)目都在CLOSURE(I)CLOSURE(I)中中b)b)若若A A B 屬于屬于CLOSURE(I)CLOSURE(I)，則每一形如則每一形如B B 的的項(xiàng)目也屬于項(xiàng)目也屬于CLOSURE(I)CLOSURE(I)c)c)重復(fù)重復(fù)b)b)直到直到CLOSURE(I)CLOSURE(I)不再擴(kuò)大不再擴(kuò)大通過通過閉包函數(shù)閉包

26、函數(shù)(CLOSURE)來求來求DFA一個(gè)狀態(tài)的一個(gè)狀態(tài)的項(xiàng)目集項(xiàng)目集35 定義轉(zhuǎn)換函數(shù)如下：定義轉(zhuǎn)換函數(shù)如下：GO（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。因此用因此用GO（I，X）轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù)得到的得到的J為轉(zhuǎn)向后狀態(tài)所含項(xiàng)目集的為轉(zhuǎn)向后狀態(tài)所含項(xiàng)目集的核核36使用閉包函數(shù)（使用閉包函數(shù)（CLOSURECLOSURE）和轉(zhuǎn)向函數(shù)和轉(zhuǎn)向函數(shù)

27、( (GO(I,X)GO(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ù)GO(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)目集得到初態(tài)的項(xiàng)目集37S . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. +

28、 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文法文法G：S E E T + E E TT int * T T int T (E)38總結(jié)：構(gòu)造識(shí)別文法活前綴總結(jié)：構(gòu)造識(shí)別文法活前綴DFADFA的三種方法的三種方法一、根據(jù)形式定義求出活前綴的正規(guī)表達(dá)式，一、根據(jù)形式

29、定義求出活前綴的正規(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ù)( (GO(I,X)GO(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í)別活前綴的DFADFA39根據(jù)根據(jù)圓點(diǎn)所在的位置圓點(diǎn)

30、所在的位置和和圓點(diǎn)后是終結(jié)符還是非終圓點(diǎn)后是終結(jié)符還是非終結(jié)符結(jié)符把把LRLR（0 0）項(xiàng)目集規(guī)范族的項(xiàng)目類型分為以項(xiàng)目集規(guī)范族的項(xiàng)目類型分為以下幾種：下幾種：移進(jìn)項(xiàng)目，形如移進(jìn)項(xiàng)目，形如 A a 待約項(xiàng)目，形如待約項(xiàng)目，形如 A B 歸約項(xiàng)目，形如歸約項(xiàng)目，形如 A 接受項(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í)存在。歸約歸約-歸約沖突歸約沖突40S . EE . TE .T + ET .(E)T .int * TT .i

31、ntS 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文法文法G：S E E T + E E TT int * T T int T (E)41LR(0)文法：文法：LR(0)文法：若其文法：若其LR(0)項(xiàng)目集規(guī)范族不存在項(xiàng)目集規(guī)范族不存在

32、移進(jìn)移進(jìn)-歸約，或歸約歸約，或歸約-歸約沖突，稱為歸約沖突，稱為LR(0)文法文法。42LR(0)分析表的構(gòu)造 LR(0)分析表相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)分析表相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)DFA的狀態(tài)轉(zhuǎn)換矩陣的狀態(tài)轉(zhuǎn)換矩陣 LR(0)分析表的構(gòu)造算法分析表的構(gòu)造算法(書上書上p135) LR(0)分析器的工作過程分析器的工作過程(書上書上p136)43令包含令包含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

33、 ，則置則置ACTIONk,# = accc) 若若GO(Ik,A)= Ij ，則置則置GOTOk,A=j，其中其中A為非終結(jié)為非終結(jié)符，符，j為某一狀態(tài)號(hào)為某一狀態(tài)號(hào)b) 若項(xiàng)目若項(xiàng)目A 屬于屬于Ik ，則對(duì)任何終結(jié)符則對(duì)任何終結(jié)符a或或#，置置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ù)GO(Ik,a)= Ij ，當(dāng)當(dāng) a為終結(jié)符時(shí)，則置為終結(jié)符時(shí)，則置ACTIONk,a為為Sj44S . EE . TE .T + ET .(E)T .int * TT .intS E .E T.E T. + E

34、T 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+(1234567891011能構(gòu)造出相應(yīng)的能構(gòu)造出相應(yīng)的LR(0)分析表嗎？分析表嗎？45 例：對(duì)文法例：對(duì)文法GE構(gòu)造出構(gòu)造出LR(0)分析表：分析表：E aA | bBA cA | dB cB | d46SLR(1)分析 大多

35、數(shù)適用的程序設(shè)計(jì)語言的文法不能滿大多數(shù)適用的程序設(shè)計(jì)語言的文法不能滿足足LR(0)文法的條件，即其規(guī)范族中會(huì)有含文法的條件，即其規(guī)范族中會(huì)有含有沖突的項(xiàng)目集（狀態(tài)）有沖突的項(xiàng)目集（狀態(tài)） 如果解決這種沖突？如果解決這種沖突？ 直覺：對(duì)于有沖突的狀態(tài)，向前查看直覺：對(duì)于有沖突的狀態(tài)，向前查看一個(gè)一個(gè)符號(hào)，以確定采用的動(dòng)作符號(hào)，以確定采用的動(dòng)作47文法文法G：(0) S S(1) S rD (2) D D,i(3) D iACTIONGOTO狀狀態(tài)態(tài)r,i#SD0S211acc2S433r1r1,S5r1r14r3r3r3r35S66r2r2r2r2I0:S SS rDI2: S rDD D,iD

36、 iI3: S rD D D ,iI4: D i I5: D D,iI1: S S I6: D D,i SriD,iLR(0)LR(0)分析表分析表48一個(gè)一個(gè)LR(0)規(guī)范族中含有如下的項(xiàng)目集（狀態(tài)）規(guī)范族中含有如下的項(xiàng)目集（狀態(tài)）II = X b , A , B 若有：若有：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b = 若一個(gè)文法的若一個(gè)文法的LR(0)分析表中所含有的動(dòng)作沖突都能用上述方分析表中所含有的動(dòng)作沖突都能用上述方法解決，則稱這個(gè)文法是法解決，則稱這個(gè)文法是SLR(1)文法文法,所構(gòu)造的分析表為所構(gòu)造的分析表為SLR(1)分析

37、表，分析表，使用使用SLR(1)分析表的分析器為分析表的分析器為SLR(1)分析分析器。器。狀態(tài)狀態(tài)I面臨某輸入符號(hào)面臨某輸入符號(hào)a1) 若若a=b，則移進(jìn)則移進(jìn)2) 若若a FOLLOW(A), 則用產(chǎn)生式則用產(chǎn)生式 A 進(jìn)行歸約進(jìn)行歸約3) 若若a FOLLOW(B), 則用產(chǎn)生式則用產(chǎn)生式 B 進(jìn)行歸約進(jìn)行歸約4) 此外，報(bào)錯(cuò)此外，報(bào)錯(cuò)49“改進(jìn)的改進(jìn)的”SLR(1)分析：分析：對(duì)所有非終結(jié)符都求出其對(duì)所有非終結(jié)符都求出其FOLLOW集合集合，這樣只，這樣只有歸約項(xiàng)目僅對(duì)面臨輸入符號(hào)包含在該歸約項(xiàng)目有歸約項(xiàng)目僅對(duì)面臨輸入符號(hào)包含在該歸約項(xiàng)目左部非終結(jié)符的左部非終結(jié)符的FOLLOW集合中，

38、才采取用該產(chǎn)集合中，才采取用該產(chǎn)生式歸約的動(dòng)作。生式歸約的動(dòng)作。501) 若項(xiàng)目若項(xiàng)目A a 屬于屬于Ik，且轉(zhuǎn)換函數(shù)且轉(zhuǎn)換函數(shù)GO(Ik,a)= Ij ，當(dāng)當(dāng)a為終結(jié)符時(shí)，為終結(jié)符時(shí)，則置則置ACTIONk,a為為Sj2) 若項(xiàng)目若項(xiàng)目A 屬于屬于Ik ，則對(duì)則對(duì)a FOLLOW(A)時(shí)時(shí)，置，置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) 其它填上其

39、它填上“報(bào)錯(cuò)標(biāo)志報(bào)錯(cuò)標(biāo)志”改進(jìn)的改進(jìn)的SLR(1)分析表的分析表的ACTION表和表和GOTO表的構(gòu)造步驟：表的構(gòu)造步驟：51文法文法G：(0) S S(1) S rD (2) D D,i(3) D i狀狀態(tài)態(tài) GOTO函函數(shù)數(shù) 核核集集合合 閉閉包包增增加加項(xiàng)項(xiàng)目目 項(xiàng)項(xiàng)目目集集 I0 S S S rD S S S rD I1 GOTO（I0，S） S S S S I2 GOTO（I0，r） S r D D D,i D i S r D D D,i D i I3 GOTO（I2，D） S rD D D ,i S rD D D ,i I4 GOTO（I2，i） D i D i I5 GOTO（I

40、3， ， ） D D, i D D, i I6 GOTO（I5，i） D D,i D D,i ACTION GOTO 狀狀態(tài)態(tài) r , i # S D 0 S2 1 1 acc 2 S4 3 3 S5 r1 4 r3 r3 5 S6 6 r2 r2 SLR(1)SLR(1)分析表分析表FOLLOW(S) = # FOLLOW(D) = #, , 52 仍有許多文法構(gòu)造的仍有許多文法構(gòu)造的LR(0)LR(0)項(xiàng)目集規(guī)范族存項(xiàng)目集規(guī)范族存在的動(dòng)作沖突不能用在的動(dòng)作沖突不能用SLR(1)SLR(1)方法解決方法解決53LR(1)分析 若項(xiàng)目集若項(xiàng)目集A B 屬于屬于I時(shí)，則時(shí)，則B 也屬于也屬于I

41、把把FIRST( )作為用產(chǎn)生式歸約的搜索符（稱為向作為用產(chǎn)生式歸約的搜索符（稱為向前搜索符），作為用產(chǎn)生式前搜索符），作為用產(chǎn)生式B 歸約時(shí)查看的符歸約時(shí)查看的符號(hào)集合（用以代替號(hào)集合（用以代替SLR(1)分析中的分析中的FOLLOW集），集），并把此搜索符號(hào)的集合也放在相應(yīng)項(xiàng)目的后面，并把此搜索符號(hào)的集合也放在相應(yīng)項(xiàng)目的后面，這種處理方法即為這種處理方法即為LR(1)方法方法54 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)目集族。55 1）構(gòu)造）構(gòu)造LR

42、（1）項(xiàng)目集的閉包函數(shù)項(xiàng)目集的閉包函數(shù) a) I的項(xiàng)目都在的項(xiàng)目都在CLOSURE(I)中中b) 若若A B , a CLOSURE(I)，B 是文法的產(chǎn)生式，是文法的產(chǎn)生式， V*，b FIRST( a),則則B ,b也屬于也屬于CLOSURE(I)c) 重復(fù)重復(fù)b)直到直到CLOSURE(I)不再擴(kuò)大不再擴(kuò)大56 2)轉(zhuǎn)換函數(shù)的構(gòu)造轉(zhuǎn)換函數(shù)的構(gòu)造 GO（I，X）= CLOSURE（J）其中：其中：I為為LR(1)的項(xiàng)目集的項(xiàng)目集，X為一文法符號(hào)為一文法符號(hào) J = 任何形如任何形如A X ,a的項(xiàng)目的項(xiàng)目 | A X ,a屬于屬于I 57文法G：(0) S S (1) S aAd (2)

43、S bAc (3) S aec (4) S bed (5) A eI0= S S, #,S aAd, #,S bAc, #,S aec, #,S bed, # I1 = GO(I0,S) = S S , # I2 = GO(I0,a) = S a Ad, #, S a ec, #, A e, d I3 = GO(I0,b) = S b Ac, #, S b ed, #, A e, c I4 = GO(I2,A) = S aA d, # I5 = GO(I2,e) = S ae c, #, A e , d I6 = GO(I3,A) = S bA c, # 查看查看I5 ，I7中的沖突，體會(huì)中的

44、沖突，體會(huì)LR(1)如何解決如何解決I11 = GO(I7,d) = S bed , # I10 = GO(I6,c) = S bAc , # I9 = GO(I5,c) = S ae c , # I8 = GO(I4,d) = S aAd , # I7 = GO(I3,e) = S be d, #, A e , c 58LR(1)分析表的構(gòu)造分析表的構(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í)，則置ACTIONk,a為為Sj2) 若項(xiàng)目若項(xiàng)目A ,a屬于屬于Ik ，則則置置ACTIONk,a = rj ，j為

45、產(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)志”59 LR(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ù)目劇烈的增長60文法G：(0) S S(1) B aB (2) S BB(3) B bI0:S S, #S BB, #B aB, a/bB b, a/bI4:B b , a/bI3:B a B, a/bB aB, a/bB b, a/bI8:B a B , a/bI7:B b , #I1:S S , #SI2:S B B, #B a B, #B b, #BbbBbbaaI6:B a B, #B aB, #B b, #aaI5:S B B , #BI9:B a