語(yǔ)義分析和中間代碼生成

關(guān)于語(yǔ)義分析和中間代碼生成第1頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月本章在編譯程序中的地位表格管理詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼產(chǎn)生優(yōu)化器目標(biāo)代碼生成器源程序單詞符號(hào)語(yǔ)法單位中間代碼中間代碼目標(biāo)代碼出錯(cuò)處理第2頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月6.1概述6.2屬性文法6.3幾種常見(jiàn)的中間語(yǔ)言（*四元式）6.4表達(dá)式及賦值語(yǔ)句的翻譯6.5控制語(yǔ)句的翻譯 6.6數(shù)組元素的翻譯6.7過(guò)程或函數(shù)調(diào)用語(yǔ)句的翻譯*6.8說(shuō)明語(yǔ)句的翻譯內(nèi)容安排第3頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月6.1概述

6.1.1語(yǔ)義分析的概念一個(gè)源程序經(jīng)過(guò)詞法分析、語(yǔ)法分析之后，表明該源程序在書寫上是正確的，并且符合程序語(yǔ)言所規(guī)定的語(yǔ)法。但是語(yǔ)法分析并未對(duì)程序內(nèi)部的邏輯含義加以分析，因此編譯程序接下來(lái)的工作是語(yǔ)義分析，即審查每個(gè)語(yǔ)法成分的靜態(tài)語(yǔ)義。如果靜態(tài)語(yǔ)義正確，則生成與該語(yǔ)言成分等效的中間代碼，或者直接生成目標(biāo)代碼。

第4頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月直接生成目標(biāo)代碼

直接生成機(jī)器語(yǔ)言或匯編語(yǔ)言形式的目標(biāo)代碼的優(yōu)點(diǎn)是編譯時(shí)間短且無(wú)需中間代碼到目標(biāo)代碼的翻譯。生成中間代碼

生成中間代碼的優(yōu)點(diǎn)是使編譯結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，特別是使目標(biāo)代碼的優(yōu)化比較容易實(shí)現(xiàn)。第5頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

語(yǔ)義分析時(shí)語(yǔ)義檢查的分類：動(dòng)態(tài)語(yǔ)義檢查需要生成相應(yīng)的目標(biāo)代碼，它是在運(yùn)行時(shí)進(jìn)行的；例如：除零溢出錯(cuò)誤。靜態(tài)語(yǔ)義檢查在編譯時(shí)完成的，它涉及以下幾個(gè)方面：

(1)類型檢查

(2)控制流檢查

(3)一致性檢查第6頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月各種條件表達(dá)式的類型不是布爾類型;運(yùn)算符的分量類型不相容;賦值語(yǔ)句左右類型不相容;形、實(shí)參類型不相容;函數(shù)說(shuō)明和函數(shù)返回類型不相容;……intx;floatf();x=f();符合變量聲明的語(yǔ)法、語(yǔ)義符合函數(shù)聲明的語(yǔ)法、語(yǔ)義符合賦值語(yǔ)句的語(yǔ)法、不符合語(yǔ)義(1)類型檢查第7頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

(2)控制流檢查用以保證控制語(yǔ)句有合法的轉(zhuǎn)向點(diǎn)。如C語(yǔ)言中不允許goto語(yǔ)句轉(zhuǎn)入case語(yǔ)句流；break語(yǔ)句需尋找包含它的最小switch、while或for語(yǔ)句方可找到轉(zhuǎn)向點(diǎn)，否則出錯(cuò)。

(3)一致性檢查如在相同作用域中標(biāo)識(shí)符只能說(shuō)明一次、case語(yǔ)句的標(biāo)號(hào)不能相同、函數(shù)調(diào)用參數(shù)個(gè)數(shù)要相同等。

第8頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月常見(jiàn)的語(yǔ)義錯(cuò)誤聲明和使用相關(guān)的語(yǔ)義錯(cuò)誤標(biāo)識(shí)符沒(méi)有聲明;重復(fù)聲明;如何檢查?每當(dāng)遇到新聲明的標(biāo)識(shí)符,查符號(hào)表如果當(dāng)前有效的所有標(biāo)識(shí)符中有相同名字的,則是重復(fù)聲明錯(cuò)誤;否則生成它的屬性信息,保存到符號(hào)表中;每當(dāng)遇到標(biāo)識(shí)符的使用,查符號(hào)表如果沒(méi)有找到,說(shuō)明該標(biāo)識(shí)符沒(méi)有聲明;否則,得到該標(biāo)識(shí)符的屬性,進(jìn)行進(jìn)一步分析;第9頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

語(yǔ)義分析階段只產(chǎn)生中間代碼而不生成目標(biāo)代碼的方法使編譯程序的開(kāi)發(fā)變得較為容易，但語(yǔ)義分析不像詞法分析和語(yǔ)法分析那樣可以分別用正規(guī)文法和上下文無(wú)關(guān)文法描述。

由于語(yǔ)義是上下文有關(guān)的，因此語(yǔ)義的形式化描述是非常困難的，目前較為常見(jiàn)的是用屬性文法作為描述程序語(yǔ)言語(yǔ)義的工具，并采用語(yǔ)法制導(dǎo)翻譯的方法完成對(duì)語(yǔ)法成分的翻譯工作。第10頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

