編譯原理教案-LR分析課件

LR分析自下而上語(yǔ)法分析算法之LR分析自下而上語(yǔ)法分析算法之復(fù)習(xí)：移進(jìn)-歸約分析復(fù)習(xí)：移進(jìn)-歸約分析文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dabbcde步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)2）#abbcde#移進(jìn)A3）#abbcde#歸約(A→b)4）#aAbcde#移進(jìn)A5）#aAbcde#歸約(A→Ab)6）#aAcde#移進(jìn)7）#aAcde#移進(jìn)B8）#aAcde#歸約(B→d)9）#aAcBe#移進(jìn)11）#S#接受S10）#aAcBe#歸約(S→aAcBe)分析符號(hào)串a(chǎn)bbcde是否G[S]的句子對(duì)輸入串a(chǎn)bbcde#的移進(jìn)-規(guī)約分析過(guò)程SaAcBeaAcdeaAbcdeabbcde文法G[S]：

(1)S→aAcBe

(2)A→在步驟3中，用A→b歸約在步驟5中，用A→Ab歸約問(wèn)題：何時(shí)移進(jìn)？何時(shí)歸約？用哪個(gè)產(chǎn)生式歸約？在步驟3中，用A→b歸約3）#abbcde#歸約(A→b)5）#aAbcde#歸約(A→Ab)4）#aAbcde#移進(jìn)6）#aAcde#移進(jìn)分析：已分析過(guò)的部分在棧中的前綴不同，而且移進(jìn)和歸約后棧中的狀態(tài)會(huì)發(fā)生變化

我們引入一個(gè)新的狀態(tài)棧來(lái)表示符號(hào)棧中的符號(hào)目前狀態(tài)用LR分析表來(lái)表示不同狀態(tài)下對(duì)于各輸入符號(hào)應(yīng)采取的動(dòng)作3）#abbcde#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S911）#S#接受01acc對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r4710）#aAcBe#歸約(S→aAcBe)023579r11狀態(tài)棧ACTIONGOTO文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dSi:移進(jìn)，并將狀態(tài)i進(jìn)棧ri:用第i個(gè)產(chǎn)生式歸約，同時(shí)狀態(tài)棧與符號(hào)棧退出相應(yīng)個(gè)符號(hào)，根據(jù)GOTO表將相應(yīng)狀態(tài)入棧步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S911）#S#接受01acc對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r4710）#aAcBe#歸約(S→aAcBe)023579r11狀態(tài)棧ACTIONGOTO文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dSi:移進(jìn)，并將狀態(tài)i進(jìn)棧ri:用第i個(gè)產(chǎn)生式歸約，同時(shí)狀態(tài)棧與符號(hào)棧退出相應(yīng)個(gè)符號(hào)，根據(jù)GOTO表將相應(yīng)狀態(tài)入棧步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#問(wèn)題：對(duì)于一個(gè)文法，狀態(tài)集是如何確定的？LR分析表是如何得到的？問(wèn)題：可歸前綴與活前綴文法G[S]：

(1)S→aAcBe[1]

(2)A→b[2]

(3)A→Ab[3]

(4)B→d[4]SaAcBe[1]

aAcd[4]e[1]

aAb[3]cd[4]e[1]

ab[2]b[3]cd[4]e[1]每次歸約句型的前部分依次為：

ab[2]

aAb[3]

aAcd[4]

aAcBe[1]規(guī)范句型的這種前部分符號(hào)串稱為可歸前綴我們把形成可歸前綴之前包括可歸前綴在內(nèi)的所有規(guī)范句型的前綴都稱為活前綴,a,ab

,a,aA,aAb

,a,aA,aAc,aAcd

,a,aA,aAc,aAcB,aAcBe可歸前綴與活前綴文法G[S]：

