《編譯原理》第五章.ppt

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