語(yǔ)法制導(dǎo)翻譯的方法就是為每個(gè)規(guī)則配上一個(gè)翻譯子程序(稱語(yǔ)義動(dòng)作或語(yǔ)義子程序)，并在語(yǔ)法分析的同時(shí)執(zhí)行這些子程序。

語(yǔ)義動(dòng)作是為規(guī)則賦予具體意義的手段，它一方面指出了一個(gè)規(guī)則所產(chǎn)生的符號(hào)串的意義，另一方面又按照這種意義規(guī)定了生成某種中間代碼應(yīng)做哪些基本動(dòng)作。

在語(yǔ)法分析過(guò)程中，當(dāng)一個(gè)規(guī)則獲得匹配(對(duì)于自上而下分析)或用于歸約(對(duì)于自下而上分析)時(shí)，此規(guī)則相應(yīng)的語(yǔ)義子程序就進(jìn)入工作，完成既定的翻譯任務(wù)。6.1.2語(yǔ)法制導(dǎo)翻譯方法第11頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

語(yǔ)法制導(dǎo)翻譯分為自下而上語(yǔ)法制導(dǎo)翻譯和自上而下語(yǔ)法制導(dǎo)翻譯，我們重點(diǎn)介紹自下而上語(yǔ)法制導(dǎo)翻譯。假定有一個(gè)自下而上的LR分析器，我們可以把這個(gè)LR分析器的能力加以擴(kuò)大，使它能在用某個(gè)規(guī)則進(jìn)行歸約的同時(shí)調(diào)用相應(yīng)的語(yǔ)義子程序進(jìn)行有關(guān)的翻譯工作；每個(gè)規(guī)則的語(yǔ)義子程序執(zhí)行之后，某些結(jié)果(語(yǔ)義信息)必須作為此規(guī)則的左部符號(hào)的語(yǔ)義值暫時(shí)保存下來(lái)，以便以后語(yǔ)義子程序引用這些信息。第12頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

此外，原LR分析器的分析棧也加以擴(kuò)充，以便能夠存放與文法符號(hào)相對(duì)應(yīng)的語(yǔ)義值。這樣，分析?？梢源娣湃愋畔ⅲ悍治鰻顟B(tài)、文法符號(hào)及文法符號(hào)對(duì)應(yīng)的語(yǔ)義值。擴(kuò)充后的分析棧如圖6–1所示。

第13頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月圖6–1擴(kuò)充后的LR分析棧第14頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

作為一個(gè)例子，我們考慮下面的文法及語(yǔ)義動(dòng)作所執(zhí)行的程序：規(guī)則 語(yǔ)義動(dòng)作

(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(注：lexval為i的整型內(nèi)部值)第15頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

我們擴(kuò)充分析棧工作的總控程序功能，使其在完成語(yǔ)法分析的同時(shí)也能完成語(yǔ)義分析工作(這時(shí)的語(yǔ)法分析棧已成為語(yǔ)義分析棧)；即在用某一個(gè)規(guī)則進(jìn)行歸約之后，調(diào)用相應(yīng)的語(yǔ)義子程序完成與所用規(guī)則相應(yīng)的語(yǔ)義動(dòng)作，并將每次工作后的語(yǔ)義值保存在擴(kuò)充后的“語(yǔ)義值”棧中。圖6–2表示算術(shù)表達(dá)式7＋9*5#的語(yǔ)法樹(shù)及各結(jié)點(diǎn)值，而表6.1則給出了根據(jù)分析表用LR語(yǔ)法制導(dǎo)翻譯方法得到的該表達(dá)式的語(yǔ)義分析和計(jì)值過(guò)程。第16頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月圖6–2語(yǔ)法制導(dǎo)翻譯計(jì)算表達(dá)式

7＋9*5#的語(yǔ)法樹(shù)第17頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月表6.1表達(dá)式7＋9*5#的語(yǔ)義分析和計(jì)值過(guò)程步驟狀態(tài)棧符號(hào)棧語(yǔ)義棧輸入串動(dòng)作10#_7＋9*5#s3203#7__＋9*5#r4301#E_7＋9*5#s44014#E+_7_9*5#s350143#E+9_7__*5#r460147#E+E_7_9*5#s5701475#E+E*_7_9_5#s38014753#E+E*5_7_9__#r49014758#E+E*E_7_9_5#r2100147#E+E_7_45#r11101#E_52#acc第18頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月6.2屬性文法

6.2.1文法的屬性

屬性是指與文法符號(hào)的類型和值等有關(guān)的一些信息，在編譯中用屬性描述處理對(duì)象的特征。隨著編譯的進(jìn)展，對(duì)語(yǔ)法分析產(chǎn)生的語(yǔ)法樹(shù)進(jìn)行語(yǔ)義分析，且分析的結(jié)果用中間代碼描述出來(lái)。對(duì)于一棵等待翻譯的語(yǔ)法樹(shù)，它的各個(gè)結(jié)點(diǎn)都是文法中的一個(gè)符號(hào)X，該X可以是終結(jié)符或非終結(jié)符。根據(jù)語(yǔ)義處理的需要，在用規(guī)則A→αXβ進(jìn)行歸約或推導(dǎo)時(shí)，應(yīng)能準(zhǔn)確而恰當(dāng)?shù)乇磉_(dá)文法符號(hào)X在歸約或推導(dǎo)時(shí)的不同特征。第19頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

