語法制導(dǎo)翻譯

1、第五章 語法制導(dǎo)翻譯及中間代碼生成5.1 在早期的一些編譯程序中，是在語法分析的基礎(chǔ)上根據(jù)源程序中各語法成份的語義，直接產(chǎn)生機(jī)器語言或匯編語言形式的目標(biāo)代碼目標(biāo)代碼?，F(xiàn)在的編譯系統(tǒng)一般都將經(jīng)過語法分析的源程序先翻譯為某種形式的中間語言代碼中間語言代碼，然后再將其翻譯為目標(biāo)代碼。 ： 使編譯程序各組成部分功能更單一; 使得編譯程序的邏輯結(jié)構(gòu)更為清晰，從而使編譯程序更易于編寫與調(diào)整;同時(shí)為代碼優(yōu)化和程序的可移植性提供了條件 本章要討論的中間代碼生成中間代碼生成，是指把單詞符號(hào)串形式的源程序轉(zhuǎn)換為另一種等價(jià)的便于代碼優(yōu)化處理和目標(biāo)代碼生成表示。 目前常見的中間語言有逆波蘭表示逆波蘭表示、三元式三元式

2、、四元式四元式等等。 中間代碼生成與語言的語義密切相關(guān)，目前采用語法制導(dǎo)翻譯來描述語義。 :對(duì)文法中的每個(gè)產(chǎn)生式都附加一個(gè)語義動(dòng)作或語義子程序, 語法分析程序除執(zhí)行相應(yīng)的語法分析動(dòng)作外，還要執(zhí)行相應(yīng)的語義動(dòng)作或調(diào)用相應(yīng)的語義子程序。 5.1 這種模式既把語法分析與語義處理分開，又令其平行地進(jìn)行，讓其在同一遍掃描中同時(shí)完成語法分析和語義處理兩項(xiàng)工作。由此可見，抽象文法符號(hào)的具體語義信息，是在。文法符號(hào)X的語義信息我們稱之為或簡稱為（Attributes）。 我們用形如X.ATTR的記號(hào)來表示文法符號(hào)X的相關(guān)。 如果一個(gè)文法符號(hào)X在一產(chǎn)生式中多次出現(xiàn)，為了在語義上能夠?qū)ζ溥M(jìn)行區(qū)分，可添加不同的上標(biāo)

3、。 文法符號(hào)及其語義屬性文法符號(hào)X的語義信息我們稱之為或簡稱為（Attributes）。 我們用形如X.ATTR的記號(hào)來表示文法符號(hào)X的相關(guān)。 如果一個(gè)文法符號(hào)X在一產(chǎn)生式中多次出現(xiàn)，為了在語義上能夠?qū)ζ溥M(jìn)行區(qū)分，可添加不同的上標(biāo)。 例如,文法GEGE:EE(1)+TE.Val=E(1).val+T.val;ET E.Val=T.Val;TdigitT.Val=digit;為了能在語法分析過程中平行地進(jìn)行語義處理，可在語法分析棧旁邊并行地設(shè)置一個(gè) 語法分語法分析棧析棧語義分語義分析棧析棧TT.Val+E# 首先介紹一種適用于定義語義的一種特殊文法，進(jìn)一步介紹適用于語義翻譯的文法的相關(guān)知識(shí)。 在

4、第三小節(jié)中我們將介紹幾種常見的; 在第四小節(jié)中引入程序設(shè)計(jì)語言中常見語法結(jié)構(gòu)的語法制導(dǎo)翻譯技術(shù)。 5.2 的實(shí)質(zhì)，就是根據(jù)文法中每個(gè)產(chǎn)生式所蘊(yùn)含的語義，為其配備一個(gè)（或多個(gè)）處理語句或子程序，對(duì)所要完成的功能進(jìn)行描述。 產(chǎn)生式的語義產(chǎn)生式的語義是由組成該產(chǎn)生式的文法符號(hào)的語義文法符號(hào)的語義所決定的。 將這些語義以“”的形式附加到各個(gè)文法符號(hào)上，再根據(jù)產(chǎn)生式所蘊(yùn)含的語義，給出每個(gè)文法符號(hào)的屬性的求值規(guī)則求值規(guī)則，從而形成一種附帶有語義屬語義屬性性的前后文無關(guān)文法，即。 定義 5.1 一一文法符號(hào)的語義性質(zhì)稱為該文法符號(hào)的語義屬性語義屬性（），簡稱為屬性屬性。用A(X)表示X的所有屬性的集合。每個(gè)

