[理學]第4章 語法分析3_自底向上分析方法LR分析ppt課件

1、編譯原理編譯原理 (Principle of Compiler) (Principle of Compiler)諶諶 志志 群群: : : 58123910: 58123910Office: Office: 一教一教501501第四章 語法分析v語法分析器概述v語法分析-自頂向下分析(預測分析器)v語法分析-自底向上分析v算符優(yōu)先分析法vLR分析器4.5 LR分析器vLRLRk k分析技術：分析技術：nL 指從左至右掃描輸入符號串nR 指構造一個最右推導的逆過程最左歸約nk 指在作出分析決議前構造分析表時要向前看的輸入符號個數(shù)，通常為 0 或

2、 1nLR 分析技術是功能最強的自底向上語法分析技術，適用文法廣，效率高，分析才干強4.5 LR分析器vLRLR分析器的邏輯構造：分析器的邏輯構造：P90 P90 SmXmSm-1Xm-1 . .S1X1S0a1 . ai . an$action 表goto 表LR 驅動程序驅動程序棧棧輸入輸入輸出輸出4.5 LR分析器vLRLR分析器的邏輯構造：分析器的邏輯構造：nLR分析程序固定不變的n分析表動作表action、形狀轉移表goton棧形狀符號、文法符號n輸入緩沖n輸出產生式序列4.5 LR分析器vLRLR分析器運轉：分析器運轉：n根據當前棧頂形狀符號與輸入符號查分析表決議下一步動作n假設當

3、前 s0X1s1X2s2Xmsm, aiai+1an$1、action sm, ai = shift ss0X1s1X2s2Xmsmais, ai+1an$2、action sm, ai = reduce As0X1s1X2s2Xm-rsm-rAs, aiai+1an$4.5 LR分析器vLRLR分析算法：分析算法： P 91 P 91關鍵步驟關鍵步驟: s : 棧頂符號棧頂符號 a : 當前符號當前符號 1. 假設假設 actions,a = “accept 停機停機, 接受接受, 勝利勝利假設假設 actions,a = “reduce A 那么那么:2a. 從棧中彈出從棧中彈出 2 *

4、| 個符號個符號2b. 把把 A 壓入棧中壓入棧中2c. 把把 goto s* , A 壓入棧中壓入棧中假設假設 actions,a = “shift s*移進移進; 把把 s* 壓入棧中壓入棧中4.5 LR分析器vLRLR分析算法：分析算法：nLR分析的關鍵問題是如何構造分析表，不同的構造方法構成不同的分析方法，主要有 LR0、SLR、LR1、LALRn例子： 分析句子：abbcde文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dabbcdeAABSa b b c deAABS4.5 LR分析器ACTIONGOTOacebd$SAB0S211Acc2S433S

5、5S64R2R2R2R2R2R25S876R3R3R3R3R3R37S98R4R4R4R4R4R49R1R1R1R1R1R1LR(0)分析表分析表4.5 LR分析器對對 abbcde$ abbcde$ 的分析過程的分析過程步驟棧輸入串ACTIONGOTO10abbcde$S220a2bbcde$S430a2b4bcde$R2340a2A3bcde$S650a2A3b6cde$R3360a2A3cde$S570a2A3c5de$S880a2A3c5d8e$R4790a2A3c5B7e$S9100a2A3c5B7e9$R11110S1$Acc4.5 LR分析器vLRLR分析過程中的性質與特點：分析

6、過程中的性質與特點：n棧中的文法符號串并上剩余的輸入串構成一個右句型規(guī)范句型n當該右句型的句柄出如今棧頂時，歸約，否那么，移進n棧中的文法符號串是當前右句型的前綴，該前綴不包含當前句型的句柄后面的符號，稱之為 活前綴4.5 LR分析器n活前綴：上例 aAbcde , a , aA , aAbn可歸前綴：包含完好句柄的活前綴4.5 LR分析器n可以證明：一個文法的規(guī)范句型的一切活前綴可以證明：一個文法的規(guī)范句型的一切活前綴構成一個言語，而且是正規(guī)言語，可以用一個構成一個言語，而且是正規(guī)言語，可以用一個 DFA DFA 來識別來識別* 并且可以由該 DFA 來決議下一步分析動作根據當前活前綴的識別

7、態(tài)4.5 LR分析器n例子：文法文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d014235769SabAbcBed8*4.5 LR分析器n每個形狀都是活前綴的識別態(tài)，雙圈形狀是可歸前綴句柄識別態(tài)，標識了*的形狀是句子識別態(tài)02357SabAbcBed*(1) S aAcBe(2) A b(3) A Ab(4) B d469814.5 LR分析器v構造識別活前綴的構造識別活前綴的DFADFAn拓廣文法：添加產生式 SS，S作為新的開場符號n文法等價n確保文法的開場符號只在產生式的左部出現(xiàn)n為了在分析過程中區(qū)別是歸約到了文法的最初開場符號還是產生式右邊出現(xiàn)的開場符號4

