1、關于語義分析和中間代碼生成第一張，PPT共八十四頁，創作于2022年6月本章在編譯程序中的地位表格管理詞法分析器語法分析器語義分析與中間代碼產生優化器目標代碼生成器源程序單詞符號語法單位中間代碼中間代碼目標代碼出錯處理第二張，PPT共八十四頁，創作于2022年6月6.1 概述 6.2 屬性文法 6.3 幾種常見的中間語言 （*四元式）6.4 表達式及賦值語句的翻譯 6.5 控制語句的翻譯 6.6 數組元素的翻譯 6.7 過程或函數調用語句的翻譯 *6.8 說明語句的翻譯內容安排第三張，PPT共八十四頁，創作于2022年6月6.1 概 述 6.1.1 語義分析的概念 一個源程序經過詞法分析、語法

2、分析之后，表明該源程序在書寫上是正確的，并且符合程序語言所規定的語法。但是語法分析并未對程序內部的邏輯含義加以分析，因此編譯程序接下來的工作是語義分析，即審查每個語法成分的靜態語義。如果靜態語義正確，則生成與該語言成分等效的中間代碼，或者直接生成目標代碼。 第四張，PPT共八十四頁，創作于2022年6月直接生成目標代碼 直接生成機器語言或匯編語言形式的目標代碼的優點是編譯時間短且無需中間代碼到目標代碼的翻譯。生成中間代碼 生成中間代碼的優點是使編譯結構在邏輯上更為簡單明確，特別是使目標代碼的優化比較容易實現。第五張，PPT共八十四頁，創作于2022年6月 語義分析時語義檢查的分類：動態語義檢查

3、 需要生成相應的目標代碼，它是在運行時進行的； 例如：除零溢出錯誤。靜態語義檢查 在編譯時完成的，它涉及以下幾個方面： (1) 類型檢查 (2) 控制流檢查 (3) 一致性檢查第六張，PPT共八十四頁，創作于2022年6月各種條件表達式的類型不是布爾類型;運算符的分量類型不相容;賦值語句左右類型不相容;形、實參類型不相容;函數說明和函數返回類型不相容;int x;float f();x = f();符合變量聲明的語法、語義符合函數聲明的語法、語義符合賦值語句的語法、不符合語義(1) 類型檢查第七張，PPT共八十四頁，創作于2022年6月 (2) 控制流檢查 用以保證控制語句有合法的轉向點。如C

4、語言中不允許goto語句轉入case語句流；break語句需尋找包含它的最小switch、while或for語句方可找到轉向點，否則出錯。 (3) 一致性檢查 如在相同作用域中標識符只能說明一次、case語句的標號不能相同、函數調用參數個數要相同等。 第八張，PPT共八十四頁，創作于2022年6月常見的語義錯誤聲明和使用相關的語義錯誤標識符沒有聲明; 重復聲明;如何檢查?每當遇到新聲明的標識符,查符號表如果當前有效的所有標識符中有相同名字的,則是重復聲明錯誤;否則生成它的屬性信息,保存到符號表中;每當遇到標識符的使用,查符號表如果沒有找到,說明該標識符沒有聲明; 否則, 得到該標識符的屬性,進

5、行進一步分析;第九張，PPT共八十四頁，創作于2022年6月 語義分析階段只產生中間代碼而不生成目標代碼的方法使編譯程序的開發變得較為容易，但語義分析不像詞法分析和語法分析那樣可以分別用正規文法和上下文無關文法描述。 由于語義是上下文有關的，因此語義的形式化描述是非常困難的，目前較為常見的是用屬性文法作為描述程序語言語義的工具，并采用語法制導翻譯的方法完成對語法成分的翻譯工作。第十張，PPT共八十四頁，創作于2022年6月 語法制導翻譯的方法就是為每個規則配上一個翻譯子程序(稱語義動作或語義子程序)，并在語法分析的同時執行這些子程序。 語義動作是為規則賦予具體意義的手段，它一方面指出了一個規則

6、所產生的符號串的意義，另一方面又按照這種意義規定了生成某種中間代碼應做哪些基本動作。 在語法分析過程中，當一個規則獲得匹配(對于自上而下分析)或用于歸約(對于自下而上分析)時，此規則相應的語義子程序就進入工作，完成既定的翻譯任務。6.1.2語法制導翻譯方法第十一張，PPT共八十四頁，創作于2022年6月 語法制導翻譯分為自下而上語法制導翻譯和自上而下語法制導翻譯，我們重點介紹自下而上語法制導翻譯。 假定有一個自下而上的LR分析器，我們可以把這個LR分析器的能力加以擴大，使它能在用某個規則進行歸約的同時調用相應的語義子程序進行有關的翻譯工作；每個規則的語義子程序執行之后，某些結果(語義信息)必須