5、屬性表示X的一個(gè)特定性質(zhì)，并可任意指定其取值范圍。我們用X.a表示A(X)中的屬性a 。 屬性屬性可表征諸如數(shù)、符號(hào)串、類型、存儲(chǔ)空間和其它需表征的實(shí)體。至少有一種屬性屬性，即詞文。它還可能具有其它屬性，例如無符號(hào)數(shù)123123，單詞“123”就是它的詞文，而其數(shù)值以及它的類型（整型）是它的其它兩個(gè)屬性。終結(jié)符的屬性是其終結(jié)符的屬性是其內(nèi)在性質(zhì)內(nèi)在性質(zhì). 的屬性屬性是從其它符號(hào)的屬性屬性經(jīng)計(jì)算而得的，即由其它符號(hào)的屬性屬性定義的。 各個(gè)文法符號(hào)的之間，可能存在某種依賴關(guān)系依賴關(guān)系，這種依賴關(guān)依賴關(guān)系系可用屬性規(guī)則（）定義。定義定義 5.25.2 設(shè)p:Xp:X0 0XX1 1X X2 2XXn

6、 n是文法G的一個(gè)產(chǎn)生式，則與p相關(guān)聯(lián)的屬性規(guī)則集 R(p)R(p)=X Xi i.a.a=f(=f(X Xk1k1.a.ak1k1,X,Xkmkm.a.akmkm)|)|X Xi i.a.aA(XA(Xi i) ) 定義了該產(chǎn)生式所涉及的文法符號(hào)之屬性的求值規(guī)則求值規(guī)則，它表示：X Xi i的a a屬性是由X Xk1k1的a ak1k1屬性，X Xkmkm的a akmkm屬性計(jì)算而得的。 對(duì)每個(gè)產(chǎn)生式p:Xp:X0 0XX1 1X X2 2XXn n ，設(shè)屬性定義性出現(xiàn)的集合為AF(p)=X Xi i.a.a| |X Xi i.a.a=f(=f(X Xk1k1.a.ak1k1,X,Xkmkm

7、.a.akmkm) R(p),0k) R(p),0kj jnn 若X Xi i是產(chǎn)生式左部的非終結(jié)符(即i=0),則稱屬性X Xi i.a.a是綜合屬性;若X Xi i出現(xiàn)在產(chǎn)生式的右部(即1in),則稱X Xi i.a.a是繼承屬性 在語法樹中,將每個(gè)結(jié)點(diǎn)均視為由若干個(gè)域組成的,則可將其中的一些域用來存放相應(yīng)文法符號(hào)諸屬性之值，并可用來為這些域命名。通常我們將每個(gè)結(jié)點(diǎn)都標(biāo)注相應(yīng)屬性值的語法樹稱為加注語法樹加注語法樹 由可知：在加注語法樹加注語法樹中，一個(gè)文法符號(hào)X X在相應(yīng)結(jié)點(diǎn)的綜合屬性之值，由其子結(jié)點(diǎn)的屬性和（或）X的其它屬性，通過相關(guān)屬性規(guī)則經(jīng)計(jì)算而得，故綜合屬性的求值在語法樹中是按的方