8、.5 LR分析器nLR0工程n在文法產生式右部的適當位置添加圓點構成工程n例： AXYZn AXYZ AXYZ AXYZ AXYZn例： A A4.5 LR分析器n移進工程：A an待約工程：A Bn歸約工程： A n接受工程： S S n工程的含義：圓點的左部表示分析過程中的某時辰用該產生式歸約時句柄已識別過的部分，圓點右部表示待識別部分4.5 LR分析器n工程集的閉包closurenI 在 closure ( I ) 中n例： 求 closure ( E E ) n假設 AB在 closure ( I ) ，且 B是產生式，將 B添加到 closure ( I ) 中E EE E + T

9、| TT T * F | FF ( E ) | id4.5 LR分析器ngoto 函數(shù)ngoto ( I, X )n例： 求 goto ( E E， E E + T , +) ngoto ( I, X ) = closure (AX)，其中 AX在 I 中E EE E + T | TT T * F | FF ( E ) | id4.5 LR分析器n構造規(guī)范的 LR0工程集族n算法 P 97nC = closure ( S S ) nC = C goto ( I, X )n例子：P 98-1004.5 LR分析器I0:E EE E + T E TT T * FT FF (E)F idI1:E E

10、 E E + TI2: E T T T * F I3: T F 4.5 LR分析器I0: I4:E EF (E ) E E + T E E + T E TE TT T * FT T * FT FT FF (E)F (E)F idF idI5: F id 4.5 LR分析器I1:E E E E+ TI6 :EE + TT T * F T F F (E) F idI2:E TTT*F I7:TT *F F (E) F id 4.5 LR分析器I4: I8:F (E )F (E) E E + TE E+ T E TT T *F T FF ( E )F id I9: I10:I11:4.5 LR分析器