7、作為此規則的左部符號的語義值暫時保存下來，以便以后語義子程序引用這些信息。第十二張，PPT共八十四頁，創作于2022年6月 此外，原LR分析器的分析棧也加以擴充，以便能夠存放與文法符號相對應的語義值。這樣，分析棧可以存放三類信息：分析狀態、文法符號及文法符號對應的語義值。擴充后的分析棧如圖61所示。 第十三張，PPT共八十四頁，創作于2022年6月圖61 擴充后的LR分析棧 第十四張，PPT共八十四頁，創作于2022年6月 作為一個例子，我們考慮下面的文法及語義動作所執行的程序： 規則 語義動作 (0) SE print valTOP (1) EE(1)+E(2)valTOP=valTOP+v

8、alTOP+2 (2) EE(1)*E(2)valTOP=valTOP*valTOP+2 (3) E(E(1) valTOP= valTOP+1 (4) Ei valTOP=lexval (注：lexval為i的整型 內 部值)第十五張，PPT共八十四頁，創作于2022年6月 我們擴充分析棧工作的總控程序功能，使其在完成語法分析的同時也能完成語義分析工作(這時的語法分析棧已成為語義分析棧)；即在用某一個規則進行歸約之后，調用相應的語義子程序完成與所用規則相應的語義動作，并將每次工作后的語義值保存在擴充后的“語義值”棧中。 圖62表示算術表達式79*5#的語法樹及各結點值，而表6.1則給出了根據

9、分析表用LR語法制導翻譯方法得到的該表達式的語義分析和計值過程。第十六張，PPT共八十四頁，創作于2022年6月圖62 語法制導翻譯計算表達式 79*5#的語法樹第十七張，PPT共八十四頁，創作于2022年6月表6.1 表達式79*5#的語義分析和計值過程步驟狀態棧符號棧語義棧輸入串動作10#_79*5#s3203# 7_ _9*5#r4301# E_79*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_

10、7_9_5#r2100147# E+E_7_45#r11101# E_52#acc第十八張，PPT共八十四頁，創作于2022年6月6.2 屬 性 文 法 6.2.1 文法的屬性 屬性是指與文法符號的類型和值等有關的一些信息，在編譯中用屬性描述處理對象的特征。 隨著編譯的進展，對語法分析產生的語法樹進行語義分析，且分析的結果用中間代碼描述出來。對于一棵等待翻譯的語法樹，它的各個結點都是文法中的一個符號X，該X可以是終結符或非終結符。根據語義處理的需要，在用規則AX進行歸約或推導時，應能準確而恰當地表達文法符號X在歸約或推導時的不同特征。 第十九張，PPT共八十四頁，創作于2022年6月 例如:

11、判斷變量X的類型是否匹配，要用X的數據類型來描述； 判斷變量X是否存在，要用X的存儲位置來描述； 而對X的運算，則要用X的值來描述； 因此，語義分析階段引入X的屬性，如X.type、X.place、X.val等來分別描述變量X的類型、存儲位置以及值等不同的特征。 文法符號屬性分： 繼承屬性 綜合屬性第二十張，PPT共八十四頁，創作于2022年6月 繼承屬性 用于“自上而下”傳遞信息。繼承屬性由相應語法樹中結點的父結點屬性計算得到，即沿語法樹向下傳遞，由根結點到分枝(子)結點，它反映了對上下文依賴的特性。繼承屬性可以很方便地用來表示程序語言上下文的結構關系。 綜合屬性 用于“自下而上”傳遞信息。

12、綜合屬性由相應語法分析樹中結點的分枝結點(即子結點)屬性計算得到，其傳遞方向與繼承屬性相反，即沿語法分析樹向上傳遞，從分枝結點到根結點。第二十一張，PPT共八十四頁，創作于2022年6月 屬性文法 是一種適用于定義語義的特殊文法，即在語言的文法中增加了屬性的文法，它將文法符號的語義以“屬性”的形式附加到各個文法的符號上(如上述與變量X相關聯的屬性X.type、X.place和X.val等)，再根據規則所包含的含義，給出每個文法符號屬性的求值規則，從而形成一種帶有語義屬性的上下文無關文法，即屬性文法。 屬性文法也是一種翻譯文法，屬性有助于更詳細地指定文法中的代碼生成動作。6.2.2 屬性文法第二

13、十二張，PPT共八十四頁，創作于2022年6月例如，簡單算術表達式求值的屬性文法如下： 規則 語義規則(1) SE print (E.val)(2) EE(1)+T E.val=E(1).val+T.val(3) ET E.val=T.val(4) TT(1)*F T.val=T(1).val*F.val(5) TT(1) T.val=T(1).val(6) F(E) F.val=E.val(7) Fi F.val=i.lexval第二十三張，PPT共八十四頁，創作于2022年6月 上面的一組規則中，每一個非終結符都有一個屬性val來表示整型值，如E.val表示E的整型值，而i.lexval則

14、表示i的整型內部值。與規則關聯的每一個語義規則的左部符號E、T、F等的屬性值的計算由其各自相應的右部符號決定，這種屬性也稱為綜合屬性。與規則SE關聯的語義規則是一個函數print(E.val)，其功能是打印E規則的值。S在語義規則中沒有出現，可以理解為其屬性是一個虛屬性。第二十四張，PPT共八十四頁，創作于2022年6月簡單變量類型說明的文法GD如下：GD：Dint Lfloat L LL, idid其對應的屬性文法為： 規則 語義規則(1) DTL L.in=T.type(2) Tint T.type=int(3) Tfloat T.type=float(4) LL(1)，id L(1).i

15、n=L.in; addtype(id.entry,L.in)(5) Lid addtype(id.entry,L.in)注意到與文法GD相應的說明語句形式可為int id1，id2,，idn 或者 float id1，id2,，idn第二十五張，PPT共八十四頁，創作于2022年6月 非終結符T有一個綜合屬性type，其值為int或float。語義規則L.in=T.type表示L.in的屬性值由相應說明語句指定的類型T.type決定；屬性L.in被確定后將隨語法樹的逐步生成而傳遞到下邊的有關結點使用，這種結點屬性稱為繼承屬性。由此可見，標識符的類型可以通過繼承屬性的復寫規則來傳遞。 例如，對輸

16、入串int a,b，根據上述的語義規則，可在其生成的語法樹中看到用“”表示的屬性傳遞情況，如圖63所示。 第二十六張，PPT共八十四頁，創作于2022年6月圖63 屬性信息傳遞情況示意第二十七張，PPT共八十四頁，創作于2022年6月屬性翻譯文法（屬性文法） 如語法分析方法是自下而上的，在用某一規則進行規約的同時就執行相應的語義，在分析出一個句子時，這個句子的“值”也就同時產生了。對于文法的每個規則都配備了一組屬性的計算規則，稱為語義規則。屬性與變量一樣，可以進行計算和傳遞。屬性加工的過程即是語義處理的過程。第二十八張，PPT共八十四頁，創作于2022年6月6.3 幾種常見的中間語言6.3.1

17、 抽象語法樹6.3.2 逆波蘭表示法6.3.3 三地址代碼第二十九張，PPT共八十四頁，創作于2022年6月6.3.1 抽象語法樹語法制導翻譯既可以基于語法分析樹也可以基于抽象語法樹進行，采用的基本方法是一樣的。現在對語法樹進行改造，去掉那些對翻譯不必要的信息，將語法樹進行抽象 - 抽象語法樹。在表達式的抽象語法樹中，運算符、關鍵字不作葉子結點而作為內部結點，葉子結點只是運算量。語法制導翻譯以語法樹作基礎, 實際上, 語法樹可以作為一種合適的中間語言形式。抽象語法樹也可以屬性化，給結點加上屬性變成帶屬性的抽象語法樹。第三十張，PPT共八十四頁，創作于2022年6月 當把語法規則中本質部分抽象出

18、來而將非本質部分去掉后，便得到抽象語法規則。這種去掉不必要信息的做法可以獲得高效的源程序中間表示。 如賦值語句x=ab*c的抽象語法樹如圖64(a)所示，而圖64(b)則是該賦值語句的普通語法樹。圖64 x=ab*c的語法樹 第三十一張，PPT共八十四頁，創作于2022年6月 抽象語法樹的一個顯著特點是結構緊湊，容易構造且結點數較少。 圖64(b)所示的普通語法樹的結點為14個；而圖64(a)所示的抽象語法樹的結點僅有7個，且每個內部結點最多只有兩個分支，因此可以將每個賦值語句或表達式表示為一棵二叉樹。 對于含有多元運算的更為復雜的語法成分，相應的抽象語法樹則為一棵多叉樹，但我們總可以將其轉變

19、為一棵二叉樹。第三十二張，PPT共八十四頁，創作于2022年6月為下面文法的句子 a-4+c 建立抽象語法樹。 E E+T | ET | T T (E) T id | num為每個運算量或運算符號都建立一個結點。可以根據表達式的運算順序自下而上的構造 - 手工構造。a+c4抽象語法樹運算符作內部結點id(a)E E TE + TTnum(4)id(c )語法樹第三十三張，PPT共八十四頁，創作于2022年6月抽象語法樹的實現抽象語法樹中的每一個結點可以由包含幾個域的記錄來實現；有向邊用指針實現。在一個運算量對應的結點(葉結)中,一個域標識運算量，另一個域是該運算量的屬性值(或指針)。在一個運算

20、符對應的結點中,一個域標識運算符，其它域包含指向運算分量的結點的指針。運算符通常叫做這個結點的標號。進行翻譯時，抽象語法樹中的結點可能會用附加域來存放結點的屬性值(或指向屬性的指針）。numvalid .op . .To entry of id右子樹根結左子樹根結第三十四張，PPT共八十四頁，創作于2022年6月 建立表達式的抽象語法樹使用的函數, 這些函數返回新建立結點的指針。1.mknode(op, left, right) 建立一個運算符結點，標號是 op, 兩個域 left 和 right 指向左右運算分量結點的指針。 2.mkleaf(id,entry) 建立一個“標識符”葉子結點,

21、 由標號 id 標識，一個域 entry 指向標識符在符號表中相應的項。 3.mkleaf(num, val) 建立一個“數”葉子結點，標號為 num ，域 val 用于存放數的值。 抽象語法樹的構造函數 第三十五張，PPT共八十四頁，創作于2022年6月 調用上述函數建立表達式 a-4+c 的抽象語法樹。建立順序自下而上是: p1, p2, p3, p4, p5抽象語法樹構造idto entry ap1num 4p2 p3 idto entry cp4 +p5第三十六張，PPT共八十四頁，創作于2022年6月 規則 語義規則 EE1+T E.nptr:=mknode(+,E1.nptr,T.

22、nptr) E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr) E T E.nptr:=T.nptr T (E) T.nptr:=E.nptr T id T.nptr:=mkleaf(id,id.entry) T num T.nptr:=mkleaf(num,num.val)建立抽象語法樹的語義規則屬性文法, nptr是綜合屬性第三十七張，PPT共八十四頁，創作于2022年6月手工構造表達式 ab*(c-d)-e/f 的抽象語法樹 ，根據表達式的運算順序自下而上的構造。 練習 +adc*b/fe第三十八張，PPT共八十四頁，創作于2022年6月 逆波蘭表示法是波蘭邏

23、輯學家盧卡西維奇(Lukasiewicz)發明的一種表示表達式的方法，這種表示法把運算量(操作數)寫在前面，把運算符寫在后面，因而又稱后綴表示法。 例如，把a+b寫成ab+，把a*(b+c)寫成abc+*。6.3.2逆波蘭表示法第三十九張，PPT共八十四頁，創作于2022年6月 1表達式的逆波蘭表示 表達式E的后綴表示的遞歸定義如下： (1) 如果E是變量或常數，則E的后綴表示即E自身。 (2) 如果E為E1 op E2形式，則它的后綴表示為 E1E2op；其中op是二元運算符，而E1、E2分別又是E1和E2的后綴表示。若op為一元運算符，則視E1和E1為空。 (3) 如果E為(E1)形式，則

24、E1的后綴表示即為E的后綴表示。第四十張，PPT共八十四頁，創作于2022年6月 上述遞歸定義的實質是：后綴表示中，操作數出現的順序與原來一致，而運算符則按運算先后的順序放入相應的操作數之后(即運算符先后的順序發生了變化)。這種表示已不再需要用括號來規定運算的順序了。第四十一張，PPT共八十四頁，創作于2022年6月寫表達式的后綴式要點：1.后綴式中運算量的順序與中綴式的相同；2.算符出現的次序即表達式的運算次序；3.不使用括號。例：a+b ab+ a*(b+c) abc+* (a+b)*(c+d) ab+cd+* -a+b*c abc*+ a/b*c-d*e abc*/de*- (A0B0)

25、 A0=B0用 表示取負算符(uminus)第四十二張，PPT共八十四頁，創作于2022年6月練習寫出下列各式的逆波蘭表示: (1) -a-(b*c/(c-d) + (-b)*a) (2) -A+B*C (D/E)/F (3) x := a-b/(c+d) 解： (1) a bc*cd-/b a*+ - (2) A BCDE/*F/+ (3) x a b c d + / - := 用 表示取負算符(uminus) := 表示賦值算符(assign)第四十三張，PPT共八十四頁，創作于2022年6月 后綴表示法表示表達式，其最大優點是易于計算機處理表達式。常用的算法是使用一個棧，自左至右掃描算術

26、表達式（后綴表示)，每掃描到運算對象，就把它推進棧；掃描到運算符，若該運算符是二目的，則對棧頂部的兩個運算對象實施該運算，并將運算結果代替這兩個運算對象而進棧；若是一目運算符，則對棧頂元素執行該運算，并以運算結果代替該元素進棧，最后的結果留在棧頂。 例如 -B+C*D的計算過程：第四十四張，PPT共八十四頁，創作于2022年6月 -B+C*D的后綴表示為B CD*+:第四十五張，PPT共八十四頁，創作于2022年6月 把表達式翻譯為后綴式的語義規則(屬性文法) 規則 語義規則 EE1 op E2 E.code:=E1.code | E2 .code | op E(E1) E.code:=E1.

27、code Eid E.code:=id屬性E.code: 是E的后綴式代碼屬性op: 二元算符: 后綴式的連接運算算符第四十六張，PPT共八十四頁，創作于2022年6月 1三地址代碼的形式 三地址代碼語句的一般形式為 x=y op z 其中，x、y和z為變量、結果或編譯時產生的臨時變量；op為運算符。 三地址代碼的每條語句通常包含三個地址，兩個用來存放運算對象，一個用來存放運算結果。 6.3.3 三地址代碼第四十七張，PPT共八十四頁，創作于2022年6月 在實際實現中，用戶定義的變量將由指向符號表中該變量項的指針所取代。 由于三地址語句只含有一個運算符，因此多個運算符組成的表達式必須用三地址

28、語句序列來表示， 如表達式x+y*z的三地址代碼為： t1=y*z t2= x+t1 其中，t1和t2是編譯時產生的臨時變量。第四十八張，PPT共八十四頁，創作于2022年6月例：賦值語句a:=(-b)*(c+d)-(c+d)的三地址碼如下所示 。t1 := minus bt2 := c+dt3 := t1*t2t4 := c+dt5 := t3-t4a := t5第四十九張，PPT共八十四頁，創作于2022年6月 2三地址代碼的具體實現 三地址代碼是中間代碼的一種抽象形式。在編譯程序中，三地址代碼語言的具體實現通常有三種表示方法：四元式、三元式和間接三元式。 1) 四元式 四元式是具有四個域

29、的記錄結構，這四個域為 (op，arg1，arg2，result) 其中，op為運算符，arg1、arg2及result為指針，它們可指向有關變量在符號表中的登記項或一臨時變量(也可空缺)。第五十張，PPT共八十四頁，創作于2022年6月 常用的三地址語句與相應的四元式對應如下： x=y op z 對應(op, y, z, x) x=y 對應(-, y, _, x) x=y 對應(=, y, _, x) call P 對應(call, _, _, P) goto L 對應(j, _, _, L) if x rop y goto L 對應(jrop, x, y, L)第五十一張，PPT共八十四頁

30、，創作于2022年6月例如，賦值語句a=b*(c+d)相應的四元式代碼為： (+,c,d,t1) (*,b,t1,t2) (=,t2,_,a) 約定：凡只需一個運算量的算符一律使用arg1；如果op是一個算術或邏輯運算符，則result總是一個新引進的臨時變量，它用來存放運算結果。由上例也可看出，四元式出現的順序與表達式計值的順序是一致的，四元式之間的聯系是通過臨時變量實現的。四元式由于其表示更接近程序設計的習慣而成為一種普遍采用的中間代碼形式。第五十二張，PPT共八十四頁，創作于2022年6月 2) 三元式 三元式是具有三個域的記錄結構，這三個域為 (op，arg1，arg2) 其中，op為

31、運算符，arg1、arg2既可指向有關名字在符號表中的登記項或臨時變量，也可以指向三元式表中的某一個三元式。 第五十三張，PPT共八十四頁，創作于2022年6月例如對于表達式：A+B*(C-D)+E/(C-D)N的三元式代碼為： 由上例可知，三元式出現的先后順序和表達式各部分的計值順序是一致的。第五十四張，PPT共八十四頁，創作于2022年6月 3) 間接三元式 在三元式代碼表的基礎上另設一張表，該表按運算的次序列出相應三元式在三元式表中的位置，這張表稱為間接碼表。三元式表只記錄不同的三元式語句，而間接碼表則表示由這些語句組成的運算次序。 例如對于表達式：A+B*(C-D)+E/(C-D)N的

32、三元式與間接碼表為： 每生成一條指令，先檢查已生成的間接三元式序列，若已有，不再生成，只把序號列入間接碼表中。第五十五張，PPT共八十四頁，創作于2022年6月 在三元式表示中，每個語句的位置同時有兩個作用：一是可作為該三元式的結果被其它三元式引用；二是三元式位置順序即為運算順序。在代碼優化階段，需要調整三元式的運算順序時會遇到困難，這是因為三元式中的arg1、arg2也可以是指向某些三元式位置的指針，當這些三元式的位置順序發生變化時，含有指向這些三元式位置指針的相關三元式也需隨之改變指針值。因此，變動一張三元式表是很困難的。第五十六張，PPT共八十四頁，創作于2022年6月 對四元式來說，引

33、用另一語句的結果可以通過引用該語句的result(通常是一個臨時變量)來實現，而間接三元式則通過間接碼表來描述語句的運算次序。這兩種方法都不存在語句位置同時具有兩種功能的現象，代碼調整時要做的改動只是局部的，因此，當需要對中間代碼表進行優化處理時，四元式與間接三元式都比三元式方便得多。第五十七張，PPT共八十四頁，創作于2022年6月寫中間語言：練習 寫出表達式：A+B*(C-D)-E/FG 的逆波蘭表示、三元式表示、四元式表示。解: 四元式表示：( - , C , D , T1 ) (* , B , T1, T2 ) ( + , A , T2, T3 ) ( ,F , G , T4 ) (

34、/ , E, T4, T5 ) ( - , T3, T5, T6 )解: 三元式表示：( - , C , D )(* , B , )( + , A , ) ( ,F , G ) ( / , E, ) ( - , , )解：逆波蘭表示： ABCD -*+EFG/ -第五十八張，PPT共八十四頁，創作于2022年6月語法制導翻譯 翻譯的任務：首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標代碼。第五十九張，PPT共八十四頁，創作于2022年6月語法制導翻譯法的基本思想 對文法中的每個規則都附加上一個語義動作或語義子程序，在執行語法分析的過程中，每當使用一條規則進行推導或歸約時，就執行相應

35、規則的語義動作，從而完成翻譯工作。第六十張，PPT共八十四頁，創作于2022年6月什么是語法制導翻譯法 在語法分析過程中，隨著分析的逐步進展，根據相應文法的每一規則所對應的語義子程序進行翻譯的方法（即隨語法分析的進展，識別出一個語法結構，就對它的語義進行分析和翻譯）。第六十一張，PPT共八十四頁，創作于2022年6月 語法制導翻譯技術分為自底向上語法制導翻譯和自頂向下語法制導翻譯。第六十二張，PPT共八十四頁，創作于2022年6月自底向上語法制導翻譯 自底向上語法制導翻譯方法是在自下而上的語法分析過程中逐步實現語義規則的方法。自底向上語法制導翻譯的特點： （1）當棧頂形成句柄執行歸約時，調用相

36、應的語義動作。 （2）語法分析棧和語義分析棧同步操作。第六十三張，PPT共八十四頁，創作于2022年6月 以LR語法制導翻譯為例，說明如何實現語法制導翻譯： 1、為文法G的每一個規則設計相應的語義子程序。 2、構造文法G的LR分析表。 3、將原LR語法分析棧擴充，以便存放文法符號對應的語義值。 4、在用某一規則進行歸約的同時，調用相應的語義子程序，完成所用規則式相應的語義動作。第六十四張，PPT共八十四頁，創作于2022年6月中間語言 為了使編譯程序在邏輯上更為簡單明確，特別是為了使目標代碼的優化比較容易實現，許多編譯程序都采用了某種復雜性介于源程序語言和機器語言之間的中間語言，并且首先把源程

37、序翻譯成這種中間語言程序（中間代碼）。第六十五張，PPT共八十四頁，創作于2022年6月 常見的中間語言形式 逆波蘭式 三元式 四元式第六十六張，PPT共八十四頁，創作于2022年6月 四元式是一種比較普遍采用的中間代碼形式。 四元式的四個成分是：算符OP、第一運算量ARG1、第二運算量ARG2以及運算結果RESULT。其中，運算量和運算結果有時指用戶自定義的變量，有時指編譯程序引進的臨時變量。第六十七張，PPT共八十四頁，創作于2022年6月賦值語句 A：=-B*（C+D）的四元式序列：序號 OP ARG1 ARG2 RESULT 注釋（1） B _ T1 T1 為臨時變量（2） + C D

38、 T2 T2 為臨時變量（3） * T1 T2 T3 T3 為臨時變量（4） ：= T3 _ A 賦值運算 表中：“”是為了區別“-”而表示的求負運算符。 凡只需一個運算量的算符，使用ARG1。第六十八張，PPT共八十四頁，創作于2022年6月6.4 表達式及賦值語句的翻譯 6.4.1 簡單算術表達式和賦值語句的翻譯 簡單算術表達式是一種僅含簡單變量的算術表達式；簡單變量是指普通變量和常數，但不含數組元素及結構引用等復合型數據結構。 簡單算術表達式的計值順序與四元式出現的順序相同，因此很容易將其翻譯成四元式形式。第六十九張，PPT共八十四頁，創作于2022年6月 實現簡單算術表達式和賦值語句到

39、四元式的翻譯一般采取下列步驟： （1）分析文法的特點。 （2）設置一系列語義變量，定義語義過程、語義函數。 （3）修改文法，寫出每一條規則的語義子程序。 （4）擴充LR分析棧，構造LR分析表。第七十張，PPT共八十四頁，創作于2022年6月 考慮以下文法GA：Ai=E EE+EE*EE(E)i 為了實現由表達式到四元式的翻譯，需要給文法加上語義子程序，以便在進行歸約的同時執行對應的語義子程序。第七十一張，PPT共八十四頁，創作于2022年6月 語義子程序所涉及的語義變量、語義過程及函數說明如下： (1) 對非終結符E定義語義變量E.place，即用E.place表示存放E值的變量名在符號表中的

40、入口地址或臨時變量名的整數碼。 (2) 定義語義函數newtemp()，即每次調用newtemp()時都將回送一個代表新臨時變量的整數碼；臨時變量名按產生的順序可設為T1、T2、。 (3) 定義語義過程emit(op,arg1,arg2,result), emit的功能是產生一個四元式并填入四元式表中。第七十二張，PPT共八十四頁，創作于2022年6月 (4) 定義語義函數lookup()，其功能是檢查是否出現在符號表中，是則返回在符號表的入口指針，否則返回NULL。 使用上述語義變量、過程和函數，可寫出文法GA中的每一個規則的語義子程序。 (1) Ai=E

41、 p=lookup(); if(p=NULL) error(); else emit(=,E.place,_,p); (2) EE(1)+E(2) E.place=newtemp(); emit(+,E(1).place,E(2).place,E.place); 第七十三張，PPT共八十四頁，創作于2022年6月(3) EE(1)*E(2) E.place=newtemp(); emit(*,E(1).place,E(2).place,E.place);(4) EE(1) E.place=newtemp(); emit(uminus,E(1) .place,_,E.place);(

42、5) E(E(1) E.place= E(1) .place ;(6) Ei p=lookup(); if(p!=NULL) E.place=p; /*另一種表示為E.place=entry(i)*/ else error();第七十四張，PPT共八十四頁，創作于2022年6月運算合法性檢查利用符號表保存的名字類型類型自動轉換填加專用指令臨時變量空間的統計了解需求、及時釋放表達式翻譯中的其他問題第七十五張，PPT共八十四頁，創作于2022年6月若考慮到變量的類型檢查和轉換，則第（3）條產生式及其有關語義描述如下：Eplace=newtemp；if E（1）typeint AND E（2）typein