8、式進(jìn)行的；X X的繼承屬性之值則由X X的父結(jié)點(diǎn)和(或)其它兄弟結(jié)點(diǎn)來定義,故繼承屬性的求值將按的方式進(jìn)行。 屬性文法屬性文法AG是一個(gè)四元組：AG=(G,A,R,B), 其中,G是已簡化的CFG;A=XVA(X)是屬性的有限集合;R=pPR(p)是屬性定義規(guī)則的有限集;B=pPB(p)是條件的有限集合，B(p)用于描述使規(guī)則R(p)有效的條件；且同時(shí)滿足：（1）對(duì)G中任意兩個(gè)不同的文法符號(hào)X和Y而言，屬性集合A(X)和A(Y)不相交,A(X)A(Y)=（2）在G的任意一個(gè)語法樹中，對(duì)文法符號(hào)X的每一次出現(xiàn)，可用于計(jì)算X的每個(gè)屬性之值的規(guī)則至多有一條。 屬性文法(續(xù))由可知，實(shí)際上就是對(duì)前后文

9、無關(guān)文法的一種拓廣。另外，每個(gè)產(chǎn)生式中的任一文法符號(hào)的屬性計(jì)算規(guī)屬性計(jì)算規(guī)則只能是唯一則只能是唯一的，且任一文法符號(hào)的綜合屬性集綜合屬性集與繼承屬性集繼承屬性集不相交不相交，即AS(X)AI(X)=,其中：AS(X)=X.a|p:XP,X.aAF(p) (綜合屬性)AI(X)=X.a|q:YX P,X.aAF(q)(繼承屬性)1.: :.;AssignmentNameExprAttributionName environmentAssignment environmentExpr environmentAssignment environment.;Name posttypeName prim

10、typeExpr posttypeName primtypetypetype real type.;.(.int_)?int_:_;21212.:.;.;( )( )( )( )ExprNameAdd NameAttributionNameenvironmentExpr environmentNameenvironmentExpr environment例5.1 簡單賦值語句文法的屬性文法);.,.(:);.,.(_.:. 4;_:int_?)int_.(.: . 3posttypeNameprimtypeNamecoercibleConditiontenvironmenNamesymbolI

11、dentifiertypedefinedprimtypeNamenAttributioidentifierNameaddrealaddtypeTypeAddoperationAddnAttributioAdd);.,.(:;.;.;.;_:int_?)int_,.(.)2()1()1(posttypeExprprimtypeExprcoercibleConditionprimtypeExprposttypeNameprimtypeExprposttypeNameprimtypeExprTypeAddtyperealtypetypeprimtypeNamecoeribleprimtypeExpr

12、 對(duì)于每個(gè)產(chǎn)生式p:X0X1X2XnP ,直接屬性依賴關(guān)系由下式給出： DDP(p)=(Xi.a,Xj.b)|Xj.b=f(,Xi.a,)R(p)若序偶(Xi.a,Xj.b)DDP(p)，則稱屬性Xj.b依賴于屬性Xi.a ，記作Xi.aXj.b。 顯然，若有Xi.aXj.b ，則對(duì)Xj.b的計(jì)值，應(yīng)在求出Xi.a的值之后進(jìn)行。但若Xi.a又直接或間接地依賴于Xj.b,則稱屬性Xi.a和Xj.b是的。含有屬性循環(huán)依賴的屬性文法AG，其中的一些屬性之值將不能得到有效的計(jì)算。 設(shè)T是L(G)中一個(gè)句子相應(yīng)的加注語法樹，并設(shè)在構(gòu)造T時(shí)使用過產(chǎn)生式p:X0X1X2Xn ，對(duì)于T中由X0,X1,X2,X

13、n所標(biāo)記的每個(gè)結(jié)點(diǎn)，若有(Xi.a,Xj.b)DDP(p),則在樹中引一條從到的有向邊，由此而得到的樹稱之為該句子的屬性化語法樹。所有這樣的有向邊構(gòu)成的集合DT(T)，稱為樹T上的依賴關(guān)系。根據(jù)DT(T)所構(gòu)造的關(guān)系圖稱為（或簡稱為）。例如，對(duì)于例5.1所給文法下的一個(gè)句子，相應(yīng)屬性化語法樹的依賴關(guān)系如P191圖5-3所示。 在文法產(chǎn)生式右部適當(dāng)?shù)奈恢蒙喜迦胝Z義動(dòng)作語義動(dòng)作而得的新文法稱為或()。在一中，若每個(gè)產(chǎn)生式右部中的全部語義動(dòng)作語義動(dòng)作均出現(xiàn)在所有文法符號(hào)的右邊，則稱這樣的為。 為了區(qū)分文法符號(hào)與語義動(dòng)作，我們用一對(duì)花括號(hào)為了區(qū)分文法符號(hào)與語義動(dòng)作，我們用一對(duì)花括號(hào)及及將插入的語義動(dòng)作