例如:

判斷變量X的類型是否匹配，要用X的數(shù)據(jù)類型來(lái)描述；判斷變量X是否存在，要用X的存儲(chǔ)位置來(lái)描述；而對(duì)X的運(yùn)算，則要用X的值來(lái)描述；

因此，語(yǔ)義分析階段引入X的屬性，如X.type、X.place、X.val等來(lái)分別描述變量X的類型、存儲(chǔ)位置以及值等不同的特征。

文法符號(hào)屬性分：繼承屬性綜合屬性第20頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

繼承屬性

用于“自上而下”傳遞信息。繼承屬性由相應(yīng)語(yǔ)法樹(shù)中結(jié)點(diǎn)的父結(jié)點(diǎn)屬性計(jì)算得到，即沿語(yǔ)法樹(shù)向下傳遞，由根結(jié)點(diǎn)到分枝(子)結(jié)點(diǎn)，它反映了對(duì)上下文依賴的特性。繼承屬性可以很方便地用來(lái)表示程序語(yǔ)言上下文的結(jié)構(gòu)關(guān)系。

綜合屬性

用于“自下而上”傳遞信息。綜合屬性由相應(yīng)語(yǔ)法分析樹(shù)中結(jié)點(diǎn)的分枝結(jié)點(diǎn)(即子結(jié)點(diǎn))屬性計(jì)算得到，其傳遞方向與繼承屬性相反，即沿語(yǔ)法分析樹(shù)向上傳遞，從分枝結(jié)點(diǎn)到根結(jié)點(diǎn)。第21頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

屬性文法是一種適用于定義語(yǔ)義的特殊文法，即在語(yǔ)言的文法中增加了屬性的文法，它將文法符號(hào)的語(yǔ)義以“屬性”的形式附加到各個(gè)文法的符號(hào)上(如上述與變量X相關(guān)聯(lián)的屬性X.type、X.place和X.val等)，再根據(jù)規(guī)則所包含的含義，給出每個(gè)文法符號(hào)屬性的求值規(guī)則，從而形成一種帶有語(yǔ)義屬性的上下文無(wú)關(guān)文法，即屬性文法。屬性文法也是一種翻譯文法，屬性有助于更詳細(xì)地指定文法中的代碼生成動(dòng)作。6.2.2屬性文法第22頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月例如，簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法如下：規(guī)則 語(yǔ)義規(guī)則(1)?S→E print(E.val)(2)?E→E(1)+T

E.val=E(1).val+T.val(3)?E→T E.val=T.val(4)?T→T(1)*FT.val=T(1).val*F.val(5)?T→T(1) T.val=T(1).val(6)?F→(E) F.val=E.val(7)?F→i F.val=i.lexval第23頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

上面的一組規(guī)則中，每一個(gè)非終結(jié)符都有一個(gè)屬性val來(lái)表示整型值，如E.val表示E的整型值，而i.lexval則表示i的整型內(nèi)部值。與規(guī)則關(guān)聯(lián)的每一個(gè)語(yǔ)義規(guī)則的左部符號(hào)E、T、F等的屬性值的計(jì)算由其各自相應(yīng)的右部符號(hào)決定，這種屬性也稱為綜合屬性。與規(guī)則S→E關(guān)聯(lián)的語(yǔ)義規(guī)則是一個(gè)函數(shù)print(E.val)，其功能是打印E規(guī)則的值。S’在語(yǔ)義規(guī)則中沒(méi)有出現(xiàn)，可以理解為其屬性是一個(gè)虛屬性。第24頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月簡(jiǎn)單變量類型說(shuō)明的文法G[D]如下：G[D]：D→intL∣floatLL→L,id∣id其對(duì)應(yīng)的屬性文法為：規(guī)則語(yǔ)義規(guī)則(1)?D→TL L.in=T.type(2)?T→int

T.type=int(3)?T→float T.type=float(4)?L→L(1)，idL(1).in=L.in;addtype(id.entry,L.in)(5)?L→id addtype(id.entry,L.in)注意到與文法G[D]相應(yīng)的說(shuō)明語(yǔ)句形式可為intid1，id2,…，idn

或者floatid1，id2,…，idn第25頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

非終結(jié)符T有一個(gè)綜合屬性type，其值為int或float。語(yǔ)義規(guī)則L.in=T.type表示L.in的屬性值由相應(yīng)說(shuō)明語(yǔ)句指定的類型T.type決定；屬性L.in被確定后將隨語(yǔ)法樹(shù)的逐步生成而傳遞到下邊的有關(guān)結(jié)點(diǎn)使用，這種結(jié)點(diǎn)屬性稱為繼承屬性。由此可見(jiàn)，標(biāo)識(shí)符的類型可以通過(guò)繼承屬性的復(fù)寫規(guī)則來(lái)傳遞。例如，對(duì)輸入串inta,b，根據(jù)上述的語(yǔ)義規(guī)則，可在其生成的語(yǔ)法樹(shù)中看到用“→”表示的屬性傳遞情況，如圖6–3所示。第26頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月圖6–3屬性信息傳遞情況示意第27頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月屬性翻譯文法（屬性文法）

