研究生院第四章-2-

第四章語法分析分析器的作用上下文無關文法的分析自上而下的分析自底向上的分析LR分析器二義文法的應用Yacc介紹自底向上的分析（1）什么是自底向上的分析使用了顯式棧來完成分析，棧中包括終結符號和非終結符號，以及其他的一些信息等$ InputString$… …… …$StartSymbol $ 接受分析器根據(jù)當前棧中的符號以及向前看的分析來決定分析器的動作：接受移進歸約報錯要對文法進行擴展也稱為移進-歸約分析，包括算符優(yōu)先分析、LR分析自底向上的分析（2）自底向上的分析與預測分析器的比較一般而言，自底向上的分析功能更強大 如：預測分析器不能處理左遞歸等，而自底向上的分析則不成問題對棧和向前看的符號的使用上：可以將輸入符號移進棧，直至它判斷出要執(zhí)行的動作為止進行動作判斷時可以使用棧中所有的符號開始時棧為空，而接受時棧中為文法的開始符號預測分析器描述的是從文法開始符號推導得到句子的過程,是一個匹配的過程，而自底向上的分析描述的推導過程的逆過程，是一個歸約的過程錯誤恢復：自底向上的分析所使用的特定算法的能力會影響到分析程序是否可早些檢測出錯誤的能力，規(guī)范的LR分析甚至在報告錯誤之前不做任何無效的歸約自底向上的分析器較為復雜自底向上的分析（3）自底向上分析舉例為輸入串構造分析樹是葉節(jié)點開始的，直至逆序得到根節(jié)點文法： S→aABe A→Abc|b B→d句子abbcde的歸約過程：

abbcde aAbcde aAde aABe S對應的最右推導：自底向上的分析（4）自底向上的分析（5）句柄定義：

右句型(最右推導可得到的句型)γ的句柄是一個產(chǎn)生式A→β以及γ中的一個位置，在這個位置可找到串β，用A代替β得到最右推導的前一個右句型。即如果有如下的最右推導序列

則在α后的A→β是αβω的句柄。非形式的說法： 一個串的句柄是和一個產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結符代表了最右推導逆過程的一步唯一性： 文法無二義時，句柄是唯一的；否則，句柄不一定唯一自底向上的分析（6）上例中的句柄

A→b是右句型abbcde的句柄，它的位置？

A→Abc是右句型aAbcde的句柄，它的位置？簡稱： 如果清楚地知道句柄的位置和應用的產(chǎn)生式的話，可以直接說子串β是αβω的句柄作用：移進-歸約分析器將終結符號從輸入移進到棧中，直到它能執(zhí)行一個歸約得到下一個右句型判斷分析中的下一個句柄是移進-歸約分析器的主要任務句柄總是為它的產(chǎn)生式構成一個完整的右部，而這個產(chǎn)生式是下一步歸約中應用的產(chǎn)生式，而且歸約發(fā)生時，句柄的最右邊的位置與棧的頂部對應自底向上的分析（7）句柄代表了最左邊的由一個內部節(jié)點和它所有的下一代組成的子樹句柄的右邊符號串只含有終結符號活前綴：一個規(guī)范句型的一個前綴，如果不含句柄后的任何符號，則稱它為該規(guī)范句型的一個活前綴活前綴不超過最右句柄的右端，因此在活前綴的右端加上一些終結符后可以使它成為右句型只要輸入串的已掃描部分可以歸約成一個活前綴，意味著所掃描的部分沒有錯誤自底向上的分析（8）例1：考慮表達式文法 E→E+E|E*E|（E）|id對于最右推導：但這個文法是有二義性的，因此存在另一個最右推導自底向上的分析（9）移進-歸約分析的實現(xiàn)用棧來保存文法符號，輸入緩沖區(qū)來保存待分析的串ω句柄的選擇：如何決定右句型中要歸約的子串當一個要歸約的子串是多個產(chǎn)生式的右部時，如何確定選擇哪個產(chǎn)生式動作（1）移進：將下一個輸入符號移進棧頂（2）歸約：句柄位于棧頂，必須在棧中確定完整的句柄，并決定用哪個產(chǎn)生式歸約（3）接受：分析成功（4）出錯：報告錯誤，調用錯誤恢復例程自底向上的分析（10） 棧 輸入 動作(1)$ id1+id2*id3$ 移進(2)$id1