14、括起來（語義動(dòng)作將插入的語義動(dòng)作括起來（語義動(dòng)作采用采用C C語言格式書寫）。而且，我們還把語義動(dòng)作視語言格式書寫）。而且，我們還把語義動(dòng)作視為翻譯文法中的一個(gè)為翻譯文法中的一個(gè)“”，稱為，稱為。插。插入語義動(dòng)作后，翻譯文法產(chǎn)生式的一般形式為：入語義動(dòng)作后，翻譯文法產(chǎn)生式的一般形式為：A(A( statementstatement;);)* * V V* *翻譯文法（續(xù)） 翻譯文法的作用是，在進(jìn)行語法分析時(shí)，無論是用產(chǎn)生式進(jìn)行推導(dǎo)還是進(jìn)行歸約，只要遇到其中帶有語義動(dòng)作的花括號(hào)，就要求編譯系統(tǒng)自動(dòng)執(zhí)行花括自動(dòng)執(zhí)行花括號(hào)內(nèi)指定的語義動(dòng)作號(hào)內(nèi)指定的語義動(dòng)作，在執(zhí)行完該動(dòng)作之后才繼續(xù)進(jìn)行下一步的語法分

15、析。 例：ExprTerm ExprExpr+TermWriteCode(“+”);Expr| TermFactor TermTerm*Factor WriteCode(“*”); Term| Factoroperand WriteCode(yytext);|( Expr )遞歸下降分析中的翻譯文法若用遞歸下降法進(jìn)行語法分析，則與非終結(jié)符號(hào)Expr相對(duì)應(yīng)的遞歸程序可擴(kuò)充為：int Eprim() if(CurrentToken=+) if(Term() WriteCode(“+”); if(Eprim() return 1; else return 0; if(CurrentToken=)|C

16、urrenToken=#) return 1;else return 0;屬性翻譯文法的定義定義定義5.95.9 （Attribute Translation Grammar，簡記為ATG）是具有以下性質(zhì)的：1每個(gè)文法符號(hào)和語義動(dòng)作符X都有一個(gè)相關(guān)的有限屬性集合A(X)，且每個(gè)屬性都有一個(gè)允許值的集合（屬性的值域，可以是無限集）。2非終結(jié)符和動(dòng)作符的屬性可分為與兩類。3的定義規(guī)則為：開始符號(hào)的具有指定的初始值； 對(duì)于給定的產(chǎn)生式p:YX1X2XnP,Xi的值由p中其它符號(hào)的屬性值進(jìn)行計(jì)算：Xi.a=f(Y.b, Xk 1.ak 1,Xkm.akm) i k1,km 4的定義規(guī)則為：對(duì)于給定的產(chǎn)

17、生式p:YX1X2XnP，Y的值由p中某些符號(hào)的屬性計(jì)算： Y.u=f(Y.v, Xk1.ak1,Xkm.akm) 1kjn； 對(duì)于動(dòng)作符號(hào)，其值由該動(dòng)作符的其它屬性計(jì)算； 終結(jié)符的具有指定的初始值。 一屬性翻譯文法稱為是的，當(dāng)且僅當(dāng)對(duì)其中的每個(gè)產(chǎn)生式p:AX1X2Xn，下面的三個(gè)條件成立：1右部符號(hào)Xi(1in)的繼承屬性之值，僅依賴于X1,X2,Xi-1的任意屬性或A的繼承屬性；2左部符號(hào)A的綜合屬性之值僅依賴于A的繼承屬性或(和)右部符號(hào)Xi(1in)的任意屬性；3對(duì)一動(dòng)作符號(hào)而言，其綜合屬性之值是以該動(dòng)作符號(hào)的繼承屬性或產(chǎn)生式右部符號(hào)的任意屬性為變?cè)暮瘮?shù)。 方法符號(hào)屬性的求值順序A的

