sun編譯原理第5章語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成(第19-21講)ppt課件

1、第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成5.1 概述概述 語(yǔ)義分析的義務(wù)語(yǔ)義分析的義務(wù)首先編譯程序?qū)彶槊總€(gè)語(yǔ)法構(gòu)造的靜態(tài)語(yǔ)義，假首先編譯程序?qū)彶槊總€(gè)語(yǔ)法構(gòu)造的靜態(tài)語(yǔ)義，假設(shè)靜態(tài)語(yǔ)義正確，再生成中間代碼。設(shè)靜態(tài)語(yǔ)義正確，再生成中間代碼。詞法分析：分析的預(yù)備階段，輸出是單詞符號(hào)序列；詞法分析：分析的預(yù)備階段，輸出是單詞符號(hào)序列；語(yǔ)法分析：分析的主要階段，輸出是語(yǔ)法樹。語(yǔ)法分析：分析的主要階段，輸出是語(yǔ)法樹。但這樣還不能完全確定源程序的正確性，也沒有獲得但這樣還不能完全確定源程序的正確性，也沒有獲得翻譯時(shí)所需的一切信息。翻譯時(shí)所需的一切信息。留意：有的編譯程序不生成中

2、間代碼而直接生留意：有的編譯程序不生成中間代碼而直接生成實(shí)踐的目的代碼。成實(shí)踐的目的代碼。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成5.2 屬性文法屬性文法詞法規(guī)那么的描畫工具：詞法規(guī)那么的描畫工具：語(yǔ)法規(guī)那么的描畫工具：語(yǔ)法規(guī)那么的描畫工具：語(yǔ)義規(guī)那么的常用描畫工具：語(yǔ)義規(guī)那么的常用描畫工具：屬性文法屬性文法正規(guī)文法或正規(guī)式正規(guī)文法或正規(guī)式上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法 根本概根本概念念第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 屬性文法屬性文法第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 屬性文法屬性文法

3、普通地，將屬性文法寫成表格方式，每個(gè)文法規(guī)那普通地，將屬性文法寫成表格方式，每個(gè)文法規(guī)那么用屬性等式的集合或相應(yīng)規(guī)那么的語(yǔ)義規(guī)那么列么用屬性等式的集合或相應(yīng)規(guī)那么的語(yǔ)義規(guī)那么列出。出。留意：文法規(guī)那么中同一產(chǎn)生式中某符號(hào)出現(xiàn)多留意：文法規(guī)那么中同一產(chǎn)生式中某符號(hào)出現(xiàn)多次必需運(yùn)用下標(biāo)進(jìn)展區(qū)分。例：次必需運(yùn)用下標(biāo)進(jìn)展區(qū)分。例： number1number2digit 第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 練習(xí)練習(xí)第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成可用依賴

4、圖或稱相關(guān)圖來(lái)決議屬性值的計(jì)算順序?？捎靡蕾噲D或稱相關(guān)圖來(lái)決議屬性值的計(jì)算順序。 屬性的計(jì)屬性的計(jì)算算第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成依賴圖以屬性等式為最小構(gòu)造單位。一個(gè)文法依賴圖以屬性等式為最小構(gòu)造單位。一個(gè)文法的依賴圖就是全部屬性等式依賴圖的總和。的依賴圖就是全部屬性等式依賴圖的總和。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯

5、技術(shù)和中間代碼生成 屬性的分屬性的分類類例：例：第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 屬性的分屬性的分類類例：例：第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成5.3 語(yǔ)法制導(dǎo)翻譯概述語(yǔ)法制導(dǎo)翻譯概述語(yǔ)義分析階段的語(yǔ)義分析階段的2個(gè)主要義務(wù)：個(gè)主要義務(wù)：1、分析言語(yǔ)的含義；、分析言語(yǔ)的含義；2、用一種中間代碼將這種含義描畫出來(lái)。、用一種中間代碼將這種含義描畫出來(lái)。目前常用過的語(yǔ)義分析方法：語(yǔ)法制導(dǎo)翻譯法。目前常用過的語(yǔ)義分析方法：語(yǔ)法制導(dǎo)翻譯法。所謂語(yǔ)法制導(dǎo)翻譯法就是在語(yǔ)法分析過程中，隨著所謂語(yǔ)法制導(dǎo)翻譯法就是在語(yǔ)法分析過程中，隨著