如語(yǔ)法分析方法是自下而上的，在用某一規(guī)則進(jìn)行規(guī)約的同時(shí)就執(zhí)行相應(yīng)的語(yǔ)義，在分析出一個(gè)句子時(shí)，這個(gè)句子的“值”也就同時(shí)產(chǎn)生了。對(duì)于文法的每個(gè)規(guī)則都配備了一組屬性的計(jì)算規(guī)則，稱為語(yǔ)義規(guī)則。屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。第28頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月6.3幾種常見(jiàn)的中間語(yǔ)言6.3.1

抽象語(yǔ)法樹(shù)6.3.2逆波蘭表示法6.3.3三地址代碼第29頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月6.3.1抽象語(yǔ)法樹(shù)語(yǔ)法制導(dǎo)翻譯既可以基于語(yǔ)法分析樹(shù)也可以基于抽象語(yǔ)法樹(shù)進(jìn)行，采用的基本方法是一樣的。現(xiàn)在對(duì)語(yǔ)法樹(shù)進(jìn)行改造，去掉那些對(duì)翻譯不必要的信息，將語(yǔ)法樹(shù)進(jìn)行抽象---抽象語(yǔ)法樹(shù)。在表達(dá)式的抽象語(yǔ)法樹(shù)中，運(yùn)算符、關(guān)鍵字不作葉子結(jié)點(diǎn)而作為內(nèi)部結(jié)點(diǎn)，葉子結(jié)點(diǎn)只是運(yùn)算量。語(yǔ)法制導(dǎo)翻譯以語(yǔ)法樹(shù)作基礎(chǔ),實(shí)際上,語(yǔ)法樹(shù)可以作為一種合適的中間語(yǔ)言形式。抽象語(yǔ)法樹(shù)也可以屬性化，給結(jié)點(diǎn)加上屬性變成帶屬性的抽象語(yǔ)法樹(shù)。第30頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

當(dāng)把語(yǔ)法規(guī)則中本質(zhì)部分抽象出來(lái)而將非本質(zhì)部分去掉后，便得到抽象語(yǔ)法規(guī)則。這種去掉不必要信息的做法可以獲得高效的源程序中間表示。如賦值語(yǔ)句x=a?b*c的抽象語(yǔ)法樹(shù)如圖6–4(a)所示，而圖6–4(b)則是該賦值語(yǔ)句的普通語(yǔ)法樹(shù)。圖6–4x=a?b*c的語(yǔ)法樹(shù)第31頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

抽象語(yǔ)法樹(shù)的一個(gè)顯著特點(diǎn)是結(jié)構(gòu)緊湊，容易構(gòu)造且結(jié)點(diǎn)數(shù)較少。圖6–4(b)所示的普通語(yǔ)法樹(shù)的結(jié)點(diǎn)為14個(gè)；而圖6–4(a)所示的抽象語(yǔ)法樹(shù)的結(jié)點(diǎn)僅有7個(gè)，且每個(gè)內(nèi)部結(jié)點(diǎn)最多只有兩個(gè)分支，因此可以將每個(gè)賦值語(yǔ)句或表達(dá)式表示為一棵二叉樹(shù)。對(duì)于含有多元運(yùn)算的更為復(fù)雜的語(yǔ)法成分，相應(yīng)的抽象語(yǔ)法樹(shù)則為一棵多叉樹(shù)，但我們總可以將其轉(zhuǎn)變?yōu)橐豢枚鏄?shù)。第32頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月為下面文法的句子a-4+c

建立抽象語(yǔ)法樹(shù)。

EE+T|E－T|TT(E)Tid|num為每個(gè)運(yùn)算量或運(yùn)算符號(hào)都建立一個(gè)結(jié)點(diǎn)?？梢愿鶕?jù)表達(dá)式的運(yùn)算順序自下而上的構(gòu)造---手工構(gòu)造。a－+c4抽象語(yǔ)法樹(shù)運(yùn)算符作內(nèi)部結(jié)點(diǎn)id(a)EE－TE+TTnum(4)id(c)語(yǔ)法樹(shù)第33頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月抽象語(yǔ)法樹(shù)的實(shí)現(xiàn)抽象語(yǔ)法樹(shù)中的每一個(gè)結(jié)點(diǎn)可以由包含幾個(gè)域的記錄來(lái)實(shí)現(xiàn)；有向邊用指針實(shí)現(xiàn)。在一個(gè)運(yùn)算量對(duì)應(yīng)的結(jié)點(diǎn)(葉結(jié))中,一個(gè)域標(biāo)識(shí)運(yùn)算量，另一個(gè)域是該運(yùn)算量的屬性值(或指針)。在一個(gè)運(yùn)算符對(duì)應(yīng)的結(jié)點(diǎn)中,一個(gè)域標(biāo)識(shí)運(yùn)算符，其它域包含指向運(yùn)算分量的結(jié)點(diǎn)的指針。運(yùn)算符通常叫做這個(gè)結(jié)點(diǎn)的標(biāo)號(hào)。進(jìn)行翻譯時(shí)，抽象語(yǔ)法樹(shù)中的結(jié)點(diǎn)可能會(huì)用附加域來(lái)存放結(jié)點(diǎn)的屬性值(或指向?qū)傩缘闹羔槪?。numvalid.op..Toentryofid右子樹(shù)根結(jié)左子樹(shù)根結(jié)第34頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

