編譯原理(4)語義_4(數組元素、過程、說明語句的翻譯)

1、第第 1 12 2 講講西北農林科技大學本科教程西北農林科技大學本科教程 主講教師：趙建邦主講教師：趙建邦 第四章第四章 語義分析和中間代碼生成語義分析和中間代碼生成l4.1 4.1 語義分析概述語義分析概述l4.2 4.2 屬性文法屬性文法l4.3 4.3 幾種常見的中間語言幾種常見的中間語言l4.4 4.4 表達式及賦值語句的翻譯表達式及賦值語句的翻譯l4.5 4.5 控制語句的翻譯控制語句的翻譯l4.6 4.6 數組元素的翻譯數組元素的翻譯l4.7 4.7 過程或函數調用語句的翻譯過程或函數調用語句的翻譯l4.8 4.8 說明語句的翻譯說明語句的翻譯l4.9 4.9 遞歸下降語法制導翻譯

2、方法簡介遞歸下降語法制導翻譯方法簡介u第四章第四章語義分析和中間代碼生成語義分析和中間代碼生成l4.6 4.6 數組元素的翻譯數組元素的翻譯l4.7 4.7 過程或函數調用語句的翻譯過程或函數調用語句的翻譯l4.8 4.8 說明語句的翻譯說明語句的翻譯u重點掌握重點掌握l二維數組賦值語句的翻譯二維數組賦值語句的翻譯本講目標本講目標 4.6 4.6 數組元素的翻譯數組元素的翻譯u關于數組關于數組l數組是用來存儲一批同類型數據的數據結構，數組中的每一數組是用來存儲一批同類型數據的數據結構，數組中的每一個元素具有同樣長度的存儲空間。個元素具有同樣長度的存儲空間。l如果在編譯時就知道一個數組存儲空間的

3、大小，則稱其為如果在編譯時就知道一個數組存儲空間的大小，則稱其為靜靜態(tài)數組態(tài)數組，否則為，否則為動態(tài)數組動態(tài)數組。 例：例： int a34; a21 = 5; void *malloc(unsigned int size); void *calloc(unsigned int num, unsigned int size);l我們主要討論我們主要討論靜態(tài)數組元素靜態(tài)數組元素的引用如何翻譯。關鍵問題：的引用如何翻譯。關鍵問題：l1.1.數組元素的地址計算方法數組元素的地址計算方法l2.2.數組元素的表示數組元素的表示4.6 4.6 數組元素的翻譯數組元素的翻譯u4.6.1 數組元素的地址計算及

4、中間代碼形式數組元素的地址計算及中間代碼形式l數組元素的地址計算數組元素的地址計算 數組元素的存放方式決定了數組元素的地址計算方法，地址數組元素的存放方式決定了數組元素的地址計算方法，地址計算方法決定了數組元素四元式的產生形式。計算方法決定了數組元素四元式的產生形式。 數組元素的存放方式：數組元素的存放方式：按行存放按行存放和和按列存放按列存放。l我們主要討論按行存放的數組元素地址計算方法。我們主要討論按行存放的數組元素地址計算方法。123456789A=A=1234567891472583694.6 4.6 數組元素的翻譯數組元素的翻譯1(a)234i1A:l1u1關鍵問題：關鍵問題：的地址

5、是什么？的地址是什么？4.6 4.6 數組元素的翻譯數組元素的翻譯123456789101112A=A=A3,3的地址：的地址： 1 + (3 - 1) * 4 + ( 3 - 1) = 114.6 4.6 數組元素的翻譯數組元素的翻譯4.6 4.6 數組元素的翻譯數組元素的翻譯4.6 4.6 數組元素的翻譯數組元素的翻譯l實現數組元素的地址計算時，將產生兩組四元式序列：實現數組元素的地址計算時，將產生兩組四元式序列： 一組計算一組計算CONSPART，其值存放在臨時變量，其值存放在臨時變量T中；中； 另一組計算另一組計算VARPART，其值存放在臨時變量，其值存放在臨時變量T1中；中；l關鍵

6、問題關鍵問題2：數組元素的表示：數組元素的表示 用用T T1(“基址基址”+“變址變址”)表示數組元素的地址。表示數組元素的地址。l對數組元素的賦值和引用就有如下兩種不同的四元式：對數組元素的賦值和引用就有如下兩種不同的四元式：(1) 變址存數變址存數：若有：若有T T1 =X，則可以用四元式，則可以用四元式 (=，X，_， TT1)表示。表示。(2) 變址取數變址取數：若有：若有X= T T1 ，則可用四元式，則可用四元式 (=， TT1 ，_，X)表示。表示。4.6 4.6 數組元素的翻譯數組元素的翻譯u4.6.2 賦值語句中數組元素的翻譯賦值語句中數組元素的翻譯l為了便于語法制導翻譯，我