18、繼承屬性(AI(A)；X1的繼承屬性(AI(X1)； X1的綜合屬性(AS(X1),進(jìn)入X1的子樹后，返回時(shí)求出）； Xn的繼承屬性(AI(Xn) ； Xn的綜合屬性(AS(Xn),進(jìn)入Xn的子樹后,返回時(shí)求出）；A的綜合屬性(AS(A),返回到A的上層）。表達(dá)式屬性翻譯文法例5.2 表達(dá)式屬性翻譯文法：Program |$1= $2= NewName( ); Expr FreeName($0 ); ; Program ExprTerm Expr Expr+$1=$2=NewName();Termprintf (“+, %s,%s,%sn”,$0,$,$0);FreeName($0);Expr

19、 | TermFactor Term Term *$1=$2=NewName();Factor printf(“*,%s,%s,%sn”,$0,$,$0); FreeName($0); Term | FactorNumberprintf(“:=,%s,-,%sn”, yytext,$);| S-屬性文法的定義 滿足下面三個(gè)條件的屬性文法稱為：所有非終結(jié)符只具有；在一個(gè)產(chǎn)生式中，每一個(gè)符號(hào)的各個(gè)的定義互不依賴；在一個(gè)產(chǎn)生式中，若某個(gè)文法符號(hào)X具有，則此之值僅依賴于該產(chǎn)生式右部且位于X左邊的符號(hào)之屬性。顯然，也滿足的條件，這就是說，一定是，而且還要求每個(gè)非終結(jié)符只具有。S-屬性文法的例子 簡單算術(shù)

20、表達(dá)式的：ProgramExpr printf(“ %dn”,$1);Expr Expr + Expr $=$1+$3;| Expr * Expr $=$1*$3;| ( Expr ) $=$2;|Number $=ToIntValue(yytext);上面的語義子程序采用了工具中的表示方法,其中分別表示產(chǎn)生式左部符號(hào),右部的第一個(gè),第二個(gè)符號(hào)(余類推)的.5.3 波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了另一種表示表達(dá)式的方法。按此方法，每一運(yùn)算符都置于其運(yùn)算對(duì)象之后，故稱為后綴表示。表達(dá)式中各個(gè)是按，故無須使用括號(hào)來指示運(yùn)算順序，因而又稱為。下面我們對(duì)照地給出一些表達(dá)式的兩種

21、表示： A+BAB+A+B*CABC*+(A+B)*(C+D)AB+CD+*x/yz-d*exyz/de*-(a=0b3)(exy)a0=b3 exy在兩種表示中，在兩種表示中，出現(xiàn)的出現(xiàn)的；在后綴表示中，在后綴表示中，按按，且每一，且每一運(yùn)算符總是跟在其運(yùn)算符總是跟在其。由于后綴表示中的各個(gè)運(yùn)算是按順序執(zhí)行的，因此，它的計(jì)由于后綴表示中的各個(gè)運(yùn)算是按順序執(zhí)行的，因此，它的計(jì)值需從左到右依次掃視表達(dá)式中的各個(gè)符號(hào)，值需從左到右依次掃視表達(dá)式中的各個(gè)符號(hào)，每遇一運(yùn)算對(duì)象每遇一運(yùn)算對(duì)象，就把它，就把它壓入棧頂壓入棧頂暫存起來；暫存起來；每遇一個(gè)二元（或一元）運(yùn)算符時(shí)每遇一個(gè)二元（或一元）運(yùn)算符時(shí)，

22、就，就取出棧頂?shù)膬蓚€(gè)（或取出棧頂?shù)膬蓚€(gè)（或一個(gè)）運(yùn)算對(duì)象一個(gè)）運(yùn)算對(duì)象進(jìn)行相應(yīng)的運(yùn)算，并用運(yùn)算結(jié)果去進(jìn)行相應(yīng)的運(yùn)算，并用運(yùn)算結(jié)果去替換棧頂替換棧頂?shù)倪@兩（或一）個(gè)運(yùn)算對(duì)象；的這兩（或一）個(gè)運(yùn)算對(duì)象；繼續(xù)掃視余留的符號(hào)，直到掃視完整個(gè)表達(dá)式為止。繼續(xù)掃視余留的符號(hào)，直到掃視完整個(gè)表達(dá)式為止。當(dāng)上述過程結(jié)束時(shí)，當(dāng)上述過程結(jié)束時(shí)，。四元式和三元式四元式和三元式是一種更接近目標(biāo)代碼的中間代碼形式，由于這種形式的中間代碼便于優(yōu)化處理，因此，在目前的許多編譯程序中得到了廣泛的應(yīng)用。是一種“三地址語句三地址語句”的等價(jià)表示。它的一般形式為：(op,arg1,arg2,)其中，op為一個(gè)二元(也可是一元或零元

23、)運(yùn)算符; arg1,arg2分別為它的兩個(gè)運(yùn)算對(duì)象，它們可以是變量、常數(shù)或系統(tǒng)定義的臨時(shí)變量名；運(yùn)算的結(jié)果將放入中。四元式還可寫為類似于PASCAL語言的賦值語句的形式：result := arg1 op arg2 四元式的格式需要指出的是，每個(gè)只能有一個(gè)運(yùn)算符，所以，一個(gè)復(fù)雜的表達(dá)式只能由多個(gè)構(gòu)成的序列表示。例如，表達(dá)式A+B*C可寫為序列 T1:=B*CT2:=A+T1當(dāng)op為一元、零元運(yùn)算（如無條件轉(zhuǎn)移）時(shí)，arg2甚至arg1應(yīng)缺省，即result:=op arg1或 op result ；對(duì)應(yīng)的一般形式為：(op,arg1,-,result)或 (op,-,-,result) 。三

24、元式為了節(jié)省臨時(shí)變量的開銷，有時(shí)也可采用一種三元式結(jié)構(gòu)來作為中間代碼，其一般形式為(i) (op,arg1,arg2)其中，(i)為的編號(hào)，也代表了該式的運(yùn)算結(jié)果；op,arg1,arg2的含義與類似，區(qū)別在于arg可以是某的序號(hào)，表示用該的結(jié)果作為運(yùn)算對(duì)象。例如，對(duì)于賦值語句a:=-b*(c+d)，若用表示，則可寫成(U_minus, b, - )( + , c, d )( * , , )( := , ,a )式中的運(yùn)算符U_minus表示一元減運(yùn)算。翻譯程序中使用的輔助函數(shù)我們以到的翻譯為例，說明如何為各產(chǎn)生式設(shè)計(jì)語義動(dòng)作。為此，先介紹若干翻譯過程中要使用的輔助函數(shù)：int LookUp(

25、char *Name)以Name查符號(hào)表，若查到則返回相應(yīng)登記項(xiàng)的序號(hào)(1),否則返回0。int Enter(char* Name)以Name為名字在符號(hào)表中登錄新的一項(xiàng),返回值為該項(xiàng)的序號(hào)。int Entry(char *Name)以Name為名字查、填符號(hào)表: int Entry(char *Name)int i=LookUp(Name); if(i) return i;else return Enter(Name);翻譯程序中使用的輔助函數(shù)(續(xù))注意，在實(shí)際的編譯系統(tǒng)中，還應(yīng)區(qū)分當(dāng)前是否在處理說明部分：若是說明部分，則查表時(shí)i應(yīng)為0（否則Name被重復(fù)定義）；若非，則i不能為0（否則Na

26、me尚未被定義）。int Trip(int op,int arg1,int arg2)根據(jù)給定的參數(shù)產(chǎn)生一個(gè)(op,arg1,arg2)并將它送入表中，其返回值為表中序號(hào)。為區(qū)分參數(shù)arg表示的是還是變量，約定當(dāng)arg0表示變量在符號(hào)表中登記項(xiàng)序號(hào)；arg=0表示參數(shù)為空。和之異同在產(chǎn)生式8中，終結(jié)符iden的屬性是它的詞文yytext，用$1表示。每個(gè)非終結(jié)符非終結(jié)符都有一個(gè)屬性，代表以該符號(hào)為根的語法樹的一個(gè)子樹的運(yùn)算結(jié)果，該屬性的取值可以是整型數(shù)，或?yàn)橐坏男蛱?hào)，或?yàn)榉?hào)表項(xiàng)的序號(hào)。 比較和這兩種表示方法可以看出，無論在一個(gè)序列還是序列中，各個(gè)或都是按相應(yīng)表達(dá)式的實(shí)際運(yùn)算順序出現(xiàn)的。其次，

