編譯原理第五章

編譯原理

CompilerPrinciples徐佳xujia@教學(xué)網(wǎng)站：南京郵電大學(xué).計(jì)算機(jī)學(xué)院

第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成compilingrunningprogramming教材：《編譯技術(shù)原理及其實(shí)現(xiàn)方法》王汝傳編著1第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成本章內(nèi)容§5.1語(yǔ)法制導(dǎo)翻譯概述一、語(yǔ)法制導(dǎo)翻譯定義二、語(yǔ)法制導(dǎo)翻譯原理三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)§5.2中間語(yǔ)言一、引言二、逆波蘭表示三、三元式四、樹形表示五、四元式2第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成本章內(nèi)容§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯二、布爾表達(dá)式的翻譯三、控制語(yǔ)句翻譯*************************************四、數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯§5.4自頂向下語(yǔ)法制導(dǎo)翻譯

一、遞歸下降的語(yǔ)法制導(dǎo)翻譯二、LL(1)語(yǔ)法制導(dǎo)翻譯§5.5屬性文法與屬性翻譯一、屬性文法與L屬性文法二、屬性翻譯3第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成本節(jié)內(nèi)容§5.1語(yǔ)法制導(dǎo)翻譯概述一、語(yǔ)法制導(dǎo)翻譯定義二、語(yǔ)法制導(dǎo)翻譯原理三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)§5.2中間語(yǔ)言一、引言二、逆波蘭表示三、三元式四、樹形表示五、四元式4§5.1語(yǔ)法制導(dǎo)翻譯概述

本節(jié)內(nèi)容一、語(yǔ)法制導(dǎo)翻譯定義

二、語(yǔ)法制導(dǎo)翻譯原理

三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)5第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.1語(yǔ)法制導(dǎo)翻譯概述

在前面我們已經(jīng)討論了詞法分析和語(yǔ)法分析，一個(gè)程序成功地通過(guò)詞法分析和語(yǔ)法分析，只能說(shuō)明它是一個(gè)合法程序，但是對(duì)程序內(nèi)部的邏輯含義并未加以考慮，從整個(gè)編譯程序來(lái)看，詞法分析和語(yǔ)法分析僅僅是編譯程序的一部分，編譯程序最終的目的是將源程序翻譯成可供計(jì)算機(jī)直接執(zhí)行的目標(biāo)程序。在某些編譯程序中，是直接生成機(jī)器語(yǔ)言或匯編語(yǔ)言形式的目標(biāo)代碼；有些編譯程序是把源程序翻譯為某種形式中間語(yǔ)言代碼，然后再把中間語(yǔ)言代碼翻譯為目標(biāo)代碼。下面就來(lái)介紹一種語(yǔ)法制導(dǎo)翻譯方法，這種方法先將源程序單詞序列翻譯成中間語(yǔ)言，然后再將中間語(yǔ)言翻譯成目標(biāo)程序。那么，什么叫語(yǔ)法制導(dǎo)翻譯呢？6第五章語(yǔ)法制導(dǎo)翻譯及中間代碼§5.1語(yǔ)法制導(dǎo)翻譯概述

一、語(yǔ)法制導(dǎo)翻譯定義

二、語(yǔ)法制導(dǎo)翻譯原理

三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)7第五章語(yǔ)法制導(dǎo)翻譯及中間代碼§5.1語(yǔ)法制導(dǎo)翻譯概述

一、語(yǔ)法制導(dǎo)翻譯定義

二、語(yǔ)法制導(dǎo)翻譯原理

三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)8§5.1語(yǔ)法制導(dǎo)翻譯概述

一、語(yǔ)法制導(dǎo)翻譯定義

語(yǔ)法制導(dǎo)翻譯就是以語(yǔ)法分析為主導(dǎo)的語(yǔ)義處理。語(yǔ)法分析過(guò)程中嵌入語(yǔ)義動(dòng)作，即調(diào)用對(duì)應(yīng)的語(yǔ)義子程序。例如在前面語(yǔ)法分析時(shí)分析a+b*c表達(dá)式，其分析語(yǔ)法樹如下：E+EE*EEabc語(yǔ)法分析是將a歸約E，再將b歸約E，將c歸約為E，然后再將E*E歸約成E，再將E+E歸約成E，所以a+b*c是一個(gè)合法的句子。如果考慮語(yǔ)義，在歸約過(guò)程中加上語(yǔ)義動(dòng)作，先將a歸約為E，將a值賦給E后，b歸約成E，同時(shí)將b值賦給E，在將c值賦給E，然后再將b*c（E*E）給E，最后再將左右兩個(gè)E值相加就是最終結(jié)果，這就是語(yǔ)法制導(dǎo)翻譯的基本思想，在語(yǔ)法分析同時(shí)進(jìn)行語(yǔ)義分析。9第五章語(yǔ)法制導(dǎo)翻譯及中間代碼§5.1語(yǔ)法制導(dǎo)翻譯概述

一、語(yǔ)法制導(dǎo)翻譯定義

二、語(yǔ)法制導(dǎo)翻譯原理

三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)10第五章語(yǔ)法制導(dǎo)翻譯及中間代碼§5.1語(yǔ)法制導(dǎo)翻譯概述

一、語(yǔ)法制導(dǎo)翻譯定義

二、語(yǔ)法制導(dǎo)翻譯原理

三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)11§5.1語(yǔ)法制導(dǎo)翻譯概述

二、語(yǔ)法制導(dǎo)翻譯原理

語(yǔ)法制導(dǎo)翻譯的原理就是先為每個(gè)文法規(guī)定相應(yīng)的語(yǔ)義，即編寫出相應(yīng)語(yǔ)義處理子程序，整個(gè)分析是以語(yǔ)法分析為主導(dǎo)。在自頂向下語(yǔ)法分析時(shí)，若某一個(gè)規(guī)則右部與輸入串相匹配時(shí)，或者，在自底向上語(yǔ)法分析時(shí)，當(dāng)一個(gè)規(guī)則被用于歸約時(shí)，此時(shí)該規(guī)則對(duì)應(yīng)的語(yǔ)義子程序就進(jìn)入工作，完成既定翻譯任務(wù)，產(chǎn)生與語(yǔ)義相應(yīng)的中間代碼或目標(biāo)代碼。