+id2*id3$ 按E→id歸約(3)$E

+id2*id3$ 移進(4)$E+

id2*id3$ 移進(5)$E+id2

*id3$ 按E→id歸約(6)$E+E

*id3$ 移進(7)$E+E*

id3$ 移進(8)$E+E*id3

$ 按E→id歸約(9)$E+E*E

$ 按E→E*E歸約(10)$E+E

$ 按E→E+E歸約(11)$E

$ 接受自底向上的分析（11）移進-歸約分析的沖突移進-歸約沖突根據(jù)棧中所有的內容和下一個輸入符號不能決定是移進還是歸約歸約-歸約沖突根據(jù)棧中所有的內容和下一個輸入符號不能決定使用哪一個產(chǎn)生式歸約移進-歸約分析的沖突的解決利用移進優(yōu)先的約定可以解決一些二義性文法引起的沖突（如if…then…else…）對于有些情況要借助其它信息解決，如FORTRAN語言中數(shù)組引用和過程調用：

A(i,j,k)，i、j、k是數(shù)組的下標表達式還是參數(shù)？LR分析器（1）LR分析算法LR文法LR(0)分析SLR(1)分析LR(1)規(guī)范分析LALR(1)分析LR分析器（2）LR(k)分析L指從左到右掃描輸入，R指構造最右推導的逆，k指的是在決定分析動作時向前看的符號個數(shù)，(k)省略時，表示k是1LR(k)分析能力強大LR分析器能夠構造識別所有上下文無關文法寫的程序設計語言的結構LR分析方法是已知的最一般的無回溯移進-歸約方法，它能夠和其他移進-歸約方法一樣有效地實現(xiàn)LR方法能分析的文法類是預測分析法能分析的文法類的真超集LR分析器能及時察覺語法錯誤，快到自左向右掃描輸入的最大可能手工構造LR分析器的工作量太大，但可以利用專門的工具（如Yacc）來構造如果文法二義或有其它難以自左向右分析的結構，分析器的生成器能定位這些結構并報告LR分析器（3）LR分析算法組成驅動程序對所有的LR分析器是一樣的，只是分析表不同棧中存儲形如s0X1s1X2s2…Xmsm的串，其中sm在棧頂，Xi是文法符號，si是狀態(tài)符號，它概括了棧中它下面部分所包含的信息LR分析器（4）分析表包括動作函數(shù)action和轉移函數(shù)goto兩部分組成根據(jù)棧頂當前的狀態(tài)sm和當前的輸入符號ai訪問action[sm,ai]，取值包括：移進s，其中s是一個狀態(tài)按文法產(chǎn)生式A→β歸約接受出錯函數(shù)goto取狀態(tài)和文法符號為變元，產(chǎn)生一個狀態(tài)LR分析器棧中的文法符號總是形成活前綴在LR(0)分析、SLR分析、規(guī)范LR分析和LALR分析中，構造一個識別文法G的活前綴的確定有限自動機，則goto函數(shù)是這個自動機的狀態(tài)轉換函數(shù)，初始狀態(tài)是初啟時置于LR分析器棧中的狀態(tài)LR分析器（5）LR分析器的格局是二元組它的第一個成分是棧的內容，第二個成分是尚未接收的輸入：(s0X1s1X2s2…Xmsm，aiai+1…an$)，這個格局代表右句型X1X2…Xmaiai+1…an動作：移進： 如果action[sm,ai]=移進s，分析器執(zhí)行移進動作，進入格局(s0X1s1X2s2…Xmsmais，ai+1…an$)，其中s=goto[sm,ai]LR分析器（6）歸約： 如果action[sm,ai]=歸約A→β,則分析器執(zhí)行歸約,進入格局(s0X1s1X2s2…Xm-rsm-rAs，aiai+1…an$),其中s=goto[sm-r,A]，r是β的長度， 完成這個動作時，首先從棧中彈出2r個符號（包括r個狀態(tài)符號和r個文法符號，這些文法符號剛好匹配產(chǎn)生式右部β），然后將產(chǎn)生式左邊的非終結符A和goto[sm-r,A]的狀態(tài)s壓入棧 在歸約動作時執(zhí)行與歸約產(chǎn)生式相關的語義動作接受： 如果action[sm,ai]=接受，分析完成出錯： 如果action[sm,ai]=出錯，分析器發(fā)現(xiàn)錯誤，調用錯誤恢復例程LR分析器（7）LR分析算法輸入：LR分析表和輸入串ω輸出：若ω是句子，得到ω的自下而上分析，否則報錯方法： 將初始狀態(tài)s0在分析器的棧頂，ω$在輸入緩沖區(qū) 讓ip指向ω$的第一個符號

