研究生院第四章_2_

1、1第四章第四章 語法分析語法分析分析器的作用分析器的作用上下文無關文法的分析上下文無關文法的分析自上而下的分析自上而下的分析自底向上的分析自底向上的分析LR分析器分析器二義文法的應用二義文法的應用Yacc介紹介紹2自底向上的分析（自底向上的分析（1）什么是自底向上的分析什么是自底向上的分析使用了顯式棧來完成分析，棧中包括終結符號和非終結符使用了顯式棧來完成分析，棧中包括終結符號和非終結符號，以及其他的一些信息等號，以及其他的一些信息等$InputString$StartSymbol $接受接受分析器根據(jù)當前棧中的符號以及向前看的分析來決定分析分析器根據(jù)當前棧中的符號以及向前看的分析來決定分析器

2、的動作：器的動作：接受接受移進移進歸約歸約報錯報錯要對文法進行擴展要對文法進行擴展也稱為移進也稱為移進-歸約分析，包括算符優(yōu)先分析、歸約分析，包括算符優(yōu)先分析、LR分析分析3自底向上的分析（自底向上的分析（2）自底向上的分析與預測分析器的比較自底向上的分析與預測分析器的比較一般而言，自底向上的分析功能更強大一般而言，自底向上的分析功能更強大如：預測分析器不能處理左遞歸等，而自底向上的分析則不如：預測分析器不能處理左遞歸等，而自底向上的分析則不成問題成問題對棧和向前看的符號的使用上：對棧和向前看的符號的使用上：可以將輸入符號移進棧，直至它判斷出要執(zhí)行的動作為止可以將輸入符號移進棧，直至它判斷出要

3、執(zhí)行的動作為止進行動作判斷時可以使用棧中所有的符號進行動作判斷時可以使用棧中所有的符號開始時棧為空，而接受時棧中為文法的開始符號開始時棧為空，而接受時棧中為文法的開始符號預測分析器描述的是從文法開始符號推導得到句子的過程預測分析器描述的是從文法開始符號推導得到句子的過程,是一個匹配的過程，而自底向上的分析描述的推導過程的是一個匹配的過程，而自底向上的分析描述的推導過程的逆過程，是一個歸約的過程逆過程，是一個歸約的過程錯誤恢復：自底向上的分析所使用的特定算法的能力會影錯誤恢復：自底向上的分析所使用的特定算法的能力會影響到分析程序是否可早些檢測出錯誤的能力，規(guī)范的響到分析程序是否可早些檢測出錯誤的

4、能力，規(guī)范的LR分分析甚至在報告錯誤之前不做任何無效的歸約析甚至在報告錯誤之前不做任何無效的歸約自底向上的分析器較為復雜自底向上的分析器較為復雜4自底向上的分析（自底向上的分析（3）自底向上分析舉例自底向上分析舉例為輸入串構造分析樹是葉節(jié)點開始的，直至逆序為輸入串構造分析樹是葉節(jié)點開始的，直至逆序得到根節(jié)點得到根節(jié)點文法：文法：SaABeAAbc | bBd句子句子abbcde的歸約過程：的歸約過程：abbcdeaAbcdeaAdeaABeS對應的最右推導：對應的最右推導：abbcdeaAbcdeaAdeaABeSrmrmrmrm5自底向上的分析（自底向上的分析（4）A Ab ba ab bc

5、 cd de eA AB BS SabbcdeaAbcdeaAdeaABeSrmrmrmrm6自底向上的分析（自底向上的分析（5）句柄句柄定義：定義：右句型右句型(最右推導可得到的句型最右推導可得到的句型)的的句柄句柄是一個產(chǎn)生式是一個產(chǎn)生式A以及以及中的一個位置，在這個位置可找到串中的一個位置，在這個位置可找到串，用用A代代替替得到最右推導的前一個右句型。即如果有如下的最右得到最右推導的前一個右句型。即如果有如下的最右推導序列推導序列則在則在后的后的A是是的句柄。的句柄。非形式的說法：非形式的說法：一個串的句柄是和一個產(chǎn)生式右部匹配的子串，并且，把一個串的句柄是和一個產(chǎn)生式右部匹配的子串，并

6、且，把它歸約成該產(chǎn)生式左部的非終結符代表了最右推導逆過程它歸約成該產(chǎn)生式左部的非終結符代表了最右推導逆過程的一步的一步唯一性：唯一性：文法無二義時，句柄是唯一的；否則，句柄不一定唯一文法無二義時，句柄是唯一的；否則，句柄不一定唯一ASrm*rm7自底向上的分析（自底向上的分析（6）上例中的句柄上例中的句柄Ab是右句型是右句型abbcde的句柄，它的位置？的句柄，它的位置？AAbc是右句型是右句型aAbcde的句柄，它的位置？的句柄，它的位置？簡稱：簡稱：如果清楚地知道句柄的位置和應用的產(chǎn)生式的話，可以直如果清楚地知道句柄的位置和應用的產(chǎn)生式的話，可以直接說子串接說子串是是的句柄的句柄作用：作用

7、：移進移進-歸約分析器將終結符號從輸入移進到棧中，直到歸約分析器將終結符號從輸入移進到棧中，直到它能執(zhí)行一個歸約得到下一個右句型它能執(zhí)行一個歸約得到下一個右句型判斷分析中的下一個句柄是移進判斷分析中的下一個句柄是移進-歸約分析器的主要任歸約分析器的主要任務務句柄總是為它的產(chǎn)生式構成一個完整的右部，而這個句柄總是為它的產(chǎn)生式構成一個完整的右部，而這個產(chǎn)生式是下一步歸約中應用的產(chǎn)生式，而且歸約發(fā)生產(chǎn)生式是下一步歸約中應用的產(chǎn)生式，而且歸約發(fā)生時，句柄的最右邊的位置與棧的頂部對應時，句柄的最右邊的位置與棧的頂部對應8自底向上的分析（自底向上的分析（7）句柄代表了最左邊的由一個內部節(jié)點和它所有的下一代