建立表達(dá)式的抽象語(yǔ)法樹(shù)使用的函數(shù),這些函數(shù)返回新建立結(jié)點(diǎn)的指針。1.mknode(op,left,right)

建立一個(gè)運(yùn)算符結(jié)點(diǎn)，標(biāo)號(hào)是op,兩個(gè)域left和right指向左右運(yùn)算分量結(jié)點(diǎn)的指針。2.mkleaf(id,entry)

建立一個(gè)“標(biāo)識(shí)符”葉子結(jié)點(diǎn),由標(biāo)號(hào)id標(biāo)識(shí)，一個(gè)域entry指向標(biāo)識(shí)符在符號(hào)表中相應(yīng)的項(xiàng)。3.mkleaf(num,val)

建立一個(gè)“數(shù)”葉子結(jié)點(diǎn)，標(biāo)號(hào)為num，域val用于存放數(shù)的值。抽象語(yǔ)法樹(shù)的構(gòu)造函數(shù)

第35頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

調(diào)用上述函數(shù)建立表達(dá)式a-4+c

的抽象語(yǔ)法樹(shù)。建立順序自下而上是:

p1,p2,p3,p4,p5抽象語(yǔ)法樹(shù)構(gòu)造idtoentryap1num4p2

–p3idtoentrycp4

+p5第36頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

規(guī)則語(yǔ)義規(guī)則

EE1+TE.nptr:=mknode('+',E1.nptr,T.nptr)EE1-TE.nptr:=mknode('-',E1.nptr,T.nptr)ETE.nptr:=T.nptrT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val)建立抽象語(yǔ)法樹(shù)的語(yǔ)義規(guī)則屬性文法,nptr是綜合屬性第37頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月手工構(gòu)造表達(dá)式a＋b*(c-d)-e/f的抽象語(yǔ)法樹(shù)，根據(jù)表達(dá)式的運(yùn)算順序自下而上的構(gòu)造。練習(xí)

+a－–dc*b/fe第38頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

逆波蘭表示法是波蘭邏輯學(xué)家盧卡西維奇(Lukasiewicz)發(fā)明的一種表示表達(dá)式的方法，這種表示法把運(yùn)算量(操作數(shù))寫在前面，把運(yùn)算符寫在后面，因而又稱后綴表示法。例如，把a(bǔ)+b寫成ab+，把a(bǔ)*(b+c)寫成abc+*。6.3.2逆波蘭表示法第39頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

1．表達(dá)式的逆波蘭表示

表達(dá)式E的后綴表示的遞歸定義如下：

(1)如果E是變量或常數(shù)，則E的后綴表示即E自身。

(2)如果E為E1?opE2形式，則它的后綴表示為E1'E2'op；其中op是二元運(yùn)算符，而E1'、E2'分別又是E1和E2的后綴表示。若op為一元運(yùn)算符，則視E1和E1'為空。

(3)如果E為(E1)形式，則E1的后綴表示即為E的后綴表示。第40頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

上述遞歸定義的實(shí)質(zhì)是：后綴表示中，操作數(shù)出現(xiàn)的順序與原來(lái)一致，而運(yùn)算符則按運(yùn)算先后的順序放入相應(yīng)的操作數(shù)之后(即運(yùn)算符先后的順序發(fā)生了變化)。這種表示已不再需要用括號(hào)來(lái)規(guī)定運(yùn)算的順序了。第41頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月寫表達(dá)式的后綴式要點(diǎn)：1.后綴式中運(yùn)算量的順序與中綴式的相同；2.算符出現(xiàn)的次序即表達(dá)式的運(yùn)算次序；3.不使用括號(hào)。例：a+bab+a*(b+c)abc+*(a+b)*(c+d)ab+cd+*-a+b*cabc*+a/b**c-d*eabc**/de*-

(A＝0∧B≠0)A0=B0≠∧用

表示取負(fù)算符(uminus)第42頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月練習(xí)寫出下列各式的逆波蘭表示:(1)-a-(b*c/(c-d)+(-b)*a)(2)-A+B*C↑(D/E)/F(3)x:=a-b/(c+d)解：(1)abc*cd-/ba*+-(2)ABCDE/↑*F/+(3)xabcd+/-:=

用

表示取負(fù)算符(uminus):=表示賦值算符(assign)第43頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

