【正文】 章 語(yǔ)法分析例：已知例：已知 文法文法 G[A]：： A?(A)|d求求 其其 LR(0)的分析表，并判斷的分析表，并判斷 ((d))∈∈ L(G)?(3)LR(0)分析表分析表(2)識(shí)別文法活前綴的識(shí)別文法活前綴的 DFA解解 :(1)拓廣拓廣 文法文法(4)分析過(guò)程分析過(guò)程■課堂練習(xí)課堂練習(xí)Date 70信息學(xué)院 孫麗云第 4章 語(yǔ)法分析例：已知例：已知 文法文法 G[E]， 分析分析 i*i+i∈∈ L(G[E])?E?E+T|TT?T*F|FF?(E)|i出現(xiàn)問(wèn)題：由該文法識(shí)別活前綴的 DFA看的出來(lái)，有的有效項(xiàng)目集中存在著 移進(jìn)－歸約 沖突，不能用LR(0)分析方法進(jìn)行分析。解決方法：對(duì)含有沖突的項(xiàng)目集向前查看一個(gè)輸入符號(hào)，這種分析方法稱為 SLR(1)分析方法 。復(fù)習(xí)： LR(0)文法中不能存在 移進(jìn)－歸約 沖突或者歸約－歸約 沖突。■引例引例Date 71信息學(xué)院 孫麗云第 4章 語(yǔ)法分析解解 ：： (1)拓廣文法拓廣文法G的拓廣文法的拓廣文法 G?[E?]：：(0)E??E(4)T?F(1)E?E+T(5)F?(E)(2)E?T(6)F?i(3)T?T*F(2)識(shí)別文法的活前綴的識(shí)別文法的活前綴的 DFA(3)SLR(1)分析表分析表(4)分析過(guò)程分析過(guò)程例：已知例：已知 文法文法 G[E]， 并用并用 SLR(1)方法分析方法分析i*i+i∈∈ L(G[E])?E?E+T|TT?T*F|FF?(E)|iSLR(1)的分析過(guò)程與 LR(0)的分析過(guò)程完全一樣，唯一不同的是分析表！Date 72信息學(xué)院 孫麗云E’??EE??E+TE??TT??T*FT??FF??(E)F??idEE’?E?E?E?+TTE?T?T?T?*F(F?(?E)E??E+TE??TT??T*FT??FF??(E)F??idI0I1I2I6FT?F?I3F?id?idI5T I2F I3idI5(E?E+?TT??T*FT??FF??(E)F??id+* T?T*?FF??(E)F??idI7F?(E?)E?E?+TEI8T E?E+T?T?T?*FI9F I3id I5(F T?T*F?I10idI4(I4*I7)F?(E)?+ I6I11G?：： (0)E??E(1)E?E+T(2)E?T(3)T?T*F(4)T?F(5)F?(E)(6)F?id(2)識(shí)別文法的活前綴的識(shí)別文法的活前綴的 DFADate 73信息學(xué)院 孫麗云第 4章 語(yǔ)法分析若有效項(xiàng)目集中存在沖突動(dòng)作若有效項(xiàng)目集中存在沖突動(dòng)作 :I={X??.b?,A??.,B??.}將將 b移進(jìn)棧移進(jìn)棧將將 ?歸約為歸約為 A將將 ?歸約為歸約為 B解決方法：解決方法： 設(shè)當(dāng)前輸入符號(hào)為設(shè)當(dāng)前輸入符號(hào)為 x,1. 若若 x= b, 則移進(jìn)則移進(jìn) 。2. 若若 x?Follow(A), 則用則用 A? ? 進(jìn)行歸約進(jìn)行歸約 。3. 若若 x?Follow(B), 則用則用 B? ? 進(jìn)行歸約進(jìn)行歸約 。4. 其余情況報(bào)錯(cuò)其余情況報(bào)錯(cuò) .要求：要求：移進(jìn)項(xiàng)目的符號(hào)集移進(jìn)項(xiàng)目的符號(hào)集 ?FOLLOW(A) ?FOLLOW(B)= ?■SLR(1)分析法分析法Date 74信息學(xué)院 孫麗云第 4章 語(yǔ)法分析對(duì)于表達(dá)式文法的例子，對(duì)于表達(dá)式文法的例子， FOLLOW 集如下集如下：： G?：：(0)E??E(4)T?F(1)E?E+T(5)F?(E)(2)E?T(6)F?id(3)T?T*FI2:FOLLOW(E )∩{*}=ΦI9:FOLLOW(E )∩{*}=Φ∴∴ 可用可用 SLR(1)方法實(shí)現(xiàn)方法實(shí)現(xiàn)FOLLOW 集集E’ $E $，），）， +T $，），）， +， *F $，），）， +， *E?E+T?T?T?*FE?T?T?T?*FI2:I9:Date 75信息學(xué)院 孫麗云第 4章 語(yǔ)法分析●SLR分析表的構(gòu)造算法分析表的構(gòu)造算法輸入：一個(gè)拓廣文法輸入：一個(gè)拓廣文法 G?輸出：對(duì)于輸出：對(duì)于 G?的分析表的的分析表的 action子表和子表和 goto子表子表方法：方法：1.構(gòu)造構(gòu)造 G?的的 LR(0)項(xiàng)目集規(guī)范族。項(xiàng)目集規(guī)范族。2.對(duì)于狀態(tài)對(duì)于狀態(tài) Ii的分析動(dòng)作如下：的分析動(dòng)作如下：(a)若若 A??.aB?Ii且且 go(Ii,a)=Ijaction[i,a]=shiftj(b)若若 A??.?Ii,對(duì)于所有對(duì)于所有 a?Follow(A)action[i,a]=reduceA??,A?S?(c)若若 S??S.?Ii,action[i,$]=accept3.若若 go(Ii,A)=Ij,A?VN,則則 goto[i,A]=j4.分析表其余位置為分析表其余位置為 errorDate 76信息學(xué)院 孫麗云第 4章 語(yǔ)法分析(3)SLR分析表分析表 Follow(E)={$,+,)}ACTION GOTO+ * ( ) id $ E T F0 S4 S5 1 2 31 S6 ACC2 R2 S7 R2 R23 R4 R4 R4 R44 S4 S5 8 2 35 R6 R6 R6 R66 S4 S5 9 37 S4 S5 108 S6 S119 R1 S7 R1 R110 R3 R3 R3 R311 R5 R5 R5 R5Date 77信息學(xué)院 孫麗云第 4章 語(yǔ)法分析(4)id*id+id的的 LR分析過(guò)程分析過(guò)程分析棧 輸入串 動(dòng)作(1)0(2)0id5(3)0F3(4)0T2(5)0T2*7(6)0T2*7id5(7)0T2*7F10(8)0T2(9)0E1(10)0E1+6(11)0E1+6id5(12)0E1+6F3(13)0E1+6T9(14)0E1id*id+id$*id+id$*id+id$*id+id$id+id$+id$+id$+id$+id$id$$$$$shiftreducebyF?idreducebyT?FshiftshiftreducebyF?idreducebyT?T*FreducebyE?TshiftshiftreducebyF?idreducebyT?FreducebyE?E+TacceptDate 78信息學(xué)院 孫麗云第 4章 語(yǔ)法分析例：已知例：已知 文法文法 G[S]：： S→( S)S|ε， 求其求其 SLR(1)的的分析表，并判斷分析表，并判斷 ()()∈∈ L(G)?(3)SLR(1)分析表分析表(2)構(gòu)造 識(shí)別文法活前綴的識(shí)別文法活前綴的 DFA，并判斷用何種方法進(jìn)行分析，并判斷用何種方法進(jìn)行分析解解 : (1)拓廣拓廣 文法文法(4)分析過(guò)程分析過(guò)程注意：注意： |ε|=0，所以用，所以用 S → ε 進(jìn)行歸約時(shí)，不進(jìn)行歸約時(shí)，不用出棧，直接將用出棧，直接將 S入棧即可。入棧即可。LR(0)分析不了的， SLR(1)有可能能分析； LR(0)能分析的， SLR(1)都能分析！■課堂練習(xí)課堂練習(xí)Date 79信息學(xué)院 孫麗云第 4章 語(yǔ)法分析例：已知例：已知 文法文法 G[E]：： E→→ E+n|n，請(qǐng)使用恰當(dāng)，請(qǐng)使用恰當(dāng)?shù)淖韵露戏治龇椒ㄟM(jìn)行語(yǔ)法分析，并判斷的自下而上分析方法進(jìn)行語(yǔ)法分析，并判斷n+n∈∈ L(G)?(3)SLR(1)分析表分析表(2)識(shí)別文法活前綴的識(shí)別文法活前綴的 DFA解解 :(1)拓廣拓廣 文法文法(4)分析過(guò)程分析過(guò)程■課后作業(yè)課后作業(yè)Date 80信息學(xué)院 孫麗云第 4章 語(yǔ)法分析SLR(1)方法與 LR(0)方法的區(qū)別 僅在于有效項(xiàng)目集中有歸約項(xiàng)目時(shí)：在 LR(0)方法 中，若項(xiàng)目集 Ik含有 A???，則在狀態(tài)，則在狀態(tài) k時(shí)時(shí)，無(wú)論面臨什么輸入符號(hào)都用，無(wú)論面臨什么輸入符號(hào)都用 ““ A??”” 進(jìn)行歸約進(jìn)行歸約 ————即假定即假定 A??產(chǎn)生式編號(hào)為產(chǎn)生式編號(hào)為 j，則在分析表，則在分析表 ACTION部分部分，對(duì)應(yīng)狀態(tài)，對(duì)應(yīng)狀態(tài) k行的所有欄目都填行的所有欄目都填 ”” rj”” 。在在 SLR(1)方法方法 中，若項(xiàng)目集中，若項(xiàng)目集 Ik含有含有 A???，則在狀態(tài)，則在狀態(tài) k時(shí)時(shí)，僅當(dāng)輸入符號(hào)為，僅當(dāng)輸入符號(hào)為 a∈FOLLOW(A )時(shí)，才用時(shí)，才用 ” A??””進(jìn)行歸約，這樣在分析表進(jìn)行歸約，這樣在分析表 ACTION部分狀態(tài)部分狀態(tài) k行，所有行，所有b不屬于不屬于 FOLLOW(A)的欄目將空出來(lái)。若正好在的欄目將空出來(lái)。若正好在 b這一這一列有移進(jìn)項(xiàng)目不會(huì)產(chǎn)生沖突。列有移進(jìn)項(xiàng)目不會(huì)產(chǎn)生沖突。SLR(1)方法比方法比 LR(0)優(yōu)越，它可以解決更多的沖突。優(yōu)越，它可以解決更多的沖突。Date 81信息學(xué)院 孫麗云第 4章 語(yǔ)法分析例：已知例：已知 文法文法 G[S]，請(qǐng)判斷，請(qǐng)判斷 id:=id∈∈ L(G)?S→id|V:=EV→idE→→ V|n■引例引例該文法的 SLR[1]分析表中存在歸約－歸約沖突，該文法不能用 SLR[1]分析方法進(jìn)行分析。所以要采用另一種新的方法 ——LR[1] 分析方法對(duì)該文法進(jìn)行語(yǔ)法分析。Date 82信息學(xué)院 孫麗云第 4章 語(yǔ)法分析 ■LR(1)分析法分析法LR(1)項(xiàng)：LR(1)項(xiàng)是由 LR(0)項(xiàng)和一個(gè)先行記號(hào)組成的對(duì)，利用中括號(hào)將 LR[1]項(xiàng)寫(xiě)作： [A????， a]其中 A????是一個(gè) LR[0]項(xiàng)，稱為 “心 ”；而 a則是一個(gè)記號(hào)（先行），稱為 “向前搜索符 ”。a∈ FOLLOW(A )Date 83信息學(xué)院 孫麗云第 4章 語(yǔ)法分析假設(shè)有 LR[1]項(xiàng)目 [A???X?， a]， 其中 X是任意符號(hào)（終結(jié)符或非終結(jié)符），那么 X就有一個(gè)到項(xiàng)目 [A??X??， a]的轉(zhuǎn)換。轉(zhuǎn)換函數(shù)（ 1） I的任何項(xiàng)目都屬于 CLOSURE(I)。（ 2）若項(xiàng)目 [A???B?， a]屬于 CLOSURE(I)， B??是文法是文法中的一條規(guī)則，中的一條規(guī)則， b屬于 First（（ ?a），則），則 項(xiàng)目 [B???,b]屬于CLOSURE(I)。（ 3）重復(fù)（ 2）直到 CLOSURE(I)不再增大為止。項(xiàng)目集 I的閉包函數(shù)■LR(1)分析法分析法Date 84信息學(xué)院 孫麗云第 4章 語(yǔ)法分析■LR(1)分析表的構(gòu)造分析表的構(gòu)造(1)若項(xiàng)目 [A???a?， b]屬于 Ik且 GO(Ik,a)=Ij,a為終結(jié)符，則置 ACTION[k,a]為 “sj”；(3)若項(xiàng)目 [S’?S?， $]屬于 Ik，則置 ACTION[k,$]為“acc”。(4)若 GO[Ik,A]=Ij,A為非終結(jié)符，則置 GOTO（ Ik,A）=j；(5)分析表中凡不能用規(guī)則 (1)(4)填入信息的空白欄均置為 “error”。(2)若項(xiàng)目 [A???， a]屬于 Ik，則置 ACTION[k,a]為“rj”，其中 j是產(chǎn)生式的編號(hào) 。Date 85信息學(xué)院 孫麗云第 4章 語(yǔ)法分析例：已知例：已知 文法文法 G[S]:S→id|V:=EV→idE→→ V|n求其求其 LR(1)的分析表，并判斷的分析表，并判斷 id:=id∈∈ L(G)?(3)LR(1)分析表分析表(2)識(shí)別文法活前綴的識(shí)別文法活前綴的 DFA解解 :(1)拓廣拓廣 文法文法(4)分析過(guò)程分析過(guò)程Date 86信息學(xué)院 孫麗云第 4章 語(yǔ)法分析解 :(1)拓廣文法并對(duì)產(chǎn)生式進(jìn)行編號(hào)0：： S’→S1：： S→id2：： S→V:=E3：： V→id4：： E→→ V5：： E→→ n(2)識(shí)別文法活前綴的識(shí)別文法活前綴的 DFA[S→V.:=E,$][S→V:=.E,$][E→.V,$][E→.n ,$][V→.id,$][S?id.,$][V?id.,:=][S’→.S,$]