語(yǔ)義動(dòng)作：給每個(gè)文法符號(hào)X賦以各種不同的語(yǔ)義值這里的語(yǔ)義值不一定指具體數(shù)值，可以是“類型”、“種屬”、“地址”或“代碼”等，我們用記號(hào)X·TYPE、X·CAT或X·VAL來(lái)表示這些值。如果某規(guī)則的右部有若干個(gè)同一符號(hào)出現(xiàn)，那么我們就用上角標(biāo)來(lái)區(qū)別這些符號(hào)。例如，假定有如下規(guī)則和語(yǔ)義動(dòng)作：12例如，假定有如下規(guī)則和語(yǔ)義動(dòng)作：E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}語(yǔ)義動(dòng)作寫在規(guī)則之后的花括號(hào)里，這里語(yǔ)義動(dòng)作是表明與規(guī)則左部文法符號(hào)E相關(guān)的語(yǔ)義值E·VAL，它是通過(guò)把規(guī)則右部文法符號(hào)的語(yǔ)義值E(1)·VAL和E(2)·VAL加在一起來(lái)決定的，規(guī)則中終結(jié)符號(hào)“+”按語(yǔ)義規(guī)則被解釋成通?！凹印钡囊馑?。各規(guī)則的語(yǔ)義動(dòng)作可以對(duì)表達(dá)式計(jì)算，也可以生成中間代碼，甚至還可以來(lái)產(chǎn)生目標(biāo)指令。例5.1設(shè)有文法E∷=E+EE∷=digit這里digit代表0和9之間任一數(shù)字，如果我們的目的僅是為了求值，則語(yǔ)義動(dòng)作如下(1)E∷=E(1)+E(２){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=digit{E·VAL:=digit}假定語(yǔ)義動(dòng)作中的“+”代表是整型加算術(shù)運(yùn)算。規(guī)則(1)的語(yǔ)義動(dòng)作為:E的語(yǔ)義值E·VAL等于E(1)和E(2)的語(yǔ)義值E(1)·VAL和E(2)·VAL之和.規(guī)則(2)的語(yǔ)義動(dòng)作為:E的語(yǔ)義值為0～9之間任一個(gè)數(shù).這樣，按照它們的語(yǔ)義動(dòng)作，我們?cè)诜治雒總€(gè)句子的同時(shí)一步一步地算出每個(gè)句子的值。13例如，假定有輸入串1+2+3，我們通過(guò)語(yǔ)法樹的分析來(lái)看如何進(jìn)行語(yǔ)法制導(dǎo)翻譯，來(lái)求出該句子最后值。輸入串1+2+3的語(yǔ)法樹如下圖所示：下面我們采用自底向上歸約過(guò)程。首先考慮底層最左E的結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)對(duì)應(yīng)于規(guī)則E∷=1和語(yǔ)義動(dòng)作E·VAL：=1。這樣，底層最左的E的值1與語(yǔ)義值E·VAL相關(guān)。類似地，值2與該結(jié)點(diǎn)的右兄弟的語(yǔ)義值E·VAL相關(guān)。如下圖所示：E+EE+EE12314

在圖所示子樹中，子樹根處E·VAL的語(yǔ)義值是3，這可用語(yǔ)義動(dòng)作E·VAL:=E(1)·VAL+E(2)·VAL算出。使用這個(gè)語(yǔ)義動(dòng)作時(shí)，以底部最左的E的E·VAL的值來(lái)代替E(1)·VAL，而以右邊E的E·VAL的值代替E(2)·VAL。以這種方法繼續(xù)下去，我們就推出如下圖所示整個(gè)語(yǔ)法樹每個(gè)結(jié)點(diǎn)的語(yǔ)義值。

E+EE?VAL=1E12E?VAL=215E+E?VAL=6EE?VAL=3EE?VAL=3+EE?VAL=1EE?VAL=212316第五章語(yǔ)法制導(dǎo)翻譯及中間代碼§5.1語(yǔ)法制導(dǎo)翻譯概述

一、語(yǔ)法制導(dǎo)翻譯定義

二、語(yǔ)法制導(dǎo)翻譯原理

三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)17第五章語(yǔ)法制導(dǎo)翻譯及中間代碼§5.1語(yǔ)法制導(dǎo)翻譯概述

一、語(yǔ)法制導(dǎo)翻譯定義

二、語(yǔ)法制導(dǎo)翻譯原理

三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)18§5.1語(yǔ)法制導(dǎo)翻譯概述

三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)上面我們從原則上討論了語(yǔ)法制導(dǎo)翻譯的原理，下面我們通過(guò)一個(gè)自底向上LR分析看如何實(shí)現(xiàn)語(yǔ)法制導(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ǔ)義值)應(yīng)暫時(shí)保存下來(lái)，以便以后用規(guī)則(3)在歸約時(shí)(動(dòng)作3)可引用這些值?，F(xiàn)在對(duì)LR分析器的分析棧加以擴(kuò)充，為了在語(yǔ)法分析過(guò)程中平行地進(jìn)行語(yǔ)義處理，使得每個(gè)文法符號(hào)之后都跟著它的語(yǔ)義值，因此，設(shè)置一個(gè)語(yǔ)義信息棧，為了清晰起見(jiàn)，我們把這個(gè)分析棧每一項(xiàng)分三部分組成：狀態(tài)STATE、文法符號(hào)SYM和語(yǔ)義值VAL。這樣，分析棧如下圖所示。

19SmY?VALYSm-1X?VALXS0－#………TOPSTATEVALSYM20SmSm-1Y?VALX?VALYXTOP(100)歸約前SiX?VALATOP(99)歸約后Y?VALSiA?VALATOP(99)求值后A?VAL:=Y?VAL和X?VAL的處理結(jié)果我們假定先歸約后執(zhí)行語(yǔ)義子程序，所以當(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）21例5.2考慮下面文法及其語(yǔ)義描述：