7、們定義一個含有數組元素的賦值為了便于語法制導翻譯，我們定義一個含有數組元素的賦值語句文法語句文法GA如下：如下： GA: (1) AV=E(2) Vielist | i(3) elistelist,E | E(4) EE+E | (E) | V思考當前文法所能表達的語言？思考當前文法所能表達的語言？其中，其中，A代表賦值語句；代表賦值語句；V代表變量名；代表變量名；E代表算術表達式；代表算術表達式；elist代表由逗號分隔的表達式，它表示數組的一個下標；代表由逗號分隔的表達式，它表示數組的一個下標；i代表簡單變量名或數組名代表簡單變量名或數組名。4.6 4.6 數組元素的翻譯數組元素的翻譯u4

8、.6.2 賦值語句中數組元素的翻譯賦值語句中數組元素的翻譯l在用產生式在用產生式(2)、(3)進行歸約時，為了能夠及時計算數組元素進行歸約時，為了能夠及時計算數組元素的的VARPART，我們將產生式，我們將產生式(2)、(3)改寫為：改寫為：(2) Vielist | i(3) elistelist,E | E(2) Velist | i(3) elistelist,E | iE則數組元素賦值語句文法變?yōu)椋簞t數組元素賦值語句文法變?yōu)椋?GA: (1) AV=E(2) Velist | i (3) elistelist,E | iE(4) EE+E | (E) | V4.6 4.6 數組元素的翻

9、譯數組元素的翻譯l關鍵非終結符之：關鍵非終結符之：使用使用GA規(guī)約如下句子：規(guī)約如下句子： x = A， A，=x可見，有可能是簡單變量規(guī)約得到，也可能是數組元素規(guī)可見，有可能是簡單變量規(guī)約得到，也可能是數組元素規(guī)約得到。因此，為設置兩個語義值：約得到。因此，為設置兩個語義值：.place和和V.offset。 GA: (1) AV=E(2) Velist | i (3) elistelist,E | iE(4) EE+E | (E) | V4.6 4.6 數組元素的翻譯數組元素的翻譯l關鍵非終結符之：關鍵非終結符之： 如果如果V是一個簡單變量名是一個簡單變量名，V.place保存該變量的入口

10、地址，保存該變量的入口地址，V.offset = null; 如果如果V是一個數組元素是一個數組元素，V.place保存該數組元素的保存該數組元素的CONSPART，V.offset 保存保存VARPART;4.6 4.6 數組元素的翻譯數組元素的翻譯l關鍵非終結符之關鍵非終結符之2：elist對于類似于如下形式的句子：對于類似于如下形式的句子： AE，E，E，E=x最終規(guī)約為最終規(guī)約為elist = x，繼而，繼而 V= x ； 可見，可見，elist負責規(guī)約數組元素中除了負責規(guī)約數組元素中除了之外的部分。對之外的部分。對elist設置設置三個屬性：三個屬性：elist.ARRAY，elis

11、t.DIM，elist.place。 GA: (1) AV=E(2) Velist | i (3) elistelist,E | iE(4) EE+E | (E) | V4.6 4.6 數組元素的翻譯數組元素的翻譯l非終結符之非終結符之2：elist(1)elist.ARRAY：表示數組名在符號表中的入口。例如：數組：表示數組名在符號表中的入口。例如：數組元素元素A3,4,6,3,2在規(guī)約過程中，所有在規(guī)約過程中，所有elist.ARRAY的值是；的值是；(2)elist.DIM：數組維數的計數器。例如：數組維數的計數器。例如： A3,4,6,3,2 規(guī)約為規(guī)約為 elist,4,6,3,2，

12、elist.DIM = 1； elist,4,6,3,2 規(guī)約為規(guī)約為 elist,6,3,2，elist.DIM = 2； 最終規(guī)約為最終規(guī)約為elist，則，則elist=5; (3)elist.place：登錄已生成：登錄已生成VARPART中間結果的單元名字在中間結果的單元名字在符號表中的存放位置，或是一個臨時變量的整數碼。因此，符號表中的存放位置，或是一個臨時變量的整數碼。因此，在逐次對在逐次對elist歸約的過程中，將逐步產生計算歸約的過程中，將逐步產生計算VARPART的四的四元式元式VARPART=(i1d2 + i2)d3 + i3)d4 + )+ in1)dn + in4.