(1)S→aAcBe[活前綴（ViablePrefixes）viable:adjcapableofgrowinganddeveloping<~seed>capableofbeingputintopractice:workable定義：S’A

是文法G中的一個(gè)規(guī)范推導(dǎo)，如果符號(hào)串是的前綴，則稱是G的一個(gè)活前綴?；钋熬Y（ViablePrefixes）viable:adjLR分析需要構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī)我們可以文法的終結(jié)符和非終結(jié)符都看成有窮自動(dòng)機(jī)的輸入符號(hào)，每次把一個(gè)符號(hào)進(jìn)?？闯梢炎R(shí)別過(guò)了該符號(hào)，同時(shí)狀態(tài)進(jìn)行轉(zhuǎn)換，當(dāng)識(shí)別到可歸前綴時(shí)，相當(dāng)于在棧中形成句柄，認(rèn)為達(dá)到了識(shí)別句柄的終態(tài)。LR分析需要構(gòu)造識(shí)別活前綴的有窮自動(dòng)機(jī)步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S911）#S#接受01acc對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r4710）#aAcBe#歸約(S→aAcBe)023579r11狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S2對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r23狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S6對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r23狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S6對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r33狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S5對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r33狀態(tài)棧ACTIONGOTO*014235769SabAbcBed8步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S8對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r33狀態(tài)棧ACTIONGOTO*014235769SabAbcBed8步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S8對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r47狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S9對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r47狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S9對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r4710）#aAcBe#歸約(S→aAcBe)023579r11狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)0S22）#abbcde#移進(jìn)02S4

4）#aAbcde#移進(jìn)023S66）#aAcde#移進(jìn)023S57）#aAcde#移進(jìn)0235S89）#aAcBe#移進(jìn)02357S911）#S#接受01acc對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程3）#abbcde#歸約(A→b)024r235）#aAbcde#歸約(A→Ab)0236r338）#aAcde#歸約(B→d)02358r4710）#aAcBe#歸約(S→aAcBe)023579r11狀態(tài)棧ACTIONGOTO014235769SabAbcBed8*步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#如何構(gòu)造識(shí)別活前綴的有限自動(dòng)機(jī)已經(jīng)有了活前綴如何構(gòu)造有限自動(dòng)機(jī)?活前綴及其可歸前綴的一般計(jì)算方法如何構(gòu)造識(shí)別活前綴的有限自動(dòng)機(jī)文法G[S]：

S’→S[0]

S→aAcBe[1]

A→b[2]

A→Ab[3]

B→d[4]句子abbcde的可歸前綴如下：

S[0]

ab[1]

aAb[3]

aAcd[4]

aAcBe[1]構(gòu)造識(shí)別其活前綴及可歸前綴的有限自動(dòng)機(jī)如下：104387131210182591461715161110SabaAbaAcdaAcBe*1*句子識(shí)別態(tài)i句柄識(shí)別態(tài)文法G[S]：

S’→S[0]

S→aAcBe[1]104387131210182591461715161110SabaAbaAcdaAcBe*X加上開(kāi)始狀態(tài)X確定化X13246859SabAbcBed7*識(shí)別活前綴的確定的有限自動(dòng)機(jī)104387131210182591461715161110活前綴及其可歸前綴的一般計(jì)算方法定義：文法G，AVN, LC(A)={|S’A,V*,VT*}規(guī)范推導(dǎo)中在非終結(jié)符A左邊所有可能出現(xiàn)的符號(hào)串的集合推論：若文法G中有產(chǎn)生式B→A，則有

LC(A)LC(B)*{}活前綴及其可歸前綴的一般計(jì)算方法定義：文法G，AVN,文法G’[S]：

S’→S[0]

S→aAcBe[1]

A→b[2]

A→Ab[3]

B→d[4]由前面的定義與推論我們知：LC(S’)={}

LC(S)=LC(S’)*{}

LC(A)=LC(S)*{a}LC(A)*{}

LC(B)=LC(S)*{aAc}化簡(jiǎn)為：[S’]=

[S]=[S’]

[A]=[S]a+[A]

[B]=[S]aAc求解方程組可得：[S’]=

[S]=

[A]=a+[A]

[B]=aAc[A]=a|[A][A]=a*=a這樣我們求出了每個(gè)非終結(jié)符在規(guī)范推導(dǎo)中用該非終結(jié)符的右部替換該非終結(jié)符之前，它的左部可能出現(xiàn)的所有前綴，也就是在規(guī)范歸約過(guò)程中用句柄歸約成該非終結(jié)符之前不包括句柄的活前綴。文法G’[S]：

