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

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

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

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

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

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

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

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

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

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

10、地址，保存該變量的入口地址，V.offset = null; 如果如果V是一個(gè)數(shù)組元素是一個(gè)數(shù)組元素，V.place保存該數(shù)組元素的保存該數(shù)組元素的CONSPART，V.offset 保存保存VARPART;4.6 4.6 數(shù)組元素的翻譯數(shù)組元素的翻譯l關(guān)鍵非終結(jié)符之關(guān)鍵非終結(jié)符之2：elist對(duì)于類似于如下形式的句子：對(duì)于類似于如下形式的句子： AE，E，E，E=x最終規(guī)約為最終規(guī)約為elist = x，繼而，繼而 V= x ； 可見，可見，elist負(fù)責(zé)規(guī)約數(shù)組元素中除了負(fù)責(zé)規(guī)約數(shù)組元素中除了之外的部分。對(duì)之外的部分。對(duì)elist設(shè)置設(shè)置三個(gè)屬性：三個(gè)屬性：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 數(shù)組元素的翻譯數(shù)組元素的翻譯l非終結(jié)符之非終結(jié)符之2：elist(1)elist.ARRAY：表示數(shù)組名在符號(hào)表中的入口。例如：數(shù)組：表示數(shù)組名在符號(hào)表中的入口。例如：數(shù)組元素元素A3,4,6,3,2在規(guī)約過程中，所有在規(guī)約過程中，所有elist.ARRAY的值是；的值是；(2)elist.DIM：數(shù)組維數(shù)的計(jì)數(shù)器。例如：數(shù)組維數(shù)的計(jì)數(shù)器。例如： 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中間結(jié)果的單元名字在中間結(jié)果的單元名字在符號(hào)表中的存放位置，或是一個(gè)臨時(shí)變量的整數(shù)碼。因此，符號(hào)表中的存放位置，或是一個(gè)臨時(shí)變量的整數(shù)碼。因此，在逐次對(duì)在逐次對(duì)elist歸約的過程中，將逐步產(chǎn)生計(jì)算歸約的過程中，將逐步產(chǎn)生計(jì)算VARPART的四的四元式元式VARPART=(i1d2 + i2)d3 + i3)d4 + )+ in1)dn + in4.

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

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 數(shù)組元素的翻譯數(shù)組元素的翻譯(4) EV if (V.offset=null) E.place=V.place; /*V是簡單變量是簡單變量*/ else T=newtemp; /*V是下標(biāo)變量是下標(biāo)變量*/ emit(= ,V.placeV.offset,_,T); E.place=T; 將數(shù)組元素的值賦給T4.6 4.6 數(shù)組元素的翻譯數(shù)組元素的翻譯(5) Velis

15、t T=newtemp; emit(，elist.ARRAY,C,T); V.place=T; V.offset=elist.place;/*假定通過數(shù)組名的符號(hào)表入口不僅能獲得地址假定通過數(shù)組名的符號(hào)表入口不僅能獲得地址a而且也能得而且也能得到常數(shù)到常數(shù)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 數(shù)組元素的翻譯數(shù)組元素的翻譯其它函數(shù)：其它函數(shù)： limit(ARRAY,k)計(jì)算數(shù)組計(jì)算數(shù)組ARRAY的第的第k維長度維長度dk4.6 4.6 數(shù)組元素的翻譯數(shù)組元素的翻譯4.6 4.6 數(shù)組元素的翻譯數(shù)組元素的翻譯例例4.

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

18、圖4-17所示。所示。104(=, T3, _, X)4.6 4.6 數(shù)組元素的翻譯數(shù)組元素的翻譯例例4.10 已知已知A是一個(gè)是一個(gè)10 20的數(shù)組的數(shù)組(每維下界均為每維下界均為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 數(shù)組元素的

19、翻譯數(shù)組元素的翻譯例例4.9 已知已知A是一個(gè)是一個(gè)10 20的數(shù)組的數(shù)組(每維下界均為每維下界均為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 數(shù)組元素的翻譯數(shù)組元素的翻譯例例.設(shè)設(shè)A為一個(gè)為一個(gè)10*20的數(shù)組，即的數(shù)組，即n1=10,n2=20,并設(shè)并設(shè)w=4.對(duì)賦值語對(duì)賦值語句句x:=A y ,

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

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

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

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

24、才能執(zhí)行本過程中的語句。址取到對(duì)應(yīng)的形參單元中。然后才能執(zhí)行本過程中的語句。4.7 4.7 過程或函數(shù)調(diào)用語句的翻譯過程或函數(shù)調(diào)用語句的翻譯u4.7.2 過程調(diào)用語句的翻譯過程調(diào)用語句的翻譯(傳址傳址)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.使用隊(duì)列保存使用隊(duì)列保存E(i);2.傳遞傳遞E(i)的地址的地址;3.call Q;4.7 4.7 過程或函數(shù)調(diào)用語句的翻譯過程或函數(shù)調(diào)用語句的翻譯l2.語義子程序：語義子程序：for

25、 (隊(duì)列隊(duì)列queue中的每個(gè)中的每個(gè)P) emit(par, _, _, P); emit(call, _, _, i.place);將將E.place加入到加入到queue的隊(duì)尾的隊(duì)尾 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說明語句的功能是說明源程序中每一個(gè)名字及其性質(zhì)。說明語句的功能是說明源程序中每一個(gè)名字及其性質(zhì)。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