repeatforeverbegin

令s是棧頂?shù)臓顟B(tài)，a是ip指向的符號 ifaction[s,a]=移進s’thenbegin

把a和s’依次壓入棧 推進ip指向下一個輸入符號

end elseifaction[s,a]=歸約A→βthenbegin

棧頂彈出2*|β|個符號 令s’是現(xiàn)在的棧頂狀態(tài) 把A和goto[s’,A]壓入棧 輸出產(chǎn)生式A→β或作相關的語義動作

end elseifaction[s,a]=接受thenreturn elseerror() endLR分析器（8）表達式文法：對文法產(chǎn)生式標號 (1)E→E+T (2)E→T (3)T→T*F (4)T→F (5)F→(E) (6)F→id為了表示的簡便，對各類動作如下簡化表示： (1)si表示移進，把當前輸入符號和狀態(tài)i壓進棧 (2)rj表示按第j個產(chǎn)生式進行歸約 (3)acc表示接受 (4)空白表示出錯LR分析器（9）LR分析器（10） 棧 輸入 動作(1)0 id*id+id$ 移進(2)0id5

*id+id$ 按F→id歸約(3)0F3

*id+id$ 按T→F歸約(4)0T2

*id+id$ 移進(5)0T2*7

id+id$ 移進(6)0T2*7id5

+id$ 按F→id歸約(7)0T2*7F10+id$ 按T→T*F歸約(8)0T2

+id$ 按E→T歸約(9)0E1

+id$ 移進(10)0E1+6

id$ 移進(11)0E1+6id5$ 按F→id歸約(12)0E1+6F3 $ 按T→F歸約(13)0E1+6T9$ 按E→E+T歸約(14)0E1 $ 接受LR分析器（11）LR文法定義：一個文法，如果能夠為它構造出LR分析表，且表的條目都唯一性質：一個文法如果是LR的，只要保證當句柄出現(xiàn)在棧頂時，自左向右掃描的移進-歸約分析器能夠及時識別它便足夠了如果句柄出現(xiàn)在棧頂時，LR分析器不需要掃描整個棧，棧頂?shù)臓顟B(tài)符號包含了所需要的一切信息LR(k)文法：最多向前看k個符號就可以決定動作的LR分析器分析的文法稱為LR(k)文法與LL文法的區(qū)別：LR(k)文法：在看見了產(chǎn)生式右部推導出的所有東西和k個向前看的符號后，能識別產(chǎn)生式右部的出現(xiàn)LL(k)文法：在看見了右部推出的前k個符號就能識別所使用的產(chǎn)生式LR分析器（12）LR(0)項目的有限自動機LR(0)項目（LR(0)item，簡稱項目、item）：是在右部帶有區(qū)分位置（一般是用一個“.”表示這個區(qū)分的位置）的產(chǎn)生式如果A→α是一個產(chǎn)生式，且α=βγ，則A→β.γ是LR(0)項目，其中β和γ可以是空串ε。如果A→ε是一個產(chǎn)生式，則它只對應了一個項目A→.項目的解釋：項目A→β.γ表示已經(jīng)看到了β(此時，β必須出現(xiàn)在棧的頂部)，且可能從下面的輸入符號中獲取γ項目A→.α表示將要用產(chǎn)生式A→α來識別A，這種項目也稱為初始項目項目A→α.表示α出現(xiàn)在分析棧的頂部，而且如果A→α在下一個歸約中使用，則它可能是句柄，這種項目稱為完整項目LR分析器（13）例2：考慮文法S→(S)S|ε，給出LR(0)項目首先構造拓廣文法：加入一個產(chǎn)生式S’→S，分析器執(zhí)行歸約S’→S時，表示分析成功在構造LR(0)項目，共8個

S’→.S

S’→S.

S→.(S)S