S’→S[0]

S→aAcBe[1不包括句柄的活前綴+句柄=？可歸前綴？令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]*={ab}

LR(0)C(A→Ab)=[A]*{Ab}={aAb}

LR(0)C(B→d)=[B]*utjh0gd={aAcd}總結(jié)：如何構(gòu)造識(shí)別文法活前綴的有限自動(dòng)機(jī)？1、根據(jù)文法算出其可歸前綴

2、根據(jù)可歸前綴，構(gòu)造識(shí)別文法活前綴的不確定有限自動(dòng)機(jī)

3、確定化，從而構(gòu)造出識(shí)別文法活前綴的確定的有限自動(dòng)機(jī)參見(jiàn)課本P124的例子不包括句柄的活前綴+句柄=？可歸前綴？令LLR分析器的構(gòu)造1、構(gòu)造識(shí)別文法活前綴的確定有限自動(dòng)機(jī)

2、根據(jù)該自動(dòng)機(jī)構(gòu)造相應(yīng)的分析表(ACTION表、GOTO表)總控程序Action/Goto表輸入符號(hào)串輸出狀態(tài)與符號(hào)棧LR分析器的構(gòu)造1、構(gòu)造識(shí)別文法活前綴的確定有限自動(dòng)機(jī)

2這種方法構(gòu)造識(shí)別可歸前綴的有限自動(dòng)機(jī)從理論的角度講是比較嚴(yán)格的，但實(shí)現(xiàn)起來(lái)卻很復(fù)雜是否存在一種比較實(shí)用的方法？這種方法構(gòu)造識(shí)別可歸前綴的有限自動(dòng)機(jī)從理論的角度講是比較嚴(yán)格由文法的產(chǎn)生式直接構(gòu)造識(shí)別活前綴和可歸前綴的有限自動(dòng)機(jī)項(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?有限自動(dòng)機(jī)的每一個(gè)狀態(tài)由一個(gè)項(xiàng)目構(gòu)成由文法的產(chǎn)生式直接構(gòu)造識(shí)別活前綴和可歸前綴的有限自動(dòng)機(jī)項(xiàng)目圓點(diǎn)的左部表示分析過(guò)程的某個(gè)時(shí)刻用該產(chǎn)生式歸約時(shí)句柄已識(shí)別的部分，圓點(diǎn)右部表示待識(shí)別的部分。構(gòu)造識(shí)別活前綴的NFA：

1、把文法的所有產(chǎn)生式的項(xiàng)目都引出，每個(gè)項(xiàng)目都為NFA的一個(gè)狀態(tài)

2、確定初態(tài)、句柄識(shí)別態(tài)、句子識(shí)別態(tài)

3、確定狀態(tài)之間的轉(zhuǎn)換關(guān)系

*若項(xiàng)目i為X→X1X2...Xi-1

?Xi...Xn

項(xiàng)目j為X→X1X2...Xi-1Xi?

Xi+1...Xn

則從狀態(tài)i到狀態(tài)j連一條標(biāo)記為Xi的箭弧

*若i為X

→?A，k為A→

?，則從狀態(tài)i畫(huà)標(biāo) 記為的箭弧到狀態(tài)k項(xiàng)目圓點(diǎn)的左部表示分析過(guò)程的某個(gè)時(shí)刻用該產(chǎn)生式歸約時(shí)句柄已識(shí)文法G‘：

S’E

ET+E

ET

Tint*T

Tint

T(E)文法的項(xiàng)目有：

1、S’

?E

2、S’E?

3、E?T+E

4、ET?+E

5、ET+?E

6、ET+E?

7、E?T

8、ET?

9、T?int*T

10、Tint?*T

11、Tint*?T

12、Tint*T?

13、

T?int

14、Tint?

15、T?(E)

16、T(?E)

17、T(E?)

18、T(E)?

文法G‘：

S’E

ET+E

ET

NFAforViablePrefixesoftheExampleT?.(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.*TeeeeEeTeeeE+eintint*TeeeeeTeNFAforViablePrefixesoftheNFAforViablePrefixesinDetail(1)S’?.ENFAforViablePrefixesinDetNFAforViablePrefixesinDetail(2)S’?.ES’?E.EE?.TeE?.T+EeNFAforViablePrefixesinDetNFAforViablePrefixesinDetail(3)S’?E.E?.T+ES’?.EE?.TT?.int*TeeET?.(E)eT?.inteeE?T.TNFAforViablePrefixesinDetNFAforViablePrefixesinDetail(4)T?.(E)S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeEE?T.+ETeeeeeeTNFAforViablePrefixesinDetNFAforViablePrefixesinDetail(5)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeEeeeeeeTE?T.+ETNFAforViablePrefixesinDetNFAforViablePrefixesinDetail(6)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeeeEeeeeeeTE?T.+ETT?(E.)ENFAforViablePrefixesinDetNFAforViablePrefixesinDetail(7)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeeeEeeeeeeTE?T.+ETT?(E.)ET?(E).)NFAforViablePrefixesinDetNFAforViablePrefixesinDetail(8)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeeeEeeeeeeTE?T.+ETT?(E.)ET?(E).)E?T+.E+NFAforViablePrefixesinDetNFAforViablePrefixesinDetail(9)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeeeEeeeeeeTE?T.+ETT?(E.)ET?(E).)E?T+.E+eeE?T+E.ENFAforViablePrefixesinDetNFAforViablePrefixesinDetail(10)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeeeEeeeeeeTE?T.+ETT?(E.)ET?(E).)E?T+.E+eeE?T+E.ET?NFAforViablePrefixesinDetNFAforViablePrefixesinDetail(11)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeeeEeeeeeeTE?T.+ETT?(E.)ET?(E).)E?T+.E+eeE?T+E.ET?T?int.*TintNFAforViablePrefixesinDetNFAforViablePrefixesinDetail(12)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeeeEeeeeeeTE?T.+ETT?(E.)ET?(E).)E?T+.E+eeE?T+E.ET?T?int.*TintT?int*.T*NFAforViablePrefixesinDetNFAforViablePrefixesinDetail(13)T?.(E)T?(.E)(S’?E.E?.T+ES’?.EE?.TE?T.T?.intT?.int*TeeeeEeeeeeeTE?T.+ETT?(E.)ET?(E).)E?T+.E+eeE?T+E.ET?T?int.*TintT?int*.T*T?int*T.TeeeNFAforViablePrefixesinDet根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符把項(xiàng)目分為以下幾種：移進(jìn)項(xiàng)目，形如A→?a待約項(xiàng)目，形如A→?B歸約項(xiàng)目，形如A→?