27、對(duì)同一表達(dá)式而言，所需的或的個(gè)數(shù)一般是相同的。 比更能節(jié)省存儲(chǔ)空間,但不利于優(yōu)化.可通過引入一些表格提高使用的效率(略,見P200-201)5.4 和的翻譯 wE中僅含簡單變量;w全部變量同類型;w翻譯時(shí)不做語義檢查.wint (void)產(chǎn)生臨時(shí)變量的函數(shù)，每次調(diào)用都定義一個(gè)新的臨時(shí)變量。返回值為該變量的編號(hào)。 文法符號(hào)X的屬性，其值為整型(00表示在符號(hào)表中序號(hào),00表示臨時(shí)變量編號(hào))1. int (int Op,int ,int ,int )根據(jù)所給實(shí)參產(chǎn)生一個(gè)四元式：(Op,)，且送入四元式表中，返回值為該四元式的序號(hào)。或?yàn)榱銜r(shí)表示該參數(shù)缺省 的 1.StatementAssignSt

28、 2.AssignStVariable : = Expr3.ExprExpr + Expr4.| Expr * Expr5.| ( Expr ) 6.| identifier 7.Varable identifier 5.5 是布爾運(yùn)算量和邏輯運(yùn)算符按一定語法規(guī)則組成的式子。通常有、三種（在某些語言中，還有（等價(jià)）及（蘊(yùn)含）等等）；可以是邏輯值（True 或 False）、布爾變量、關(guān)系表達(dá)式以及由括號(hào)括起來的布爾表達(dá)式。不論是布爾變量還是布爾表達(dá)式，都只能取邏輯值True或False。在計(jì)算機(jī)內(nèi)通常用1（或非零整數(shù)）表示真值（True），用0表示假值(False)。是形如的式子，其中和為簡單

