[工學(xué)]編譯原理第10章(已改無錯字)
2023-03-20 13:14:46 本頁面
【正文】 =B op C n1 B0 B n2 C0 C 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é)院 計算機系 《 編譯原理 》 25 簡介 DAG的構(gòu)造過程 p282 ? 函數(shù) NODE(A)—— 以名字 A在對應(yīng)表中查找結(jié)點 NODE(A)= n DAG中已 有 標(biāo)記為 A的結(jié)點，編號為 n NULL DAG中 無 標(biāo)記為 A的結(jié)點 ? 構(gòu)造 DAG的大致過程 – 對每一個三地址代碼，按其類型不同分別構(gòu)造 – 0型 A:=B ?NODE(B)=NULL 新建葉結(jié)點 標(biāo)記 B0 附加標(biāo)記 A ni B0 A ?NODE(B)≠NULL 找到標(biāo)記或附加標(biāo)記為 B的結(jié)點 附加標(biāo)記 A ni B ,A B0 注意：附加標(biāo)記 A時，若 DAG中原有附加標(biāo)記為 A的結(jié)點，則要把名字 A從原結(jié)點的附加標(biāo)記中刪除 進入下一環(huán)節(jié) ?copyright / 26 陜西理工學(xué)院 計算機系 《 編譯原理 》 26 簡介 DAG的構(gòu)造過程 p282 – 1型 A:=op B ?NODE(B)=NULL 新建葉結(jié)點 ni ni 若 B為常數(shù)，計算 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é)點 nj， 標(biāo)記 op 附加標(biāo)記 A ni B0 B (4)已有代表 op B的 nj nj再附加標(biāo)記 A (4) nj op X ,A (5)無代表 op B的結(jié)點 (5) 新 建結(jié)點 nj， 標(biāo)記 op 附加標(biāo)記 A A 注意：附加標(biāo)記 A時，刪除其它 DAG結(jié)點附加標(biāo)記的 A ?copyright / 27 陜西理工學(xué)院 計算機系 《 編譯原理 》 27 簡介 DAG的構(gòu)造過程 p282 – 2型 A:=B op C ?NODE(B)=NODE(C)=NULL 新建葉結(jié)點 ni,nj j=i+1 ni 若 B,C為常數(shù)，計算 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é)點 nk，標(biāo)記 op 附加標(biāo)記 A ni B0 B (4)已有代表 B op C的 nk nk再附加 A ,A (5)無代表 B op C的結(jié)點 新 建結(jié)點 nk，標(biāo)記 op 附加標(biāo)記 A nj C0 nj C0 C (4) nk op X (5) op A注意：附加標(biāo)記 A時，刪除其它 A ?copyright / 28 陜西理工學(xué)院 計算機系 《 編譯原理 》 28 僅含 0,1,2型代碼 的基本塊的 DAG構(gòu)造算法 p282 ? 開始 ， DAG為空。 ? 對基本塊中每一條中間代碼 ,依次執(zhí)行以下步驟 1.{判定代碼類型 } 如果 NODE(B)無定義 ，則構(gòu)造一 標(biāo)記為 B的葉 結(jié)點 并定義 NODE（ B）為這個結(jié)點。 – 如果當(dāng)前代碼是 0型 ，則記 NODE(B)的值為 n， 轉(zhuǎn) 4。 – 如果當(dāng)前代碼是 1型 ，則轉(zhuǎn) 2(1)。 – 如果當(dāng)前代碼是 2型 ，則： (I)如果 NODE(C)無定義 ，則構(gòu)造一 標(biāo)記為 C的葉結(jié) 點 并定義 NODE(C)為這個結(jié)點。 (II)轉(zhuǎn) 2(2) ?copyright / 29 陜西理工學(xué)院 計算機系 《 編譯原理 》 29 2． {合并已知量 } – (1)如果 NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點 ,則轉(zhuǎn) 2(3), 否則轉(zhuǎn) 3(1)。 – (2)如果 NODE(B)和 NODE(C)都是標(biāo)記為常數(shù)的葉結(jié) 點，則轉(zhuǎn) 2(4)，否則轉(zhuǎn) 3(2)。 – (3)執(zhí)行 op B，令得到的新常數(shù)為 P。如果 NODE(B) 是處理當(dāng)前代碼時新構(gòu)造出來的結(jié)點，則刪除它。 如果 NODE(P)無定義，則構(gòu)造一用 P做標(biāo)記的葉結(jié)點 n。置 NODE(P)=n，轉(zhuǎn) 4。 – (4)執(zhí)行 B op C，令得到的新常數(shù)為 P。如果 NODE(B) 或 NODE(C)是處理當(dāng)前代碼時新構(gòu)造出來的結(jié)點，則 刪除它。如果 NODE(P)無定義，則構(gòu)造一用 P做標(biāo)記的 葉結(jié)點 n。置 NODE(P)=n，轉(zhuǎn) 4。 ?copyright / 30 陜西理工學(xué)院 計算機系 《 編譯原理 》 30 3． {找公共子表達式 } – (1)檢查 DAG中是否已 有 一結(jié)點，其 唯一后繼為 NODE(B)， 且標(biāo)記為 op。如果 沒有 ，則 構(gòu)造該結(jié) 點 n，否則就把已有的結(jié)點作為它的結(jié)點并設(shè)該 結(jié)點為 n，轉(zhuǎn) 4。 – (2)檢查中 DAG中是否已 有 一結(jié)點，其 左后繼為 NODE(B)，其 右后繼為 NODE(C)，且標(biāo)記為 op。如 果
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1