接受項(xiàng)目，形如S’→S?

根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符把項(xiàng)目分為以下TranslationtotheDFAS’?.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項(xiàng)目集TranslationtotheDFAS’?.E構(gòu)成識(shí)別一個(gè)文法活前綴的DFA項(xiàng)目集（狀態(tài)）的全體稱為這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族NFA確定化為DFA的工作量較大，我們考慮直接構(gòu)造出項(xiàng)目集作為DFA的狀態(tài)，就可直接構(gòu)造DFA通過(guò)閉包函數(shù)(CLOSURE)來(lái)求DFA一個(gè)狀態(tài)的項(xiàng)目集構(gòu)成識(shí)別一個(gè)文法活前綴的DFA項(xiàng)目集（狀態(tài)）的全體稱為這個(gè)文如果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ò)大定義轉(zhuǎn)換函數(shù)如下：

GOTO（I，X）=CLOSURE（J）

其中：I為包含某一項(xiàng)目集的狀態(tài)，X為一文法符號(hào)

J={任何形如A→X?

的項(xiàng)目|A→?

X屬于I}如果I是文法G’的一個(gè)項(xiàng)目集，定義和構(gòu)造I的閉包CLOSUR圓點(diǎn)不在產(chǎn)生式右部最左邊的項(xiàng)目稱為核，唯一的例外是S’→

?S。因此用GOTO（I，X）轉(zhuǎn)換函數(shù)得到的J為轉(zhuǎn)向后狀態(tài)所含項(xiàng)目集的核使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GOTO(I,X))構(gòu)造文法G’的LR(0)的項(xiàng)目集規(guī)范族，步驟如下：a)置項(xiàng)目S’→