后綴表示法表示表達(dá)式，其最大優(yōu)點(diǎn)是易于計(jì)算機(jī)處理表達(dá)式。常用的算法是使用一個(gè)棧，自左至右掃描算術(shù)表達(dá)式（后綴表示)，每掃描到運(yùn)算對(duì)象，就把它推進(jìn)棧；掃描到運(yùn)算符，若該運(yùn)算符是二目的，則對(duì)棧頂部的兩個(gè)運(yùn)算對(duì)象實(shí)施該運(yùn)算，并將運(yùn)算結(jié)果代替這兩個(gè)運(yùn)算對(duì)象而進(jìn)棧；若是一目運(yùn)算符，則對(duì)棧頂元素執(zhí)行該運(yùn)算，并以運(yùn)算結(jié)果代替該元素進(jìn)棧，最后的結(jié)果留在棧頂。例如

-B+C*D的計(jì)算過(guò)程：第44頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月-B+C*D的后綴表示為BCD*+:第45頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

把表達(dá)式翻譯為后綴式的

語(yǔ)義規(guī)則(屬性文法)

規(guī)則

語(yǔ)義規(guī)則E→E1opE2

E.code:=E1.code||E2.code||opE→(E1)E.code:=E1.codeE→idE.code:=id屬性E.code:是E的后綴式代碼屬性op:二元算符‖:后綴式的連接運(yùn)算算符第46頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

1．三地址代碼的形式三地址代碼語(yǔ)句的一般形式為

x=yopz

其中，x、y和z為變量、結(jié)果或編譯時(shí)產(chǎn)生的臨時(shí)變量；op為運(yùn)算符。

三地址代碼的每條語(yǔ)句通常包含三個(gè)地址，兩個(gè)用來(lái)存放運(yùn)算對(duì)象，一個(gè)用來(lái)存放運(yùn)算結(jié)果。6.3.3三地址代碼第47頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

在實(shí)際實(shí)現(xiàn)中，用戶定義的變量將由指向符號(hào)表中該變量項(xiàng)的指針?biāo)〈?/p>

由于三地址語(yǔ)句只含有一個(gè)運(yùn)算符，因此多個(gè)運(yùn)算符組成的表達(dá)式必須用三地址語(yǔ)句序列來(lái)表示，如表達(dá)式x+y*z的三地址代碼為：

t1=y*zt2=x+t1

其中，t1和t2是編譯時(shí)產(chǎn)生的臨時(shí)變量。第48頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月例：賦值語(yǔ)句a:=(-b)*(c+d)-(c+d)的三地址碼如下所示。t1:=minusbt2:=c+dt3:=t1*t2t4:=c+dt5:=t3-t4a:=t5第49頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

2．三地址代碼的具體實(shí)現(xiàn)三地址代碼是中間代碼的一種抽象形式。在編譯程序中，三地址代碼語(yǔ)言的具體實(shí)現(xiàn)通常有三種表示方法：四元式、三元式和間接三元式。

1)四元式四元式是具有四個(gè)域的記錄結(jié)構(gòu)，這四個(gè)域?yàn)?/p>

(op，arg1，arg2，result)

其中，op為運(yùn)算符，arg1、arg2及result為指針，它們可指向有關(guān)變量在符號(hào)表中的登記項(xiàng)或一臨時(shí)變量(也可空缺)。第50頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

常用的三地址語(yǔ)句與相應(yīng)的四元式對(duì)應(yīng)如下：

x=yopz對(duì)應(yīng)(op,y,z,x)x=?y 對(duì)應(yīng)(-,y,_,x)x=y 對(duì)應(yīng)(=,y,_,x)callP 對(duì)應(yīng)(call,_,_,P)gotoL 對(duì)應(yīng)(j,_,_,L)ifxropygotoL對(duì)應(yīng)(jrop,x,y,L)第51頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月例如，賦值語(yǔ)句a=b*(c+d)相應(yīng)的四元式代碼為：①(+,c,d,t1)②(*,b,t1,t2)③(=,t2,_,a)

約定：凡只需一個(gè)運(yùn)算量的算符一律使用arg1；如果op是一個(gè)算術(shù)或邏輯運(yùn)算符，則result總是一個(gè)新引進(jìn)的臨時(shí)變量，它用來(lái)存放運(yùn)算結(jié)果。由上例也可看出，四元式出現(xiàn)的順序與表達(dá)式計(jì)值的順序是一致的，四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的。四元式由于其表示更接近程序設(shè)計(jì)的習(xí)慣而成為一種普遍采用的中間代碼形式。第52頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

2)三元式三元式是具有三個(gè)域的記錄結(jié)構(gòu)，這三個(gè)域?yàn)?/p>

(op，arg1，arg2)

其中，op為運(yùn)算符，arg1、arg2既可指向有關(guān)名字在符號(hào)表中的登記項(xiàng)或臨時(shí)變量，也可以指向三元式表中的某一個(gè)三元式。

第53頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月例如對(duì)于表達(dá)式：A+B*(C-D)+E/(C-D)^N的三元式代碼為：

由上例可知，三元式出現(xiàn)的先后順序和表達(dá)式各部分的計(jì)值順序是一致的。第54頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

3)間接三元式在三元式代碼表的基礎(chǔ)上另設(shè)一張表，該表按運(yùn)算的次序列出相應(yīng)三元式在三元式表中的位置，這張表稱為間接碼表。三元式表只記錄不同的三元式語(yǔ)句，而間接碼表則表示由這些語(yǔ)句組成的運(yùn)算次序。例如對(duì)于表達(dá)式：A+B*(C-D)+E/(C-D)^N的三元式與間接碼表為：

