new《編譯原理》第五章.ppt

《new《編譯原理》第五章.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《new《編譯原理》第五章.ppt（193頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

編譯原理CompilerPrinciples 蔣凌云jianglingyun 南京郵電大學(xué) 計(jì)算機(jī)學(xué)院 第五章語法制導(dǎo)翻譯及中間代碼生成 教材 編譯技術(shù)原理及其實(shí)現(xiàn)方法 王汝傳編著 第五章語法制導(dǎo)翻譯及中間代碼生成 本章內(nèi)容 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 5 2中間語言一 引言二 逆波蘭表示三 三元式四 樹形表示五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 本章內(nèi)容 5 3自底向上語法制導(dǎo)翻譯一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯二 布爾表達(dá)式的翻譯三 控制語句翻譯 四 數(shù)組元素的翻譯五 過程語句的翻譯六 說明語句的翻譯 5 4自頂向下語法制導(dǎo)翻譯一 遞歸下降的語法制導(dǎo)翻譯二 LL 1 語法制導(dǎo)翻譯 5 5屬性文法與屬性翻譯一 屬性文法與L屬性文法二 屬性翻譯 第五章語法制導(dǎo)翻譯及中間代碼生成 本節(jié)內(nèi)容 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 5 2中間語言一 引言二 逆波蘭表示三 三元式四 樹形表示五 四元式 5 1語法制導(dǎo)翻譯概述 本節(jié)內(nèi)容 一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 第五章語法制導(dǎo)翻譯及中間代碼生成 5 1語法制導(dǎo)翻譯概述在前面我們已經(jīng)討論了詞法分析和語法分析 一個(gè)程序成功地通過詞法分析和語法分析 只能說明它是一個(gè)合法程序 但是對(duì)程序內(nèi)部的邏輯含義并未加以考慮 從整個(gè)編譯程序來看 詞法分析和語法分析僅僅是編譯程序的一部分 編譯程序最終的目的是將源程序翻譯成可供計(jì)算機(jī)直接執(zhí)行的目標(biāo)程序 在某些編譯程序中 是直接生成機(jī)器語言或匯編語言形式的目標(biāo)代碼 有些編譯程序是把源程序翻譯為某種形式中間語言代碼 然后再把中間語言代碼翻譯為目標(biāo)代碼 下面就來介紹一種語法制導(dǎo)翻譯方法 這種方法先將源程序單詞序列翻譯成中間語言 然后再將中間語言翻譯成目標(biāo)程序 那么 什么叫語法制導(dǎo)翻譯呢 第五章語法制導(dǎo)翻譯及中間代碼 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 第五章語法制導(dǎo)翻譯及中間代碼 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義語法制導(dǎo)翻譯就是以語法分析為主導(dǎo)的語義處理 在自頂向下語法分析過程中嵌入語義動(dòng)作 即調(diào)用對(duì)應(yīng)的語義子程序 例如在前面語法分析時(shí)分析a b c表達(dá)式 其分析語法樹如下 E E E E E a b c 語法分析是將a歸約E 再將b歸約E 將c歸約為E 然后再將E E歸約成E 再將E E歸約成E 所以a b c是一個(gè)合法的句子 如果考慮語義 在歸約過程中加上語義動(dòng)作 先將a歸約為E 將a值賦給E后 b歸約成E 同時(shí)將b值賦給E 在將c值賦給E 然后再將b c E E 給E 最后再將左右兩個(gè)E值相加就是最終結(jié)果 這就是語法制導(dǎo)翻譯的基本思想 在語法分析同時(shí)進(jìn)行語義分析 第五章語法制導(dǎo)翻譯及中間代碼 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 第五章語法制導(dǎo)翻譯及中間代碼 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 5 1語法制導(dǎo)翻譯概述二 語法制導(dǎo)翻譯原理語法制導(dǎo)翻譯的原理就是先為每個(gè)文法規(guī)定相應(yīng)的語義 即編寫出相應(yīng)語義處理子程序 整個(gè)分析是以語法分析為主導(dǎo) 在自頂向下語法分析時(shí) 若某一個(gè)規(guī)則右部與輸入串相匹配時(shí) 或者 在自底向上語法分析時(shí) 當(dāng)一個(gè)規(guī)則被用于歸約時(shí) 此時(shí)該規(guī)則對(duì)應(yīng)的語義子程序就進(jìn)入工作 完成既定翻譯任務(wù) 產(chǎn)生與語義相應(yīng)的中間代碼或目標(biāo)代碼 語義動(dòng)作 給每個(gè)文法符號(hào)X賦以各種不同的語義值這里的語義值不一定指具體數(shù)值 可以是 類型 種屬 地址 或 代碼 等 我們用記號(hào)X TYPE X CAT或X VAL來表示這些值 如果某規(guī)則的右部有若干個(gè)同一符號(hào)出現(xiàn) 那么我們就用上角標(biāo)來區(qū)別這些符號(hào) 例如 假定有如下規(guī)則和語義動(dòng)作 例如 假定有如下規(guī)則和語義動(dòng)作 E E 1 E 2 E VAL E 1 VAL E 2 VAL 語義動(dòng)作寫在規(guī)則之后的花括號(hào)里 這里語義動(dòng)作是表明與規(guī)則左部文法符號(hào)E相關(guān)的語義值E VAL 它是通過把規(guī)則右部文法符號(hào)的語義值E 1 VAL和E 2 VAL加在一起來決定的 規(guī)則中終結(jié)符號(hào) 按語義規(guī)則被解釋成通常 加 的意思 各規(guī)則的語義動(dòng)作可以對(duì)表達(dá)式計(jì)算 也可以生成中間代碼 甚至還可以來產(chǎn)生目標(biāo)指令 例5 1設(shè)有文法 E E E E digit 這里digit代表0和9之間任一數(shù)字 如果我們的目的僅是為了求值 則語義動(dòng)作如下 1 E E 1 E E VAL E 1 VAL E 2 VAL 2 E digit E VAL digit 假定語義動(dòng)作中的 代表是整型加算術(shù)運(yùn)算 規(guī)則 1 的語義動(dòng)作為 E的語義值E VAL等于E 1 和E 2 的語義值E 1 VAL和E 2 VAL之和 規(guī)則 2 的語義動(dòng)作為 E的語義值為0 9之間任一個(gè)數(shù) 這樣 按照它們的語義動(dòng)作 我們?cè)诜治雒總€(gè)句子的同時(shí)一步一步地算出每個(gè)句子的值 例如 假定有輸入串1 2 3 我們通過語法樹的分析來看如何進(jìn)行語法制導(dǎo)翻譯 來求出該句子最后值 輸入串1 2 3的語法樹如下圖所示 下面我們采用自底向上歸約過程 首先考慮底層最左E的結(jié)點(diǎn) 這個(gè)結(jié)點(diǎn)對(duì)應(yīng)于規(guī)則E 1和語義動(dòng)作E VAL 1 這樣 底層最左的E的值1與語義值E VAL相關(guān) 類似地 值2與該結(jié)點(diǎn)的右兄弟的語義值E VAL相關(guān) 如下圖所示 E E E E E 1 2 3 在圖所示子樹中 子樹根處E VAL的語義值是3 這可用語義動(dòng)作E VAL E 1 VAL E 2 VAL算出 使用這個(gè)語義動(dòng)作時(shí) 以底部最左的E的E VAL的值來代替E 1 VAL 而以右邊E的E VAL的值代替E 2 VAL 以這種方法繼續(xù)下去 我們就推出如下圖所示整個(gè)語法樹每個(gè)結(jié)點(diǎn)的語義值 E E E VAL 1 E 1 2 E VAL 2 E E VAL 6 E E VAL 3 E E VAL 3 E E VAL 1 E E VAL 2 1 2 3 第五章語法制導(dǎo)翻譯及中間代碼 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 第五章語法制導(dǎo)翻譯及中間代碼 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 5 1語法制導(dǎo)翻譯概述三 語法制導(dǎo)翻譯實(shí)現(xiàn)上面我們從原則上討論了語法制導(dǎo)翻譯的原理 下面我們通過一個(gè)自底向上LR分析看如何實(shí)現(xiàn)語法制導(dǎo)翻譯 例如 有規(guī)則 1 X 動(dòng)作1 2 Y 動(dòng)作2 3 A XY 動(dòng)作3 當(dāng)使用規(guī)則 1 2 歸約時(shí) 動(dòng)作1 和 動(dòng)作2 工作結(jié)果的有關(guān)信息 作為X和Y的語義值 應(yīng)暫時(shí)保存下來 以便以后用規(guī)則 3 在歸約時(shí) 動(dòng)作3 可引用這些值 現(xiàn)在對(duì)LR分析器的分析棧加以擴(kuò)充 為了在語法分析過程中平行地進(jìn)行語義處理 使得每個(gè)文法符號(hào)之后都跟著它的語義值 因此 設(shè)置一個(gè)語義信息棧 為了清晰起見 我們把這個(gè)分析棧每一項(xiàng)分三部分組成 狀態(tài)STATE 文法符號(hào)SYM和語義值VAL 這樣 分析棧如下圖所示 TOP STATE VAL SYM TOP 100 歸約前 TOP 99 歸約后 Y VAL TOP 99 求值后 A VAL Y VAL和X VAL的處理結(jié)果 我們假定先歸約后執(zhí)行語義子程序 所以當(dāng)X Y歸約為A時(shí) 此時(shí)棧頂指針下退 例如 開始TOP指100VAL TOP Y VAL 100 VAL TOP 1 X VAL 99 若歸約后 此時(shí)TOP指99 所以VAL TOP X VAL 99 VAL TOP 1 Y VAL 100 若求值后 此時(shí)TOP指99 所以VAL TOP A VAL 99 例5 2考慮下面文法及其語義描述 規(guī)則語義動(dòng)作 0 S E printE VAL 1 E E 1 E 2 E VAL E 1 VAL E 2 VAL 2 E E 1 E 2 E VAL E 1 VAL E 2 VAL 3 E E 1 E VAL E 1 VAL 4 E i E VAL LEXVAL 其中 語義動(dòng)作中的 代表整型加 乘算術(shù)運(yùn)算 而且詞法分析程序?qū)⑺蛠砻總€(gè)i的整型內(nèi)部值LEXVAL 假定語義動(dòng)作是緊接在歸約之后執(zhí)行的 上面所列的語義動(dòng)作就相當(dāng)于下面所列的程序段 規(guī)則程序段 0 S E printVAL TOP 1 E E 1 E 2 VAL TOP VAL TOP VAL TOP 2 2 E E 1 E 2 VAL TOP VAL TOP VAL TOP 2 3 E E 1 VAL TOP VAL TOP 1 4 E i VAL TOP LEXVAL 由于有一個(gè) 號(hào) 所以為TOP 2 由于有一個(gè) 號(hào) 所以為TOP 1 由于有一個(gè) 號(hào) 所以為TOP 2 根據(jù)上述程序段 若輸入2 3 2 就有如下圖所示的語法制導(dǎo)翻譯的分析樹 S E E E E E 2 2 3 E VAL 8 E VAL 6 E VAL 2 E VAL 2 E VAL 3 LEXVAL 2 LEXVAL 3 LEXVAL 2 對(duì)2 3 2利用P136 表4 23進(jìn)行分析和翻譯 實(shí)為計(jì)算值 該輸入串過程如下表所示 當(dāng)狀態(tài)1面臨 時(shí)對(duì)應(yīng)的分析動(dòng)作為acc 接受 此時(shí) 相應(yīng)的語義動(dòng)作為printVAL TOP 即輸出語義程序的計(jì)值結(jié)果 8 第五章語法制導(dǎo)翻譯及中間代碼生成 本節(jié)內(nèi)容 5 1語法制導(dǎo)翻譯概述一 語法制導(dǎo)翻譯定義二 語法制導(dǎo)翻譯原理三 語法制導(dǎo)翻譯實(shí)現(xiàn) 5 2中間語言一 引言二 逆波蘭表示三 三元式四 樹形表示五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言一 引言1 什么是中間語言就是和源程序等價(jià)的一種編碼形式 其復(fù)雜性介于源程序和機(jī)器語言中間 源程序 前端 中間代碼 代碼優(yōu)化器 中間代碼 代碼生成器 目標(biāo)程序 符號(hào)表 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言一 引言2 為什么要引入中間語言 1 為了使編譯程序結(jié)構(gòu)上邏輯簡(jiǎn)單明確 2 為了便于目標(biāo)代碼優(yōu)化工作 3 便于目標(biāo)代碼生成 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示 1 波蘭表示的概念對(duì)于一個(gè)算術(shù)表達(dá)式A B或邏輯表達(dá)式A B 根據(jù)運(yùn)算符和運(yùn)算對(duì)象的位置關(guān)系 可分為三種等價(jià)表示形式 1 中綴表示法運(yùn)算符在運(yùn)算對(duì)象中間 如 A B A B a b c d e f 等 2 后綴表示法將運(yùn)算符放在運(yùn)算對(duì)象后面 通常將后綴表示稱為逆波蘭表示 如 A B表示為AB A B表示為AB a b c表示為abc 對(duì)于逆波蘭表示非常適合機(jī)械處理 只要從左到右按運(yùn)算順序一個(gè)個(gè)計(jì)算下去3 前綴表示法即將運(yùn)算符放在運(yùn)算對(duì)象前面 如 AB AB 例如表達(dá)式中綴表示和后綴表示如下表所示 p155表5 2 說明 以后我們主要討論逆波蘭表示 即后綴表示 因前綴表示并不常用 所以有時(shí)也將后綴表示籠統(tǒng)地統(tǒng)稱為波蘭表示 從上表中可以看出 1 在中綴表示和后綴表示中 運(yùn)算對(duì)象按相同次序出現(xiàn) 2 在后綴表示中 運(yùn)算符是按實(shí)際計(jì)算順序從左到右排列 且每一運(yùn)算符總是跟在它的運(yùn)算對(duì)象之后 2 逆波蘭 后綴 表示的優(yōu)點(diǎn)1 后綴表示是一種無括號(hào)表示法 不但簡(jiǎn)明 而且又確切規(guī)定了計(jì)算順序 2 運(yùn)算處理極其簡(jiǎn)單方便 只要從左到右掃描后綴表達(dá)式各個(gè)符號(hào) 就能進(jìn)行對(duì)表達(dá)式的處理一般步驟是從左到右掃描后綴表達(dá)式各個(gè)符號(hào) 每碰到運(yùn)算對(duì)象時(shí)就把它推進(jìn)棧 每碰到一個(gè)K元運(yùn)算符時(shí) 就取出棧頂?shù)腒個(gè)運(yùn)算對(duì)象進(jìn)行相應(yīng)的運(yùn)算 并且用運(yùn)算結(jié)果去替換棧頂?shù)腒個(gè)運(yùn)算對(duì)象 然后再繼續(xù)掃描表達(dá)式中余留符號(hào) 如此等等 直到整個(gè)表達(dá)式計(jì)算完畢為止 當(dāng)上述過程結(jié)束后 整個(gè)表達(dá)式之值將留于棧頂 3 便于生成目標(biāo)指令 3 逆波蘭 后綴 表示的形成為了說明逆波蘭 后綴 表示的形成 荷蘭學(xué)者W DEJKSTRA給出下面形象的解釋 比棧頂高進(jìn)棧 比棧頂?shù)突蛳嗤耐藯?下面用圖解形式來說明A B C形成的過程 A 運(yùn)算對(duì)象A移進(jìn)對(duì)象棧 B C 下面用圖解形式來說明A B C形成的過程 A 向下進(jìn)運(yùn)算符棧 B C 下面用圖解形式來說明A B C形成的過程 AB 運(yùn)算對(duì)象B移進(jìn)對(duì)象棧 C 下面用圖解形式來說明A B C形成的過程 AB 向下進(jìn)運(yùn)算符棧 C 下面用圖解形式來說明A B C形成的過程 ABC 運(yùn)算對(duì)象C移進(jìn)對(duì)象棧 下面用圖解形式來說明A B C形成的過程 ABC 退棧往左 下面用圖解形式來說明A B C形成的過程 ABC 退棧往左 最后生成A B C的后綴式ABC 4 用后綴表式對(duì)表達(dá)式處理的過程下面通過求后綴表達(dá)式ab c 的值 來說明用后綴表式對(duì)表達(dá)式處理的過程設(shè)a b和c分別為1 3和5 為了求13 5 的值 其計(jì)算過程如下 1 把1推進(jìn)棧 2 把3推進(jìn)棧 3 將棧頂兩個(gè)元素1和3相加 使它們退出棧 然后把結(jié)果4存入棧 4 把5推進(jìn)棧 5 將棧頂兩個(gè)元素4和5相乘 使它們退出棧 然后將結(jié)果20存入棧 結(jié)束時(shí)棧頂?shù)闹?這里是20 是整個(gè)表達(dá)式值 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言二 逆波蘭表示2 逆波蘭表示的擴(kuò)充只要遵守在運(yùn)算對(duì)象后直接緊跟運(yùn)算符這條規(guī)則 我們就可以簡(jiǎn)單地把這種后綴式擴(kuò)充到比通常表達(dá)式更大范圍 即擴(kuò)充到程序語言的其它語法成分 1 賦值語句 左部 表達(dá)式 把賦值號(hào) 看成是一個(gè)賦值運(yùn)算符 它的后綴式為 左部 表達(dá)式的后綴式 例如 x 5x a b c d的后綴式分別為x5 xab cd 賦值語句的后綴式的處理方法和后綴式表達(dá)式處理方法類似 所不同的是棧中保存的是左部變量的地址 而不是其值 在賦值運(yùn)算處理結(jié)束后 不產(chǎn)生任何中間計(jì)算結(jié)果 因而也不存在保存中間計(jì)算結(jié)果的問題 而是把存放在運(yùn)算棧中棧頂兩項(xiàng) 左部 和 表達(dá)式 的值這兩個(gè)量退掉 2 條件語句ifEthenS1elseS 對(duì)于用后綴式來表示條件語句 我們假定后綴式中各符號(hào)存放在一個(gè)一維數(shù)組POST 1 n 之中 每一個(gè)數(shù)組元素存放一個(gè)運(yùn)算對(duì)象或運(yùn)算符 同時(shí)我們約定如下幾個(gè)符號(hào) JUMP表示無條件轉(zhuǎn) JLT表示小于轉(zhuǎn) JEZ表示零轉(zhuǎn) 后綴式PJUMP表示無條件轉(zhuǎn)移到下標(biāo)P所指那個(gè)元素POST p 即從該符號(hào)開始繼續(xù)執(zhí)行 后綴式ePJEZ表示當(dāng)后綴表達(dá)式e的值為零時(shí) 則轉(zhuǎn)移至POST P 后綴式e1e2PJLT表示當(dāng)后綴表達(dá)式e1小于后綴表達(dá)式e2時(shí) 則轉(zhuǎn)移至POST P 于是 對(duì)于形如 ifethenS1elseS2 的條件語句可按后綴式寫成e p1JEZS1 p2JUMPS2 我們約定e 0時(shí) 該條件語句的值是S1 否則等于S2 對(duì)于后綴式條件語句中 e S1 和S2 分別是e S1和S2的后綴式 此外 p1表示S2 在數(shù)組POST的起始位置 p2表示S2 之后那個(gè)符號(hào)位置 上述后綴式條件語句的意思是 若e 0時(shí) 則轉(zhuǎn)至POST p1 對(duì)S2 進(jìn)行計(jì)算 否則計(jì)算S1 然后轉(zhuǎn)到POST p2 的位置 e p1JEZS1 p2JUMPS2 p1和p2等處理S2后再反填 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言二 逆波蘭表示3 語法制導(dǎo)翻譯生成后綴式下面我們討論語法制導(dǎo)翻譯生成后綴式的過程 我們以例4 15文法G E 為例 說明如何按語法制導(dǎo)翻譯方法把一個(gè)中綴形式的簡(jiǎn)單算術(shù)表達(dá)式翻譯成為后綴式 后綴式的語義動(dòng)作規(guī)則語義動(dòng)作 1 E E 1 T E CODE E 1 CODE T CODE 2 E T E CODE T CODE 3 T T 1 F T CODE T 1 CODE F CODE 4 T F T CODE F CODE 5 F E F CODE E CODE 6 F i F CODE i 幾點(diǎn)說明 E CODE T CODE F CODE表示構(gòu)成后綴式的符號(hào)串符號(hào) 表示兩個(gè)串的 捻接 運(yùn)算 即并置運(yùn)算 顯然 E 1 CODE T CODE 是E CODE 因?yàn)榉?hào)在后 其它類似 下面將上述語義動(dòng)作具體化成語義子程序 自底向上分析要?dú)w約時(shí)先調(diào)用相應(yīng)子程序生成后綴式假定后綴式存放在數(shù)組POST中假設(shè)要?dú)w約的句柄為E 1 T 在語法分析棧中 則首先要求調(diào)用相應(yīng)于E 1 T的語義子程序 此時(shí)E 1 和T已調(diào)用過相應(yīng)的語義子程序 因此 它們的后綴式已被生成 對(duì)應(yīng)于E 1 T的語義子程序所要完成的工作是把已生成的兩后綴式捻接起來 然后再添上符號(hào) 如果我們?cè)O(shè)置一個(gè)數(shù)組存放后綴式 那么語義動(dòng)作就可以不涉及捻接運(yùn)算 令這個(gè)數(shù)組為POST p為下標(biāo) 初值為1 如下圖 POST P 對(duì)于上述文法G E 的語義動(dòng)作 可以改寫為如下相應(yīng)的語義子程序 1 E E 1 T POST p p p 1 2 E T 3 T T 1 F POST p p p 1 4 T F 5 F E 6 F i POST p i p p 1 最后 我們以表達(dá)式a b c為例按照P118 表4 15文法G E LR分析表給出語法制導(dǎo)翻譯產(chǎn)生后綴式過程 其中SUBK表示第K個(gè)規(guī)則相對(duì)應(yīng)的語義子程序 分析過程如下表 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言三 三元式表示1 三元式 1 定義三元式的一般形式為 i OP ARG1 ARG2 其中 i 為三元式的編號(hào) 不同三元式不能有相同的編號(hào)OP是運(yùn)算符部分ARG1和ARG2是運(yùn)算對(duì)象部分 它們或者指向符號(hào)表登記項(xiàng)指示器 對(duì)于運(yùn)算對(duì)象是常數(shù)或標(biāo)識(shí)符的情況 或者是一個(gè)指向三元式序列 或三元式表 中某一個(gè)三元式位置的指示器 對(duì)于運(yùn)算對(duì)象是中間結(jié)果的情況 如 A B C對(duì)應(yīng)的三元式表示為 1 B C 2 A 1 注 運(yùn)算符OP通常用一個(gè)整數(shù)碼表示 它除了標(biāo)識(shí)運(yùn)算符的種屬之外 還附帶地表示其它一些語義特性 例如若OP表示一個(gè)加法運(yùn)算符 則相應(yīng)的整數(shù)碼除了標(biāo)識(shí)加法運(yùn)算本身外 還兼有表示數(shù)據(jù)類型 如整型 實(shí)型等 運(yùn)算方式 定點(diǎn) 浮點(diǎn) 和運(yùn)算精度等信息 且不同語義屬性使用不同的運(yùn)算符代碼 對(duì)于一目運(yùn)算符OP ARG1和ARG2只需其一 我們可以隨意規(guī)定選用一個(gè) 例如 規(guī)定用ARG1 至于多目運(yùn)算符可以用若干個(gè)相繼三元式表示 如 賦值語句x b c d 用三元式來表示 則可寫成 1 b 2 c d 3 1 2 4 x 3 其中 三元式 3 就引用三元式 1 和 2 的結(jié)果作為它的兩個(gè)運(yùn)算對(duì)象 三元式出現(xiàn)先后順序和表達(dá)式各部分計(jì)算順序相一致 2 三元式的生成同樣可以用語法制導(dǎo)翻譯來產(chǎn)生三元式 下面給出文法G E 的語義動(dòng)作來描述這種翻譯的算法 1 E E 1 T E VAL TRIP E 1 VAL T VAL 2 E T E VAL T VAL 3 T T 1 F T VAL TRIP T 1 VAL F VAL 4 T F T VAL F VAL 5 F E F VAL E VAL 6 F i F VAL ENTRY i 其中語義值E VAL T VAL和F VAL 是一個(gè)指示器 或指向有關(guān)符號(hào)表某一項(xiàng) 或指向三元式表自身某一項(xiàng) TRIP OP ARG1 ARG2 是一個(gè)語義子程序 回送新產(chǎn)生的三元式存放在三元式表位置 ENTRY i 是一個(gè)語義子程序 通過ENTRY查i在符號(hào)表中位置 即對(duì)應(yīng)地址 若查不到 認(rèn)為有錯(cuò)誤 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言三 三元式表示2 間接三元式為了便于代碼優(yōu)化 常常采用間接三元式 這由兩張表組成 1 三元式表 用來存放各三元式本身 2 執(zhí)行表 間接碼表 它按執(zhí)行三元式順序 依次列出相應(yīng)各三元式在三元式表中位置 例如 對(duì)于如下賦值語句 x a b c a b 若按三元式表示 可寫成 按間接三元式表示 則可寫成 執(zhí)行表三元式表 1 1 a b 2 2 1 c 1 3 2 1 3 4 x 3 4 1 a b 2 1 c 3 a b 4 2 3 5 x 4 其中 三元式 1 和 3 完全一樣 但是不能將 3 省去 間接三元式的優(yōu)點(diǎn) 1 便于代碼優(yōu)化在進(jìn)行代碼優(yōu)化時(shí) 常常要從中間代碼刪去一些運(yùn)算 或者把某些運(yùn)算移到另外位置上 若采用一般三元式 則由于三元式之間引用太多 很難做到這一點(diǎn) 2 節(jié)省空間由于在間接三元式執(zhí)行表中已經(jīng)依次列出每次要執(zhí)行的那個(gè)三元式 所以 若有若干個(gè)相同三元式 則僅須在三元式表中保存其中之一 如上面賦值語句右部表達(dá)式中有兩個(gè)a b子表達(dá)式 而三元式表中只出現(xiàn)一次 a b 對(duì)于間接三元式表示 語義子程序應(yīng)增添產(chǎn)生執(zhí)行表的動(dòng)作 在填寫三元式表時(shí) 應(yīng)首先看一下此三元式是否在其中 如已在其中 則無需填入 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言四 樹形表示1 表示方法我們可以用樹形數(shù)據(jù)結(jié)構(gòu)來表示一個(gè)表達(dá)式或語句 在樹表示中 葉子結(jié)點(diǎn)表示運(yùn)算對(duì)象 即常量或變量 其它結(jié)點(diǎn)表示運(yùn)算符 如表達(dá)式 a b a b a 的樹表示分別定義為 a b a b a 雙目運(yùn)算對(duì)應(yīng)二叉樹 多目運(yùn)算對(duì)應(yīng)多叉樹 單目運(yùn)算對(duì)應(yīng)單叉樹 如表達(dá)式a b c d e f 的二叉樹如下圖 后序遍歷上述二叉樹便得到該表達(dá)式的逆波蘭表示為ab cd ef a b c d e f 表達(dá)式的三元式可以看作是樹的直接表示 圖5 7所對(duì)應(yīng)的三元式為 1 a b 2 c d 3 e f 4 2 3 5 1 4 顯然 每一個(gè)三元式對(duì)應(yīng)一棵子樹 子樹的根便是三元式的運(yùn)算符 三元式的運(yùn)算對(duì)象是子樹兩個(gè)分枝 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言四 樹形表示2 樹表示生成對(duì)文G E 翻譯成樹形表示語義動(dòng)作描述如下 1 E E 1 T E VAL NODE E 1 VAL T VAL 2 E T E VAL T VAL 3 T T 1 F T VAL NODE T 1 VAL F VAL 4 T F T VAL F VAL 5 F E F VAL E VAL 6 F i F VAL LEAF i 其中 語義值E VAL T VAL和F VAL是一個(gè)指示器 指向樹一個(gè)結(jié)點(diǎn) NODE OP LEFT RIGHT 是一個(gè)函數(shù)子程序 OP是一個(gè)二元運(yùn)算符 LEFT RIGHT為指示器 每調(diào)用此函數(shù)一次 就建立一個(gè)新結(jié)點(diǎn) 其標(biāo)記為OP LEFT和RIGHT分別指向左右子樹根結(jié)點(diǎn)指針 從NODE回送的值是一個(gè)指示器 指向這棵新樹的根 LEAF i 是建立一個(gè)末端結(jié)點(diǎn) 葉結(jié)點(diǎn) 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 第五章語法制導(dǎo)翻譯及中間代碼生成 5 2中間語言一 引言1 什么是中間語言2 為什么要引入中間語言二 逆波蘭表示1 表達(dá)式逆波蘭表示2 逆波蘭表示的擴(kuò)充3 語法制導(dǎo)翻譯生成后綴式三 三元式1 三元式2 間接三元式四 樹形表示1 表示方法2 樹表示生成五 四元式 5 2中間語言五 四元式表示 四元式是一種用得比較多的一種中間語言代碼形式 四元式一般形式是 OP ARG1 ARG2 RESULT 其中 OP是運(yùn)算符 其含義與三元式中OP類似 ARG1和ARG2是運(yùn)算對(duì)象 RESULT是運(yùn)算結(jié)果 例如 賦值語句a b c d 用四元式表示 則可寫成 1 b T1 2 c d T2 3 T1 T2 T3 4 T3 a 四元式之間聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的 調(diào)整四元式之間相對(duì)位置并不意味著一定要改變一系列指示器值 因此 對(duì)中間代碼進(jìn)行優(yōu)化處理時(shí) 四元式比三元式方便得多 下面主要討論如何用四元式表示各種語句 并產(chǎn)生四元式語義子程序 第五章語法制導(dǎo)翻譯及中間代碼生成 本節(jié)內(nèi)容 5 3自底向上語法制導(dǎo)翻譯一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯二 布爾表達(dá)式的翻譯三 控制語句翻譯四 數(shù)組元素的翻譯五 過程語句的翻譯六 說明語句的翻譯 5 4自頂向下語法制導(dǎo)翻譯一 遞歸下降的語法制導(dǎo)翻譯二 LL 1 語法制導(dǎo)翻譯 5 5屬性文法與屬性翻譯一 屬性文法與L屬性文法二 屬性翻譯 第五章語法制導(dǎo)翻譯及中間代碼生成 5 3自底向上語法制導(dǎo)翻譯 一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式2 類型檢查與類型轉(zhuǎn)換二 布爾表達(dá)式的翻譯1 概述2 布爾表達(dá)式的翻譯方法3 翻譯成四元式的實(shí)現(xiàn)三 控制語句翻譯1 語句標(biāo)號(hào)和goto語句的翻譯2 條件語句的翻譯3 布爾表達(dá)式的翻譯方法4 while循環(huán)語句翻譯5 for循環(huán)語句的翻譯 四 數(shù)組元素的翻譯1 下標(biāo)變量地址的計(jì)算2 數(shù)組元素的翻譯五 過程語句的翻譯1 參數(shù)傳遞方式2 過程語句的翻譯六 說明語句的翻譯1 變量說明的翻譯2 數(shù)組說明的翻譯3 過程說明的翻譯 第五章語法制導(dǎo)翻譯及中間代碼生成 5 3自底向上語法制導(dǎo)翻譯 一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式2 類型檢查與類型轉(zhuǎn)換二 布爾表達(dá)式的翻譯1 概述2 布爾表達(dá)式的翻譯方法3 翻譯成四元式的實(shí)現(xiàn)三 控制語句翻譯1 語句標(biāo)號(hào)和goto語句的翻譯2 條件語句的翻譯3 布爾表達(dá)式的翻譯方法4 while循環(huán)語句翻譯5 for循環(huán)語句的翻譯 四 數(shù)組元素的翻譯1 下標(biāo)變量地址的計(jì)算2 數(shù)組元素的翻譯五 過程語句的翻譯1 參數(shù)傳遞方式2 過程語句的翻譯六 說明語句的翻譯1 變量說明的翻譯2 數(shù)組說明的翻譯3 過程說明的翻譯 第五章語法制導(dǎo)翻譯及中間代碼生成 5 3自底向上語法制導(dǎo)翻譯 一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式2 類型檢查與類型轉(zhuǎn)換二 布爾表達(dá)式的翻譯1 概述2 布爾表達(dá)式的翻譯方法3 翻譯成四元式的實(shí)現(xiàn)三 控制語句翻譯1 語句標(biāo)號(hào)和goto語句的翻譯2 條件語句的翻譯3 布爾表達(dá)式的翻譯方法4 while循環(huán)語句翻譯5 for循環(huán)語句的翻譯 四 數(shù)組元素的翻譯1 下標(biāo)變量地址的計(jì)算2 數(shù)組元素的翻譯五 過程語句的翻譯1 參數(shù)傳遞方式2 過程語句的翻譯六 說明語句的翻譯1 變量說明的翻譯2 數(shù)組說明的翻譯3 過程說明的翻譯 5 3自底向上語法制導(dǎo)翻譯一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式我們首先討論僅含有簡(jiǎn)單變量的表達(dá)式和賦值語句到四元式的翻譯 對(duì)于復(fù)雜的表達(dá)式和賦值語句的翻譯將在以后討論 為簡(jiǎn)便起見 假定賦值語句中所含的全部變量是同一類型整型變量 此外在翻譯過程中也不作語義檢查 1 賦值語句的文法1 A V E5 T F2 E E 1 T6 F E 3 E T7 F i4 T T 1 F8 V i為了實(shí)現(xiàn)到四元式的翻譯 需要引進(jìn)一系列語義變量和語義子程序 2 語義變量和語義子程序 NEWTEMP是一個(gè)函數(shù) 每次調(diào)用時(shí) 都定義一個(gè)新臨時(shí)變量 回送一個(gè)代表新臨時(shí)變量名的整數(shù)碼作為函數(shù)值 為直觀起見 我們將NEWTEMP產(chǎn)生的臨時(shí)變量依次記為T 等等 ENTRY i 是一個(gè)函數(shù)過程 查找符號(hào)名i在表中的入口地址 X PLACE是和非終結(jié)符X相聯(lián)系的語義變量 表示存放X值的變量名在符號(hào)表的入口或整數(shù)碼 若此變量是一個(gè)臨時(shí)變量 如 F i F PLACE ENTRY i 表示存放F值變量名i在符號(hào)表中的入口地址 即從變量F PLACE值可知i在符號(hào)表中的位置 GEN OP ARG1 ARG2 RESULT 是一個(gè)語義過程 該過程把四元式 OP ARG1 ARG2 RESULT 填入四元式表中 因此 上面定義文法G A 語義子程序的描述如下 3 語義子程序的描述 1 A V E GEN E PLACE V PLACE 2 E E 1 T E PLACE NEWTEMP GEN E 1 PLACE T PLACE E PLACE 3 E T E PLACE T PLACE 4 T T 1 F T PLACE NEWTEMP GEN T 1 PLACE F PLACE T PLACE 5 T F T PLACE F PLACE 6 F E F PLACE E PLACE 7 F i F PLACE ENTRY i 8 V i V PLACE ENTRY i 在進(jìn)行自底向上語法制導(dǎo)翻譯時(shí) 還需一張LR分析表 上述文法G A 是一個(gè)SLR 1 文法 其分析表如下 4 文法G A SLR 1 分析表 5 對(duì)x a b c語法制導(dǎo)翻譯產(chǎn)生四元式過程 以賦值語句x a b c為例 分析表幾點(diǎn)說明 在分析表中Vx Ea Tb Fc之類記號(hào) 表示與非終結(jié)符V E T F相關(guān)聯(lián)的V PLACE E PLACE T PLACE F PLACE中存放著ENTRY x ENTRY a ENTRY b ENTRY c 符號(hào)指針 指向符號(hào)表 在四元式中 如 b c T1 實(shí)際上是某種整數(shù)編碼 反映運(yùn)算符本身及其信息特征 如類型等 b c實(shí)際上也是指示器 指示符號(hào)表入口 T1是臨時(shí)變量 實(shí)際上也是整數(shù)碼 下面我們根據(jù)上面分析表敘述對(duì)x a b c語法制導(dǎo)翻譯產(chǎn)生四元式過程 第五章語法制導(dǎo)翻譯及中間代碼生成 5 3自底向上語法制導(dǎo)翻譯 一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式2 類型檢查與類型轉(zhuǎn)換二 布爾表達(dá)式的翻譯1 概述2 布爾表達(dá)式的翻譯方法3 翻譯成四元式的實(shí)現(xiàn)三 控制語句翻譯1 語句標(biāo)號(hào)和goto語句的翻譯2 條件語句的翻譯3 布爾表達(dá)式的翻譯方法4 while循環(huán)語句翻譯5 for循環(huán)語句的翻譯 四 數(shù)組元素的翻譯1 下標(biāo)變量地址的計(jì)算2 數(shù)組元素的翻譯五 過程語句的翻譯1 參數(shù)傳遞方式2 過程語句的翻譯六 說明語句的翻譯1 變量說明的翻譯2 數(shù)組說明的翻譯3 過程說明的翻譯 5 3自底向上語法制導(dǎo)翻譯一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯2 類型檢查與類型轉(zhuǎn)換 1 目的1 類型檢查是編譯程序語義檢查不可缺少的一部分 類型檢查就是對(duì)訪問數(shù)據(jù)的操作和被訪問數(shù)據(jù)的類型進(jìn)行檢查檢查操作的合法性和數(shù)據(jù)類型的相容性 例如 在PASCAL語言中 若算術(shù)運(yùn)算符的操作數(shù)為布爾量 或者賦給實(shí)型變量值是個(gè)指針 則編譯程序報(bào)告 類型不相容 的診斷信息 2 允許類型混合 但在處理時(shí)要統(tǒng)一 所以必須進(jìn)行類型轉(zhuǎn)換 例如 加法運(yùn)算 允許運(yùn)算對(duì)象是整型數(shù)或?qū)嵭蛿?shù) 如果一個(gè)運(yùn)算對(duì)象是實(shí)型 另一個(gè)運(yùn)算對(duì)象是整型 其運(yùn)算結(jié)果的類型是實(shí)型 由于實(shí)型數(shù)和整型數(shù)的內(nèi)部表示不相同 因此為了使整型數(shù)能參加實(shí)型數(shù)運(yùn)算 必須事先將整型數(shù)轉(zhuǎn)換成實(shí)型數(shù) 2 類型檢查類型檢查可在生成中間代碼時(shí)進(jìn)行 也可在生成目標(biāo)代碼時(shí)進(jìn)行 但最好是在生成中間代碼時(shí)進(jìn)行 因?yàn)檎Z法和語義檢查最好盡早進(jìn)行 這樣能盡早避免徒勞的工作 在上面對(duì)簡(jiǎn)單算術(shù)表達(dá)式和賦值語句翻譯到四元式的討論中 我們假定各個(gè)變量是同一類型整型變量 并且規(guī)定在四元式的op代碼中 本身就會(huì)有類型信息 所以 在上例各語義子程序中 我們并未考慮有關(guān)類型方面語義處理 3 類型轉(zhuǎn)換方法為了簡(jiǎn)單起見 我們僅考慮整型和實(shí)型的情況 這種混合運(yùn)算中 給每個(gè)非終結(jié)符的語義值增添類型信息X MODEX MODE的值或?yàn)閞 實(shí)型 或?yàn)閕nt 整型 原來X的信息除X PLACE 還有X MODE 對(duì)表達(dá)式的每一規(guī)則的語義子程序進(jìn)行修改 增加關(guān)于類型信息的語義規(guī)則 必要時(shí)應(yīng)產(chǎn)生對(duì)運(yùn)算量進(jìn)行類型轉(zhuǎn)換的四元式 itr A T 把整型變量A轉(zhuǎn)換成實(shí)型變量 結(jié)果存在T中 此外 在書寫語義子程序時(shí) 為閱讀上的直觀性 我們用 i i等表示整型運(yùn)算符 用 r r等表示實(shí)型運(yùn)算符 現(xiàn)以規(guī)則E E 1 OPE 2 為例 給出語義子程序的具體描述如下 現(xiàn)以規(guī)則E E 1 OPE 2 為例 給出語義子程序的具體描述如下 T NEWTEMP IFE 1 MODE intANDE 2 MODE intTHEN BEGINGEN opi E 1 PLACE E 2 PLACE T E MODE int END ELSEIFE 1 MODE rANDE 2 MODE rTHEN BEGINGEN opr E 1 PLACE E 2 PLACE T E MODE r END ELSEIFE 1 MODE int andE 2 MODE r THEN BEGINU NEWTEMP GEN itr E 1 PLACE U GEN opr U E 2 PLACE T E MODE r END ELSE E 1 MODE randE 2 MODE int BEGINU NEWTEMP GEN itr E 2 PLACE U GEN opr E 1 PLACE U T E MODE r END E PLACE T 這樣 對(duì)于輸入串為 X 2 A I 1 其中I為整型量 X A為實(shí)型量 則產(chǎn)生四元式序列為 itr 2 T1 r X T T i I 1 T3 itr T3 T r A T4 T5 r T2 T5 T6 第五章語法制導(dǎo)翻譯及中間代碼生成 5 3自底向上語法制導(dǎo)翻譯 一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式2 類型檢查與類型轉(zhuǎn)換二 布爾表達(dá)式的翻譯1 概述2 布爾表達(dá)式的翻譯方法3 翻譯成四元式的實(shí)現(xiàn)三 控制語句翻譯1 語句標(biāo)號(hào)和goto語句的翻譯2 條件語句的翻譯3 布爾表達(dá)式的翻譯方法4 while循環(huán)語句翻譯5 for循環(huán)語句的翻譯 四 數(shù)組元素的翻譯1 下標(biāo)變量地址的計(jì)算2 數(shù)組元素的翻譯五 過程語句的翻譯1 參數(shù)傳遞方式2 過程語句的翻譯六 說明語句的翻譯1 變量說明的翻譯2 數(shù)組說明的翻譯3 過程說明的翻譯 第五章語法制導(dǎo)翻譯及中間代碼生成 5 3自底向上語法制導(dǎo)翻譯 一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式2 類型檢查與類型轉(zhuǎn)換二 布爾表達(dá)式的翻譯1 概述2 布爾表達(dá)式的翻譯方法3 翻譯成四元式的實(shí)現(xiàn)三 控制語句翻譯1 語句標(biāo)號(hào)和goto語句的翻譯2 條件語句的翻譯3 布爾表達(dá)式的翻譯方法4 while循環(huán)語句翻譯5 for循環(huán)語句的翻譯 四 數(shù)組元素的翻譯1 下標(biāo)變量地址的計(jì)算2 數(shù)組元素的翻譯五 過程語句的翻譯1 參數(shù)傳遞方式2 過程語句的翻譯六 說明語句的翻譯1 變量說明的翻譯2 數(shù)組說明的翻譯3 過程說明的翻譯 5 3自底向上語法制導(dǎo)翻譯二 布爾表達(dá)式的翻譯1 概述布爾表達(dá)式由布爾運(yùn)算符 與 或 和 非 等作用于布爾量或關(guān)系表達(dá)式構(gòu)成 關(guān)系表達(dá)式的形式是E1ropE2 其中rop是關(guān)系運(yùn)算符 如 及 而E1和E2是算術(shù)表達(dá)式 1 布爾表達(dá)式的用途在程序設(shè)計(jì)語言中 布爾表達(dá)式有兩個(gè)基本用途 1 一個(gè)是求邏輯值 邏輯值的結(jié)果是真或假 2 另一個(gè)用得最多的是在控制語句中用作條件表達(dá)式 例如 在if then if then else和while do語句里表示控制條件 2 布爾表達(dá)式的文法布爾表達(dá)式文法G E 如下 E E E E E E E i iropi說明 1 布爾表達(dá)式的文法是一個(gè)二義文法例如 該文法的一個(gè)句子a b c有兩棵不同的語法樹與之對(duì)應(yīng) 所以該文法是一個(gè)二義文法 E E E E E a b c E E E a E E b c 2 規(guī)定布爾運(yùn)算符的優(yōu)先順序是 并假定 和 為左結(jié)合 所有關(guān)系運(yùn)算符優(yōu)先級(jí)相同 且高于任何布爾運(yùn)算符 低于算術(shù)運(yùn)算符 3 i可認(rèn)為是布爾表達(dá)式也可視為數(shù)值 1為真true 0為假false 4 iropi中rop是關(guān)系運(yùn)算符 i是布爾變量或算術(shù)值 3 布爾表達(dá)式求值方法1 把真和假數(shù)值化 使布爾表達(dá)式計(jì)算類似于算術(shù)表達(dá)式的計(jì)算 常用1表示真 0表示假 或者用非零整數(shù)表示真 如 1 0 0 0 1 1 0 0 1 0 0 12 采取某種優(yōu)化措施 有時(shí)并不需要將一個(gè)布爾表達(dá)式從頭算到尾 而只須計(jì)算它的一個(gè)子表達(dá)式 便能確定整個(gè)布爾表達(dá)式真和假 例如 對(duì)于A B 只要計(jì)算出A為真 則不管B值如何 A B之值一定為真 又如對(duì)A B 只要計(jì)算出A為假 則A B必然為假 等等 對(duì)于三種邏輯運(yùn)算 可作如下等價(jià)的解釋 A B ifAthentrueelseB A B ifAthenBelsefalse A ifAthenfalseelsetrue 用這種方式實(shí)現(xiàn)控制語句的布爾表達(dá)式尤其方便 對(duì)應(yīng)上述兩種計(jì)算方法 其布爾表達(dá)式有兩種不同的翻譯方法 第五章語法制導(dǎo)翻譯及中間代碼生成 5 3自底向上語法制導(dǎo)翻譯 一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式2 類型檢查與類型轉(zhuǎn)換二 布爾表達(dá)式的翻譯1 概述2 布爾表達(dá)式的翻譯方法3 翻譯成四元式的實(shí)現(xiàn)三 控制語句翻譯1 語句標(biāo)號(hào)和goto語句的翻譯2 條件語句的翻譯3 布爾表達(dá)式的翻譯方法4 while循環(huán)語句翻譯5 for循環(huán)語句的翻譯 四 數(shù)組元素的翻譯1 下標(biāo)變量地址的計(jì)算2 數(shù)組元素的翻譯五 過程語句的翻譯1 參數(shù)傳遞方式2 過程語句的翻譯六 說明語句的翻譯1 變量說明的翻譯2 數(shù)組說明的翻譯3 過程說明的翻譯 5 3自底向上語法制導(dǎo)翻譯二 布爾表達(dá)式的翻譯2 布爾表達(dá)式的翻譯方法 1 如同翻譯算術(shù)表達(dá)式一樣 用于求值例如 布爾表達(dá)式 a b c d 將被翻譯成如下四元式 1 a T1 2 c d T2 3 b T2 T3 4 T1 T3 T4 仿照翻譯算術(shù)表達(dá)式的方法 很容易寫出布爾表達(dá)式文法G E 的每個(gè)規(guī)則用于求值的語義動(dòng)作 1 E E 1 E 2 E PLACE NEWTEMP GEN E 1 PLACE E 2 PLACE E PLACE 2 E E 1 E 2 E PLACE NEWTEMP GEN E 1 PLACE E 2 PLACE E PLACE 3 E E 1 E PLACE NEWTEMP GEN E 1 PLACE E PLACE 4 E E 1 E PLACE E 1 PLACE 5 E i E PLACE ENTRY i 6 E iropi E PLACE NEWTEMP GEN rop ENTRY i 1 ENTRY i 2 E PLACE 2 作為條件控制的布爾表達(dá)式的翻譯1 布爾表達(dá)式E作為條件控制的代碼結(jié)構(gòu)對(duì)于條件語句ifEthenS1elseS2中布爾表達(dá)式E 它的作用就是控制S1和S2的選擇 我們賦于E代碼兩種出口 其一為 真出口 另一個(gè)是 假出口 它們分別指出當(dāng)E值為true和false時(shí) 控制轉(zhuǎn)向的目標(biāo) 即某一四元式所在位置或序號(hào) 條件語句可翻譯成如下圖 E的代碼 S1的代碼 true false S2的代碼 2 三種形式的四元式作為條件控制的布爾表達(dá)式E的翻譯歸納起來只有三種形式的四元式 jnz a1 p 若a1為真時(shí) 則轉(zhuǎn)向第p個(gè)四元式 jrop a1 a2 p 若關(guān)系a1ropa2成立時(shí) 轉(zhuǎn)向第p個(gè)四元式 j p 無條件轉(zhuǎn)向第p個(gè)四元式 除上述兩種真轉(zhuǎn)外 可用無條件表示假轉(zhuǎn) 例如 對(duì)于條件語句 ifa b cthenS1elseS2經(jīng)翻譯后 可得如下四元式序列 1 jnz a 5 2 j 3 3 j b c 5 4 j p 1 5 關(guān)于S1的四元式序列 P j q p 1 關(guān)于S2的四元式序列 q 1 a為真 a b c就為真 轉(zhuǎn)5執(zhí)行 2 a為假 a b c的值取決于b c的值 所以轉(zhuǎn)3執(zhí)行 3 a為假 且b c 則a b c為真 轉(zhuǎn)5執(zhí)行 4 a為假 且b c也是假 則a b c為假 執(zhí)行S2語句 即應(yīng)轉(zhuǎn)p 1執(zhí)行 p 執(zhí)行完S1 對(duì)應(yīng)四元式為 5 則應(yīng)轉(zhuǎn)到條件語句的下一條語句執(zhí)行 所以無條件跳轉(zhuǎn)到 q 執(zhí)行 四元式 1 4 中顯然含有多余的四元式 如 2 顯然是不需要 第五章語法制導(dǎo)翻譯及中間代碼生成 5 3自底向上語法制導(dǎo)翻譯 一 簡(jiǎn)單算術(shù)表達(dá)式和賦值語句的翻譯1 翻譯成四元式2 類型檢查與類型轉(zhuǎn)換二 布爾表達(dá)式的翻譯1 概述2 布爾表達(dá)式的翻譯方法3 翻譯成四元式的實(shí)現(xiàn)三 控制語句翻譯1 語句標(biāo)號(hào)和goto語句的翻譯2 條件語句的翻譯3 布爾表達(dá)式的翻譯方法4 while循環(huán)語句翻譯5 for循環(huán)語句的翻譯 四 數(shù)組元素的翻譯1 下標(biāo)變量地址的計(jì)算2 數(shù)組元素的翻譯五 過程語句的翻譯1 參數(shù)傳遞方式2 過程語句的翻譯六 說明語句的翻譯1 變量說明的翻譯2 數(shù)組說明的翻譯3 過程說明的翻譯 5 3自底向上語法制導(dǎo)翻譯二 布爾表達(dá)式的翻譯3 翻譯成四元式的實(shí)現(xiàn) 1 回填在自底向上的語法制導(dǎo)翻譯過程中 在產(chǎn)生一個(gè)條件或無條件轉(zhuǎn)移四元式時(shí) 它所要轉(zhuǎn)移到的那個(gè)四元式尚未產(chǎn)生 故無法立即產(chǎn)生一個(gè)完全控制轉(zhuǎn)移四元式 例如 對(duì)于上例 在產(chǎn)生第一個(gè)四元式時(shí) 因?yàn)檎Z句S1的中間代碼尚未產(chǎn)生 故此時(shí)只得產(chǎn)生一個(gè)空缺轉(zhuǎn)移目標(biāo)的四元式 jnz a 0 且將此四元式的序號(hào)作為語義信息存起來 待開始翻譯語句S1時(shí) 再將S1的第一個(gè)四元式序號(hào) 即5 填入這個(gè)不完全條件轉(zhuǎn)移四元式中 我們把這種事后再填轉(zhuǎn)移目標(biāo)叫做回填 2 真鏈T和假鏈F在翻譯過程中 有時(shí)會(huì)存在著若干個(gè)轉(zhuǎn)移四元式 如例中的1和3兩個(gè)四元式 它們有同一個(gè)轉(zhuǎn)移目標(biāo)5 但此目標(biāo)的具體位置在形成四元式時(shí)還不知道 此時(shí) 我們將這些四元式鏈接起來 并且用一個(gè)指示器指示這條鏈的鏈頭 以后 便可以從鏈頭開始 沿著這條鏈逐個(gè)為其中各四元式填入轉(zhuǎn)移目標(biāo) 1 jnz a 5 2 j 3 3 j b c 5 4 j p 1 5 關(guān)于S1的四元式序列 P j q p 1 關(guān)于S2的四元式序列 q 5 3自底向上語法制導(dǎo)翻譯二 布爾表達(dá)式的翻譯3 翻譯成四元式的實(shí)現(xiàn) 在實(shí)際操作時(shí) 1 將要填真出口的各四元式鏈接起來 組成一個(gè)鏈稱真鏈T 記為TC2 將要填假出口的各四元式鏈接起來 組成一個(gè)鏈稱假鏈F 記為FC首先定義兩個(gè)語義變量E TC和E FC分別指示T鏈和F鏈的鏈頭 如下圖 鏈中各個(gè)四元式RESULT字段為相應(yīng)結(jié)點(diǎn)指針字段 當(dāng)其不為零時(shí) 它是鏈中后繼四元式的序號(hào)如 3 中的1 否則 相應(yīng)四元式是鏈尾結(jié)點(diǎn) 如 1 中的0 3 改寫布爾表達(dá)式文法G E 為了使用語法制導(dǎo)翻譯做回填工作 便于編制相應(yīng)的語義子程序 我們對(duì)上面布爾表達(dá)式文法G E 改寫為E E E E E E i iropiE E E E 這樣 當(dāng)掃描到E 和E 并歸約到E 和E 時(shí)就可以及時(shí)回填 知道真假出口 如果不是這樣改寫 當(dāng)掃描到E 和E 時(shí) 還不能歸約 因此就不能及時(shí)回填 4 文法G E 各規(guī)則語義子程序1 語義變量和語義過程為了構(gòu)造語義子程序 我們引入下面語義變量和語義過程 NXQ是指示器 用來指示所要產(chǎn)生下一個(gè)四元式的序號(hào) NXQ的初值為1 每當(dāng)執(zhí)行一次GEN之后 NXQ之值增1 如 100 101 102 NXQ103 GEN功能同前 每被調(diào)用一次 NXQ值增加一 形成一個(gè)四元式 送入四元式表 BACKPATCH p t 是一過程 把四元式序號(hào)t填入以p為鏈頭的鏈中各個(gè)四元式第四區(qū)段上 過程描述如下 PROCEDUREBACKPATCH p t BEGIN Q p WHILEQ0DO BEGIN q 四元式Q的第四區(qū)段的內(nèi)容 把t填進(jìn)四元式Q的第四區(qū)段 Q q END 將四元式鏈頭序號(hào)P送到工作單元Q 即將下一個(gè)四元式序號(hào)保存到q中 讓Q指向下一個(gè)四元式 Q0表示沒到鏈尾 執(zhí)行循環(huán)體 執(zhí)行算法BACKPATCH示意圖假定要填入四元式序號(hào)t 31 四元式10 20 30形成一個(gè)鏈 其鏈頭是30 鏈尾是10 現(xiàn)在執(zhí)行算法BACKPATCH進(jìn)行回填 0 10 20 10 20 30 31 31 31 30 20 10 0 20 10 0 Q q MERG p1 p2 是一個(gè)函數(shù)過程 把以鏈頭分別為p1和p2兩條鏈進(jìn)行合并 并返回合并以后的鏈頭 過程描述如下 POINTERPROCEDUREMERGE p1 p2 IFp2 0THENMERG p1ELSE BEGINp p2 WHILE四元式p第四區(qū)段的內(nèi)容0DO p 四元式p第四區(qū)段的內(nèi)容 把p1填進(jìn)四元式p的第四區(qū)段 MERGE p2 END p2 0意味著p2空 所以合并后p1為鏈頭 循環(huán)目的是找到p2的鏈尾 將p1鏈頭和p2后鏈尾鏈在一起 即p1和p2兩個(gè)鏈合并 返回鏈頭p2 p2鏈頭是合并后鏈頭 執(zhí)行算法MERG示意圖假定P1為四元式10 20 30一個(gè)鏈 其鏈頭P1 30 P2為四元式40 50 60另一個(gè)鏈 其鏈頭P2 60 現(xiàn)在執(zhí)行算法MERG 將P1和P2兩個(gè)鏈進(jìn)行合并 使得合并后的鏈頭就是60 即P2的鏈頭算法MERG示意圖 0 10 20 10 20 30 P1 30 0 10 20 10 20 30 P1