?

S為初態(tài)集的核，然后對(duì)核求閉包CLOSURE（{S’→

?

S}）得到初態(tài)的項(xiàng)目集

b)對(duì)初態(tài)集或其它所構(gòu)造的項(xiàng)目集應(yīng)用轉(zhuǎn)換函數(shù)GOTO(I，X)=CLOSURE(J)求出新?tīng)顟B(tài)J的項(xiàng)目集

c)重復(fù)b)直到不出現(xiàn)新的項(xiàng)目集為止圓點(diǎn)不在產(chǎn)生式右部最左邊的項(xiàng)目稱為核，唯一的例外是S’→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+(TS’?.ES’?E.E?T.T?int.總結(jié)：構(gòu)造識(shí)別文法活前綴DFA的三種方法一、根據(jù)形式定義求出活前綴的正規(guī)表達(dá)式，然后由此正規(guī)表達(dá)式構(gòu)造NFA再確定化為DFA二、求出文法的所有項(xiàng)目，按一定規(guī)則構(gòu)造識(shí)別活前綴的NFA再確定化為DFA三、使用閉包函數(shù)（CLOSURE）和轉(zhuǎn)向函數(shù)(GOTO(I,X))構(gòu)造文法G’的LR(0)的項(xiàng)目集規(guī)范族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識(shí)別活前綴的DFA總結(jié)：構(gòu)造識(shí)別文法活前綴DFA的三種方法一、根據(jù)形式定義求出LR（0）項(xiàng)目集規(guī)范族的項(xiàng)目類型分為如下四種：1）移進(jìn)項(xiàng)目A→?a2）待約項(xiàng)目A→?B3）歸約項(xiàng)目A→?

4）接受項(xiàng)目S‘→S?

一個(gè)項(xiàng)目集可能包含多種項(xiàng)目a)移進(jìn)和歸約項(xiàng)目同時(shí)存在。移進(jìn)-歸約沖突b)歸約和歸約項(xiàng)目同時(shí)存在。歸約-歸約沖突LR(0)文法：若其LR(0)項(xiàng)目集規(guī)范族不存在移進(jìn)-歸約，或歸約-歸約沖突，稱為L(zhǎng)R(0)文法。LR（0）項(xiàng)目集規(guī)范族的項(xiàng)目類型分為如下四種：LR(0)分析表的構(gòu)造LR(0)分析表相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)DAF的狀態(tài)轉(zhuǎn)換矩陣LR(0)分析表的構(gòu)造算法書(shū)上p130,倒數(shù)4行，

A→?改為A→?aLR(0)分析器的工作過(guò)程LR(0)分析表的構(gòu)造LR(0)分析表相當(dāng)于識(shí)別活前綴的有限令包含S‘→?S

的項(xiàng)目集Ik的下標(biāo)k為分析器的初態(tài)LR(0)分析表的ACTION和GOTO表的構(gòu)造步驟如下：

a)若項(xiàng)目A→?a屬于Ik，且轉(zhuǎn)換函數(shù)GO(Ik,a)=Ij，當(dāng)a為終結(jié)符時(shí)，則置ACTION[k,a]為Sj

b)若項(xiàng)目A→?屬于Ik，則對(duì)a為任何終結(jié)符或‘#’，置ACTION[k,a]=rj，j為產(chǎn)生式在文法G‘中的編號(hào)

c)若GO(Ik,A)=Ij，則置GOTO[k,A]=j，其中A為非終結(jié)符，j為某一狀態(tài)號(hào)

d)若項(xiàng)目S‘→S

