[理學(xué)]第4章語(yǔ)法分析3_自底向上分析方法lr分析(已修改)
2024-12-20 01:05 本頁(yè)面
【正文】 編譯原理 (Principle of Compiler) 諶 志 群 Email: Tel: 13958123910 Office: 一教 501 2 第四章 語(yǔ)法分析 ?語(yǔ)法分析器概述 ?語(yǔ)法分析 自頂向下分析 (預(yù)測(cè)分析器 ) ?語(yǔ)法分析 自底向上分析 ?算符優(yōu)先分析法 ?LR分析器 3 LR分析器 ?LR（ k）分析技術(shù)： ? L 指從左至右掃描輸入符號(hào)串 ? R 指構(gòu)造一個(gè)最右推導(dǎo)的逆過(guò)程（最左歸約） ? k 指在作出分析決定前（構(gòu)造分析表時(shí)）要向前看的輸入符號(hào)個(gè)數(shù)，通常為 0 或 1 ? LR 分析技術(shù)是功能最強(qiáng)的（自底向上）語(yǔ)法分析技術(shù)，適用文法廣，效率高，分析能力強(qiáng) 4 LR分析器 ?LR分析器的邏輯結(jié)構(gòu)： P90 Sm Xm Sm1 Xm1 . . S1 X1 S0 a1 ... ai ... an $ action 表 goto 表 LR 驅(qū)動(dòng)程序 棧 輸入 輸出 5 LR分析器 ?LR分析器的邏輯結(jié)構(gòu)： ? LR分析程序 —— 固定不變的 ? 分析表 —— 動(dòng)作表（ action）、狀態(tài)轉(zhuǎn)移表（ goto） ? 棧 —— 狀態(tài)符號(hào)、文法符號(hào) ? 輸入緩沖 ? 輸出 —— 產(chǎn)生式序列 6 LR分析器 ?LR分析器運(yùn)行： ? 根據(jù)當(dāng)前棧頂狀態(tài)符號(hào)與輸入符號(hào)查分析表決定下一步動(dòng)作 ? 假設(shè)當(dāng)前 （ s0X1s1X2s2… Xmsm, aiai+1…an$） action [sm, ai] = shift s （ s0X1s1X2s2… Xmsmais, ai+1…an$） action [sm, ai] = reduce A→ β （ s0X1s1X2s2… XmrsmrAs, aiai+1…an$） 7 LR分析器 ?LR分析算法： P 91 關(guān)鍵步驟 : s : 棧頂符號(hào) a : 當(dāng)前符號(hào) 1. 如果 action[s,a] = “accept” 停機(jī) , 接受 , 成功 2. 如果 action[s,a] = “reduce A ?β” 則 : 2a. 從棧中彈出 2 * |β| 個(gè)符號(hào) 2b. 把 A 壓入棧中 2c. 把 goto [ s* , A ] 壓入棧中 3. 如果 action[s,a] = “shift s*” 移進(jìn) 。 把 s* 壓入棧中 8 LR分析器 ?LR分析算法： ? LR分析的關(guān)鍵問(wèn)題是如何構(gòu)造分析表，不同的構(gòu)造方法形成不同的分析方法，主要有 LR（ 0）、 SLR、 LR（ 1）、 LALR 9 ? 例子： 分析句子： abbcde 文法 G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d a b b c d e A A B S a b b c d e A A B S 10 LR分析器 ACTION GOTO a c e b d $ S A B 0 S2 1 1 Acc 2 S4 3 3 S5 S6 4 R2 R2 R2 R2 R2 R2 5 S8 7 6 R3 R3 R3 R3 R3 R3 7 S9 8 R4 R4 R4 R4 R4 R4 9 R1 R1 R1 R1 R1 R1 LR(0)分析表 11 LR分析器 對(duì) abbcde$ 的分析過(guò)程 步驟 棧 輸入串 ACTION GOTO 1 0 abbcde$ S2 2 0a2 bbcde$ S4 3 0a2b4 bcde$ R2 3 4 0a2A3 bcde$ S6 5 0a2A3b6 cde$ R3 3 6 0a2A3 cde$ S5 7 0a2A3c5 de$ S8 8 0a2A3c5d8 e$ R4 7 9 0a2A3c5B7 e$ S9 10 0a2A3c5B7e9 $ R1 1 11 0S1 $ Acc 12 LR分析器 ?LR分析過(guò)程中的性質(zhì)與特點(diǎn)： ? 棧中的文法符號(hào)串并上剩余的輸入串構(gòu)成一個(gè)右句型（規(guī)范句型） ? 當(dāng)該右句型的句柄出現(xiàn)在棧頂時(shí)，歸約，否則，移進(jìn) ? 棧中的文法符號(hào)串是當(dāng)前（右）句型的前綴，該前綴不包含當(dāng)前句型的句柄后面的符號(hào)，稱(chēng)之為 活前綴 13 LR分析器 ? 活前綴：上例 aAbcde ? , a , aA , aAb ? 可歸前綴 ：包含完整句柄的活前綴 14 LR分析器 ? 可以證明：一個(gè)文法的規(guī)范句型的所有活前綴
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1