8、組句柄代表了最左邊的由一個內部節(jié)點和它所有的下一代組成的子樹成的子樹句柄的右邊符號串只含有終結符號句柄的右邊符號串只含有終結符號活前綴：一個規(guī)范句型的一個前綴，如果不含句柄后的任活前綴：一個規(guī)范句型的一個前綴，如果不含句柄后的任何符號，則稱它為該規(guī)范句型的一個活前綴何符號，則稱它為該規(guī)范句型的一個活前綴活前綴不超過最右句柄的右端，因此在活前綴的右端加上一活前綴不超過最右句柄的右端，因此在活前綴的右端加上一些終結符后可以使它成為右句型些終結符后可以使它成為右句型只要輸入串的已掃描部分可以歸約成一個活前綴，意味著所只要輸入串的已掃描部分可以歸約成一個活前綴，意味著所掃描的部分沒有錯誤掃描的部分沒有

9、錯誤S SA A9自底向上的分析（自底向上的分析（8）例例1：考慮表達式文法：考慮表達式文法 EE+E | E*E | （E）| id對于最右推導：對于最右推導：但這個文法是有二義性的，因此存在另一個最右推導但這個文法是有二義性的，因此存在另一個最右推導321*rm32*rm3*rm*rm*rmid*idid id*idE id*EE E*EE EEE10自底向上的分析（自底向上的分析（9）移進移進-歸約分析的實現(xiàn)歸約分析的實現(xiàn)用棧來保存文法符號，輸入緩沖區(qū)來保存待分析用棧來保存文法符號，輸入緩沖區(qū)來保存待分析的串的串句柄的選擇：句柄的選擇：如何決定右句型中要歸約的子串如何決定右句型中要歸約的

10、子串當一個要歸約的子串是多個產(chǎn)生式的右部時，如當一個要歸約的子串是多個產(chǎn)生式的右部時，如何確定選擇哪個產(chǎn)生式何確定選擇哪個產(chǎn)生式動作動作（1）移進：將下一個輸入符號移進棧頂）移進：將下一個輸入符號移進棧頂（2）歸約：句柄位于棧頂，必須在棧中確定完整的句柄，）歸約：句柄位于棧頂，必須在棧中確定完整的句柄，并決定用哪個產(chǎn)生式歸約并決定用哪個產(chǎn)生式歸約（3）接受：分析成功）接受：分析成功（4）出錯：報告錯誤，調用錯誤恢復例程）出錯：報告錯誤，調用錯誤恢復例程11自底向上的分析（自底向上的分析（10）棧棧輸輸 入入動動 作作 (1) $ id1+id2*id3$ 移進移進 (2) $id1 +id2*

11、id3$ 按按Eid歸約歸約 (3) $E +id2*id3$ 移進移進 (4) $E+ id2*id3$ 移進移進 (5) $E+id2 *id3$ 按按Eid歸約歸約 (6) $E+E *id3$ 移進移進 (7) $E+E* id3$ 移進移進 (8) $E+E*id3 $ 按按Eid歸約歸約 (9) $E+E*E $ 按按EE*E歸約歸約 (10)$E+E $ 按按EE+E歸約歸約 (11)$E $ 接受接受12自底向上的分析（自底向上的分析（11）移進移進-歸約分析的沖突歸約分析的沖突移進移進-歸約沖突歸約沖突根據(jù)棧中所有的內容和下一個輸入符號不能決定是移進還是根據(jù)棧中所有的內容和下

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

13、數(shù)？13LR分析器分析器（1）LR分析算法分析算法LR文法文法LR(0)分析分析SLR(1)分析分析LR(1)規(guī)范分析規(guī)范分析LALR(1)分析分析14LR分析器分析器（2）LR(k)分析分析L指從左到右掃描輸入，指從左到右掃描輸入，R指構造最右推導的逆，指構造最右推導的逆，k指的是指的是在決定分析動作時向前看的符號個數(shù)，在決定分析動作時向前看的符號個數(shù)，(k)省略時，表示省略時，表示k是是1LR(k)分析能力強大分析能力強大LR分析器能夠構造識別所有上下文無關文法寫的程序設計語分析器能夠構造識別所有上下文無關文法寫的程序設計語言的結構言的結構LR分析方法是已知的最一般的無回溯移進分析方法是已

14、知的最一般的無回溯移進-歸約方法，它能歸約方法，它能夠和其他移進夠和其他移進-歸約方法一樣有效地實現(xiàn)歸約方法一樣有效地實現(xiàn)LR方法能分析的文法類是預測分析法能分析的文法類的真超方法能分析的文法類是預測分析法能分析的文法類的真超集集LR分析器能及時察覺語法錯誤，快到自左向右掃描輸入的最分析器能及時察覺語法錯誤，快到自左向右掃描輸入的最大可能大可能手工構造手工構造LR分析器的工作量太大，但可以利用專門的工分析器的工作量太大，但可以利用專門的工具（如具（如Yacc）來構造來構造如果文法二義或有其它難以自左向右分析的結構，分析器的如果文法二義或有其它難以自左向右分析的結構，分析器的生成器能定位這些結構

15、并報告生成器能定位這些結構并報告15LR分析器分析器（3）LR分析算法分析算法組成組成驅動程序對所有的驅動程序對所有的LR分析器是一樣的，只是分析表不同分析器是一樣的，只是分析表不同棧中存儲形如棧中存儲形如s0X1s1X2s2Xmsm的串，其中的串，其中sm在棧頂，在棧頂，Xi是是文法符號，文法符號，si是是狀態(tài)狀態(tài)符號，它概括了棧中它下面部分所包符號，它概括了棧中它下面部分所包含的信息含的信息輸輸入入棧棧L LR R分分析析程程序序輸輸出出a ac ct ti io on nL LR R分分析析器器模模型型a a1 1. . . .a ai i. . . .a an n$ $s sm mX