S→(.S)S

S→(S.)S

S→(S).S

S→(S)S.

S→.LR分析器（14）LR(0)項目集合的有限自動機的構造若有項目A→α.γ，且假設γ以符號X（終結符或非終結符）開始（即γ=Xη），則讀入X后，項目變?yōu)锳→αX.η，在自動機中有一個標記為X的由狀態(tài)A→α.Xη到狀態(tài)A→αX.η的轉換 這個轉換的意義是：如果X是一個終結符，表示X在分析中被從輸入移進到棧的頂部如果X是一個非終結符，可以理解為是用產(chǎn)生式X→β歸約時發(fā)生，這個歸約前面必須有一個β的識別，而由初始項目X→.β給出的狀態(tài)表明這個識別的開始，此時，必須考慮加入下面的轉換如果X是非終結符，則對每個項目A→α.Xη，添加一個到項目X→.β的ε轉換（如果以X為左部的產(chǎn)生式多于一個，則每個都要如此處理）LR分析器（15）自動機的初始狀態(tài)與分析程序的初始狀態(tài)對應：棧是空的，且將要識別一個文法的開始符號S，但由于S可能出現(xiàn)在多個產(chǎn)生式的左部，所以拓廣文法，加入S’和產(chǎn)生式S’→S，S’是拓廣文法的開始符號，S’→.S是自動機的開始狀態(tài)自動機的接受狀態(tài)：此處的自動機是用于了解分析的狀態(tài)，而不是完全識別串，因此分析程序本身決定何時接受，自動機不必關心，所以可以沒有接受狀態(tài)LR分析器（16）例2對應的NFA：LR分析器（17）例2對應的DFA：LR分析器（18）文法的LR項目的閉包計算對于文法G的LR項目集I，閉包closure(I)的計算：J:=Irepeat forJ的每個項目A→α.Bβ和G的每個產(chǎn)生式B→γ，若B→.γ 不在J中do

把B→.γ加入Juntil沒有更多的項目可以加入JLR(0)分析算法僅根據(jù)棧中的符號就可以決定動作若項目A→α.aβ屬于Ik且GO1(Ik，a)=Ij，a為終結符，則置ACTION[k，a]為sj若項目A→α.屬于Ik，那么對任何終結符a（或結束符$），置ACTION[k，a]為rj(假定產(chǎn)生式A→α是文法的第j個產(chǎn)生式)若項目S’→S.屬于Ik，則置ACTION[k，$]為接受若GO[Ik，A]=Ij

，A為非終結符，則置goto[k，A]=j。分析表中凡不能用規(guī)則1~4填入信息的空白格均置為報錯1 此處的GO是指自動機的狀態(tài)轉換，而不是LR分析中的轉移表（用goto表示）LR分析器（19）項目的分類：核心項目：包括初始項目S’→.S和所有點不在左端的項目非核心項目：它們的點都在左端項目分類的意義：DFA應用的項目集是核心項目的閉包形成若有一個文法，核心項目唯一地判斷出狀態(tài)以及它的轉換，則只需指出核心項目就可以完整地表示出項目集合的DFALR分析器（20）SLR分析規(guī)范的LR(0)族：提供了構造SLR分析表的基礎對于LR(0)規(guī)范族中的項目集：I={X→α.bβ,

A→α., B→α.}LR(0)無法區(qū)分這三個不沖突的項目，此時要考察FOLLOW(A)和FOLLOW(B)集合構造算法：C:={closure({[S’→.S]})}repeat for對C的每個項目集I和每個文法符號X，若 goto(I,X)非空且不在C中do

把goto(I,X)加入C中until沒有更多的項目可以加入CLR分析器（21）例3：拓廣的表達式文法： E’→E E→E+T|T T→T*F|F F→(E)|id對應的LR(0)項目集規(guī)范族如下：

I0: E’→.E I5: F→id. E→.E+T E→.T I6: E→E+.T T→.T*F T→.T*F T→.F T→.F F→.(E) F→.(E) F→.id F→.idLR分析器（22）