規(guī)則語(yǔ)義動(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}其中：語(yǔ)義動(dòng)作中的+、*代表整型加、乘算術(shù)運(yùn)算，而且詞法分析程序?qū)⑺蛠?lái)每個(gè)i的整型內(nèi)部值LEXVAL。

假定語(yǔ)義動(dòng)作是緊接在歸約之后執(zhí)行的。上面所列的語(yǔ)義動(dòng)作就相當(dāng)于下面所列的程序段：

22規(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}23根據(jù)上述程序段，若輸入2*3+2，就有如下圖所示的語(yǔ)法制導(dǎo)翻譯的分析樹。S’EEEEE+*223E?VAL=8E?VAL=6E?VAL=2E?VAL=2E?VAL=3LEXVAL=2LEXVAL=3LEXVAL=224對(duì)2*3+2利用P136.表4.23進(jìn)行分析和翻譯(實(shí)為計(jì)算值)該輸入串過(guò)程如下表所示。當(dāng)狀態(tài)1面臨#時(shí)對(duì)應(yīng)的分析動(dòng)作為acc(接受)，此時(shí)，相應(yīng)的語(yǔ)義動(dòng)作為printVAL[TOP]，即輸出語(yǔ)義程序的計(jì)值結(jié)果：8。步驟狀態(tài)棧語(yǔ)義值棧符號(hào)棧輸入串歸約規(guī)則及動(dòng)作10－＃2*3+2＃S3203－－＃2*3+2＃r4301－2＃E*3+2＃GOTO[0,E]=1,S54015－2－＃E*3+2＃S350153－2－－＃E*3+2＃r460158－2－3＃E*E+2＃GOTO[5,E]=8,r2701－6＃E+2＃GOTO[0,E]=1,S48014－6－＃E+2＃S390143－6－－＃E+2＃r4100147－6－2＃E+E＃GOTO[4,E]=7,r11101－8＃E＃acc25第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成本節(jié)內(nèi)容§5.1語(yǔ)法制導(dǎo)翻譯概述一、語(yǔ)法制導(dǎo)翻譯定義二、語(yǔ)法制導(dǎo)翻譯原理三、語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)§5.2中間語(yǔ)言一、引言二、逆波蘭表示三、三元式四、樹形表示五、四元式26第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言

一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式27第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言

一、引言

1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式28第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言

一、引言1.什么是中間語(yǔ)言

2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式29§5.2中間語(yǔ)言

一、引言1.什么是中間語(yǔ)言

就是和源程序等價(jià)的一種編碼形式，其復(fù)雜性介于源程序和機(jī)器語(yǔ)言中間。源程序前端中間代碼代碼優(yōu)化器中間代碼代碼生成器目標(biāo)程序符號(hào)表30第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言

一、引言

1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言

二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式31§5.2中間語(yǔ)言

一、引言

2.為什么要引入中間語(yǔ)言

(1)為了使編譯程序結(jié)構(gòu)上邏輯簡(jiǎn)單明確(2)為了便于目標(biāo)代碼優(yōu)化工作(3)便于目標(biāo)代碼生成32第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言

一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式33第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言

一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式34第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言

一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示

1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式35§5.2中間語(yǔ)言

二、逆波蘭表示

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，36例如表達(dá)式中綴表示和后綴表示如下表所示(p155表5.2）說(shuō)明：

以后我們主要討論逆波蘭表示，即后綴表示，因前綴表示并不常用，所以有時(shí)也將后綴表示籠統(tǒng)地統(tǒng)稱為波蘭表示。從上表中可以看出：(1)在中綴表示和后綴表示中，運(yùn)算對(duì)象按相同次序出現(xiàn)。(2)在后綴表示中，運(yùn)算符是按實(shí)際計(jì)算順序從左到右排列，且每一運(yùn)算符總是跟在它的運(yùn)算對(duì)象之后。

中綴表示后綴表示a+b*ca*(b+c/d)a*b+(c-d)/ca+b=3∨d∧c(a+b)*(c-d)a<ba∨b<cabc*+abcd/+*ab*cd-c/+ab+3=dc∧∨ab+cd-*ab<abc<∨37(2)逆波蘭(后綴)表示的優(yōu)點(diǎn)

1）后綴表示是一種無(wú)括號(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)上述過(guò)程結(jié)束后，整個(gè)表達(dá)式之值將留于棧頂。

3)便于生成目標(biāo)指令38

(3)

逆波蘭(后綴)表示的形成為了說(shuō)明逆波蘭(后綴)表示的形成，荷蘭學(xué)者W.DEJKSTRA給出下面形象的解釋。波蘭表示運(yùn)算對(duì)象表達(dá)式運(yùn)算符進(jìn)棧運(yùn)算符棧退棧比棧頂高進(jìn)棧，比棧頂?shù)突蛳嗤耐藯?9

下面用圖解形式來(lái)說(shuō)明A+B*C形成的過(guò)程。A運(yùn)算對(duì)象A移進(jìn)對(duì)象棧#+B*C#①40

下面用圖解形式來(lái)說(shuō)明A+B*C形成的過(guò)程。A＋>#，＋向下進(jìn)運(yùn)算符棧＋#B*C#②41

下面用圖解形式來(lái)說(shuō)明A+B*C形成的過(guò)程。AB運(yùn)算對(duì)象B移進(jìn)對(duì)象棧＋#*C#③42

下面用圖解形式來(lái)說(shuō)明A+B*C形成的過(guò)程。AB*>+，*向下進(jìn)運(yùn)算符棧*＋#C#④43

下面用圖解形式來(lái)說(shuō)明A+B*C形成的過(guò)程。ABC運(yùn)算對(duì)象C移進(jìn)對(duì)象棧*＋##⑤44

下面用圖解形式來(lái)說(shuō)明A+B*C形成的過(guò)程。ABC*#<*，*退棧往左＋##⑥45

下面用圖解形式來(lái)說(shuō)明A+B*C形成的過(guò)程。ABC*＋#<＋，＋退棧往左##⑥最后生成A+B*C的后綴式ABC*＋46(4)用后綴表式對(duì)表達(dá)式處理的過(guò)程下面通過(guò)求后綴表達(dá)式ab+c*的值，來(lái)說(shuō)明用后綴表式對(duì)表達(dá)式處理的過(guò)程設(shè)a，b和c分別為1，3和5，為了求13+5*的值，其計(jì)算過(guò)程如下：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á)式值。47第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言