11、n構造識別文法一切活前綴的 DFAn工程集作為形狀，工程集族作為形狀集n例子：P 100ngoto ( I, X ) 作為形狀轉換函數(shù)I1I0+to I7EI6I9I3I2I4I11I8I7I10*TI5to I4to I3to I5to I4to I5to I6to I2to I3F(FTid* *idFF(Eid+)id(FT4.5 LR分析器例：文法例：文法 G G: :S S E EE E T + E T + E E E T TT T int int * * T T T T int int T T (E) (E)S . EE . TE .T + ET .(E)T .int * TT .

12、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(int+(1234567891011TT4.5 LR分析器n每個形狀都是識別態(tài)，識別的是從初態(tài)到該形狀的通路上標志的文法符號構成的活前綴n含有規(guī)約工程的是可歸前綴識別態(tài)n含有 “S S 的是“句子識別

13、態(tài)4.5 LR分析器例：文法例：文法G G: :(0) S(0) S S S(1) S (1) S aA aA (2) S (2) S bB bB(3) A (3) A cA cA (4) A (4) A d d (5) B (5) B cB cB(6) B (6) B d d (0) S (0) S S S (1) S (1) S aA aA (2) S (2) S bB bB (3) A (3) A cA cA (4) A (4) A d d (5) B (5) B cB cB (6) B (6) B d d I0:I0:S S S SS S aAaAS S bBbBI4:I4:A cA

14、cA AA A cAcAA A d dI2:I2:S aS aA AA A cAcAA A d dI5:I5:B cB cB BB B cBcBB B d dI3:I3:S bS bB BB B cBcBB B d dI1:I1:S SS SI8:I8:A cAA cAI10:I10:A dA dI6:I6:S aAS aAI7:I7:S bBS bBI11:I11:B dB dI9:I9:B cBB cBb ba aS Sc cc cc cc cA Ad dd dA AB Bd dd dB B4.5 LR分析器n初態(tài)是活前綴 的有效工程集n活前綴的有效工程集n活前綴 的有效工程集是從初態(tài)出發(fā)

15、經過 道路所到達的那個形狀所代表的工程集* 根據當前活前綴的有效工程集確定下一步的分析動作I0:I0:S S S SS S aAaAS S bBbBI4:I4:A cA cA AA A cAcAA A d dI2:I2:S aS aA AA A cAcAA A d dI5:I5:B cB cB BB B cBcBB B d dI3:I3:S bS bB BB B cBcBB B d dI1:I1:S SS SI8:I8:A cAA cAI10:I10:A dA dI6:I6:S aAS aAI7:I7:S bBS bBI11:I11:B dB dI9:I9:B cBB cBb ba aS Sc

16、 cc cc cA Ad dd dA AB Bd dd dB B (0) S (0) S S S (1) S (1) S aA aA (2) S (2) S bB bB (3) A (3) A cA cA (4) A (4) A d d (5) B (5) B cB cB (6) B (6) B d d c c步驟棧輸入串ACTIONGOTO10accd$S220a2ccd$S430a2c4cd$S440a2c4c4d$S1050a2c4c4d10$R4860a2c4c4A8$R3870a2c4A8$R3680a2A6$R1190S1$Acc (0) S (0) S S S (1) S (1)

17、 S aA aA (2) S (2) S bB bB (3) A (3) A cA cA (4) A (4) A d d (5) B (5) B cB cB (6) B (6) B d d n有了識別活前綴的有了識別活前綴的 DFA 可以分析句子：可以分析句子：accd = accA = acA = aA = S = S* 每個形狀識別其左邊活前綴步驟棧輸入串動作1$accd$移進移進2$ accd$移進移進3$ a c cd$移進移進4$ a c c d$移進移進5$ a c c d$歸約歸約46$ a c c A $歸約歸約37$ a c A$歸約歸約38$ a A$歸約歸約19$ S$A

18、cc (0) S (0) S S S (1) S (1) S aA aA (2) S (2) S bB bB (3) A (3) A cA cA (4) A (4) A d d (5) B (5) B cB cB (6) B (6) B d d accd = accA = acA = aA = S = S4.5 LR分析器n有了識別活前綴的有了識別活前綴的 DFA 可以分析句子：可以分析句子：n處于含有移進工程的形狀可移進句子中下一個符號為 b0b4.5 LR分析器n含有歸約工程A 的形狀是可歸前綴識別態(tài)，處于此形狀可歸約用 A * 含有接受工程的形狀是句子識別態(tài)，歸約后完成分析04.5 LR

19、分析器n處于含有待約工程B A 的形狀可以等待歸約用 A ，然后形狀轉移0A4.5 LR分析器n構造構造 LR0分析表：分析表：n假設 goto (Ik，a)= Ij，那么 actionk，a= Sjn假設 goto (Ik，A)= Ij，那么 gotok，A= jn假設 Ik 包含 SS ，那么 action k，$ = accn假設 Ik 包含 A ，那么 acitonk，a= rj，a為任何終結符號或 $，j為產生式 A的編號含有歸約工程的形狀是可歸前綴識別態(tài)I0:I0:S S S SS S aAaAS S bBbBI4:I4:A cA cA AA A cAcAA A d dI2:I2:

20、S aS aA AA A cAcAA A d dI5:I5:B cB cB BB B cBcBB B d dI3:I3:S bS bB BB B cBcBB B d dI1:I1:S SS SI8:I8:A cAA cAI10:I10:A dA dI6:I6:S aAS aAI7:I7:S bBS bBI11:I11:B dB dI9:I9:B cBB cBb ba aS Sc cc cc cc cA Ad dd dA AB Bd dd dB B (0) S (0) S S S (1) S (1) S aA aA (2) S (2) S bB bB (3) A (3) A cA cA (4)

21、A (4) A d d (5) B (5) B cB cB (6) B (6) B d d 4.5 LR分析器ACTIONGOTOabcd$SAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5r5r5r510r4r4r4r4r411r6r6r6r6r6r6LR0分析表步驟棧輸入串ACTIONGOTO10accd$S220a2ccd$S430a2c4cd$S440a2c4c4d$S1050a2c4c4d10$R4860a2c4c4A8$R3870a2c4A8$R3680a2A6$R1190S

22、1$Acc (0) S (0) S S S (1) S (1) S aA aA (2) S (2) S bB bB (3) A (3) A cA cA (4) A (4) A d d (5) B (5) B cB cB (6) B (6) B d d n有了有了LR(0)分析表可以分析句子：分析表可以分析句子：accd = accA = acA = aA = S = S4.5 LR分析器n工程集合中的沖突工程集合中的沖突n移進-歸約沖突n工程集合中同時含有形如 A a和 B的工程n歸約-歸約沖突n工程集合中同時含有形如 A 和 B 的工程n工程集合中假設存在沖突，LR0分析表中存在多重定義入口

23、文法文法G G：(0) S(0) S S S(1) S (1) S rD rD (2) D(2) D D,i D,i(3) D (3) D i iI0:I0:S S S SS S rDrDI2: I2: S rS rD DD D D,iD,iD D i iI3: I3: S rD S rD D D D D ,i,iI4: I4: D i D i I5: I5: D D,D D,i iI1: I1: S S S S I6: I6: D D,i D D,i S Sr ri iD D, ,i iLR(0)LR(0)分析表分析表4.5 LR分析器n假設文法假設文法 G 的規(guī)范的規(guī)范 LR0工程集族中不含有工程集族中不含有移進移進-歸約沖突和歸約歸約沖突和歸約-歸約沖突，那么稱文法歸約沖突，那么稱文法 G 為為 LR0文法文法n構造分析表時沒有向前看，或者說向前看了 0 個符號n基于 LR0分析表的 LR 分析稱為 LR0分析4.5 LR分析器n對于規(guī)范對于規(guī)范 LR0工程集族中有沖突的工程集工