I1: E’→E. I7: T→T*.F E→E.+T F→.(E) F→.id I2: E→T. T→T.*F I8: F→(E.) E→E.+T I3: T→F. I9: E→E+T. I4: F→(.E) T→T.*F E→.E+T E→.T I10: T→T*F. T→.T*F T→.F I11: F→(E). F→.(E) F→.idLR分析器（23）LR分析器（24）如果將這個DFA中的每個狀態(tài)定為接受狀態(tài)，而I0定為初態(tài)，則這個DFA識別文法的活前綴對于項目A→β1.β2對活前綴αβ1是有效的，是指存 在推導序列A→β1.β2對活前綴αβ1有效表明當αβ1在分析棧頂時如果β2是ε，則A→β1是句柄，應該用這個產(chǎn)生式歸約如果β2不是ε，則表示句柄還沒有完全進棧，要繼續(xù)移進同一個活前綴的兩個有效項目可能對應了不同的動作，引起了沖突這種沖突可以通過向前看幾個符號解決，也可以通過其它方式解決LR分析器（25）SLR分析表的構造輸入：拓廣文法G’輸出：G’的SLR分析表函數(shù)action和goto方法：(1)構造C={I0,I1,…,In}，即G’的LR(0)項目集規(guī)范族 (2)狀態(tài)i從Ii構造，它的動作如下確定： (a)如果[A→α.aβ]在Ii中，并且δ(Ii,a)=Ij，則置

action(i,a)為sj,含義是把a和狀態(tài)j移進棧,a必須為終結符 (b)如果[A→α.]在Ii中，則對FOLLOW(A)中的所有a，置

action(i,a)為rj,j是產(chǎn)生式A→α的編號。含義是按產(chǎn)生 式A→α歸約，這里A不是S’ (c)如果[S’→S.]在Ii中，則置action(i,$)=acc，表示接受 (3)對所有的非終結符A，使用下面的規(guī)則構造狀態(tài)i的轉移： 如果δ(Ii,A)=Ij，則goto[i,A]=j (4)不能由規(guī)則(2)和(3)定義的條目置為出錯 (5)分析器的初始狀態(tài)是包含[S’→.S]的項目集對應的狀態(tài)LR分析器（26）如果在規(guī)則(2)的構造中產(chǎn)生的動作有沖突，則該文法不是SLR(1)文法由上述算法生成的分析表成為文法G的SLR(1)分析表每個SLR(1)文法都不是二義的存在非二義的文法，這個文法不是SLR(1)的對于在棧頂狀態(tài)s中的任何項目A→α.Xβ，當X是一個終結符，且X在FOLLOW(B)中時，s中沒有完整的項目B→γ.。（若不滿足，則存在移進-歸約沖突）對于在s中的任何兩個完整項目A→α.和B→γ.，F(xiàn)OLLOW(A)與FOLLOW(B)的交集為空集。（若不滿足，則存在歸約-歸約沖突）SLR(1)分析能力比LR(0)強，但仍然不能夠滿足要求LR分析器（27）LR(1)規(guī)范分析SLR分析不能解決某些移進-歸約沖突，而LR(1)規(guī)范分析可以，參考陳意云書的例3.31和3.32LR(1)項目：[A→α.β，a]，其中A→αβ是產(chǎn)生式，a是終結符號或$。1是指第二個成分的長度，這個成分稱為項目的搜索符搜索符對β非空的項目[A→α.β，a]是不起作用的，但對項目[A→α.，a]，表示只有在下一個輸入符號為a時才能要求按A→α歸約SLR(1)和LR(1)對向前看符號的使用的不同：SLR(1)是在LR(0)項目的DFA構造完成后才考慮提供向前看的符號，DFA的構造中不考慮向前看的符號LR(1)是在一開始就考慮向前看符號，DFA的構造是在考慮向前看符號的基礎上進行的LR分析器（28）LR(1)項目[A→α.β，a]對活前綴γ是有效的，如果存 在著推導其中：γ=δαa是ω的第一個符號，或者ω是ε則a是$例：考慮文法S→BB B→aB|b