13、6 4.6 數組元素的翻譯數組元素的翻譯(1) AV=E if(V.offset=null) emit(=,E.place,_,V.place); /*V是簡單變量是簡單變量*/ else emit(=,E.place,_,V.placeV.offset); /*V是下標變量是下標變量*/ 含有數組元素含有數組元素的賦值語句對應的文法的賦值語句對應的文法GAGA及相應的語義子程序及相應的語義子程序如下如下( (省略語義檢查，僅給出主要語義動作省略語義檢查，僅給出主要語義動作) )：CONSPARTVARPARTu4.6.2 賦值語句中數組元素的翻譯賦值語句中數組元素的翻譯(語義子程序語義子程序

14、)(2) EE(1) +E(2) T=newtemp; emit(+,E(1).place, E(2).place,T); E.place=T;(3) E(E(1) ) E.place= E(1).place;4.6 4.6 數組元素的翻譯數組元素的翻譯(4) EV if (V.offset=null) E.place=V.place; /*V是簡單變量是簡單變量*/ else T=newtemp; /*V是下標變量是下標變量*/ emit(= ,V.placeV.offset,_,T); E.place=T; 將數組元素的值賦給T4.6 4.6 數組元素的翻譯數組元素的翻譯(5) Velis

15、t T=newtemp; emit(，elist.ARRAY,C,T); V.place=T; V.offset=elist.place;/*假定通過數組名的符號表入口不僅能獲得地址假定通過數組名的符號表入口不僅能獲得地址a而且也能得而且也能得到常數到常數C(CONSPART=a-C) */(6) Vi V.place=entry(i); V.offset=null;(8) elistiE elist.place=E.place; elist.DIM:=1; elist.ARRAY=entry(i);(7) elistelist(1),E T=newtemp; k=elist(1).DIM+1

16、; dk=limit(elist(1).ARRAY,k); emit(*,elist(1).place,dk ,T); emit(+,E.place,T,T); elist.ARRAY=elist(1).ARRAY; elist.place=T; elist.DIM=k;VARPART=(i1d2 + i2)d3 + i3)d4 + + in1dn)+in4.6 4.6 數組元素的翻譯數組元素的翻譯其它函數：其它函數： limit(ARRAY,k)計算數組計算數組ARRAY的第的第k維長度維長度dk4.6 4.6 數組元素的翻譯數組元素的翻譯4.6 4.6 數組元素的翻譯數組元素的翻譯例例4.

17、10 已知已知A是一個是一個10 20的數組的數組(每維下界均為每維下界均為1)且按行存且按行存放，求：放，求：(1) 賦值語句賦值語句X = AI,J的四元式序列；的四元式序列； (2) 賦值語句賦值語句AI + 2，J + 1 = M + N的四元式序列的四元式序列要求給出語法制導翻譯過程。要求給出語法制導翻譯過程。解答解答 由于由于A是是10 20的數組，故的數組，故: d1 = 10，d2 = 20，C = l1 d2 + l2 = 21。(1) 根據文法根據文法GA及對應的語義加工子程序，賦值語句及對應的語義加工子程序，賦值語句X=AI, J的語法制導翻譯過程如圖的語法制導翻譯過程如

18、圖4-17所示。所示。104(=, T3, _, X)4.6 4.6 數組元素的翻譯數組元素的翻譯例例4.10 已知已知A是一個是一個10 20的數組的數組(每維下界均為每維下界均為1)且按行存且按行存放，求：放，求：(1) 賦值語句賦值語句X = AI,J的四元式序列的四元式序列: 100(*, I, 20, T1) /*d2=20*/101(+, J, T1, T1) /*得到得到20I+J*/102(, A, 21, T2) /*得到得到A21*/103(= ,T2T1,_,T3) /*T2T1即為即為AI,J，即，即 T3=T21*/105(+，M，N，T5)4.6 4.6 數組元素的

19、翻譯數組元素的翻譯例例4.9 已知已知A是一個是一個10 20的數組的數組(每維下界均為每維下界均為1)且按行存放，且按行存放，求：求：(2) 賦值語句賦值語句AI + 2，J + 1 = M + N的四元式序列的四元式序列:100(+，I，2，T1)101(+，J，1，T2)102(*，T1，20，T3)103(+，T2，T3，T3)104(，A，21，T4)106( =，T5，_，T4T3) /*T4T3 = T5*/4.6 4.6 數組元素的翻譯數組元素的翻譯例例.設設A為一個為一個10*20的數組，即的數組，即n1=10,n2=20,并設并設w=4.對賦值語對賦值語句句x:=A y ,