6、分析的逐漸進(jìn)展，根據(jù)相應(yīng)文法的每一規(guī)那么所對(duì)分析的逐漸進(jìn)展，根據(jù)相應(yīng)文法的每一規(guī)那么所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)展翻譯的方法。應(yīng)的語(yǔ)義子程序進(jìn)展翻譯的方法。語(yǔ)法制導(dǎo)翻譯法可分為自下向上語(yǔ)法制導(dǎo)翻譯和語(yǔ)法制導(dǎo)翻譯法可分為自下向上語(yǔ)法制導(dǎo)翻譯和自上向下語(yǔ)法制導(dǎo)翻譯。自上向下語(yǔ)法制導(dǎo)翻譯。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 語(yǔ)法分析時(shí)屬性的計(jì)算語(yǔ)法分析時(shí)屬性的計(jì)算第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代

7、碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 語(yǔ)法制導(dǎo)翻譯舉例語(yǔ)法制導(dǎo)翻譯舉例1、有一屬性文法為：、有一屬性文法為：1P bQbprint:12Q cRprint:23Q aprint:34R Qadprint:4輸入串為輸入串為bccaadadb，且采用自底向上語(yǔ)法分析方法時(shí)，那么，且采用自底向上語(yǔ)法分析方法時(shí)，那么輸出序列是？輸出序列是？2、試給出以下文法的適宜自下而上翻譯的語(yǔ)義動(dòng)作，使得當(dāng)、試給出以下文法的適宜自下而上翻譯的語(yǔ)義動(dòng)作，使得當(dāng)輸入串是輸入串是aacbb時(shí)，其輸出串是時(shí)，

8、其輸出串是12020。1A aB 2A c3B Ab342421print:1print:2print:0第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成詞法規(guī)那么的描畫工具：詞法規(guī)那么的描畫工具：語(yǔ)法規(guī)那么的描畫工具：語(yǔ)法規(guī)那么的描畫工具：語(yǔ)義規(guī)那么的常用描畫工具：語(yǔ)義規(guī)那么的常用描畫工具：屬性文法屬性文法正規(guī)文法或正規(guī)式正規(guī)文法或正規(guī)式上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法 小結(jié)小結(jié)第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 小結(jié)小結(jié)第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成

9、語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 語(yǔ)法制導(dǎo)翻譯舉例語(yǔ)法制導(dǎo)翻譯舉例有一屬性文法為：有一屬性文法為：1P bQbprint:12Q cRprint:23Q aprint:34R Qadprint:4輸入串為輸入串為bab，且采用自底向上語(yǔ)法分析方法，且采用自底向上語(yǔ)法分析方法時(shí)，那么輸出序列是？時(shí)，那么輸出序列是？31第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 語(yǔ)法制導(dǎo)翻譯舉例語(yǔ)法制導(dǎo)翻譯舉例第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 綜合練習(xí)綜合練習(xí)給出文法給出文法GS： S SaA|AA AbB|BB cSd|e1試證明試證明AacA

10、d是文法是文法GS的一個(gè)句型；的一個(gè)句型；2請(qǐng)寫出該句型的一切短語(yǔ)、直接短語(yǔ)以及請(qǐng)寫出該句型的一切短語(yǔ)、直接短語(yǔ)以及句柄；句柄；3為文法為文法GS的相應(yīng)產(chǎn)生式寫出語(yǔ)義動(dòng)作，的相應(yīng)產(chǎn)生式寫出語(yǔ)義動(dòng)作，使句型使句型AacAd經(jīng)該翻譯方案后，輸出為經(jīng)該翻譯方案后，輸出為11435第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成5.4 中間言語(yǔ)中間言語(yǔ)所謂中間代碼方式是指用來(lái)描畫源程序并與之等所謂中間代碼方式是指用來(lái)描畫源程序并與之等效的一種編碼方式，可根據(jù)詳細(xì)情況將它設(shè)計(jì)成效的一種編碼方式，可根據(jù)詳細(xì)情況將它設(shè)計(jì)成各種方式。各種方式。普通來(lái)說(shuō)，對(duì)于一個(gè)多遍掃描的編譯程序，越到

