【正文】 2 , … , Am→ αm (4) 此外報(bào)錯(cuò)。bB, A→ α, B→r SLR（ 1）分析法 仔細(xì)分析構(gòu)造 LR(0)分析表的方法，容易看出使分析表出現(xiàn)多重定義的原因在于其中的規(guī)則 2，即對(duì)于每一個(gè)項(xiàng)目集 Ik中的歸約項(xiàng)目 A→ α ?，不管當(dāng)前輸入符號(hào)是什么，都將 ACTION表中第 K行的各個(gè)元素均置為 rj，其中 j為規(guī)則 A→ α的編號(hào) 。id ( id id * SLR（ 1）分析法 不難看出在 I1， I2， I9中既含有移進(jìn)項(xiàng)目，又含有歸約項(xiàng)目，因而這個(gè)表達(dá)式的文法不是 LR(0)文法。id I4: ( ( F T I5: F→id T T→ *F T I3:T→F →E T*F T→ → T→T (E) F→ →E 1 E→E+T 2 E→T 3 T→T *F 4 T→F 5 F→(E) 6 F→id E→E+ (E) F→ F F→ id I4: ( ( F T I5: F→id T T→ *F T I3:T→F →E T*F T→ → →S 1. S→A 2. S→B 3. A→ aAb 4. A→c 5. B→ aBb 6. B→d 狀態(tài) ACTION a b c d $ GOTO S A B 6 7 8 9 10 S8 r6 r6 r6 r6 r6 S10 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 0 1 2 3 4 5 S4 S5 S6 acc S4 S5 S6 r1 r1 r1 r1 r1 r2 r2 r2 r2 r2 r4 r4 r4 r4 r4 1 2 3 7 9 文法 G[S]的 LR(0)分析表 SLR（ 1）分析法 這個(gè)條件比較苛刻，對(duì)于大多數(shù)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，一般都不能滿足 LR(0)文法的條件，即使是描述一個(gè)算述表達(dá)式的簡(jiǎn)單文法也不是LR(0)文法。Bb I6: B→d c B→ →S a Ab A→ → b I8: A→ aAb) ) I5: S →(S) a I1: S39。(S) S → →S 1. S →(S) 2. S →a LR（ 0）分析法 由上述構(gòu)造過(guò)程可以看出， LR(0)分析器的 特點(diǎn) 是不需要向前查看輸入符號(hào)就能歸約，即 當(dāng)棧頂形成句柄，不管不一個(gè)輸入符號(hào)是什么，都可以立即進(jìn)行歸約而不會(huì)發(fā)生錯(cuò)誤。 S 識(shí)別活前綴的 DFA 0. S39?！鶶 a I2: S →( →S 1. S →(S) 2. S →a 識(shí)別文法規(guī)范句型活前綴的 DFA如下圖所示 ： LR（ 0）分析法 I0: S39?！鶶 ? 屬于 Ik，則置 ACTION[k, $]=acc。 LR（ 0）分析法 1. 若項(xiàng)目 A→ α?xβ屬 于 Ik, 且轉(zhuǎn)換函數(shù) GO(Ik , x)=Ii , 當(dāng) x 為終結(jié)符時(shí)，則置 ACTION[k, x]=Si。 S A B a c d c d I3: S→B a Bb B→ I2: S→A c B→ S S→ I9: A→ aB (4) LR(0)分析表的構(gòu)造 : 若一個(gè)文法 G的拓廣文法 G39。 LR（ 0）分析法 注意， DFA中的每一個(gè)狀態(tài)都是終態(tài) ，當(dāng) M到達(dá)它們時(shí)，識(shí)別出某規(guī)范句型的一個(gè)活前綴，對(duì)那些只含歸約項(xiàng)目的項(xiàng)目集，如I I I5 、 I I I10， 當(dāng) M到達(dá)這些狀態(tài)時(shí)，表示已識(shí)別出一個(gè)句柄，這些狀態(tài)稱為句柄識(shí)別態(tài) 。Ab B→ aa Ab A→ d I0: I1: S39。B A→ b b A B a S39。 LR（ 0）分析法 I7: A→ aAAb B→ aa Ab A→ d I0: I1: S39。B A→ →S 1. S→A 2. S→B 3. A→ aAb 4. A→c 5. B→ aBb 6. B→d LR（ 0）分析法 S39。 (b) 對(duì)初態(tài)項(xiàng)目集或其它已構(gòu)造的項(xiàng) 目集，應(yīng)用狀態(tài)轉(zhuǎn)移函數(shù) GO(I,X) 求出新的項(xiàng)目集（后繼狀態(tài)）。d } I0= LR（ 0）分析法 通過(guò)閉包函數(shù)（ CLOSURE）和狀態(tài)轉(zhuǎn)移函數(shù) (GO)很容易構(gòu)造出文法 G39。B, A→ d } = I4 { S39。aAb , A→ } = I1 GO(I0 , a ) = CLOSURE({A→a X ?∈ I} LR（ 0）分析法 例如： 初態(tài)的項(xiàng)目集 GO(I0 , S ) = CLOSURE({S39。d 0. S39。B， A→ S }，則 即為初態(tài)的項(xiàng)目集 I0 CLOSURE(I) { S39。 (b) 若 A→ α? Bβ屬于 CLOSURE(I)， 則每一形如 B →? γ的項(xiàng)目 也屬于 CLOSURE(I)。并加進(jìn)一個(gè)新的規(guī)則 S39。為左部的規(guī)則僅只有一個(gè) ，它是歸約項(xiàng)目的特殊情況，它表示整個(gè)句子已經(jīng)分析完畢，可以接受。 ④ 接受項(xiàng)目 ，形如 S39。 一個(gè) LR(0)項(xiàng)目指明了對(duì)文法規(guī)范句型活前綴的不同識(shí)別狀態(tài) , 由于不同的 LR(0)項(xiàng)目反映了在分析過(guò)程中棧頂?shù)牟煌闆r ，因此，我們可以根據(jù)圓點(diǎn)位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符， 將一個(gè)文法的全部 LR(0)項(xiàng)目進(jìn)行分類 。α 我們把文法 G中右部標(biāo)有圓點(diǎn)的規(guī)則稱為G的一個(gè) LR(0)項(xiàng)目。 LR（ 0）分析法 為了刻畫在分析過(guò)程中 , 文法的一個(gè)規(guī)則右部符號(hào)串已 有多大一部分被識(shí)別 ，我們可在文法中每個(gè)規(guī)則右部適當(dāng)位置上加一個(gè)圓點(diǎn)來(lái)表示。 LR（ 0）分析法 由此可知， LR（ 0）分析法 ?LR(0)項(xiàng)目 由活前綴定義可知，在一個(gè)規(guī)范句型的活前綴中，絕不含有句柄右邊的任何符號(hào)。 LR（ 0）分析法 例如，對(duì)前例，文法 G[S]的規(guī)范句型aaAbb的句柄是 aAb，棧中符號(hào)串為 aaAb，此句型的活前綴為 ε,a,aa,aaA,aaAb，它們均不含句柄右邊符號(hào) b。 2. 規(guī)范句型活前綴是指規(guī)范句型的前綴， 這種前綴不包含句柄右邊的任何符號(hào)。 構(gòu)造 LR分析表的 基本思想是 : 從給定的上下文無(wú)關(guān)文法直接構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的 DFA，然后再將 DFA轉(zhuǎn)換成一張 LR分析表。 0. S39。 輸出 ：若 W是句子，得到 W的自下而上 分析成功，否則輸出錯(cuò)誤信息。 總控程序也稱為驅(qū)動(dòng)程序。此時(shí)，分析棧 中只剩文法開(kāi)始符號(hào) S39。 2. LR分析表 分析動(dòng)作 (ACTION)表 狀態(tài)轉(zhuǎn)換 ( GOTO )表 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程 分析動(dòng)作表元素 ACTION[Si , a]規(guī)定了當(dāng)狀態(tài) Si面臨輸入符號(hào) a時(shí)應(yīng)執(zhí)行的動(dòng)作。 由此可知 ， LR分析器的每一步分析工作，都是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一確定的。 FOLLOW(T)={+,*,),$} Sm T E $ $ S0 X1 S1 分析棧 輸出 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程 分析棧用來(lái)存放分析過(guò)程中的歷史和展望信息。 總控程序 LR分析表 a1 規(guī)范歸約分析法的 關(guān)鍵 是在分析過(guò)程中如何確定分析棧棧頂?shù)姆?hào)串是否形成句柄。 大多數(shù)用無(wú)二義性上下文無(wú)關(guān)文法描述的語(yǔ)言都可以用 LR分析法進(jìn)行有效的分析 ， LR分析法 而且這種分析法分析速度快，并能準(zhǔn)確及時(shí)地指出輸入串的語(yǔ)法錯(cuò)誤和出錯(cuò)的位置。第 7章 自下而上的 LR(k)分析 本章討論 LR分析法 LR分析法 LR分析法是一種自下而上進(jìn)行規(guī)范歸約的語(yǔ)法分析方法。 這種分析法比遞歸下降分析法、預(yù)測(cè)分析法和算符優(yōu)先分析法對(duì)文法的限制要少得多。 LR分析法 LR分析法的基本思想 : LR分析法是一種規(guī)范歸約分析法。 它由 分析棧 、 分析表 和 總控程序 3個(gè)部分組成。 ai LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程 例如，對(duì)文法 G[E]: E→E+T| T T→T*F | F F→(E) | id 狀態(tài) Sm不僅表征了從分析開(kāi)始到現(xiàn)在已掃描過(guò)的輸入符號(hào)被歸約成 $E＋ T，而且由 Sm可以預(yù)測(cè)，如果輸入串沒(méi)有語(yǔ)法錯(cuò)誤，根據(jù)歸約時(shí)所用規(guī)則（非終結(jié)符 T的規(guī)則）推測(cè)出未來(lái)可能遇到的輸入符號(hào)僅是 中的任意一個(gè)符號(hào)。 + S0 S1 分 析 棧 示 意 圖 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程 若當(dāng)前讀到的輸入符號(hào)是‘ *’ ，根據(jù)文法可知‘ *’的優(yōu)先級(jí)高于‘＋’，棧頂尚未形成句柄 ， 則應(yīng)將‘ *’移入棧中； 若當(dāng)前讀到的輸入符號(hào)是‘＋’或）或‘ $’時(shí)，根據(jù)文法可知棧頂已形成句柄，則應(yīng)將符號(hào)串 E＋ T歸約為 E； 若當(dāng)前讀到的輸入符號(hào)不是上述四種符號(hào)之一，則表示輸入串有語(yǔ)法錯(cuò)誤。 一張 LR分析表由 和 兩部分組成， 狀態(tài)轉(zhuǎn)換表元素 GOTO[Si , X]規(guī)定了當(dāng)狀態(tài) Si面臨文法符號(hào) X時(shí)，應(yīng)轉(zhuǎn)移到的下一個(gè)狀態(tài)。 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程 ?接受 （ acc): 表示分析成功。 ?報(bào)錯(cuò) ：表示輸入串含有錯(cuò)誤，此時(shí)出現(xiàn)棧頂 的某一狀態(tài)遇到了不該遇到的輸入符 號(hào)。 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程 總控程序算法 ： 輸入 ：輸入串 W和 LR分析表。 ) ( error) ] a , [ ( ERROR S ACTION if else == ) ] a , [ ( r S ACTION if else j == ) ] a , [ ( S S ACTION if i == ) ]! a , [ ( acc S ACTION while = } a a { i中； 將下一個(gè)輸入符號(hào)讀入 進(jìn)棧； 和輸入符號(hào)將狀態(tài)} S A] , S GOTO[ A S′ | | | | { A j 〞= ? ? 進(jìn)棧； 和 ，將當(dāng)前棧頂狀態(tài)為 個(gè)輸入符號(hào)退棧； 個(gè)狀態(tài)和 將 歸約： 條規(guī)則 用第a a aLR分析器的邏輯結(jié)構(gòu)和工作過(guò)程 例 1 設(shè)文法 G′為： 相應(yīng)于文法的 LR分析表如下表所示。 LR分析器的關(guān)鍵部分是分析表的構(gòu)造。 例如，字符串 abc的前綴有 ε,a,ab,abc。 LR（ 0）分析法 這也就是說(shuō)， 在 LR分析過(guò)程中的任何時(shí)刻，棧中的文法符號(hào)應(yīng)是某一規(guī)范句型的活前綴 ，這是因?yàn)橐坏┚湫途浔跅５捻敳啃纬?，就?huì)立即被歸約，因此，只要輸入串已掃描過(guò)的部分保持可歸約成一個(gè)活前綴，那就意味著所掃描過(guò)的部分是正確的。 LR分析器的工作過(guò)