20、 z翻譯成四元式。翻譯成四元式。 注意：數組下界為注意：數組下界為1應該生成的三地址序列為：應該生成的三地址序列為：T1:=y*20T1:=T1+zT2:=4*T1T3:=A-84T4=T3T2x:=T4C=( (l1*n2)+l2)*w4.6 4.6 數組元素的翻譯數組元素的翻譯VAR=( (i1*n2)+i2)*w4.7 4.7 過程或函數調用語句的翻譯過程或函數調用語句的翻譯u4.7.1 過程調用過程調用l1.定義和調用過程定義和調用過程(函數、方法等函數、方法等)是程序語言的主要特征之一。是程序語言的主要特征之一。主要功能有：主要功能有： (1) 是模塊化程序設計的主要手段；是模塊化程

21、序設計的主要手段； (2) 節(jié)省程序代碼；節(jié)省程序代碼； (3) 擴充語言能力。擴充語言能力。l2.過程調用：實質是把程序控制轉到子程序。過程調用：實質是把程序控制轉到子程序。l3.過程調用中遇到的主要問題：過程調用中遇到的主要問題： (1) 如何進行參數傳遞；如何進行參數傳遞； (2) 子程序執(zhí)行完之后如何回到主調程序；子程序執(zhí)行完之后如何回到主調程序； (3) 子程序回到主調程序時，運行環(huán)境的恢復。子程序回到主調程序時，運行環(huán)境的恢復。4.7 4.7 過程或函數調用語句的翻譯過程或函數調用語句的翻譯l在編譯階段對過程調用語句的翻譯，所做的工作主要是在編譯階段對過程調用語句的翻譯，所做的工作

22、主要是參數參數傳遞傳遞。l1.參數：參數： (1) 實在參數：來自于主調過程實在參數：來自于主調過程 (2) 形式參數：存在于被調過程形式參數：存在于被調過程l2.傳遞方式：傳遞方式： (1) 傳地址傳地址(call by reference)：把實參的地址傳給形參；：把實參的地址傳給形參； (2) 傳值傳值(call by value)：把實參值的拷貝傳給形參。：把實參值的拷貝傳給形參。4.7 4.7 過程或函數調用語句的翻譯過程或函數調用語句的翻譯l如何傳遞實參地址？如何傳遞實參地址？ (1) 如果實參是一個變量（包括下標變量），則直接傳遞該變如果實參是一個變量（包括下標變量），則直接傳遞

23、該變量的地址；量的地址； (2) 如果實參是一個常量或表達式如果實參是一個常量或表達式(如：如：2或者或者X+2)，現將它的，現將它的值計算出來并存放在臨時變量值計算出來并存放在臨時變量T中，然后傳遞中，然后傳遞T的地址。的地址。l被調過程執(zhí)行的時候，會在棧中為其分配內存空間。被調過程執(zhí)行的時候，會在棧中為其分配內存空間。 被調過程的每個形參都有一個單元被調過程的每個形參都有一個單元(稱為稱為形式單元形式單元)，用來存放，用來存放對應實參的地址。對應實參的地址。 因此，在被調過程的內部語句執(zhí)行之前，必須先把實參的地因此，在被調過程的內部語句執(zhí)行之前，必須先把實參的地址取到對應的形參單元中。然后

24、才能執(zhí)行本過程中的語句。址取到對應的形參單元中。然后才能執(zhí)行本過程中的語句。4.7 4.7 過程或函數調用語句的翻譯過程或函數調用語句的翻譯u4.7.2 過程調用語句的翻譯過程調用語句的翻譯(傳址傳址)l1.文法：文法： GS: Scall i (elist) elist elist,E | EP() Q(x,y,z); Q(int a,int b,int c) call i(E(1),E(2),E(3);1.使用隊列保存使用隊列保存E(i);2.傳遞傳遞E(i)的地址的地址;3.call Q;4.7 4.7 過程或函數調用語句的翻譯過程或函數調用語句的翻譯l2.語義子程序：語義子程序：for

25、 (隊列隊列queue中的每個中的每個P) emit(par, _, _, P); emit(call, _, _, i.place);將將E.place加入到加入到queue的隊尾的隊尾 GS: Scall i (elist) elist elist,E elist E初始化初始化queue,僅包含僅包含E.place 例如：例如：call Q(A+B,Z)被翻譯為：被翻譯為：(100) (+, A, B, T)(101) (par, _, _, T)(102) (par, _, _, Z)(103) (call, _, _, Q)4.8 4.8 說明語句的翻譯說明語句的翻譯u4.8.1 變量說明的翻譯變量說明的翻譯l說明語句的功能是說明源程序中每一個名字及其性質。說明語句的功能是說明源程序中每一個名字及其性質。l文法文法1：l文法文法2： GD: D int namelist | float namelist namelist namelist,i | i GD: D D,i | int i | float i (1) D int i fill