一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式48§5.2中間語(yǔ)言

二、逆波蘭表示

2.逆波蘭表示的擴(kuò)充

只要遵守在運(yùn)算對(duì)象后直接緊跟運(yùn)算符這條規(guī)則，我們就可以簡(jiǎn)單地把這種后綴式擴(kuò)充到比通常表達(dá)式更大范圍，即擴(kuò)充到程序語(yǔ)言的其它語(yǔ)法成分。

（1）賦值語(yǔ)句〈左部〉:=〈表達(dá)式〉把賦值號(hào)“:=”看成是一個(gè)賦值運(yùn)算符，它的后綴式為〈左部〉〈表達(dá)式的后綴式〉：=例如：x:=5x:=a*b-c/d的后綴式分別為x5:=xab*cd/-:=49

賦值語(yǔ)句的后綴式的處理方法和后綴式表達(dá)式處理方法類似。所不同的是棧中保存的是左部變量的地址，而不是其值，在賦值運(yùn)算處理結(jié)束后，不產(chǎn)生任何中間計(jì)算結(jié)果，因而也不存在保存中間計(jì)算結(jié)果的問(wèn)題，而是把存放在運(yùn)算棧中棧頂兩項(xiàng)〈左部〉和〈表達(dá)式〉的值這兩個(gè)量退掉。（2）條件語(yǔ)句ifEthenS1elseS２對(duì)于用后綴式來(lái)表示條件語(yǔ)句，我們假定后綴式中各符號(hào)存放在一個(gè)一維數(shù)組POST［1··n］之中，每一個(gè)數(shù)組元素存放一個(gè)運(yùn)算對(duì)象或運(yùn)算符。同時(shí)我們約定如下幾個(gè)符號(hào)：①JUMP表示無(wú)條件轉(zhuǎn)；②JLT表示小于轉(zhuǎn)；③JEZ表示零轉(zhuǎn)。后綴式PJUMP表示無(wú)條件轉(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]50于是，對(duì)于形如ifethenS1elseS2的條件語(yǔ)句可按后綴式寫成e’p1JEZS1’p2JUMPS2’我們約定e≠0時(shí),該條件語(yǔ)句的值是S1,否則等于S2。對(duì)于后綴式條件語(yǔ)句中:e’、S1’和S2’分別是e、S1和S2的后綴式。此外,p1表示S2’在數(shù)組POST的起始位置,p2表示S2’之后那個(gè)符號(hào)位置。上述后綴式條件語(yǔ)句的意思是,若e’=0時(shí),則轉(zhuǎn)至POST[p1］對(duì)S2’進(jìn)行計(jì)算,否則計(jì)算S1’,然后轉(zhuǎn)到POST［p2］的位置。

e’p1JEZS1’p2JUMPS2（p1和p2等處理S2后再反填）e’p1JEZS1’p2JUMPS2’51第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示

1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式52§5.2中間語(yǔ)言

二、逆波蘭表示

3.語(yǔ)法制導(dǎo)翻譯生成后綴式下面我們討論語(yǔ)法制導(dǎo)翻譯生成后綴式的過(guò)程。我們以例4.15文法G［E］為例，說(shuō)明如何按語(yǔ)法制導(dǎo)翻譯方法把一個(gè)中綴形式的簡(jiǎn)單算術(shù)表達(dá)式翻譯成為后綴式。

53

后綴式的語(yǔ)義動(dòng)作規(guī)則語(yǔ)義動(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(xiàn)·CODE‖*}(4)T∷=F{T·CODE:=F·CODE}(5)F∷=(E){F·CODE:=E·CODE}(6)F∷=i{F·CODE:=i}幾點(diǎn)說(shuō)明: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)在后,其它類似.下面將上述語(yǔ)義動(dòng)作具體化成語(yǔ)義子程序:54自底向上分析要?dú)w約時(shí)先調(diào)用相應(yīng)子程序生成后綴式假定后綴式存放在數(shù)組POST中假設(shè)要?dú)w約的句柄為E(1)+T(在語(yǔ)法分析棧中)，則首先要求調(diào)用相應(yīng)于E(1)+T的語(yǔ)義子程序，此時(shí)E(1)和T已調(diào)用過(guò)相應(yīng)的語(yǔ)義子程序，因此，它們的后綴式已被生成，對(duì)應(yīng)于E(1)+T的語(yǔ)義子程序所要完成的工作是把已生成的兩后綴式捻接起來(lái)，然后再添上符號(hào)“+”。如果我們?cè)O(shè)置一個(gè)數(shù)組存放后綴式，那么語(yǔ)義動(dòng)作就可以不涉及捻接運(yùn)算。令這個(gè)數(shù)組為POST，p為下標(biāo)，初值為1。如下圖：

…E(1).CODET.CODE+POST(P)55對(duì)于上述文法G［E］的語(yǔ)義動(dòng)作，可以改寫為如下相應(yīng)的語(yǔ)義子程序：(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}表示讀入操作數(shù)56最后，我們以表達(dá)式a+b*c為例按照P118.表4.15文法G［E］LR分析表給出語(yǔ)法制導(dǎo)翻譯產(chǎn)生后綴式過(guò)程，其中SUBK表示第K個(gè)規(guī)則相對(duì)應(yīng)的語(yǔ)義子程序。分析過(guò)程如下表：步驟狀態(tài)棧符號(hào)棧輸入串歸約規(guī)則調(diào)用子程序后綴式10＃a+b*c#205＃a+b*c#F::=iSUB6a303＃F+b*c#T::=FSUB4a402＃T+b*c#E(1)::=TSUB2a501＃E(1)+b*c#a6016＃E(1)+b*c#a70165＃E(1)+b*c#F::=iSUB6ab80163＃E(1)+F*c#T(1)::=FSUB4ab90169＃E(1)+T(1)

*c#ab1001697＃E(1)+T(1)*