對于最右推導：，項目[B→a.B，a]對于活前綴γ=aaa是有效的，δ=aa，A=B，ω=ab，α=a和β=B 對于最右推導：，項目[B→a.B，$]對于活前綴Baa是有效的LR分析器（29）有效的LR(1)項目集族的構造方法本質上和構造LR(0)項目集規(guī)范族的方法是一樣的Closure函數(shù)的構造：考慮對活前綴γ有效的項目集中的項目[A→α.Bβ，a]。 必定存在一個最右推導 ,其中γ=δα ，假定βax推出終結符串by，則對每個形式B→η的產(chǎn) 生式，有推導 ，于是[B→.η，b]對 γ有效b可能是從β推出的第一個終結符，或者β是空串，b就成了a，即b=FIRST(βax)，但在此處，考慮到a是終結符，所以有FIRST(βax)=FIRST(βa)LR分析器（30）Closure函數(shù)構造的算法：Functionclosure(I)Begin repeat for對I的每個項目[A→α.Bβ，a]，G’中的每個產(chǎn)生式B→γ 和FIRST(βa)的每個終結符b,如果[B→.γ，b]不在I中do

把[B→.γ，b]加到I中

until再沒有項目可加到I中

returnIendLR分析器（31）Goto函數(shù)的構造： functiongoto(I,X)

begin

令J是項目[A→αX.β，a]的集合，使得[A→α.Xβ，a] 在I中

returnclosure(J) end項目的構造： procedureitems(G’)

begin C:=closure({[S’→.S，$]}) repeat forC的每個項目I和每個文法符號X，若goto(I,X)非空且 不在C中do

把goto(I,X)加入C中

until再沒有項目集可以加入C中 endLR分析器（31）規(guī)范的LR(1)分析表的構造與SLR分析表的構造相似輸入：拓廣文法G’輸出：G’的LR(1)分析表函數(shù)action和goto方法：(1)構造C={I0,I1,…,In}，即G’的LR(1)項目集規(guī)范族 (2)狀態(tài)i從Ii構造，它的動作如下確定： (a)如果[A→α.aβ,b]在Ii中，并且goto(Ii,a)=Ij，則置

action(i,a)為sj,含義是把a和狀態(tài)j移進棧,a必須為終結符 (b)如果[A→α.,a]在Ii中且A不是S’，則置action(i,a)為rj, j是產(chǎn)生式A→α的編號。含義是按產(chǎn)生式A→α歸約 (c)如果[S’→S.,$]在Ii中，則置action(i,$)=acc，表示接受 (3)對所有的非終結符A，使用下面的規(guī)則構造狀態(tài)i的轉移： 如果DFA的轉換函數(shù)goto(Ii,A)=Ij，則goto[i,A]=j (4)不能由規(guī)則(2)和(3)定義的條目置為出錯 (5)分析器的初始狀態(tài)是包含[S’→.S,$]的項目集對應的狀態(tài)LR分析器（32）如果這個分析表中的動作函數(shù)沒有多重定義的條目，則這個文法是LR(1)文法在實際中，除非有二義性，幾乎所有合理的程序設計語言的文法都是LR(1)文法LR(1)分析過于復雜，產(chǎn)生的項目集合過多，尤其是很多項目集合的不同僅僅是因為第二個成分的不同例4：考慮拓廣文法

S’→S S→CC C→cC|dLR分析器（33）LR分析器（34）LR分析器（35）LALR(1)分析（lookahead-LR分析）引入LALR分析：LR(1)項目集合的DFA狀態(tài)過于龐大，且很多狀態(tài)的引入只是因為向前看的符號的不同構造同心的LR(1)項目集：它們的第一個成分集合相同LR(1)項目的DFA的狀態(tài)核心是LR(0)項目的DFA的一個狀態(tài)若具有相同核心的LR(1)項目的DFA的兩個狀態(tài)s1和s2，假設在符號X上有一個從狀態(tài)s1到狀態(tài)t1的轉換，則在X上必然有一個從狀態(tài)s2到一個狀態(tài)t2的轉換，且狀態(tài)t1和t2具有相同的核心LALR具有和SLR一樣個數(shù)的狀態(tài)，但保留了LR分析的一些特征，能力比SLR要強LALR分析表的構造：將具有相同核心的LR(1)項目合并，動作和轉移函數(shù)也做相應的合并LR分析器（36）LALR(1)分析表是在LR(1)分析表的基礎上構造的，但可能引入LR(1)分析中不存在的沖突不會引入移進-歸約沖突（因為如果LALR(1)分析表中存在這類沖突，則在同心項目合并前的LR(1)分析表中必定存在沖突）可能引進歸約-歸約沖突LR(1)能發(fā)現(xiàn)的錯誤，LALR(1)也能發(fā)現(xiàn)，只是在報錯前可能要多作一些虛假的歸約對例4的LR(1)分析，構造LALR(1)分析：合并同心項目：I36：C→c.C,c/d/$ C→.cC,c/d/$ C→.d,c/d/$ I47：C→d.,c/d/$ I89：C→cC.,c/d/$LR分析器（37）考慮輸入串ccd$，對于LR(1)分析，把0c3c3d4入棧，在狀態(tài)4發(fā)現(xiàn)錯誤而對于LALR(1)分析，把0c36c36d47入棧 然后用C→d歸約，棧的內容變?yōu)?c36c36C89 再用C→cC歸約，棧的內容變?yōu)?c36C89 第二次用C→cC歸約，棧的內容變?yōu)?C2此時發(fā)現(xiàn)錯誤二義文法的應用二義性文法不是LR文法，但二義性文法在一些情況下的表示更為簡單在LR分析中消除二義性的規(guī)則使用優(yōu)先級和結合規(guī)則來解決分析動作的沖突移進優(yōu)先于歸約的規(guī)則可以解決最長匹配問題如懸掛else的問題特殊情況產(chǎn)生式引起的二義性，可能導致歸約-歸約沖突，可以規(guī)定此時按特殊情況產(chǎn)生式歸約