16、Xm ms sm m- -1 1X Xm m- -1 1. . . .s s0 0g go ot to o16LR分析器分析器（4）分析表包括動作函數(shù)分析表包括動作函數(shù)action和轉移函數(shù)和轉移函數(shù)goto兩部兩部分組成分組成根據(jù)棧頂當前的狀態(tài)根據(jù)棧頂當前的狀態(tài)sm和當前的輸入符號和當前的輸入符號ai訪問訪問actionsm , ai，取值包括：取值包括：移進移進s，其中，其中s是一個狀態(tài)是一個狀態(tài)按文法產(chǎn)生式按文法產(chǎn)生式A歸約歸約接受接受出錯出錯函數(shù)函數(shù)goto取狀態(tài)和文法符號為變元，產(chǎn)生一個狀態(tài)取狀態(tài)和文法符號為變元，產(chǎn)生一個狀態(tài)vLR分析器棧中的文法符號總是形成活前綴分析器棧中的文法符

17、號總是形成活前綴v在在LR(0)分析、分析、SLR分析、規(guī)范分析、規(guī)范LR分析和分析和LALR分析中分析中，構造一個識別文法，構造一個識別文法G的活前綴的確定有限自動機，的活前綴的確定有限自動機，則則goto函數(shù)是這個自動機的狀態(tài)轉換函數(shù)，初始狀態(tài)函數(shù)是這個自動機的狀態(tài)轉換函數(shù)，初始狀態(tài)是初啟時置于是初啟時置于LR分析器棧中的狀態(tài)分析器棧中的狀態(tài)17LR分析器分析器（5）LR分析器的分析器的格局格局是二元組是二元組它的第一個成分是棧的內容，第二個成分是尚未接收它的第一個成分是棧的內容，第二個成分是尚未接收的輸入：的輸入：(s0X1s1X2s2Xmsm，aiai+1an$)，這個格局，這個格局代

18、表右句型代表右句型X1X2Xmaiai+1an動作：動作：移進：移進：如果如果actionsm , ai=移進移進s，分析器執(zhí)行移進動作，進分析器執(zhí)行移進動作，進入格局入格局(s0X1s1X2s2Xmsmais，ai+1an$) ，其中，其中s=gotosm , ai18LR分析器分析器（6）歸約：歸約：如果如果actionsm , ai=歸約歸約A, 則分析器執(zhí)行歸約則分析器執(zhí)行歸約, 進進入格局入格局(s0X1s1X2s2Xm-rsm-rAs， aiai+1an$), 其中其中s=gotosm-r , A，r是是的長度，的長度，完成這個動作時，首先從棧中彈出完成這個動作時，首先從棧中彈出2

19、r個符號（包括個符號（包括r個狀態(tài)符號和個狀態(tài)符號和r個文法符號，這些文法符號剛好匹配個文法符號，這些文法符號剛好匹配產(chǎn)生式右部產(chǎn)生式右部 ），然后將產(chǎn)生式左邊的非終結符），然后將產(chǎn)生式左邊的非終結符A和和gotosm-r , A的狀態(tài)的狀態(tài)s壓入棧壓入棧在歸約動作時執(zhí)行與歸約產(chǎn)生式相關的語義動作在歸約動作時執(zhí)行與歸約產(chǎn)生式相關的語義動作接受：接受：如果如果actionsm , ai=接受，分析完成接受，分析完成出錯：出錯：如果如果actionsm , ai=出錯，分析器發(fā)現(xiàn)錯誤，調用錯出錯，分析器發(fā)現(xiàn)錯誤，調用錯誤恢復例程誤恢復例程19LR分析器分析器（7）LR分析算法分析算法輸入：輸入：L

20、R分析表和輸入串分析表和輸入串輸出：若輸出：若是句子，得到是句子，得到的自下而上分析，否則報錯的自下而上分析，否則報錯方法：方法：將初始狀態(tài)將初始狀態(tài)s0在分析器的棧頂，在分析器的棧頂，$在輸入緩沖區(qū)在輸入緩沖區(qū)讓讓ip指向指向$的第一個符號的第一個符號repeat forever begin令令s是棧頂?shù)臓顟B(tài)，是棧頂?shù)臓顟B(tài)，a是是ip指向的符號指向的符號if actions , a = 移進移進s then begin把把a和和s依次壓入棧依次壓入棧推進推進ip指向下一個輸入符號指向下一個輸入符號endelse if actions , a=歸約歸約A then begin棧頂彈出棧頂彈出2

21、*|個符號個符號令令s是現(xiàn)在的棧頂狀態(tài)是現(xiàn)在的棧頂狀態(tài)把把A和和gotos , A壓入棧壓入棧輸出產(chǎn)生式輸出產(chǎn)生式A或作相關的語義動作或作相關的語義動作endelse if actions , a=接受接受 then returnelse error()end20LR分析器分析器（8）表達式文法：對文法產(chǎn)生式標號表達式文法：對文法產(chǎn)生式標號(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fid為了表示的簡便，對各類動作如下簡化表示：為了表示的簡便，對各類動作如下簡化表示：(1) si表示移進，把當前輸入符號和狀態(tài)表示移進，把當前輸入符號和狀態(tài)i壓進棧壓進棧(2)

22、 rj表示按第表示按第j個產(chǎn)生式進行歸約個產(chǎn)生式進行歸約(3) acc表示接受表示接受(4) 空白表示出錯空白表示出錯21LR分析器分析器（9）狀 態(tài)狀 態(tài)動 作動 作id + * ( ) $id + * ( ) $0 0s5s51 12 23 34 4s5s55 56 6s5s57 7s5s58 89 910101111s6s6r2r2r4r4accaccs6s6r1r1r3r3r5r5s7s7r4r4r4r4r4r4r2r2r2r2s4s4s4s4r6r6r6r6r6r61 1s4s4s4s4s11s11s7s7r1r1r1r1r3r3r3r3r3r3r5r5r5r5r5r5轉 移轉 移E

23、 T FE T Fr6r62 23 310102 23 39 93 38 822LR分析器分析器（10）棧棧輸輸 入入動動 作作 (1) 0 id*id+id$ 移進移進 (2) 0 id 5 *id+id$ 按按Fid歸約歸約 (3) 0 F 3 *id+id$ 按按TF歸約歸約 (4) 0 T 2 *id+id$ 移進移進 (5) 0 T 2 * 7 id+id$ 移進移進 (6) 0 T 2 * 7 id 5 +id$ 按按Fid歸約歸約 (7) 0 T 2 * 7 F 10 +id$ 按按TT*F歸約歸約 (8) 0 T 2 +id$ 按按ET歸約歸約 (9) 0 E 1 +id$ 移

24、進移進 (10)0 E 1 + 6 id$ 移進移進 (11)0 E 1 + 6 id 5 $ 按按Fid歸約歸約 (12)0 E 1 + 6 F 3 $ 按按TF歸約歸約 (13)0 E 1 + 6 T 9 $ 按按EE+T歸約歸約 (14)0 E 1 $ 接受接受23LR分析器分析器（11）LR文法文法定義：一個文法，如果能夠為它構造出定義：一個文法，如果能夠為它構造出LR分析表，且表分析表，且表的條目都唯一的條目都唯一性質：性質：一個文法如果是一個文法如果是LR的，只要保證當句柄出現(xiàn)在棧頂時，自左的，只要保證當句柄出現(xiàn)在棧頂時，自左向右掃描的移進向右掃描的移進-歸約分析器能夠及時識別它便

25、足夠了歸約分析器能夠及時識別它便足夠了如果句柄出現(xiàn)在棧頂時，如果句柄出現(xiàn)在棧頂時，LR分析器不需要掃描整個棧，棧頂分析器不需要掃描整個棧，棧頂?shù)臓顟B(tài)符號包含了所需要的一切信息的狀態(tài)符號包含了所需要的一切信息LR(k)文法：最多向前看文法：最多向前看k個符號就可以決定動作的個符號就可以決定動作的LR分分析器分析的文法稱為析器分析的文法稱為LR(k)文法文法與與LL文法的區(qū)別：文法的區(qū)別：LR(k)文法：在看見了產(chǎn)生式右部推導出的所有東西和文法：在看見了產(chǎn)生式右部推導出的所有東西和k個向個向前看的符號后，能識別產(chǎn)生式右部的出現(xiàn)前看的符號后，能識別產(chǎn)生式右部的出現(xiàn)LL(k)文法：在看見了右部推出的前

