[工學(xué)]編譯原理第10章-預(yù)覽頁(yè)
【正文】 n3 op A 2型 Ⅱ A:=B[C] n1 B0 B n2 C0 C n3 =[] A 2型 Ⅲ D [C]:=B n1 D0 D n2 C0 C n3 B0 B n4 []= 2型 Ⅳ if B rop C goto (S) n1 B0 B n2 C0 C n3 rop (S) 變址 取數(shù) 變址 存數(shù) 條件 轉(zhuǎn)移 ?copyright / 25 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 25 簡(jiǎn)介 DAG的構(gòu)造過(guò)程 p282 ? 函數(shù) NODE(A)—— 以名字 A在對(duì)應(yīng)表中查找結(jié)點(diǎn) NODE(A)= n DAG中已 有 標(biāo)記為 A的結(jié)點(diǎn)，編號(hào)為 n NULL DAG中 無(wú) 標(biāo)記為 A的結(jié)點(diǎn) ? 構(gòu)造 DAG的大致過(guò)程 – 對(duì)每一個(gè)三地址代碼，按其類型不同分別構(gòu)造 – 0型 A:=B ?NODE(B)=NULL 新建葉結(jié)點(diǎn) 標(biāo)記 B0 附加標(biāo)記 A ni B0 A ?NODE(B)≠NULL 找到標(biāo)記或附加標(biāo)記為 B的結(jié)點(diǎn) 附加標(biāo)記 A ni B ,A B0 注意：附加標(biāo)記 A時(shí)，若 DAG中原有附加標(biāo)記為 A的結(jié)點(diǎn)，則要把名字 A從原結(jié)點(diǎn)的附加標(biāo)記中刪除 進(jìn)入下一環(huán)節(jié) ?copyright / 26 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 26 簡(jiǎn)介 DAG的構(gòu)造過(guò)程 p282 – 1型 A:=op B ?NODE(B)=NULL 新建葉結(jié)點(diǎn) ni ni 若 B為常數(shù)，計(jì)算 p=op B 常數(shù) (2)NODE(p)=j 刪除 ni， nj附加標(biāo)記 A (1) p A ni (2) nj p A 若 B不為常數(shù)， ni標(biāo)記 B0 (3) ni B0 nj op A ?NODE(B)≠NULL NODE(B)=i (1)NODE(p)=NULL ni標(biāo)記 p 附加標(biāo)記 A (3)新 建結(jié)點(diǎn) nj， 標(biāo)記 op 附加標(biāo)記 A ni B0 B (4)已有代表 op B的 nj nj再附加標(biāo)記 A (4) nj op X ,A (5)無(wú)代表 op B的結(jié)點(diǎn) (5) 新 建結(jié)點(diǎn) nj， 標(biāo)記 op 附加標(biāo)記 A A 注意：附加標(biāo)記 A時(shí)，刪除其它 DAG結(jié)點(diǎn)附加標(biāo)記的 A ?copyright / 27 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 27 簡(jiǎn)介 DAG的構(gòu)造過(guò)程 p282 – 2型 A:=B op C ?NODE(B)=NODE(C)=NULL 新建葉結(jié)點(diǎn) ni,nj j=i+1 ni 若 B,C為常數(shù)，計(jì)算 p=B op C (2)NODE(p)=k 刪 ni nj,nk附加標(biāo)記 A (1) p A (2) nk p A 若 B,C不為常數(shù) ,ni標(biāo)記 B0,nj標(biāo)記 C0 (3) ni B0 nk op A ?NODE(B)≠NULL NODE(B)=i ?NODE(C)≠NULL NODE(C)=j (1)NODE(p)=NULL 刪 nj,ni標(biāo)記 p附加 A (3)新 建結(jié)點(diǎn) nk，標(biāo)記 op 附加標(biāo)記 A ni B0 B (4)已有代表 B op C的 nk nk再附加 A ,A (5)無(wú)代表 B op C的結(jié)點(diǎn) 新 建結(jié)點(diǎn) nk，標(biāo)記 op 附加標(biāo)記 A nj C0 nj C0 C (4) nk op X (5) op A注意：附加標(biāo)記 A時(shí)，刪除其它 A ?copyright / 28 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 28 僅含 0,1,2型代碼 的基本塊的 DAG構(gòu)造算法 p282 ? 開(kāi)始 ， DAG為空。 ?copyright / 14 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 14 基本塊入口語(yǔ)句的確定 p279 ? 確定規(guī)則 第一條 語(yǔ) 句；或者 句或無(wú)條件轉(zhuǎn)移 語(yǔ)句 轉(zhuǎn)移到的 語(yǔ) 句；或者 在 條件轉(zhuǎn)移 語(yǔ)句 后面的 語(yǔ)句 ? 舉例 (1)read X (2)read Y (3)R:=X mod Y (4)if R=0 goto(8) (5)X:=Y (6)Y:=R (7)goto(3) (8)write Y (9)halt 共 4個(gè)入口語(yǔ)句 規(guī)則 2 規(guī)則 1 規(guī)則 2 規(guī)則 3 ① ② ③ ④ ，對(duì)應(yīng) 4個(gè)基本塊 ?copyright / 15 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 15 劃分基本塊的算法 p279 ? ? ，構(gòu)造其所 屬的基本塊。 – 如果當(dāng)前代碼是 1型 ，則轉(zhuǎn) 2(1)。 – (3)執(zhí)行 op B，令得到的新常數(shù)為 P。 – (4)執(zhí)行 B op C，令得到的新常數(shù)為 P。 ?copyright / 30 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 30 3． {找公共子表達(dá)式 } – (1)檢查 DAG中是否已 有 一結(jié)點(diǎn)，其 唯一后繼為 NODE(B)， 且標(biāo)記為 op。 ?copyright / 31 陜西理工學(xué)院 計(jì)算機(jī)系 《 編譯原理 》 31 4.{附加標(biāo)記 A} – 如果 NODE(A)無(wú)定義 ，則把 A附加 在結(jié)點(diǎn) n上并令 NODE(A)=n； 否則先 把 A從 NODE(A)結(jié)點(diǎn)上附加標(biāo)識(shí) 符集中 刪除 （注意，如果 NODE(A)是葉結(jié)點(diǎn)，則其 標(biāo)記 A不刪除），把 A附加 到新結(jié)點(diǎn) n上并令 NODE(A)=n。（中國(guó)科技） D： =B*C E： =AB B： =B*C A： =ED 作業(yè)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1