?屬于Ik，則置ACTION[k,#]=acc

e)其它填上“報(bào)錯(cuò)標(biāo)志”令包含S‘→?S的項(xiàng)目集Ik的下標(biāo)k為分析器的初態(tài)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+(1234567891011S’?.ES’?E.E?T.T?int.SLR(1)分析大多數(shù)適用的程序設(shè)計(jì)語(yǔ)言的文法不能滿足LR(0)文法的條件，即其規(guī)范族中會(huì)有含有沖突的項(xiàng)目集（狀態(tài)）如果解決這種沖突？直覺(jué)：對(duì)于有沖突的狀態(tài)，向前查看一個(gè)符號(hào)，以確定采用的動(dòng)作SLR(1)分析大多數(shù)適用的程序設(shè)計(jì)語(yǔ)言的文法不能滿足LR(文法G‘：

(0)S’S

(1)SrD

(2)DD,i

(3)DiI0:

S‘→?S

S‘→?rDI2:

S→r?D

D

→?D,i

D→?iI3:

S→rD

?

D→D?,iI4:

D→i

?I5:

D→D,?iI1:

S‘→S?I6:

D→D,i

?SriD,iLR(0)分析表文法G‘：

(0)S’S

(1)SrD

(I3:

S→rD

?

D→D?,i向前查看一個(gè)符號(hào)，看其是否是S的后跟符號(hào)（FOLLOW(S)）,若否則移進(jìn)，是則歸約。SLR(1)分析表I3:

S→rD?

D→D?,i向前查看一個(gè)符一個(gè)LR(0)規(guī)范族中含有如下的項(xiàng)目集（狀態(tài)）I

I={X→?b,A→?

,B→?

}

若有：FOLLOW(A)∩FOLLOW(B)=?

FOLLOW(A)∩=?

FOLLOW(B)∩=?狀態(tài)I面臨某輸入符號(hào)a

1)若a=b，則移進(jìn)

2)若aFOLLOW(A),則用產(chǎn)生式A→進(jìn)行歸約

3)若aFOLLOW(B),則用產(chǎn)生式B→進(jìn)行歸約

4)此外，報(bào)錯(cuò)若一個(gè)文法的LR(0)分析表中所含有的動(dòng)作沖突都能用上述方法解決，則稱這個(gè)文法是SLR(1)文法一個(gè)LR(0)規(guī)范族中含有如下的項(xiàng)目集（狀態(tài)）I

I={“改進(jìn)的”SLR(1)分析：對(duì)所有非終結(jié)符都求出其FOLLOW集合，這樣只有歸約項(xiàng)目?jī)H對(duì)面臨輸入符號(hào)包含在該歸約項(xiàng)目左部非終結(jié)符的FOLLOW集合中，才采取用該產(chǎn)生式歸約的動(dòng)作。改進(jìn)的SLR(1)分析表的ACTION表和GOTO表的構(gòu)造步驟：

a)若項(xiàng)目A→?a屬于Ik，且轉(zhuǎn)換函數(shù)GO(Ik,a)=Ij，當(dāng)a為終結(jié)符時(shí)，則置ACTION[k,a]為Sj

b)若項(xiàng)目A→?屬于Ik，則對(duì)a為任何終結(jié)符或‘#’，且滿足aFOLLOW(A)時(shí)，置ACTION[k,a]=rj，j為產(chǎn)生式在文法G‘中的編號(hào)

c)若GO(Ik,A)=Ij，則置GOTO[k,A]=j，其中A為非終結(jié)符，j為某一狀態(tài)號(hào)

d)若項(xiàng)目S‘→S

?屬于Ik，則置ACTION[k,#]=acc

e)其它填上“報(bào)錯(cuò)標(biāo)志”“改進(jìn)的”SLR(1)分析：仍有許多文法構(gòu)造的LR(0)項(xiàng)目集規(guī)范族存在的動(dòng)作沖突不能用SLR(1)方法解決仍有許多文法構(gòu)造的LR(0)項(xiàng)目集規(guī)范族存在的動(dòng)作沖突不能用LR(1)分析若項(xiàng)目集[A→?B]屬于I時(shí)，則[B→?]也屬于I把FIRST()作為用產(chǎn)生式歸約的搜索符（稱為向前搜索符），作為用產(chǎn)生式B→歸約時(shí)查看的符號(hào)集合（用以代替SLR(1)分析中的FOLLOW集），并把此搜索符號(hào)的集合也放在相應(yīng)項(xiàng)目的后面，這種處理方法即為L(zhǎng)R(1)方法LR(1)分析若項(xiàng)目集[A→?B]屬于I時(shí)，則[B→?LR(1)項(xiàng)目集族的構(gòu)造：針對(duì)初始項(xiàng)目S’→?S,#求閉包后再用轉(zhuǎn)換函數(shù)逐步求出整個(gè)文法的LR(1)項(xiàng)目集族。1）構(gòu)造LR（1）項(xiàng)目集的閉包函數(shù)

a)I的項(xiàng)目都在CLOSURE(I)中