26、文法：在看見了右部推出的前k個符號就能識別所使用個符號就能識別所使用的產(chǎn)生式的產(chǎn)生式24LR分析器分析器（12）LR(0)項目的有限自動機項目的有限自動機LR(0)項目（項目（LR(0) item，簡稱項目、，簡稱項目、item）：）：是是在右部帶有區(qū)分位置（一般是用一個在右部帶有區(qū)分位置（一般是用一個“.”表示表示這個區(qū)分的位置）的產(chǎn)生式這個區(qū)分的位置）的產(chǎn)生式如果如果A是一個產(chǎn)生式，且是一個產(chǎn)生式，且=，則則A.是是LR(0)項目，其中項目，其中和和可以是空串可以是空串。如果如果A是一個產(chǎn)生式，則它只對應了一個項目是一個產(chǎn)生式，則它只對應了一個項目A.項目的解釋：項目的解釋：項目項目A.表

27、示已經(jīng)看到了表示已經(jīng)看到了(此時，此時，必須出現(xiàn)在棧的必須出現(xiàn)在棧的頂部頂部)，且可能從下面的輸入符號中獲取，且可能從下面的輸入符號中獲取項目項目A.表示將要用產(chǎn)生式表示將要用產(chǎn)生式A來識別來識別A，這種項目這種項目也稱為初始項目也稱為初始項目項目項目A.表示表示出現(xiàn)在分析棧的頂部，而且如果出現(xiàn)在分析棧的頂部，而且如果A在下一個歸約中使用，則它可能是句柄，這種項目稱在下一個歸約中使用，則它可能是句柄，這種項目稱為完整項目為完整項目25LR分析器分析器（13）例例2：考慮文法：考慮文法S(S)S | ，給出給出LR(0)項目項目首先構造拓廣文法：加入一個產(chǎn)生式首先構造拓廣文法：加入一個產(chǎn)生式SS

28、，分析器執(zhí)行歸分析器執(zhí)行歸約約SS時，表示分析成功時，表示分析成功在構造在構造LR(0)項目，共項目，共8個個 S.S SS. S.(S)S S(.S)S S(S.)S S(S).S S(S)S. S.26LR分析器分析器（14）LR(0)項目集合的有限自動機的構造項目集合的有限自動機的構造若有項目若有項目A.，且假設且假設以符號以符號X（終結符或非終終結符或非終結符）開始（即結符）開始（即=X），），則讀入則讀入X后，項目變?yōu)楹?，項目變?yōu)锳X.，在自動機中有一個標記為在自動機中有一個標記為X的由狀態(tài)的由狀態(tài)A.X到狀態(tài)到狀態(tài)AX.的轉換的轉換這個轉換的意義是：這個轉換的意義是：如果如果X是一

29、個終結符，表示是一個終結符，表示X在分析中被從輸入移進到在分析中被從輸入移進到棧的頂部棧的頂部如果如果X是一個非終結符，可以理解為是用產(chǎn)生式是一個非終結符，可以理解為是用產(chǎn)生式X歸約時發(fā)生，這個歸約前面必須有一個歸約時發(fā)生，這個歸約前面必須有一個的識別，而由的識別，而由初始項目初始項目X.給出的狀態(tài)表明這個識別的開始，此時給出的狀態(tài)表明這個識別的開始，此時，必須考慮加入下面的轉換，必須考慮加入下面的轉換如果如果X是非終結符，則對每個項目是非終結符，則對每個項目A.X，添加一添加一個到項目個到項目X.的的轉換（如果以轉換（如果以X為左部的產(chǎn)生式多為左部的產(chǎn)生式多于一個，則每個都要如此處理）于一個

30、，則每個都要如此處理）27LR分析器分析器（15）自動機的初始狀態(tài)與分析程序的初始狀態(tài)對應：棧是自動機的初始狀態(tài)與分析程序的初始狀態(tài)對應：棧是空的，且將要識別一個文法的開始符號空的，且將要識別一個文法的開始符號S，但由于但由于S可可能出現(xiàn)在多個產(chǎn)生式的左部，所以拓廣文法，加入能出現(xiàn)在多個產(chǎn)生式的左部，所以拓廣文法，加入S和產(chǎn)生式和產(chǎn)生式SS，S是拓廣文法的開始符號，是拓廣文法的開始符號，S.S是是自動機的開始狀態(tài)自動機的開始狀態(tài)自動機的接受狀態(tài)：此處的自動機是用于了解分析的自動機的接受狀態(tài)：此處的自動機是用于了解分析的狀態(tài)，而不是完全識別串，因此分析程序本身決定何狀態(tài)，而不是完全識別串，因此分