c#ab11016975＃E(1)+T*c#F::=iSUB6abc12016970＃E(1)+T(1)*F#T::=T(1)*FSUB3abc*130169＃E(1)+T#E::=E(1)+TSUB1abc*+1401＃E#abc*+57第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式58第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式

1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式59§5.2中間語(yǔ)言

三、三元式表示

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))60注：運(yùn)算符OP通常用一個(gè)整數(shù)碼表示，它除了標(biāo)識(shí)運(yùn)算符的種屬之外，還附帶地表示其它一些語(yǔ)義特性。例如若OP表示一個(gè)加法運(yùn)算符，則相應(yīng)的整數(shù)碼除了標(biāo)識(shí)加法運(yùn)算本身外，還兼有表示數(shù)據(jù)類型(如整型、實(shí)型等)、運(yùn)算方式(定點(diǎn)、浮點(diǎn))和運(yùn)算精度等信息，且不同語(yǔ)義屬性使用不同的運(yùn)算符代碼。

三元式出現(xiàn)先后順序和表達(dá)式各部分計(jì)算順序相一致！對(duì)于一目運(yùn)算符OP，ARG1和ARG2只需其一。我們可以隨意規(guī)定選用一個(gè)，例如，規(guī)定用ARG1。至于多目運(yùn)算符可以用若干個(gè)相繼三元式表示。如：賦值語(yǔ)句x:=-b*(c+d)用三元式來(lái)表示，則可寫成(1)(-,b,)(2)(+,c,d)(3)(*,(1),(2))(4)(:=,x,(3))其中，三元式(3)就引用三元式(1)和(2)的結(jié)果作為它的兩個(gè)運(yùn)算對(duì)象61(2)三元式的生成同樣可以用語(yǔ)法制導(dǎo)翻譯來(lái)產(chǎn)生三元式：下面給出文法G［E］的語(yǔ)義動(dòng)作來(lái)描述這種翻譯的算法：(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)}其中語(yǔ)義值E·VAL、T·VAL和F·VAL，是一個(gè)指示器，或指向有關(guān)符號(hào)表某一項(xiàng)，或指向三元式表自身某一項(xiàng)，TRIP(OP，ARG1，ARG2)是一個(gè)語(yǔ)義子程序，回送新產(chǎn)生的三元式存放在三元式表位置。ENTRY(i)是一個(gè)語(yǔ)義子程序，通過(guò)ENTRY查i在符號(hào)表中位置，即對(duì)應(yīng)地址，若查不到，認(rèn)為有錯(cuò)誤。62第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式

1.三元式

2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式63§5.2中間語(yǔ)言

三、三元式表示

2.間接三元式為了便于代碼優(yōu)化，常常采用間接三元式。這由兩張表組成：（1）三元式表，用來(lái)存放各三元式本身；（2）執(zhí)行表(間接碼表)，它按執(zhí)行三元式順序，依次列出相應(yīng)各三元式在三元式表中位置。例如，對(duì)于如下賦值語(yǔ)句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)64間接三元式的優(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è)相同三元式，則僅須在三元式表中保存其中之一。如上面賦值語(yǔ)句右部表達(dá)式中有兩個(gè)a*b子表達(dá)式，而三元式表中只出現(xiàn)一次(*,a,b)。對(duì)于間接三元式表示，語(yǔ)義子程序應(yīng)增添產(chǎn)生執(zhí)行表的動(dòng)作。在填寫三元式表時(shí)，應(yīng)首先看一下此三元式是否在其中，如已在其中，則無(wú)需填入。

65第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式66第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示

1.表示方法

2.樹表示生成

五、四元式67§5.2中間語(yǔ)言

四、樹形表示

1.表示方法我們可以用樹形數(shù)據(jù)結(jié)構(gòu)來(lái)表示一個(gè)表達(dá)式或語(yǔ)句。在樹表示中，葉子結(jié)點(diǎn)表示運(yùn)算對(duì)象，即常量或變量，其它結(jié)點(diǎn)表示運(yùn)算符，如表達(dá)式a+b,a-b,-a的樹表示分別定義為：+ab－ab－a68雙目運(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-/-－*/ab+－cdef69表達(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è)分枝。70第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示

1.表示方法

2.樹表示生成

五、四元式71§5.2中間語(yǔ)言

四、樹形表示2.樹表示生成對(duì)文法G[E]翻譯成樹形表示語(yǔ)義動(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)}其中：語(yǔ)義值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))72第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式73第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成§5.2中間語(yǔ)言一、引言1.什么是中間語(yǔ)言2.為什么要引入中間語(yǔ)言二、逆波蘭表示1.表達(dá)式逆波蘭表示2.逆波蘭表示的擴(kuò)充3.語(yǔ)法制導(dǎo)翻譯生成后綴式三、三元式1.三元式2.間接三元式

四、樹形表示1.表示方法

2.樹表示生成

五、四元式74§5.2中間語(yǔ)言

五、四元式表示四元式是一種用得比較多的一種中間語(yǔ)言代碼形式，四元式一般形式是(OP，ARG1，ARG2，RESULT)其中：OP是運(yùn)算符，其含義與三元式中OP類似；ARG1和ARG2是運(yùn)算對(duì)象，RESULT是運(yùn)算結(jié)果例如：賦值語(yǔ)句a:=-b*(c+d)用四元式表示，則可寫成(1)(-,b,,T1)(2)(+,c,d,T2)(3)(*,T1,T2,T3)(4)(:=,T3,,a)

四元式之間聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的，調(diào)整四元式之間相對(duì)位置并不意味著一定要改變一系列指示器值。因此，對(duì)中間代碼進(jìn)行優(yōu)化處理時(shí)，四元式比三元式方便得多。下面主要討論如何用四元式表示各種語(yǔ)句，并產(chǎn)生四元式語(yǔ)義子程序。75第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成本節(jié)內(nèi)容§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯二、布爾表達(dá)式的翻譯三、控制語(yǔ)句翻譯四、數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯§5.4自頂向下語(yǔ)法制導(dǎo)翻譯一、遞歸下降的語(yǔ)法制導(dǎo)翻譯二、LL(1)語(yǔ)法制導(dǎo)翻譯§5.5屬性文法與屬性翻譯一、屬性文法與L屬性文法二、屬性翻譯76第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成