b)若A→?B，a屬于CLOSURE(I)，B→

是文法的產(chǎn)生式，V*，bFIRST(a),則B→?,b也屬于CLOSURE(I)

c)重復(fù)b)直到CLOSURE(I)不再擴(kuò)大2)轉(zhuǎn)換函數(shù)的構(gòu)造

GOTO（I，X）=CLOSURE（J）

其中：I為L(zhǎng)R(1)的項(xiàng)目集，X為一文法符號(hào)

J={任何形如A→X?

,a的項(xiàng)目|A→?

X,a屬于I}LR(1)項(xiàng)目集族的構(gòu)造：針對(duì)初始項(xiàng)目S’→?S,#求閉包后I0:S’?

?S,#S?aAd,#S?bAc,#S?aec,#S?bed,#文法G‘：

(0)S’S

(1)SaAd

(2)SbAc

(3)Saec

(4)Sbed

(5)AeI1:S’?S?,#I2:Sa?Ad,#Sa?ec,#A?e,dI3:Sb?Ac,#Sb?ed,#A?e,cI4:SaA?d,#I5:Sae?c,#Ae?,dI6:SbA?c,#I7:Sbe?d,#Ae?,cI8:SaAd?,#I9:Saec?,#I10:SbAc?,#I11:Sbed?,#查看I5，I7中的沖突，體會(huì)LR(1)如何解決I0:文法G‘：

(0)S’S

(1)SaALR(1)分析表的構(gòu)造1)若項(xiàng)目[A→?a,b]屬于Ik，且轉(zhuǎn)換函數(shù)GO(Ik,a)=Ij，當(dāng)a為終結(jié)符時(shí)，則置ACTION[k,a]為Sj2)若項(xiàng)目[A→?,a]屬于Ik，則對(duì)a為任何終結(jié)符或‘#’，置ACTION[k,a]=rj，j為產(chǎn)生式在文法G‘中的編號(hào)3)若GO(Ik,A)=Ij，則置GOTO[k,A]=j，其中A為非終結(jié)符，j為某一狀態(tài)號(hào)4)若項(xiàng)目[S‘→S

?,#]屬于Ik，則置ACTION[k,#]=acc5)其它填上“報(bào)錯(cuò)標(biāo)志”LR(1)分析表的構(gòu)造1)若項(xiàng)目[A→?a,b]屬LR(1)項(xiàng)目集的構(gòu)造對(duì)某些同心集的分裂可能使?fàn)顟B(tài)數(shù)目劇烈的增長(zhǎng)LR(1)項(xiàng)目集的構(gòu)造對(duì)某些同心集的分裂可能使?fàn)顟B(tài)數(shù)目劇烈的文法G‘：

(0)S’S

(1)BaB

(2)SBB

(3)BbI0:S’?

?S,#S?BB,#B?aB,a/bB?b,a/bI1:S’?S?,#I2:SB?B,#B?aB,#B?b,#I5:SBB?,#I6:Sa?B,#B?aB,#B?b,#I9:BaB?,#I4:Bb?,a/bI3:Ba?B,a/bB?aB,a/bB?b,a/bI8:BaB?,a/bI7:Bb?,#SBbbBbbaaaaBBLR(1)項(xiàng)目集和轉(zhuǎn)換函數(shù)文法G‘：

(0)S’S

(1)BaB