11、普通來(lái)說(shuō)，對(duì)于一個(gè)多遍掃描的編譯程序，越到后面的階段，所產(chǎn)生的中間代碼越接近于機(jī)器代后面的階段，所產(chǎn)生的中間代碼越接近于機(jī)器代碼。碼。常用的中間代碼有逆波蘭式表示后綴式、三常用的中間代碼有逆波蘭式表示后綴式、三元式、樹形籠統(tǒng)的語(yǔ)法樹、四元式、三地址元式、樹形籠統(tǒng)的語(yǔ)法樹、四元式、三地址碼表示等。碼表示等。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 逆波蘭式逆波蘭式逆波蘭表示法是把運(yùn)算量操作數(shù)寫在前面，把逆波蘭表示法是把運(yùn)算量操作數(shù)寫在前面，把運(yùn)算符寫在后面，又稱為后綴表示法。運(yùn)算符寫在后面，又稱為后綴表示法。特征：操作符在前，操作數(shù)緊隨其后，無(wú)需用括號(hào)限特征：操作

12、符在前，操作數(shù)緊隨其后，無(wú)需用括號(hào)限制運(yùn)算的優(yōu)先級(jí)和結(jié)合性，且求表達(dá)式值較中綴表達(dá)制運(yùn)算的優(yōu)先級(jí)和結(jié)合性，且求表達(dá)式值較中綴表達(dá)式方便。式方便。例：將例：將(a+b)*(a-c)-d)*(x+y)翻譯成逆波蘭表示，并求翻譯成逆波蘭表示，并求出當(dāng)出當(dāng)a=3,b=7,c=1,d=2,x=4,y=6時(shí)該表達(dá)式的值。時(shí)該表達(dá)式的值。程序語(yǔ)句也可用逆波蘭式表示。程序語(yǔ)句也可用逆波蘭式表示。練習(xí)：求練習(xí)：求(b+c)*e+(b+c)/f的逆波蘭式？的逆波蘭式？第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成三元式由三元式由3 3個(gè)域和一個(gè)序號(hào)組成：個(gè)域和一個(gè)序號(hào)組成：i i(op(

13、op，arg1arg1，arg2)arg2)其中其中opop為運(yùn)算符，為運(yùn)算符，arg1,arg2arg1,arg2是是2 2個(gè)運(yùn)算對(duì)象。個(gè)運(yùn)算對(duì)象。例：算術(shù)表達(dá)式的三地址碼例：算術(shù)表達(dá)式的三地址碼x=y op z x=y op z 的三元式為：的三元式為：(1) (op(1) (op，y y，z) z)(2) (=(2) (=，x x，(1)(1) 三元式三元式三元式的運(yùn)算結(jié)果由每一個(gè)三元式前的序號(hào)指示。三元式的運(yùn)算結(jié)果由每一個(gè)三元式前的序號(hào)指示。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成例：賦值語(yǔ)句例：賦值語(yǔ)句a=(c+d)*(c+d)相應(yīng)的三元式代碼為相應(yīng)的

14、三元式代碼為(1) (+，c，d)(2) (+，c，d)(3) (*，(1)，(2)(3) (=，a，(3) 三元式舉例三元式舉例三元式出現(xiàn)的先后順序和表達(dá)式各部分的計(jì)值三元式出現(xiàn)的先后順序和表達(dá)式各部分的計(jì)值順序是一致的。順序是一致的。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成在三元式代碼表的根底上另設(shè)一張表，該表按運(yùn)在三元式代碼表的根底上另設(shè)一張表，該表按運(yùn)算的次序列出相應(yīng)三元式在表中的位置，這張表算的次序列出相應(yīng)三元式在表中的位置，這張表稱為間接碼表。三元式表只記錄不同的三元式語(yǔ)稱為間接碼表。三元式表只記錄不同的三元式語(yǔ)句，間接碼表表示由這些語(yǔ)句組成的運(yùn)算次

15、序。句，間接碼表表示由這些語(yǔ)句組成的運(yùn)算次序。間接三元式間接三元式例：賦值語(yǔ)句例：賦值語(yǔ)句a=(c+d)*(c+d)三元式代碼為三元式代碼為相應(yīng)的間接三元式代碼由三相應(yīng)的間接三元式代碼由三元式表和間接碼表組成：元式表和間接碼表組成：三元式表：三元式表：(1) (+，c，d)(2) (*，(1)，(1)(3) (=，a，(2)間接碼表：間接碼表：(1)(1)(2)(3)(1) (+，c，d)(2) (+，c，d)(3) (*，(1)，(2)(4) (=，a，(3)第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成樹形表示樹形表示樹形表示法可以很方便的表示一個(gè)表達(dá)式或語(yǔ)句。樹

16、形表示法可以很方便的表示一個(gè)表達(dá)式或語(yǔ)句。其中：一個(gè)表達(dá)式中的簡(jiǎn)單變量或常數(shù)的樹形表其中：一個(gè)表達(dá)式中的簡(jiǎn)單變量或常數(shù)的樹形表示就是該變量或常數(shù)本身。示就是該變量或常數(shù)本身。簡(jiǎn)單表達(dá)式的樹形表示見課本簡(jiǎn)單表達(dá)式的樹形表示見課本P109 圖圖5.8樹形構(gòu)造普通表示成二叉樹的方式。樹形構(gòu)造普通表示成二叉樹的方式。練習(xí)：求練習(xí)：求a=(b+c)*e+(b+c)/f的樹形表示？的樹形表示？第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 四元式四元式四元式是具有四個(gè)域的記錄構(gòu)造，這四個(gè)域?yàn)樗脑绞蔷哂兴膫€(gè)域的記錄構(gòu)造，這四個(gè)域?yàn)?op，arg1，arg2，result)其中其中

17、op為運(yùn)算符，為運(yùn)算符， arg1，arg2為運(yùn)算對(duì)象，為運(yùn)算對(duì)象， result為為編譯程序?yàn)榇娣胖虚g運(yùn)算結(jié)果引進(jìn)的暫時(shí)變量。編譯程序?yàn)榇娣胖虚g運(yùn)算結(jié)果引進(jìn)的暫時(shí)變量。例：賦值語(yǔ)句例：賦值語(yǔ)句a=b*(c+d)相應(yīng)的四元式代碼為相應(yīng)的四元式代碼為(1) (+，c，d，t1)(2) (*，b，t1，t2)(3) (=，t2， ，a)四元式出現(xiàn)的順序與表達(dá)式計(jì)算的順序一致，四元式出現(xiàn)的順序與表達(dá)式計(jì)算的順序一致，四元式之間的聯(lián)絡(luò)是經(jīng)過暫時(shí)變量實(shí)現(xiàn)的。四元式之間的聯(lián)絡(luò)是經(jīng)過暫時(shí)變量實(shí)現(xiàn)的。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 三地址碼三地址碼三地址碼的方式定義為

18、：三地址碼的方式定義為：X=a op b其中，其中，X，a和和b為變量名、常量或編譯時(shí)產(chǎn)生的暫時(shí)為變量名、常量或編譯時(shí)產(chǎn)生的暫時(shí)變量；變量；op為運(yùn)算符。為運(yùn)算符。留意：三地址語(yǔ)句中等號(hào)右邊只含有一個(gè)運(yùn)算符，因留意：三地址語(yǔ)句中等號(hào)右邊只含有一個(gè)運(yùn)算符，因此多個(gè)運(yùn)算符組成的表達(dá)式必需用三地址語(yǔ)句序列來(lái)此多個(gè)運(yùn)算符組成的表達(dá)式必需用三地址語(yǔ)句序列來(lái)表示，如：表示，如：x+y*z的三地址碼序列為：的三地址碼序列為： 1 t1=y*z 2 t2=x+t1其中其中t1和和t2是編譯時(shí)產(chǎn)生的暫時(shí)變量，三地址碼是語(yǔ)是編譯時(shí)產(chǎn)生的暫時(shí)變量，三地址碼是語(yǔ)法樹的一種線性表示。法樹的一種線性表示。第第5章章 語(yǔ)法

19、制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 綜合練習(xí)綜合練習(xí)求求a=(b+c)*e的各種中間言語(yǔ)表示方式。的各種中間言語(yǔ)表示方式。1、逆波蘭式、逆波蘭式2、三元式、三元式3、間接三元式、間接三元式4、樹形表示、樹形表示5、四元式、四元式6、三地址代碼、三地址代碼第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成練習(xí)練習(xí)1 1、四元式之間的聯(lián)絡(luò)是經(jīng)過、四元式之間的聯(lián)絡(luò)是經(jīng)過 實(shí)實(shí)現(xiàn)的?，F(xiàn)的。2 2、間接三元式表示法的優(yōu)點(diǎn)為、間接三元式表示法的優(yōu)點(diǎn)為 A. A. 采用間接碼表，便于優(yōu)化處置采用間接碼表，便于優(yōu)化處置B. B. 節(jié)省存儲(chǔ)空間，不便于表的修正節(jié)省存儲(chǔ)

20、空間，不便于表的修正C. C. 便于優(yōu)化處置，節(jié)省存儲(chǔ)空間便于優(yōu)化處置，節(jié)省存儲(chǔ)空間D. D. 節(jié)省存儲(chǔ)空間，不便于優(yōu)化處置節(jié)省存儲(chǔ)空間，不便于優(yōu)化處置暫時(shí)變量暫時(shí)變量A第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成5.5 自下而上語(yǔ)法制導(dǎo)翻譯自下而上語(yǔ)法制導(dǎo)翻譯自下而上語(yǔ)法制導(dǎo)翻譯方法是在自下而上的語(yǔ)自下而上語(yǔ)法制導(dǎo)翻譯方法是在自下而上的語(yǔ)法分析過程中逐漸實(shí)現(xiàn)語(yǔ)義規(guī)那么的方法。法分析過程中逐漸實(shí)現(xiàn)語(yǔ)義規(guī)那么的方法。自下而上翻譯的特點(diǎn)：自下而上翻譯的特點(diǎn)：1 1當(dāng)棧頂構(gòu)成句柄執(zhí)行歸約時(shí)，調(diào)用相應(yīng)當(dāng)棧頂構(gòu)成句柄執(zhí)行歸約時(shí)，調(diào)用相應(yīng)的語(yǔ)義動(dòng)作；的語(yǔ)義動(dòng)作；2 2語(yǔ)法分析棧

21、與語(yǔ)義分析棧同步操作。語(yǔ)法分析棧與語(yǔ)義分析棧同步操作。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成表達(dá)式中間代碼生成表達(dá)式中間代碼生成1逆波蘭式的生成逆波蘭式的生成算術(shù)表達(dá)式的逆波蘭式的生成只需對(duì)其籠統(tǒng)語(yǔ)算術(shù)表達(dá)式的逆波蘭式的生成只需對(duì)其籠統(tǒng)語(yǔ)法樹進(jìn)展后序遍歷即可。法樹進(jìn)展后序遍歷即可。例：求例：求(b+c)*e的逆波蘭式可利用語(yǔ)法分析結(jié)果的逆波蘭式可利用語(yǔ)法分析結(jié)果的籠統(tǒng)語(yǔ)法樹獲得。的籠統(tǒng)語(yǔ)法樹獲得。思索假設(shè)求思索假設(shè)求a=(b+c)*e+(b+c)/f的逆波蘭式？的逆波蘭式？第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成表達(dá)式中間代碼生

22、成表達(dá)式中間代碼生成 1212o p( o p , , , )o p( o p , , , ) (, , , )nnEEEETEETi dEEi d i d E o p E1 E2 o p o p E Tn是編譯過程中的暫時(shí)變量，用以存儲(chǔ)中間結(jié)果。是編譯過程中的暫時(shí)變量，用以存儲(chǔ)中間結(jié)果。 2表達(dá)式的四元式變換如下：表達(dá)式的四元式變換如下：例：求例：求a=(b+c)*e+(b+c)/f的四元式的四元式第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成1 1、表達(dá)式、表達(dá)式A+BA+B* *(C+D)(C+D)的逆波蘭表示為的逆波蘭表示為 2 2、寫出賦值語(yǔ)句、寫出賦值語(yǔ)句

23、x=(a+b)x=(a+b)* *c/dc/d的四元式序列。的四元式序列。課后練習(xí)課后練習(xí)第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成一、中間代碼有如下方式：一、中間代碼有如下方式： 表達(dá)式中間代碼生成小結(jié)表達(dá)式中間代碼生成小結(jié)1 1、逆波蘭式、逆波蘭式2 2、三元式、三元式3 3、間接三元式、間接三元式4 4、樹形表示、樹形表示5 5、四元式、四元式6 6、三地址代碼、三地址代碼二、表達(dá)式二、表達(dá)式(b+c)(b+c)* *e/(b-c)+fe/(b-c)+f的中間代碼的中間代碼第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 if語(yǔ)句中間

24、代碼生成語(yǔ)句中間代碼生成if if 語(yǔ)句的方式：語(yǔ)句的方式：if (E) S1 else S2;if (E) S1 else S2;這里的表達(dá)式這里的表達(dá)式E E普通是布爾表達(dá)式或邏輯表達(dá)式。普通是布爾表達(dá)式或邏輯表達(dá)式。if if語(yǔ)句的中心操作不是計(jì)算，而是轉(zhuǎn)移，包括條件轉(zhuǎn)語(yǔ)句的中心操作不是計(jì)算，而是轉(zhuǎn)移，包括條件轉(zhuǎn)移與無(wú)條件轉(zhuǎn)移。移與無(wú)條件轉(zhuǎn)移。因此因此if if語(yǔ)句翻譯成中間代碼時(shí)，變成對(duì)布爾表達(dá)式的語(yǔ)句翻譯成中間代碼時(shí)，變成對(duì)布爾表達(dá)式的判別與轉(zhuǎn)移組合。所生成的四元式中間代碼由兩條根判別與轉(zhuǎn)移組合。所生成的四元式中間代碼由兩條根本語(yǔ)句組成：本語(yǔ)句組成：12(jnz, ,)(jp, ,

25、,)aLL表示假設(shè)表示假設(shè)a非零那么轉(zhuǎn)移到地址非零那么轉(zhuǎn)移到地址L1表示無(wú)條件轉(zhuǎn)移到地址表示無(wú)條件轉(zhuǎn)移到地址L2if語(yǔ)句中間代碼生成語(yǔ)句中間代碼生成if if 語(yǔ)句有兩種方式語(yǔ)句有兩種方式方式方式1 1： if ( E ) S;if ( E ) S;(計(jì)算計(jì)算E的四元式值并存入的四元式值并存入T)(jnz,T, ,L)(jp, , ,next)L:(S的四元式的四元式)next:(后續(xù)程序四元式后續(xù)程序四元式)中間代碼生成過程：中間代碼生成過程：例：求例：求if(ab) x=x+1; y=y+1;的四元式序列；的四元式序列；流程圖流程圖NY方式方式2 2： if ( E ) S1 else S

26、2if ( E ) S1 else S2if語(yǔ)句中間代碼生成語(yǔ)句中間代碼生成121122 (jnz, , ,) (jp, , ,)() (jp, , , next)()TLLLSLS：的四元式：的四元式(E的四元式，值存入的四元式，值存入T)next： (后續(xù)程序四元式后續(xù)程序四元式)中間代碼生成過程中間代碼生成過程例：求例：求if(ab) x=x+1; else x=x-1; y=1;的四元式序列；的四元式序列；NY第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成if語(yǔ)句中間代碼生成語(yǔ)句中間代碼生成if if語(yǔ)句四元式生成過程中，有一個(gè)關(guān)鍵技術(shù)問題語(yǔ)句四元式生成過程中

27、，有一個(gè)關(guān)鍵技術(shù)問題如何填寫轉(zhuǎn)移地址的問題。由于在生成四元式轉(zhuǎn)移語(yǔ)如何填寫轉(zhuǎn)移地址的問題。由于在生成四元式轉(zhuǎn)移語(yǔ)句時(shí)，轉(zhuǎn)移的目的地址還不確定，這需求用到轉(zhuǎn)移地句時(shí)，轉(zhuǎn)移的目的地址還不確定，這需求用到轉(zhuǎn)移地址回填技術(shù)。址回填技術(shù)。例：求例：求 if(cd) x=x+1; y=y+x; else x=x-1; y=x+1;的四元式序列。的四元式序列。練習(xí)：練習(xí)：求求 y=a+1; if(xy) x=x+1; y=y-1; y=x*x;的四元式序列；的四元式序列；第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成布爾表達(dá)式代碼生成布爾表達(dá)式代碼生成在語(yǔ)句在語(yǔ)句if ( E )

28、S1 else S2if ( E ) S1 else S2中，表達(dá)式中，表達(dá)式E E的作用是提供的作用是提供選擇執(zhí)行語(yǔ)句選擇執(zhí)行語(yǔ)句S1S1還是還是S2S2的判別。因此不用保管的判別。因此不用保管E E的的值，而是將計(jì)算結(jié)果表示為程序執(zhí)行流程的轉(zhuǎn)移。值，而是將計(jì)算結(jié)果表示為程序執(zhí)行流程的轉(zhuǎn)移。此時(shí)此時(shí)E E的值只需有兩個(gè)即可。所以的值只需有兩個(gè)即可。所以E E被視為布爾表達(dá)被視為布爾表達(dá)式。式。E E的真值被轉(zhuǎn)換為一個(gè)條件轉(zhuǎn)移，稱為的真值被轉(zhuǎn)換為一個(gè)條件轉(zhuǎn)移，稱為“真出真出口。口。E E的假值被轉(zhuǎn)換為一個(gè)無(wú)條件轉(zhuǎn)移，稱為的假值被轉(zhuǎn)換為一個(gè)無(wú)條件轉(zhuǎn)移，稱為“假出口。假出口。最簡(jiǎn)單的情況最簡(jiǎn)單的情

29、況E是一個(gè)布爾變量是一個(gè)布爾變量a，那么有，那么有12(jnz, ,)(jp, , ,)aLL真出口真出口假出口假出口第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成布爾量間的運(yùn)算除了普通的布爾代數(shù)運(yùn)算外，還有一布爾量間的運(yùn)算除了普通的布爾代數(shù)運(yùn)算外，還有一種運(yùn)算方法，稱為種運(yùn)算方法，稱為“短路布爾操作。它的意義是：短路布爾操作。它的意義是：對(duì)于一個(gè)二元布爾操作，假設(shè)根據(jù)第對(duì)于一個(gè)二元布爾操作，假設(shè)根據(jù)第1 1個(gè)布爾量的值就個(gè)布爾量的值就可以判別這個(gè)布爾結(jié)果，那么就不用計(jì)算第可以判別這個(gè)布爾結(jié)果，那么就不用計(jì)算第2 2個(gè)布爾量個(gè)布爾量了。就是說(shuō)，在某種情況下第了。就是說(shuō)

30、，在某種情況下第2 2個(gè)布爾量被短路了。個(gè)布爾量被短路了。布爾表達(dá)式代碼生成布爾表達(dá)式代碼生成如，對(duì)于二元操作如，對(duì)于二元操作a and b a and b ，假設(shè)，假設(shè)a a是假，不論是假，不論b b 是什么，是什么，a a and b and b 的結(jié)果都是假。所以的結(jié)果都是假。所以b b被短路掉，就不用計(jì)算了，這被短路掉，就不用計(jì)算了，這種短路的操作對(duì)代碼來(lái)說(shuō)是很重要的。有些時(shí)候，沒被短種短路的操作對(duì)代碼來(lái)說(shuō)是很重要的。有些時(shí)候，沒被短路的操作會(huì)引起錯(cuò)誤。例如：路的操作會(huì)引起錯(cuò)誤。例如：if( !NULL)&(val0).pp這是這是C言語(yǔ)中常見的語(yǔ)句，但假設(shè)出現(xiàn)言語(yǔ)中常見的語(yǔ)句

31、，但假設(shè)出現(xiàn)p=NULL 時(shí)還要時(shí)還要對(duì)對(duì)pval求值將引起內(nèi)存錯(cuò)誤。求值將引起內(nèi)存錯(cuò)誤。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 短路的布爾操作類似于短路的布爾操作類似于if語(yǔ)句，它們經(jīng)常用語(yǔ)句，它們經(jīng)常用if表達(dá)式定義，例如：表達(dá)式定義，例如：21121212 and if thenelse false or ifthen true elseEEEEEEEE將將E1的真出口與全句的真出口并聯(lián)，的真出口與全句的真出口并聯(lián)，E1的假出口轉(zhuǎn)移至的假出口轉(zhuǎn)移至E2的第的第1個(gè)四元式，個(gè)四元式，E2的真出口是全句的真出口，的真出口是全句的真出口，E2的的假出口是全句的

32、假出口。假出口是全句的假出口。 布爾表達(dá)式代碼生成布爾表達(dá)式代碼生成將將E1的真出口轉(zhuǎn)移至的真出口轉(zhuǎn)移至E2的第的第1個(gè)四元式，個(gè)四元式，E1的假出口與的假出口與全句假出口并聯(lián)一樣，全句假出口并聯(lián)一樣，E2的真出口就是全句的真的真出口就是全句的真出口，出口，E2的假出口也是全句的假出口。的假出口也是全句的假出口。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成舉例舉例1、a & b，求其短路布爾操作四元式序列。，求其短路布爾操作四元式序列。(1) (jnz,a, ,(3)(2) (jp, , ,false)(3) (jnz,b, ,true) (4) (jp,

33、, ,false)根據(jù)布爾表達(dá)式的四元式定義可將其四元式代碼寫成：根據(jù)布爾表達(dá)式的四元式定義可將其四元式代碼寫成：例：求表達(dá)式例：求表達(dá)式ab | cd & ef 的短路布爾操的短路布爾操作四元式序列。作四元式序列。true表示布爾表達(dá)式的真出口；表示布爾表達(dá)式的真出口；false表示布爾表達(dá)式的假出口；表示布爾表達(dá)式的假出口；留意：留意：&優(yōu)先級(jí)高于優(yōu)先級(jí)高于|a|b ?練習(xí)：求表達(dá)式練習(xí)：求表達(dá)式x | y & z 的短路布爾操作四的短路布爾操作四元式序列。元式序列。第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成舉例舉例求以下語(yǔ)句的四元式序

34、列。求以下語(yǔ)句的四元式序列。 if(ab | cd ) a=a*b; else x=x-y; y=x*x;(1)(,a,b,t1)(7)(*,a,b,t3)(2)(jnz,t1, ,(7)(8)(=,t3, ,a)(3)(jp, , ,(4)(9)(jp, , , (12)(4)(,c,d,t2)(10)(-,x,y,t4)(5)(jnz,t2, ,(7)(11)(=,t4, ,x)(6)(jp, , ,(10)(12)(*,x,x,t5)(13)(=,t5, ,y)練習(xí)練習(xí)求以下語(yǔ)句的求以下語(yǔ)句的四元式序列。四元式序列。 if(ab|cd&e) x=a*b+y;else x=x-y;y=x+x;第第5章章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成循環(huán)語(yǔ)句中間