§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

1.翻譯成四元式2.類型檢查與類型轉(zhuǎn)換二、布爾表達(dá)式的翻譯

1.概述2.布爾表達(dá)式的翻譯方法3.翻譯成四元式的實(shí)現(xiàn)三、控制語(yǔ)句翻譯1.語(yǔ)句標(biāo)號(hào)和goto語(yǔ)句的翻譯2.條件語(yǔ)句的翻譯3.布爾表達(dá)式的翻譯方法4.while循環(huán)語(yǔ)句翻譯5.for循環(huán)語(yǔ)句的翻譯四、數(shù)組元素的翻譯1.下標(biāo)變量地址的計(jì)算2.數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯1.參數(shù)傳遞方式2.過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯1.變量說(shuō)明的翻譯2.數(shù)組說(shuō)明的翻譯3.過(guò)程說(shuō)明的翻譯

77第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成

§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

1.翻譯成四元式2.類型檢查與類型轉(zhuǎn)換二、布爾表達(dá)式的翻譯

1.概述2.布爾表達(dá)式的翻譯方法

3.翻譯成四元式的實(shí)現(xiàn)三、控制語(yǔ)句翻譯1.語(yǔ)句標(biāo)號(hào)和goto語(yǔ)句的翻譯2.條件語(yǔ)句的翻譯3.布爾表達(dá)式的翻譯方法4.while循環(huán)語(yǔ)句翻譯5.for循環(huán)語(yǔ)句的翻譯四、數(shù)組元素的翻譯1.下標(biāo)變量地址的計(jì)算2.數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯1.參數(shù)傳遞方式2.過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯1.變量說(shuō)明的翻譯2.數(shù)組說(shuō)明的翻譯3.過(guò)程說(shuō)明的翻譯

78第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成

§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯1.翻譯成四元式2.類型檢查與類型轉(zhuǎn)換二、布爾表達(dá)式的翻譯

1.概述2.布爾表達(dá)式的翻譯方法

3.翻譯成四元式的實(shí)現(xiàn)三、控制語(yǔ)句翻譯1.語(yǔ)句標(biāo)號(hào)和goto語(yǔ)句的翻譯2.條件語(yǔ)句的翻譯3.布爾表達(dá)式的翻譯方法4.while循環(huán)語(yǔ)句翻譯5.for循環(huán)語(yǔ)句的翻譯四、數(shù)組元素的翻譯1.下標(biāo)變量地址的計(jì)算2.數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯1.參數(shù)傳遞方式2.過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯1.變量說(shuō)明的翻譯2.數(shù)組說(shuō)明的翻譯3.過(guò)程說(shuō)明的翻譯

79§5.3自底向上語(yǔ)法制導(dǎo)翻譯

一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

1.翻譯成四元式

我們首先討論僅含有簡(jiǎn)單變量的表達(dá)式和賦值語(yǔ)句到四元式的翻譯，對(duì)于復(fù)雜的表達(dá)式和賦值語(yǔ)句的翻譯將在以后討論。為簡(jiǎn)便起見(jiàn)，假定賦值語(yǔ)句中所含的全部變量是同一類型整型變量，此外在翻譯過(guò)程中也不作語(yǔ)義檢查。

(1)賦值語(yǔ)句的文法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)一系列語(yǔ)義變量和語(yǔ)義子程序。

80(2)語(yǔ)義變量和語(yǔ)義子程序

①NEWTEMP是一個(gè)函數(shù)，每次調(diào)用時(shí)，都定義一個(gè)新臨時(shí)變量，回送一個(gè)代表新臨時(shí)變量名的整數(shù)碼作為函數(shù)值。為直觀起見(jiàn)，我們將NEWTEMP產(chǎn)生的臨時(shí)變量依次記為T１，Ｔ２…等等。

②ENTRY(i)是一個(gè)函數(shù)過(guò)程，查找符號(hào)名i在表中的入口地址。

③X·PLACE是和非終結(jié)符X相聯(lián)系的語(yǔ)義變量，表示存放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è)語(yǔ)義過(guò)程，該過(guò)程把四元式(OP，ARG1，ARG2，RESULT)填入四元式表中。因此，上面定義文法G[A]語(yǔ)義子程序的描述如下：81(3)語(yǔ)義子程序的描述(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)行自底向上語(yǔ)法制導(dǎo)翻譯時(shí)，還需一張LR分析表，上述文法G［A］是一個(gè)SLR(1)文法，其分析表如下：82（4）文法G[A]SLR(1)分析表狀態(tài)ACTIONGOTOi+*():=#AVETF0S2131acc2r83S44S9S85675S10r16r3S11r3r37r5r5r5r58S9S812679r7r7r7r710S9S813711S9S81412S10S1513r2S11r2r214r4r4r4r415r6r6r6r683（5）對(duì)x:=a+b*c語(yǔ)法制導(dǎo)翻譯產(chǎn)生四元式過(guò)程（以賦值語(yǔ)句x:=a+b*c為例）步驟狀態(tài)棧符號(hào)棧PLACE輸入串歸約規(guī)則調(diào)用子程序四元式10＃－X:=a+b*c#202＃x－Vx:=a+b*c#V::=iSUB8303＃V－Vx:=a+b*c#4034＃V:=－Vx-a+b*c#50349＃V:=a－Vx-Fa+b*c#F::=iSUB760347＃V:=F－Vx-Ta+b*c#T::=FSUB570346＃V:=T－Vx-Ea+b*c#E::=TSUB380345＃V:=E－Vx-Ea+b*c#903450＃V:=E+－Vx-Ea-b*c#10034509＃V:=E+b－Vx-Ea-Fb*c#F::=iSUB711034507＃V:=E+F－Vx-Ea-Tb*c#T::=FSUB512034503＃V:=E+T－Vx-Ea-Tb*c#130345031＃V:=E+T*－Vx-Ea-Tb-c#1403450319＃V:=E+T*c－Vx-Ea-Tb-FC#F::=iSUB71503450314＃V:=E+T*F－Vx-Ea-T1#T::=T(1)*FSUB4(*,b,c,T1)16034503＃V:=E+T－Vx-T2#E::=E(1)+TSUB2(+,a,T1,T2)170345＃V:=E－Vx-T2#A::=V:=ESUB1(:=,T2,,x)1801＃A#84分析表幾點(diǎn)說(shuō)明：在分析表中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ù)碼.85第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成