(分析可發(fā)現(xiàn)I3和I6，I4和I7，I8和I9分別為同心集I3:Ba?B,a/bB?aB,a/bB?b,a/bI6:Sa?B,#B?aB,#B?b,#I4:Bb?,a/bI7:Bb?,#I8:BaB?,a/bI9:BaB?,#I3,6:Sa?B,a/b/#B?aB,a/b/#B?b,a/b/#I4,7:Bb?,a/b/#I8,9:BaB?,a/b/#合并為合并為合并為分析可發(fā)現(xiàn)I3和I6，I4和I7，I8和I9分別為同LALR(1)分析對(duì)LR(1)項(xiàng)目集規(guī)范族合并同心集，若合并同心集后不產(chǎn)生新的沖突，則為L(zhǎng)ALR(1)項(xiàng)目集。LALR(1)分析對(duì)LR(1)項(xiàng)目集規(guī)范族合并同心集，若合并合并同心集的幾點(diǎn)說(shuō)明同心集合并后心仍相同，只是超前搜索符集合為各同心集超前搜索符的和集合并同心集后轉(zhuǎn)換函數(shù)自動(dòng)合并LR(1)文法合并同心集后也只可能出現(xiàn)歸約-歸約沖突，而沒(méi)有移進(jìn)-歸約沖突合并同心集后可能會(huì)推遲發(fā)現(xiàn)錯(cuò)誤的時(shí)間，但錯(cuò)誤出現(xiàn)的位置仍是準(zhǔn)確的合并同心集的幾點(diǎn)說(shuō)明同心集合并后心仍相同，只是超前搜索符集合合并同心集后合并同心集后二義性文法在LR分析中的應(yīng)用對(duì)于某些二義文法，可以人為地給出優(yōu)先性和結(jié)合性的規(guī)定，從而可以構(gòu)造出比相應(yīng)非二義性文法更優(yōu)越的LR分析器二義性文法在LR分析中的應(yīng)用對(duì)于某些二義文法，可以人為地給出LR(0),SLR(1),LR(1),LR(k),LALR(1)LR(0)SLR(1):生成的LR(0)項(xiàng)目集如有沖突，則根據(jù)非終結(jié)符的FOLLOW集決定LR(1)、LR(k):項(xiàng)由心與向前搜索符組成，搜索符長(zhǎng)度為1或kLALR(1):對(duì)LR(1)項(xiàng)目集規(guī)范族合并同心集LR(0),SLR(1),LR(1),LR(k),LALR(作業(yè)p152,第6,11,18題作業(yè)p152,第6,11,18題演講完畢，謝謝觀看！演講完畢，謝謝觀看！LR分析自下而上語(yǔ)法分析算法之LR分析自下而上語(yǔ)法分析算法之復(fù)習(xí)：移進(jìn)-歸約分析復(fù)習(xí)：移進(jìn)-歸約分析文法G[S]：

(1)S→aAcBe

(2)A→b

(3)A→Ab

(4)B→dabbcde步驟符號(hào)棧輸入符號(hào)串動(dòng)作1）#abbcde#移進(jìn)2）#abbcde#移進(jìn)A3）#abbcde#歸約(A→b)4）#aAbcde#移進(jìn)A5）#aAbcde#歸約(A→Ab)6）#aAcde#移進(jìn)7）#aAcde#移進(jìn)B8）#aAcde#歸約(B→d)9）#aAcBe#移進(jìn)11）#S#接受S10）#aAcBe#歸約(S→aAcBe)分析符號(hào)串a(chǎn)bbcde是否G[S]的句子對(duì)輸入串a(chǎn)bbcde#的移進(jìn)-規(guī)約分析過(guò)程SaAcBeaAcdeaAbcdeabbcde文法G[S]：

(1)S→aAcBe

(2)A→在步驟3中，用A→b歸約在步驟5中，用A→Ab歸約問(wèn)題：何時(shí)移進(jìn)？何時(shí)歸約？用哪個(gè)產(chǎn)生式歸約？在步驟3中，用A→b歸約3）#abbcde#歸約(A→b)5）#aAbcde#歸約(A→Ab)4）#aAbcde#移進(jìn)6）#aAcde#移進(jìn)分析：已分析過(guò)的部分在棧中的前綴不同，而且移進(jìn)和歸約后棧中的狀態(tài)會(huì)發(fā)生變化

我們引入一個(gè)新的狀態(tài)棧來(lái)表示符號(hào)棧中的符號(hào)目前狀態(tài)用LR分析表來(lái)表示不同狀態(tài)下對(duì)于各輸入符號(hào)應(yīng)采取的動(dòng)作3）#abbcde#步驟符號(hào)棧輸入符號(hào)串