每生成一條指令，先檢查已生成的間接三元式序列，若已有，不再生成，只把序號(hào)列入間接碼表中。第55頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

在三元式表示中，每個(gè)語(yǔ)句的位置同時(shí)有兩個(gè)作用：一是可作為該三元式的結(jié)果被其它三元式引用；二是三元式位置順序即為運(yùn)算順序。在代碼優(yōu)化階段，需要調(diào)整三元式的運(yùn)算順序時(shí)會(huì)遇到困難，這是因?yàn)槿街械腶rg1、arg2也可以是指向某些三元式位置的指針，當(dāng)這些三元式的位置順序發(fā)生變化時(shí)，含有指向這些三元式位置指針的相關(guān)三元式也需隨之改變指針值。因此，變動(dòng)一張三元式表是很困難的。第56頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

對(duì)四元式來(lái)說(shuō)，引用另一語(yǔ)句的結(jié)果可以通過(guò)引用該語(yǔ)句的result(通常是一個(gè)臨時(shí)變量)來(lái)實(shí)現(xiàn)，而間接三元式則通過(guò)間接碼表來(lái)描述語(yǔ)句的運(yùn)算次序。這兩種方法都不存在語(yǔ)句位置同時(shí)具有兩種功能的現(xiàn)象，代碼調(diào)整時(shí)要做的改動(dòng)只是局部的，因此，當(dāng)需要對(duì)中間代碼表進(jìn)行優(yōu)化處理時(shí)，四元式與間接三元式都比三元式方便得多。第57頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月寫中間語(yǔ)言：練習(xí)

寫出表達(dá)式：A+B*(C-D)-E/F↑G

的逆波蘭表示、三元式表示、四元式表示。解:四元式表示：①(-,C,D,T1)②(*,B,T1,T2)③(+,A,T2,T3)④(↑,F,G,T4)⑤(/,E,T4,T5)⑥(-,T3,T5,T6)解:三元式表示：①(-,C,D)②

(*,B,①)③

(+,A,②)④(↑,F,G)⑤(/,E,④)⑥(-,③,⑤)解：逆波蘭表示：ABCD-*+EFG↑/-第58頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月語(yǔ)法制導(dǎo)翻譯

翻譯的任務(wù)：首先是語(yǔ)義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼。第59頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月語(yǔ)法制導(dǎo)翻譯法的基本思想對(duì)文法中的每個(gè)規(guī)則都附加上一個(gè)語(yǔ)義動(dòng)作或語(yǔ)義子程序，在執(zhí)行語(yǔ)法分析的過(guò)程中，每當(dāng)使用一條規(guī)則進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行相應(yīng)規(guī)則的語(yǔ)義動(dòng)作，從而完成翻譯工作。第60頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月什么是語(yǔ)法制導(dǎo)翻譯法在語(yǔ)法分析過(guò)程中，隨著分析的逐步進(jìn)展，根據(jù)相應(yīng)文法的每一規(guī)則所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的方法（即隨語(yǔ)法分析的進(jìn)展，識(shí)別出一個(gè)語(yǔ)法結(jié)構(gòu)，就對(duì)它的語(yǔ)義進(jìn)行分析和翻譯）。第61頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

語(yǔ)法制導(dǎo)翻譯技術(shù)分為自底向上語(yǔ)法制導(dǎo)翻譯和自頂向下語(yǔ)法制導(dǎo)翻譯。第62頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月自底向上語(yǔ)法制導(dǎo)翻譯自底向上語(yǔ)法制導(dǎo)翻譯方法是在自下而上的語(yǔ)法分析過(guò)程中逐步實(shí)現(xiàn)語(yǔ)義規(guī)則的方法。自底向上語(yǔ)法制導(dǎo)翻譯的特點(diǎn)：（1）當(dāng)棧頂形成句柄執(zhí)行歸約時(shí)，調(diào)用相應(yīng)的語(yǔ)義動(dòng)作。（2）語(yǔ)法分析棧和語(yǔ)義分析棧同步操作。第63頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

以LR語(yǔ)法制導(dǎo)翻譯為例，說(shuō)明如何實(shí)現(xiàn)語(yǔ)法制導(dǎo)翻譯：

1、為文法G的每一個(gè)規(guī)則設(shè)計(jì)相應(yīng)的語(yǔ)義子程序。

2、構(gòu)造文法G的LR分析表。

3、將原LR語(yǔ)法分析棧擴(kuò)充，以便存放文法符號(hào)對(duì)應(yīng)的語(yǔ)義值。

4、在用某一規(guī)則進(jìn)行歸約的同時(shí)，調(diào)用相應(yīng)的語(yǔ)義子程序，完成所用規(guī)則式相應(yīng)的語(yǔ)義動(dòng)作。第64頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月中間語(yǔ)言為了使編譯程序在邏輯上更為簡(jiǎn)單明確，特別是為了使目標(biāo)代碼的優(yōu)化比較容易實(shí)現(xiàn)，許多編譯程序都采用了某種復(fù)雜性介于源程序語(yǔ)言和機(jī)器語(yǔ)言之間的中間語(yǔ)言，并且首先把源程序翻譯成這種中間語(yǔ)言程序（中間代碼）。第65頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