29、算術(shù)表達(dá)式，為關(guān)系運(yùn)算符（）。若和之值使該關(guān)系式成立，則此關(guān)系表達(dá)式之值為True，否則為False。的為了方便起見，下面我們僅討論由文法 (5.1)對(duì)于的計(jì)值和翻譯，可采用類似的方式來進(jìn)行。例如，對(duì)于，可翻譯為：但是，對(duì)于一個(gè)而言，我們的目的。因此，有時(shí)只需計(jì)算它的一個(gè)子表達(dá)式，便能確定整個(gè)的真假值。例如，對(duì)于，只要知道 為真，則無論取何值，表達(dá)式的結(jié)果一定為真?？梢姡瑢?duì)于三種常見邏輯運(yùn)算，可作如下等價(jià)的解釋：的對(duì)于，其等價(jià)的表述是 ） 顯然，采用此種結(jié)構(gòu)可產(chǎn)生更為有效的中間代碼。這里需假定原的計(jì)算過程中不含有任何的。 在上式的計(jì)算中，根據(jù)的取值不同，計(jì)算的結(jié)果以及運(yùn)算的中止點(diǎn)亦不同。例如，

30、當(dāng)（真）時(shí)，結(jié)果為 且中止于左邊第一個(gè)處。這樣中止的點(diǎn)我們稱為該的，同時(shí)，把使取值為的稱為，反之稱為。對(duì)一個(gè)而言，它至少有一個(gè)和一個(gè)（當(dāng)然可以有多個(gè)）。在用于控制流程的的計(jì)算中，這些分別指出當(dāng) 值為和時(shí)，（即某一四元式的序號(hào)）。 中的我們來研究包含在控制語句if E then S1 else S2或while E do S中的E的翻譯。在這類語句中，僅用于對(duì)程序流程進(jìn)行控制。根據(jù)這兩種語句的語義，我們可右圖 (a)和(b)所示的結(jié)構(gòu)進(jìn)行翻譯。在圖(a)中可知，E的分別為語句S1和S2的四元式的序號(hào)。圖(b)中，E的為S的，為整個(gè)while語句的出口 TE的代碼S1的代碼S2的代碼E的代碼S的代