§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

1.翻譯成四元式

2.類型檢查與類型轉(zhuǎn)換二、布爾表達(dá)式的翻譯

1.概述2.布爾表達(dá)式的翻譯方法

3.翻譯成四元式的實(shí)現(xiàn)三、控制語(yǔ)句翻譯1.語(yǔ)句標(biāo)號(hào)和goto語(yǔ)句的翻譯2.條件語(yǔ)句的翻譯3.布爾表達(dá)式的翻譯方法4.while循環(huán)語(yǔ)句翻譯5.for循環(huán)語(yǔ)句的翻譯四、數(shù)組元素的翻譯1.下標(biāo)變量地址的計(jì)算2.數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯1.參數(shù)傳遞方式2.過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯1.變量說(shuō)明的翻譯2.數(shù)組說(shuō)明的翻譯3.過(guò)程說(shuō)明的翻譯

86§5.3自底向上語(yǔ)法制導(dǎo)翻譯

一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

2.類型檢查與類型轉(zhuǎn)換

(1)目的1)類型檢查是編譯程序語(yǔ)義檢查不可缺少的一部分。類型檢查就是對(duì)訪問(wèn)數(shù)據(jù)的操作和被訪問(wèn)數(shù)據(jù)的類型進(jìn)行檢查檢查操作的合法性和數(shù)據(jù)類型的相容性。例如，在PASCAL語(yǔ)言中，若算術(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ù)。87

(2)類型檢查

類型檢查可在生成中間代碼時(shí)進(jìn)行，也可在生成目標(biāo)代碼時(shí)進(jìn)行，但最好是在生成中間代碼時(shí)進(jìn)行，因?yàn)檎Z(yǔ)法和語(yǔ)義檢查最好盡早進(jìn)行，這樣能盡早避免徒勞的工作。在上面對(duì)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句翻譯到四元式的討論中，我們假定各個(gè)變量是同一類型整型變量，并且規(guī)定在四元式的op代碼中，本身就會(huì)有類型信息。所以，在上例各語(yǔ)義子程序中，我們并未考慮有關(guān)類型方面語(yǔ)義處理。88（3）類型轉(zhuǎn)換方法為了簡(jiǎn)單起見(jiàn)，我們僅考慮整型和實(shí)型的情況。①這種混合運(yùn)算中，給每個(gè)非終結(jié)符的語(yǔ)義值增添類型信息X.MODE

X·MODE的值或?yàn)閞(實(shí)型)或?yàn)閕nt(整型)。原來(lái)X的信息除X.PLACE，還有X.MODE。②對(duì)表達(dá)式的每一規(guī)則的語(yǔ)義子程序進(jìn)行修改，增加關(guān)于類型信息的語(yǔ)義規(guī)則。③必要時(shí)應(yīng)產(chǎn)生對(duì)運(yùn)算量進(jìn)行類型轉(zhuǎn)換的四元式，(itr,A,,T)把整型變量A轉(zhuǎn)換成實(shí)型變量，結(jié)果存在T中。此外，在書寫語(yǔ)義子程序時(shí)，為閱讀上的直觀性，我們用+i,*i等表示整型運(yùn)算符，用+r,*r等表示實(shí)型運(yùn)算符。現(xiàn)以規(guī)則E∷=E(1)OPE(2)為例，給出語(yǔ)義子程序的具體描述如下：89現(xiàn)以規(guī)則E∷=E(1)OPE(2)為例，給出語(yǔ)義子程序的具體描述如下：T:=NEWTEMP;IFE(1)·MODE=intANDE(2)·MODE=intTHENBEGINGEN(opi,E(1)·PLACE,E(2)·PLACE,T);E·MODE:=intENDELSEIFE(1)·MODE=rANDE(2)·MODE=rTHENBEGINGEN(opr,E(1)·PLACE,E(2)·PLACE,T);E·MODE:=rENDELSEIFE(1)·MODE=int/*andE(2)·MODE=r*/THENBEGINU:=NEWTEMP;GEN(itr,E(1)·PLACE,-,U);GEN(opr,U,E(2)·PLACE,T);E·MODE:=rENDELSE/*E(1)·MODE=randE(2)·MODE=int*/BEGINU:=NEWTEMP;GEN(itr,E(2)·PLACE,-,U);GEN(opr,E(1)·PLACE,U,T);E·MODE:=rEND;E·PLACE:=T;90這樣,對(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)91第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成

§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

1.翻譯成四元式2.類型檢查與類型轉(zhuǎn)換二、布爾表達(dá)式的翻譯

1.概述2.布爾表達(dá)式的翻譯方法

3.翻譯成四元式的實(shí)現(xiàn)三、控制語(yǔ)句翻譯1.語(yǔ)句標(biāo)號(hào)和goto語(yǔ)句的翻譯2.條件語(yǔ)句的翻譯3.布爾表達(dá)式的翻譯方法4.while循環(huán)語(yǔ)句翻譯5.for循環(huán)語(yǔ)句的翻譯四、數(shù)組元素的翻譯1.下標(biāo)變量地址的計(jì)算2.數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯1.參數(shù)傳遞方式2.過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯1.變量說(shuō)明的翻譯2.數(shù)組說(shuō)明的翻譯3.過(guò)程說(shuō)明的翻譯

92第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成

§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

1.翻譯成四元式2.類型檢查與類型轉(zhuǎn)換二、布爾表達(dá)式的翻譯