31、析程序本身決定何時接受，自動機不必關心，所以可以沒有接受狀態(tài)時接受，自動機不必關心，所以可以沒有接受狀態(tài)28LR分析器分析器（16）例例2對應的對應的NFA：S S. .S SS S. .( (S S) )S SS S( (. .S S) )S SS SS S. .S S. .S S( (S S) )S S. .S S( (S S. .) )S SS S( (S S) ). .S SS S( (S S) )S S29LR分析器分析器（17）例例2對應的對應的DFA：S.SS.SS.(S)SS.(S)SS.S.0 0S(.S)SS(.S)SS.(S)SS.(S)SS.S.2 2SS.SS.1 1

32、S(S.)SS(S.)S3 3S(S).SS(S).SS.(S)SS.(S)SS.S.4 4S(S)S.S(S)S.5 5S S( (S S) )S S( ( (30LR分析器分析器（18）文法的文法的LR項目的閉包計算項目的閉包計算對于文法對于文法G的的LR項目集項目集I，閉包閉包closure(I)的計算：的計算：J := Irepeatfor J 的每個項目的每個項目A.B和和G的每個產(chǎn)生式的每個產(chǎn)生式B，若若B.不在不在J中中 do把把B.加入加入Juntil 沒有更多的項目可以加入沒有更多的項目可以加入JLR(0)分析算法分析算法僅根據(jù)棧中的符號就可以決定動作僅根據(jù)棧中的符號就可以決

33、定動作若項目若項目A.a屬于屬于Ik且且GO1(Ik，a)= Ij，a為終結符，則置為終結符，則置ACTIONk，a為為sj若項目若項目A.屬于屬于Ik，那么對任何終結符，那么對任何終結符a（或結束符（或結束符$），置），置ACTIONk，a為為rj(假定產(chǎn)生式假定產(chǎn)生式A是文法的第是文法的第j個產(chǎn)生式個產(chǎn)生式)若項目若項目SS.屬于屬于Ik，則置，則置ACTIONk，$為接受為接受若若GOIk，A= Ij ，A為非終結符，則置為非終結符，則置gotok，A=j。分析表中凡不能用規(guī)則分析表中凡不能用規(guī)則14填入信息的空白格均置為報錯填入信息的空白格均置為報錯1此處的此處的GO是指自動機的狀態(tài)轉

34、換，而不是是指自動機的狀態(tài)轉換，而不是LR分析中的轉移表（用分析中的轉移表（用goto表示）表示）31LR分析器分析器（19）項目的分類：項目的分類：核心項目：包括初始項目核心項目：包括初始項目S.S和所有點不在左和所有點不在左端的項目端的項目非核心項目：它們的點都在左端非核心項目：它們的點都在左端項目分類的意義：項目分類的意義：DFA應用的項目集是核心項目的閉包形成應用的項目集是核心項目的閉包形成若有一個文法，核心項目唯一地判斷出狀態(tài)以及若有一個文法，核心項目唯一地判斷出狀態(tài)以及它的轉換，則只需指出核心項目就可以完整地表它的轉換，則只需指出核心項目就可以完整地表示出項目集合的示出項目集合的D

35、FA32LR分析器分析器（20）SLR分析分析規(guī)范的規(guī)范的LR(0)族：提供了構造族：提供了構造SLR分析表的基礎分析表的基礎對于對于LR(0)規(guī)范族中的項目集：規(guī)范族中的項目集：I = X.b, A. , B. LR(0)無法區(qū)分這三個不沖突的項目，此時要考察無法區(qū)分這三個不沖突的項目，此時要考察FOLLOW(A)和和FOLLOW(B)集合集合構造算法：構造算法：C := closure(S.S)repeatfor 對對C的每個項目集的每個項目集I和每個文法符號和每個文法符號X，若若goto(I , X)非空且不在非空且不在C中中 do把把goto(I , X)加入加入C中中until 沒有

36、更多的項目可以加入沒有更多的項目可以加入C33LR分析器分析器（21）例例3：拓廣的表達式文法：拓廣的表達式文法：EEEE+T | TTT*F | FF(E) | id對應的對應的LR(0)項目集規(guī)范族如下：項目集規(guī)范族如下：I0:E.E I5: Fid.E .E+TE .T I6: EE+.TT .T*FT.T*FT .FT.FF .(E)F.(E)F .idF.id34LR分析器分析器（22）I1:EE. I7: TT*.FE E.+TF.(E)F.idI2: E T.T T.*F I8: F(E.)EE.+TI3: T F. I9: EE+T.I4: F (.E)TT.*FE .E+TE

37、 .T I10: TT*F.T .T*FT .F I11: F(E).F .(E)F .id35LR分析器分析器（23）I I0 0I I1 1I I6 6I I9 9I I2 2E E+ +T T* *指向I指向I7 7F F指向I指向I3 3( (指向I指向I4 4idid指向I指向I5 5I I7 7I I1010* *F F( (指向I指向I4 4idid指向I指向I5 5I I3 3I I4 4I I8 8I I1111E E) )+ +指向I指向I6 6T T指向I指向I2 2F F指向I指向I3 3I I5 5idididid( (F FT T( (36LR分析器分析器（24）如

38、果將這個如果將這個DFA中的每個狀態(tài)定為接受狀態(tài)，而中的每個狀態(tài)定為接受狀態(tài)，而I0定為初定為初態(tài)，則這個態(tài)，則這個DFA識別文法的活前綴識別文法的活前綴對于項目對于項目A1.2對活前綴對活前綴1是是有效有效的，是指存的，是指存在推導序列在推導序列A1.2對活前綴對活前綴1有效表明當有效表明當1在分析棧頂時在分析棧頂時v如果如果2是是，則則A1是句柄，應該用這個產(chǎn)生式歸約是句柄，應該用這個產(chǎn)生式歸約v如果如果2不是不是，則表示句柄還沒有完全進棧，要繼續(xù)移進則表示句柄還沒有完全進棧，要繼續(xù)移進同一個活前綴的兩個有效項目可能對應了不同的動作同一個活前綴的兩個有效項目可能對應了不同的動作，引起了沖突

39、，引起了沖突v這種沖突可以通過向前看幾個符號解決，也可以通過其這種沖突可以通過向前看幾個符號解決，也可以通過其它方式解決它方式解決AS21rm*rm37LR分析器分析器（25）SLR分析表的構造分析表的構造輸入：拓廣文法輸入：拓廣文法G輸出：輸出：G的的SLR分析表函數(shù)分析表函數(shù)action和和goto方法：方法：(1)構造構造C=I0 , I1 , , In ，即即G的的LR(0)項目集規(guī)范族項目集規(guī)范族 (2)狀態(tài)狀態(tài)i從從Ii構造，它的動作如下確定：構造，它的動作如下確定： (a) 如果如果A.a在在Ii中，并且中，并且( Ii , a) = Ij，則置則置 action(i , a)為

40、為sj,含義是把含義是把a和狀態(tài)和狀態(tài)j移進棧移進棧, a必須為終結符必須為終結符 (b) 如果如果A.在在Ii中，則對中，則對FOLLOW(A)中的所有中的所有a，置置 action(i , a)為為rj, j是產(chǎn)生式是產(chǎn)生式A的編號。含義是按產(chǎn)生的編號。含義是按產(chǎn)生 式式A歸約，這里歸約，這里A不是不是S (c) 如果如果SS.在在Ii中，則置中，則置action(i , $)=acc，表示接受表示接受 (3)對所有的非終結符對所有的非終結符A，使用下面的規(guī)則構造狀態(tài)使用下面的規(guī)則構造狀態(tài)i的轉移：的轉移： 如果如果( Ii , A) = Ij，則則gotoi , A=j (4)不能由規(guī)則

41、不能由規(guī)則(2)和和(3)定義的條目置為出錯定義的條目置為出錯 (5)分析器的初始狀態(tài)是包含分析器的初始狀態(tài)是包含S.S的項目集對應的狀態(tài)的項目集對應的狀態(tài)38LR分析器分析器（26）如果在規(guī)則如果在規(guī)則(2)的構造中產(chǎn)生的動作有沖突，則該文的構造中產(chǎn)生的動作有沖突，則該文法不是法不是SLR(1)文法文法由上述算法生成的分析表成為文法由上述算法生成的分析表成為文法G的的SLR(1)分析表分析表每個每個SLR(1)文法都不是二義的文法都不是二義的存在非二義的文法，這個文法不是存在非二義的文法，這個文法不是SLR(1)的的對于在棧頂狀態(tài)對于在棧頂狀態(tài)s中的任何項目中的任何項目A.X，當當X是一個是

42、一個終結符，且終結符，且X在在FOLLOW (B)中時，中時，s中沒有完整的項中沒有完整的項目目B.。（。（若不滿足，則存在移進若不滿足，則存在移進-歸約沖突）歸約沖突）對于在對于在s中的任何兩個完整項目中的任何兩個完整項目A.和和B.，F(xiàn)OLLOW(A)與與FOLLOW(B)的交集為空集。（若不滿的交集為空集。（若不滿足，則存在歸約足，則存在歸約-歸約沖突）歸約沖突）SLR(1)分析能力比分析能力比LR(0)強，但仍然不能夠滿足要求強，但仍然不能夠滿足要求39LR分析器分析器（27）LR(1)規(guī)范分析規(guī)范分析SLR分析不能解決某些移進分析不能解決某些移進-歸約沖突，而歸約沖突，而LR(1)規(guī)

43、范規(guī)范分析可以，參考陳意云書的例分析可以，參考陳意云書的例3.31和和3.32LR(1)項目：項目：A.，a，其中其中A是產(chǎn)生式，是產(chǎn)生式，a是終結符號或是終結符號或$。1是指第二個成分的長度，這個成分稱為項目的搜索符是指第二個成分的長度，這個成分稱為項目的搜索符搜索符對搜索符對非空的項目非空的項目A.，a是不起作用的，但對是不起作用的，但對項目項目A. ，a，表示只有在下一個輸入符號為表示只有在下一個輸入符號為a時才能要求按時才能要求按A歸約歸約SLR(1)和和LR(1)對向前看符號的使用的不同：對向前看符號的使用的不同：SLR(1)是在是在LR(0)項目的項目的DFA構造完成后才考慮提供向

44、構造完成后才考慮提供向前看的符號，前看的符號，DFA的構造中不考慮向前看的符號的構造中不考慮向前看的符號LR(1)是在一開始就考慮向前看符號，是在一開始就考慮向前看符號，DFA的構造是在的構造是在考慮向前看符號的基礎上進行的考慮向前看符號的基礎上進行的40LR分析器分析器（28）LR(1)項目項目A.，a對活前綴對活前綴是是有效有效的，如果存的，如果存在著推導在著推導 其中：其中： = a是是的第一個符號，或者的第一個符號，或者是是則則a是是$例：考慮文法例：考慮文法SBB BaB | b對于最右推導：對于最右推導： ，項目，項目Ba.B，a對于對于活前綴活前綴 =aaa是有效的，是有效的，=

45、aa，A=B，=ab， =a和和=B對于最右推導：對于最右推導： ，項目，項目Ba.B，$對于活前對于活前綴綴Baa是有效的是有效的ASrm*rmaaaBabaaBabSrm*rmBaaBBaBSrm*rm41LR分析器分析器（29）有效的有效的LR(1)項目集族的構造方法本質上和構造項目集族的構造方法本質上和構造LR(0)項目集項目集規(guī)范族的方法是一樣的規(guī)范族的方法是一樣的Closure函數(shù)的構造：函數(shù)的構造：v考慮對活前綴考慮對活前綴有效的項目集中的項目有效的項目集中的項目A.B，a。必定存在一個最右推導必定存在一個最右推導 , 其中其中=，假定假定ax推出終結符串推出終結符串by，則對每

46、個形式則對每個形式B的產(chǎn)的產(chǎn)生式，有推導生式，有推導 ，于是，于是B.，b對對有效有效vb可能是從可能是從推出的第一個終結符，或者推出的第一個終結符，或者是空串，是空串，b就成了就成了a，即即b = FIRST(ax)，但在此處，考慮到但在此處，考慮到a是終結符，所以是終結符，所以有有FIRST(ax)= FIRST(a)xBxASrm*rmaa byBbySrm*rm42LR分析器分析器（30）Closure函數(shù)構造的算法：函數(shù)構造的算法：Function closure(I)Beginrepeatfor 對對I的每個項目的每個項目A.B，a，G中的每個產(chǎn)生式中的每個產(chǎn)生式B 和和FIRST

47、(a)的每個終結符的每個終結符b,如果如果B.，b不在不在I中中 do把把B.，b加到加到I中中until 再沒有項目可加到再沒有項目可加到I中中return Iend43LR分析器分析器（31）Goto函數(shù)的構造：函數(shù)的構造：function goto( I , X )begin令令J是項目是項目A X.，a的集合，使得的集合，使得A .X，a 在在I中中return closure(J)end項目的構造：項目的構造：procedure items(G)beginC := closure(S.S，$)repeat for C的每個項目的每個項目I和每個文法符號和每個文法符號X，若若goto(

48、I , X)非空且非空且 不在不在C中中 do把把goto(I , X)加入加入C中中until 再沒有項目集可以加入再沒有項目集可以加入C中中end44LR分析器分析器（31）規(guī)范的規(guī)范的LR(1)分析表的構造與分析表的構造與SLR分析表的構造相似分析表的構造相似輸入：拓廣文法輸入：拓廣文法G輸出：輸出：G的的LR(1)分析表函數(shù)分析表函數(shù)action和和goto方法：方法：(1)構造構造C=I0 , I1 , , In ，即即G的的LR(1)項目集規(guī)范族項目集規(guī)范族 (2)狀態(tài)狀態(tài)i從從Ii構造，它的動作如下確定：構造，它的動作如下確定： (a) 如果如果A.a, b在在Ii中，并且中，并

49、且goto( Ii , a) = Ij，則置則置 action(i , a)為為sj,含義是把含義是把a和狀態(tài)和狀態(tài)j移進棧移進棧, a必須為終結符必須為終結符 (b) 如果如果A. , a在在Ii中且中且A不是不是S，則置則置action(i , a)為為rj, j是產(chǎn)生式是產(chǎn)生式A的編號。含義是按產(chǎn)生式的編號。含義是按產(chǎn)生式A歸約歸約 (c) 如果如果SS. , $在在Ii中，則置中，則置action(i , $)=acc，表示接受表示接受 (3)對所有的非終結符對所有的非終結符A，使用下面的規(guī)則構造狀態(tài)使用下面的規(guī)則構造狀態(tài)i的轉移：的轉移： 如果如果DFA的轉換函數(shù)的轉換函數(shù)goto(

50、 Ii , A) = Ij，則則gotoi , A=j (4)不能由規(guī)則不能由規(guī)則(2)和和(3)定義的條目置為出錯定義的條目置為出錯 (5)分析器的初始狀態(tài)是包含分析器的初始狀態(tài)是包含S.S , $的項目集對應的狀態(tài)的項目集對應的狀態(tài)45LR分析器分析器（32）如果這個分析表中的動作函數(shù)沒有多重定義的條目，則如果這個分析表中的動作函數(shù)沒有多重定義的條目，則這個文法是這個文法是LR(1)文法文法在實際中，除非有二義性，幾乎所有合理的程序設計語在實際中，除非有二義性，幾乎所有合理的程序設計語言的文法都是言的文法都是LR(1)文法文法LR(1)分析過于復雜，產(chǎn)生的項目集合過多，尤其是很分析過于復雜

51、，產(chǎn)生的項目集合過多，尤其是很多項目集合的不同僅僅是因為第二個成分的不同多項目集合的不同僅僅是因為第二個成分的不同例例4：考慮拓廣文法：考慮拓廣文法S SS CCC cC | d46LR分析器分析器（33）S S . .S S, ,$ $S S. .C CC C, ,$ $C C. .c cC C, , c c/ /d dC C. .d d, ,c c/ /d dI I0 0S S S S. ., ,$ $I I1 1S SC C. .C C, ,$ $C C. .c cC C, ,$ $C C. .d d, ,$ $I I2 2S SC CC C. ., ,$ $I I5 5C Cc c.

52、.C C, ,$ $C C. .c cC C, ,$ $C C. .d d, ,$ $I I6 6C Cc cC C. ., ,$ $I I9 9C Cd d. ., ,$ $I I7 7C Cc c. .C C, ,c c/ /d dC C. .c cC C, ,c c/ /d dC C. .d d, ,c c/ /d dI I3 3C Cc cC C. ., ,c c/ /d dI I8 8C Cd d. ., ,c c/ /d dI I4 4d dd dC CC CC CS Sc cd dc cc cC Cc cd d47LR分析器分析器（34）狀狀 態(tài)態(tài)動動 作作c c d d $ $

53、0 0s s3 31 12 23 34 45 56 67 78 89 9s s6 6a ac cc cs s7 7r r1 11 1r r2 2轉轉 移移S S C C2 29 9s s4 45 58 8s s3 3s s4 4r r3 3r r3 3s s6 6s s7 7r r3 3r r2 2r r2 248LR分析器分析器（35）LALR(1)分析（分析（lookahead-LR分析）分析）引入引入LALR分析：分析：LR(1)項目集合的項目集合的DFA狀態(tài)過于龐大，且很多狀態(tài)的狀態(tài)過于龐大，且很多狀態(tài)的引入只是因為向前看的符號的不同引入只是因為向前看的符號的不同構造同心的構造同心的L

54、R(1)項目集：它們的第一個成分集合相項目集：它們的第一個成分集合相同同vLR(1)項目的項目的DFA的狀態(tài)核心是的狀態(tài)核心是LR(0)項目的項目的DFA的一個狀態(tài)的一個狀態(tài)v若具有相同核心的若具有相同核心的LR(1)項目的項目的DFA的兩個狀態(tài)的兩個狀態(tài)s1和和s2，假設假設在符號在符號X上有一個從狀態(tài)上有一個從狀態(tài)s1到狀態(tài)到狀態(tài)t1的轉換，則在的轉換，則在X上必然有上必然有一個從狀態(tài)一個從狀態(tài)s2到一個狀態(tài)到一個狀態(tài)t2的轉換，且狀態(tài)的轉換，且狀態(tài)t1和和t2具有相同的具有相同的核心核心LALR具有和具有和SLR一樣個數(shù)的狀態(tài)，但保留了一樣個數(shù)的狀態(tài)，但保留了LR分分析的一些特征，能力比

55、析的一些特征，能力比SLR要強要強LALR分析表的構造：分析表的構造：v將具有相同核心的將具有相同核心的LR(1)項目合并，動作和轉移函數(shù)也做相項目合并，動作和轉移函數(shù)也做相應的合并應的合并49LR分析器分析器（36）LALR(1)分析表是在分析表是在LR(1)分析表的基礎上構造的，分析表的基礎上構造的，但可能引入但可能引入LR(1)分析中不存在的沖突分析中不存在的沖突v不會引入移進不會引入移進-歸約沖突（因為如果歸約沖突（因為如果LALR(1)分析表中存在分析表中存在這類沖突，則在同心項目合并前的這類沖突，則在同心項目合并前的LR(1)分析表中必定存在分析表中必定存在沖突）沖突）v可能引進歸

56、約可能引進歸約-歸約沖突歸約沖突LR(1)能發(fā)現(xiàn)的錯誤，能發(fā)現(xiàn)的錯誤，LALR(1)也能發(fā)現(xiàn)，只是在報也能發(fā)現(xiàn)，只是在報錯前可能要多作一些虛假的歸約錯前可能要多作一些虛假的歸約對例對例4的的LR(1)分析，構造分析，構造LALR(1)分析：分析：合并同心項目：合并同心項目：I36：Cc.C , c/d/$ C.cC , c/d/$ C.d , c/d/$ I47：Cd. , c/d/$ I89：CcC. , c/d/$50LR分析器分析器（37）狀狀 態(tài)態(tài)動動 作作c c d d $ $0 0s s3 36 61 12 23 36 64 47 75 58 89 9s s3 36 6a ac c

57、c cs s4 47 7r r1 11 1r r2 2轉轉 移移S S C C2 2s s4 47 75 58 89 9s s3 36 6s s4 47 7r r3 3r r3 3r r3 3r r2 2r r2 2考慮輸入串考慮輸入串ccd$，對于對于LR(1)分析，把分析，把0 c 3 c 3 d 4入棧，在狀態(tài)入棧，在狀態(tài)4發(fā)現(xiàn)錯誤發(fā)現(xiàn)錯誤而對于而對于LALR(1)分析，把分析，把0 c 36 c 36 d 47入棧入棧然后用然后用Cd歸約，棧的內容變?yōu)闅w約，棧的內容變?yōu)? c 36 c 36 C 89再用再用CcC歸約，棧的內容變?yōu)闅w約，棧的內容變?yōu)? c 36 C 89第二次用第二次

58、用CcC歸約，棧的內容變?yōu)闅w約，棧的內容變?yōu)? C 2此時發(fā)現(xiàn)錯誤此時發(fā)現(xiàn)錯誤51二義文法的應用二義文法的應用二義性文法不是二義性文法不是LR文法，但二義性文法在一些情況下的表示更為文法，但二義性文法在一些情況下的表示更為簡單簡單在在LR分析中消除二義性的規(guī)則分析中消除二義性的規(guī)則使用優(yōu)先級和結合規(guī)則來解決分析動作的沖突使用優(yōu)先級和結合規(guī)則來解決分析動作的沖突移進優(yōu)先于歸約的規(guī)則可以解決最長匹配問題如懸掛移進優(yōu)先于歸約的規(guī)則可以解決最長匹配問題如懸掛else的問的問題題特殊情況產(chǎn)生式引起的二義性，可能導致歸約特殊情況產(chǎn)生式引起的二義性，可能導致歸約-歸約沖突，可歸約沖突，可以規(guī)定此時按特殊情況

59、產(chǎn)生式歸約以規(guī)定此時按特殊情況產(chǎn)生式歸約如文法：如文法：EE sub E sup E | E sub E | E sup E | E | c如果描述如果描述E sub E sup E的文法符號和狀態(tài)序列已經(jīng)在分析的文法符號和狀態(tài)序列已經(jīng)在分析棧中，當面臨棧中，當面臨或或$時，選擇下面的哪個產(chǎn)生式歸約？時，選擇下面的哪個產(chǎn)生式歸約？EE sub E sup EEE sup E此時可以通過規(guī)定哪個產(chǎn)生式優(yōu)先歸約來解決此時可以通過規(guī)定哪個產(chǎn)生式優(yōu)先歸約來解決52自底向上分析程序中的錯誤校正（自底向上分析程序中的錯誤校正（1）綜述：綜述：何時發(fā)現(xiàn)錯誤？何時發(fā)現(xiàn)錯誤？當分析表中檢測到一個空白項（或錯誤項

60、），表示發(fā)現(xiàn)了錯誤當分析表中檢測到一個空白項（或錯誤項），表示發(fā)現(xiàn)了錯誤LR分析中訪問轉移表不會發(fā)現(xiàn)錯誤分析中訪問轉移表不會發(fā)現(xiàn)錯誤如何更好地發(fā)現(xiàn)錯誤？如何更好地發(fā)現(xiàn)錯誤？盡可能多的空白項可以使得分析程序盡可能早地發(fā)現(xiàn)錯誤，這盡可能多的空白項可以使得分析程序盡可能早地發(fā)現(xiàn)錯誤，這樣的錯誤信息更有意義，且是確定的樣的錯誤信息更有意義，且是確定的但過多的空白項使得分析表過于龐大（考慮但過多的空白項使得分析表過于龐大（考慮LALR和和LR分析分析），如果減少錯誤項，可能在報錯前會有一些不必要的歸約動），如果減少錯誤項，可能在報錯前會有一些不必要的歸約動作發(fā)生，使得報錯不準確作發(fā)生，使得報錯不準確特定