常見(jiàn)的中間語(yǔ)言形式逆波蘭式三元式四元式第66頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

四元式是一種比較普遍采用的中間代碼形式。四元式的四個(gè)成分是：算符OP、第一運(yùn)算量ARG1、第二運(yùn)算量ARG2以及運(yùn)算結(jié)果RESULT。其中，運(yùn)算量和運(yùn)算結(jié)果有時(shí)指用戶自定義的變量，有時(shí)指編譯程序引進(jìn)的臨時(shí)變量。第67頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月賦值語(yǔ)句A：=-B*（C+D）的四元式序列：序號(hào)OPARG1ARG2RESULT注釋（1）

B_T1T1

為臨時(shí)變量（2）+CDT2T2

為臨時(shí)變量（3）*T1T2T3T3

為臨時(shí)變量（4）：=T3_A賦值運(yùn)算

表中：“”是為了區(qū)別“-”而表示的求負(fù)運(yùn)算符。凡只需一個(gè)運(yùn)算量的算符，使用ARG1。第68頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月6.4表達(dá)式及賦值語(yǔ)句的翻譯

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

簡(jiǎn)單算術(shù)表達(dá)式是一種僅含簡(jiǎn)單變量的算術(shù)表達(dá)式；簡(jiǎn)單變量是指普通變量和常數(shù)，但不含數(shù)組元素及結(jié)構(gòu)引用等復(fù)合型數(shù)據(jù)結(jié)構(gòu)。

簡(jiǎn)單算術(shù)表達(dá)式的計(jì)值順序與四元式出現(xiàn)的順序相同，因此很容易將其翻譯成四元式形式。第69頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

實(shí)現(xiàn)簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句到四元式的翻譯一般采取下列步驟：（1）分析文法的特點(diǎn)。（2）設(shè)置一系列語(yǔ)義變量，定義語(yǔ)義過(guò)程、語(yǔ)義函數(shù)。（3）修改文法，寫出每一條規(guī)則的語(yǔ)義子程序。（4）擴(kuò)充LR分析棧，構(gòu)造LR分析表。第70頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

考慮以下文法G[A]：A→i=E?E→E+E∣E*E∣?E∣(E)∣i

為了實(shí)現(xiàn)由表達(dá)式到四元式的翻譯，需要給文法加上語(yǔ)義子程序，以便在進(jìn)行歸約的同時(shí)執(zhí)行對(duì)應(yīng)的語(yǔ)義子程序。第71頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

語(yǔ)義子程序所涉及的語(yǔ)義變量、語(yǔ)義過(guò)程及函數(shù)說(shuō)明如下：

(1)對(duì)非終結(jié)符E定義語(yǔ)義變量E.place，即用E.place表示存放E值的變量名在符號(hào)表中的入口地址或臨時(shí)變量名的整數(shù)碼。

(2)定義語(yǔ)義函數(shù)newtemp(?)，即每次調(diào)用newtemp(?)時(shí)都將回送一個(gè)代表新臨時(shí)變量的整數(shù)碼；臨時(shí)變量名按產(chǎn)生的順序可設(shè)為T1、T2、……。

(3)定義語(yǔ)義過(guò)程emit(op,arg1,arg2,result),emit的功能是產(chǎn)生一個(gè)四元式并填入四元式表中。第72頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月

(4)定義語(yǔ)義函數(shù)lookup()，其功能是檢查是否出現(xiàn)在符號(hào)表中，是則返回在符號(hào)表的入口指針，否則返回NULL。

使用上述語(yǔ)義變量、過(guò)程和函數(shù)，可寫出文法G[A]中的每一個(gè)規(guī)則的語(yǔ)義子程序。

(1)?A→i=E{p=lookup();if(p==NULL)error(?);elseemit(=,E.place,_,p);}(2)?E→E(1)+E(2){E.place=newtemp(?);emit(+,E(1).place,E(2).place,E.place);}第73頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月(3)?E→E(1)*E(2){E.place=newtemp(?);

emit(*,E(1).place,E(2).place,E.place);}(4)?E→?E(1){E.place=newtemp(?);

emit(uminus,E(1).place,_,E.place);}(5)?E→(E(1))?{E.place=E(1).place;}(6)?E→i

?{p=lookup();if(p!=NULL)E.place=p;/*另一種表示為E.place=entry(i)*/elseerror(?);}第74頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月運(yùn)算合法性檢查利用符號(hào)表保存的名字類型類型自動(dòng)轉(zhuǎn)換填加專用指令臨時(shí)變量空間的統(tǒng)計(jì)了解需求、及時(shí)釋放表達(dá)式翻譯中的其他問(wèn)題第75頁(yè)，課件共84頁(yè)，創(chuàng)作于2023年2月若考慮到變量的類型檢查和轉(zhuǎn)換，則第（3）條產(chǎn)生式及其有關(guān)語(yǔ)義描述如下：｛E．place∶=newtemp；ifE（1）．type＝intANDE（2）．type＝intthen

beginemit(*,E(1).place,E(2).place,E.place)；