1.概述2.布爾表達(dá)式的翻譯方法3.翻譯成四元式的實(shí)現(xiàn)三、控制語(yǔ)句翻譯1.語(yǔ)句標(biāo)號(hào)和goto語(yǔ)句的翻譯2.條件語(yǔ)句的翻譯3.布爾表達(dá)式的翻譯方法4.while循環(huán)語(yǔ)句翻譯5.for循環(huán)語(yǔ)句的翻譯四、數(shù)組元素的翻譯1.下標(biāo)變量地址的計(jì)算2.數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯1.參數(shù)傳遞方式2.過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯1.變量說(shuō)明的翻譯2.數(shù)組說(shuō)明的翻譯3.過(guò)程說(shuō)明的翻譯

93§5.3自底向上語(yǔ)法制導(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ì)語(yǔ)言中，布爾表達(dá)式有兩個(gè)基本用途:1）一個(gè)是求邏輯值，邏輯值的結(jié)果是真或假。2）另一個(gè)用得最多的是在控制語(yǔ)句中用作條件表達(dá)式，例如，在if-then、if-then-else和while-do語(yǔ)句里表示控制條件。94(2)布爾表達(dá)式的文法布爾表達(dá)式文法G［E］如下:E∷=E∧E|E∨E|E|(E)|i|iropi

說(shuō)明：1）布爾表達(dá)式的文法是一個(gè)二義文法例如：該文法的一個(gè)句子a∧b∨c有兩棵不同的語(yǔ)法樹與之對(duì)應(yīng)，所以該文法是一個(gè)二義文法。EEE∨EE∧abcEEE∧aEE∨bc952）規(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ù)值96(3)布爾表達(dá)式求值方法

1）把真和假數(shù)值化，使布爾表達(dá)式計(jì)算類似于算術(shù)表達(dá)式的計(jì)算，常用1表示真，0表示假，或者用非零整數(shù)表示真。如：1∨（0∧0）∨0=1∨（1∧0）∨0=1∨0∨0=1

2）采取某種優(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:ifAthentrueelseBA∧B:ifAthenBelsefalseA:ifAthenfalseelsetrue用這種方式實(shí)現(xiàn)控制語(yǔ)句的布爾表達(dá)式尤其方便。對(duì)應(yīng)上述兩種計(jì)算方法，其布爾表達(dá)式有兩種不同的翻譯方法。97第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成

§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

1.翻譯成四元式2.類型檢查與類型轉(zhuǎn)換二、布爾表達(dá)式的翻譯

1.概述

2.布爾表達(dá)式的翻譯方法

3.翻譯成四元式的實(shí)現(xiàn)三、控制語(yǔ)句翻譯1.語(yǔ)句標(biāo)號(hào)和goto語(yǔ)句的翻譯2.條件語(yǔ)句的翻譯3.布爾表達(dá)式的翻譯方法4.while循環(huán)語(yǔ)句翻譯5.for循環(huán)語(yǔ)句的翻譯四、數(shù)組元素的翻譯1.下標(biāo)變量地址的計(jì)算2.數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯1.參數(shù)傳遞方式2.過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯1.變量說(shuō)明的翻譯2.數(shù)組說(shuō)明的翻譯3.過(guò)程說(shuō)明的翻譯

98§5.3自底向上語(yǔ)法制導(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)99仿照翻譯算術(shù)表達(dá)式的方法，很容易寫出布爾表達(dá)式文法G［E］的每個(gè)規(guī)則用于求值的語(yǔ)義動(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)}}100(2)作為條件控制的布爾表達(dá)式的翻譯

1)布爾表達(dá)式E作為條件控制的代碼結(jié)構(gòu)對(duì)于條件語(yǔ)句ifEthenS1elseS2中布爾表達(dá)式E，它的作用就是控制S1和S2的選擇，我們賦于E代碼兩種出口，其一為“真出口”，另一個(gè)是“假出口”，它們分別指出當(dāng)E值為true和false時(shí)，控制轉(zhuǎn)向的目標(biāo)(即某一四元式所在位置或序號(hào))。條件語(yǔ)句可翻譯成如下圖：E的代碼S1的代碼truefalseS2的代碼1012)三種形式的四元式作為條件控制的布爾表達(dá)式E的翻譯歸納起來(lái)只有三種形式的四元式

(jnz,a1,,p)若a1為真時(shí),則轉(zhuǎn)向第p個(gè)四元式。(jrop,a1,a2,p)若關(guān)系a1ropa2成立時(shí),轉(zhuǎn)向第p個(gè)四元式。(j,,,p)無(wú)條件轉(zhuǎn)向第p個(gè)四元式。除上述兩種真轉(zhuǎn)外，可用無(wú)條件表示假轉(zhuǎn)102例如,對(duì)于條件語(yǔ)句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ǔ)句，即應(yīng)轉(zhuǎn)p+1執(zhí)行（p）執(zhí)行完S1（對(duì)應(yīng)四元式為（5））則應(yīng)轉(zhuǎn)到條件語(yǔ)句的下一條語(yǔ)句執(zhí)行，所以無(wú)條件跳轉(zhuǎn)到（q）執(zhí)行。四元式(1)～(4)中顯然含有多余的四元式，如(2)顯然是不需要。

103第五章語(yǔ)法制導(dǎo)翻譯及中間代碼生成

§5.3自底向上語(yǔ)法制導(dǎo)翻譯一、簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯

1.翻譯成四元式2.類型檢查與類型轉(zhuǎn)換二、布爾表達(dá)式的翻譯

1.概述2.布爾表達(dá)式的翻譯方法

3.翻譯成四元式的實(shí)現(xiàn)三、控制語(yǔ)句翻譯1.語(yǔ)句標(biāo)號(hào)和goto語(yǔ)句的翻譯2.條件語(yǔ)句的翻譯3.布爾表達(dá)式的翻譯方法4.while循環(huán)語(yǔ)句翻譯5.for循環(huán)語(yǔ)句的翻譯四、數(shù)組元素的翻譯1.下標(biāo)變量地址的計(jì)算2.數(shù)組元素的翻譯五、過(guò)程語(yǔ)句的翻譯1.參數(shù)傳遞方式2.過(guò)程語(yǔ)句的翻譯六、說(shuō)明語(yǔ)句的翻譯1.變量說(shuō)明的翻譯2.數(shù)組說(shuō)明的翻譯3.