31、碼TFF真假值的確定一個(gè)布爾表達(dá)式 的真假值的確定，是在語法翻譯過程中，根據(jù)(5.2)-(5.4)等價(jià)解釋式逐步進(jìn)行的。例如，對(duì)于布爾表達(dá)式若為真，則 必為真，故的必是 的(之一);若為假，則 的真假值取決于的真假值，此時(shí)，需對(duì)進(jìn)行計(jì)算，由此可見，的應(yīng)為對(duì)應(yīng)的四元式的序號(hào)(的入口)，同時(shí),的真、假出口也是 的真、假出口。類似地，可確定 、及更復(fù)雜的表達(dá)式的。 條件語句的翻譯結(jié)果在設(shè)計(jì)布爾表達(dá)式翻譯算法（即編寫語義動(dòng)作）時(shí)，可定義和使用如下三類四元式：當(dāng)為真(非零)時(shí)，轉(zhuǎn)向第 四元式；當(dāng)關(guān)系 成立時(shí)，轉(zhuǎn)向第 四元式； 無條件轉(zhuǎn)向第 四元式例如，對(duì)于條件語句if ABC then S1 else

32、S2經(jīng)翻譯后，可得四元式序列：(1) (jnz,A,-,5)(2) (j,- ,-,3)(3) (j,B,C,5)(4) (j,-,-,p+1)(5) S1相應(yīng)的四元式序列相應(yīng)的四元式序列(p) (j,-,-,q)(p+1) S2相應(yīng)的四元式序列相應(yīng)的四元式序列(q) 其中，表達(dá)式A的真出口為5（也是整個(gè)表達(dá)式的真出口），假出口為3（即表達(dá)式BC的第一四元式）；B0時(shí),它給出本鏈的后繼四元式的序號(hào)， =0時(shí)表示本四元式是鏈尾結(jié)點(diǎn)。 (1)(jnz,A,-,0)( 2 )( j , - , - , 3 ) (3)(j,B,C,1) (4)(j, -,-,0) 的四元式序列及其鏈和鏈文法的“”為便于實(shí)現(xiàn)布爾表達(dá)式的語法制導(dǎo)翻譯，我們先改寫文法，以便能在翻譯過程中的適當(dāng)時(shí)機(jī)獲得所需的語義屬性值。例如，可將文法(5.1)改寫為： (5.7) 將文法進(jìn)行“拆分拆分”的:1.在翻譯完運(yùn)算符（）左側(cè)的表達(dá)式后，能夠及時(shí)獲取其語義屬性及2.完成用下一四元式序號(hào)（即運(yùn)算符右側(cè)表達(dá)式的第一四元式之序號(hào)）回填前一表達(dá)式的相應(yīng)真（假）鏈（），3.