如文法：E→EsubEsupE|EsubE|EsupE|{E}|c 如果描述EsubEsupE的文法符號和狀態(tài)序列已經(jīng)在分析棧中，當面臨}或$時，選擇下面的哪個產(chǎn)生式歸約？

E→EsubEsupE E→EsupE

此時可以通過規(guī)定哪個產(chǎn)生式優(yōu)先歸約來解決自底向上分析程序中的錯誤校正（1）綜述：何時發(fā)現(xiàn)錯誤？當分析表中檢測到一個空白項（或錯誤項），表示發(fā)現(xiàn)了錯誤LR分析中訪問轉移表不會發(fā)現(xiàn)錯誤如何更好地發(fā)現(xiàn)錯誤？盡可能多的空白項可以使得分析程序盡可能早地發(fā)現(xiàn)錯誤，這樣的錯誤信息更有意義，且是確定的但過多的空白項使得分析表過于龐大（考慮LALR和LR分析），如果減少錯誤項，可能在報錯前會有一些不必要的歸約動作發(fā)生，使得報錯不準確特定的自底向上分析算法的能力會影響分析程序是否可以更早地檢測錯誤的能力，如LR(0)、SLR(1)、LALR(1)、LR(1)等的檢錯能力不一樣由于分析算法的不同，錯誤被延后報告時，雖然可能會引入一些無用的歸約動作，但是不會移進錯誤的符號自底向上分析程序中的錯誤糾正（2）錯誤的糾正：緊急方式：LR分析為例，試圖分離含錯誤的語法短語從棧頂開始退棧，直至出現(xiàn)狀態(tài)s為止，它有選定的非終結符A的轉移；拋棄0個或多個輸入符號，直至找到符號a為止，它能合法地跟隨A（A的選擇可能是不唯一的，通常表示較大的程序結構的非終結符，如表達式、語句或程序塊等）；分析器再把狀態(tài)goto[s,A]壓進棧，恢復正常分析短語級恢復考察LR分析表的每個出錯條目和根據(jù)語言的使用情況決定可能引起該條目的輸入錯誤，然后為該條目編一個適當?shù)腻e誤恢復例程自底向上分析程序中的錯誤糾正（3）例5：考慮文法：E→E+E|E*E|(E)|id自底向上分析程序中的錯誤糾正（3） 這個例子中錯誤的糾正仍然可能會有一些多余的歸約（因為將一些出錯項目改為了歸約），出錯例程：

e1:/*狀態(tài)0,2,4,5要求輸入符號為運算對象首字符，即id或(，遇 到+、*或$時調用本例程*/ 把一個假想的id推進棧，上面以狀態(tài)3覆蓋 給出診斷信息“缺少運算對象”

e2:/*狀態(tài)0,1,2,4,5遇到)時調用本例程*/ 刪除輸入中的) 給出診斷信息“不配對的右括號”

e3:/*狀態(tài)1,6要求輸入符號為