編譯原理與技術(shù)講義 第9章 語法制導(dǎo)的中間代碼翻譯

1、編譯原理與技術(shù)第9章語法制導(dǎo)的中間代碼翻譯青島大學(xué)信息工程學(xué)院主要內(nèi)容中間語言 聲明語句的翻譯賦值語句的翻譯 基本控制結(jié)構(gòu)的翻譯轉(zhuǎn)向語句的翻譯 編譯原理與技術(shù)29.1 語法制導(dǎo)的中間代碼翻譯引論 中間代碼翻譯在編譯程序中的位置 使用中間代碼的好處包括：（1）把源程序翻譯成目標(biāo)代碼的工作分階段進(jìn)行，便于控制和管理開發(fā)工作的復(fù)雜度，集中地解決不同階段的不同問題。例如，語義檢查可以發(fā)現(xiàn)類型不匹配、缺乏類型等可能導(dǎo)致程序運行得錯誤。（2）便于把與機器特性密切相關(guān)的目標(biāo)代碼的生成盡可能的限制在編譯的后端，有利于重定目標(biāo)機器，使得一種中間代碼可以為多種不同類型的目標(biāo)機器服務(wù)。這是目前最流行的編程語言Jav

2、a以及.NET編程環(huán)境所采用的策略（當(dāng)然，除了中間表示以外，它們的運行系統(tǒng)還需要虛擬機VM或通用語言運行時CLR等技術(shù)）。 語義分析器中間代碼生成器代碼優(yōu)化器語法樹中間代碼語法樹中間代碼目標(biāo)代碼生成器編譯原理與技術(shù)39.1 中間語言在編譯過程中表示源程序的數(shù)據(jù)結(jié)構(gòu)統(tǒng)稱為中間表示（中間語言）。用中間語言表示的程序叫做中間代碼。中間語言的設(shè)計既要包含足夠的結(jié)構(gòu)，可以支持高級程序語言的結(jié)構(gòu)，如類型、模塊、接口、安全機制、垃圾搜集等，又要便于到目標(biāo)機器的的自動映射，有助于翻譯成時空方面都高效的運行代碼。編譯原理與技術(shù)49.1 中間語言中間語言可以按照下列特性分類：抽象程度 中間語言可以非常抽象，像語法

3、樹一樣抽象地表示幾乎所有的操作，也可以具體到接近于目標(biāo)機器及其指令。抽象的中間語言如分析樹、有向無環(huán)圖，底層的中間語言包括字節(jié)代碼，它們的語句集合類似于匯編語言或機器的符號指令，而三地址碼介于這兩類表示之間?，F(xiàn)代計算機體系結(jié)構(gòu)（存儲管理、寄存器、指令）的發(fā)展對中間代碼的設(shè)計產(chǎn)生了深刻的影響。例如，P-code和Java bytecode都屬于字節(jié)代碼，但是，它們的代碼本身與支持環(huán)境存在很大的差異。運行時信息 中間語言可能使用目標(biāo)機器和運行環(huán)境的詳細(xì)信息（如數(shù)據(jù)類型、變量的位置），也可以不使用這些信息。抽象程度高的語言一般不包含目標(biāo)機器的信息，而字節(jié)代碼和三地址碼通常都包含了數(shù)據(jù)類型以及相關(guān)的算

4、符。一般的字節(jié)碼如P-code和Java bytecode都有相應(yīng)特殊的虛擬機器來解釋并運行字節(jié)代碼?，F(xiàn)代計算機技術(shù)的發(fā)展對程序的安全性、互操作性、并發(fā)性等嚴(yán)格要求，使得運行環(huán)境更加復(fù)雜。編譯原理與技術(shù)59.1 中間語言使用編譯的數(shù)據(jù)結(jié)構(gòu) 中間語言可以包含符號表的全部信息，例如符號范圍、嵌套層次和變量的偏移，目標(biāo)代碼的產(chǎn)生就可以完全倚賴于這樣的中間代碼。否則，產(chǎn)生目標(biāo)代碼時就需要查詢符號表等數(shù)據(jù)結(jié)構(gòu)。語法樹、分析樹和有向無環(huán)圖通常需要符號表的信息才能完成分析和翻譯的工作，三地址碼也需要使用符號表，一般的字節(jié)碼已經(jīng)把這些信息轉(zhuǎn)換成對應(yīng)虛擬機的信息?；ヂ?lián)、開放、異構(gòu)等特性增加了編譯系統(tǒng)數(shù)據(jù)結(jié)構(gòu)與管

5、理的復(fù)雜性，例如，統(tǒng)一的命名空間，除了要包含一個程序的名字以外，還要處理甚至是用其它語言編寫的構(gòu)件中的各種名字。用途 編譯過程包含了不同的階段和任務(wù)，每個階段和任務(wù)都有最合適的中間表示：分析樹特別適合對源程序進(jìn)行語法和語義分析，有向無環(huán)圖適合代碼優(yōu)化和生成，后綴表示便于計算機的計算，字節(jié)碼和三地址碼由于更接近機器代碼而最適宜目標(biāo)碼的生成和移植。但是，一個編譯程序通常都不會使用太多的中間表示，以免各個中間表示之間的轉(zhuǎn)換造成的效率損失。編譯原理與技術(shù)69.1 中間語言后綴式后綴式定義9.1 后綴式的遞歸定義如下：（1）如果E是一個變量或常量，則E的后綴式就是E本身；（2）如果E是形如E1 op E

6、2的表達(dá)式，其中op是任意的二元運算符 ，那么， E的后綴式為E1 E2 op，其中E1和 E2分別是E1和E2的后綴式；（3）如果E是(E1)形式的表達(dá)式，那么，E1的后綴式就是E的后綴式。 上述定義容易擴充到含單目算符如負(fù)號“”或否“not”的表達(dá)式，也不難擴充到包含數(shù)組元素。 編譯原理與技術(shù)79.1 中間語言后綴式后綴式的例子(a+b) (a+c) 的后綴式為ab+ac+a+b+c/d (a+c)的后綴式為abcd/ac+not A or not (C and not B)的后綴式為A not CB not and not or對于數(shù)組變量，把和分割維數(shù)的逗號“,”都看作是二目算符，那么

7、ai的后綴式可以表示成為a iai, j, k 的后綴式為aijk,編譯原理與技術(shù)89.1 中間語言后綴式后綴式的兩個特點（1）后綴式形式的表達(dá)式計算順序唯一，無需使用括號來明確計算順序；（2）只要直到每個算符的目數(shù)，計算參與運算數(shù)的個數(shù)，對于后綴式不論從左還是從右進(jìn)行掃描，都能對它進(jìn)行唯一的分解。例如abc/ 所代表的中綴表達(dá)式是 a/(bc)ab+cd+ 所代表的中綴表達(dá)式是 (a+b) (c+d)后綴式特別適合利用棧的結(jié)構(gòu)進(jìn)行計算：自左向右掃描表達(dá)式的后綴表示，每遇到一個對象就把它壓入棧內(nèi)；每遇到一個算符，就從棧頂取出相應(yīng)個數(shù)的運算對象進(jìn)行計算，再將結(jié)果壓入棧頂。最后，棧頂元素就是表達(dá)式

8、的運算結(jié)果。 編譯原理與技術(shù)99.1 中間語言后綴式后綴形式擴充到其它的語言結(jié)構(gòu) 對于賦值表達(dá)式V=E，如果把賦值號看作是二目算符，那么，它的后綴形式為VE= ，其中V和E分別是V和E的后綴式。例如，賦值語句t = (a+b) /c (de)的后綴形式為t ab+c/de = 賦值語句ai = aj+m, k的后綴形式為a i ajm+k, =無條件轉(zhuǎn)移語句goto L的后綴表達(dá)形式為L GOTO，其中GOTO看作是為單目運算符。編譯原理與技術(shù)109.1 中間語言后綴式對于條件語句if E then S1 else S2，設(shè)E、S1和S2分別是E、S1和S2的后綴形式，L1對應(yīng)語句S1的起點，

9、L2對應(yīng)語句S2的起點，那么，上述條件語句的后綴形式可以表示為E L1 GOTO S1L2 GOTO S2。例如，條件語句if (a b) then max = b else max = a的后綴形式為ab 10 GOTO max b= 20 GOTO max a=其中10表示條件為真時轉(zhuǎn)移到的標(biāo)號，10表示條件為假時無條件轉(zhuǎn)移到的標(biāo)號處。編譯原理與技術(shù)119.1 中間語言后綴式復(fù)合語句S1;S2的后綴形式可以簡單的表示成S1S2，其中S1和S2分別時語句S1和S2的后綴形式。但是，如果像C、Java、Pascal等語言允許在程序塊中增加聲明語句，那么，就應(yīng)改對程序塊的標(biāo)志“”或begin和e

10、nd分別引進(jìn)相應(yīng)的標(biāo)志，如BLOCKBEGIN和BLOCKEND。這樣，程序塊 S1;S2的后綴式為BLOCKBEGIN S1S2 BLOCKEND 循環(huán)語句while E do S的后綴式可以下列語句：L1:if not E then goto L2 else S; goto L1L2:參照條件語句和復(fù)合語句，可以把while循環(huán)語句表示成E L2 GOTO S L1 GOTO 編譯原理與技術(shù)129.1 中間語言后綴式例9.1 把下面的程序段寫成后綴的形式 int i;float a, b, result;i = 1; a = 0;while ( i = 20 ) b = b + a; a

11、= b; i = i+1result = b; 它的后綴形式為BLOCKBEGIN i int a b result,float i 1= a 0 = i 20 = L2 GOTO b ba + = ab= i i 1+= L1 GOTO result b =BLOCKEND編譯原理與技術(shù)139.1 中間語言后綴式例9.2 表9.1描述了把賦值語句轉(zhuǎn)換成后綴形式的語法制導(dǎo)的翻譯規(guī)則。其中綜合屬性code表示符號的后綴形式，屬性表示標(biāo)識符id的名字，num.lexva表示常數(shù)num的值；符號“|”表示把語義代碼連接起來（讀作“捻接”或“并置”）。運算符的屬性“op”給出具體的算符，

12、如“+”、“*”或“and”。文法規(guī)則語義規(guī)則S id = ES.code := | E.code | “”E E1 bop E2E.code := E1.code | E2.code | bop.opE sop E1E.code := E1.code | sop.opE (E1)E.code := E1.codeE idE.code := E numE.code := num.lexval編譯原理與技術(shù)149.1 中間語言圖形表示 a := (b + cd) + cd的語法樹如圖9.2(a)所示，它的后綴式為abcd+cd+ =。有向無環(huán)圖DAG也是一種中間表示

13、，和語法樹相比，它以更緊湊的方式給出同樣的信息，因為它把公共子表達(dá)式也標(biāo)示出來。圖9.2(b)的公共子表達(dá)式cd不止一個父結(jié)點。 :=a+ c b d c d 語法樹和分析樹都是常見的圖形中間代碼，語法樹省略了語法的終結(jié)符號，描述了源程序在語義上的層次結(jié)構(gòu)，是分析樹的濃縮表示。語法樹作為中間表示允許把翻譯從分析中分離出來，形成先分析后翻譯的方式。后綴式可以看作式語法樹的一種線性表示，它是后序遍歷或深度優(yōu)先遍歷語法得到結(jié)點的一個序列。:=a+ c d + b 圖9.2(b)9.2(a)編譯原理與技術(shù)159.1 中間語言圖形表示例9.3 表9.2描述了把一個簡化的賦值語句改造成語法樹的翻譯規(guī)則，使

14、用的是二義性文法，假定算符的優(yōu)先性和結(jié)合性遵循通常的約定，二目運算+和是典型程序語言運算符號集合中選出的兩個代表，其中mkunode(op, child)是構(gòu)造單目運算結(jié)點的函數(shù)。按照這個定義，可以把輸入a := (b + cd) + cd翻譯成圖9.2(a)形式的語法樹。文法規(guī)則語義規(guī)則S id = ES.tree := mknode( , mkleaf(id, ), E.tree) E E1 + E2E.tree := mknode( +, E1 .tree, E2 .tree,)E E1 E2E.tree := mknode( , E1 .tree, E2 .tree,)

15、 E E1E.tree := mkunode(, E1 .tree)E (E1)E. tree := E1. treeE idE. tree := mkleaf(id, )E numF. tree := mkleaf(num, num.lexval):=a+ c b d c d 編譯原理與技術(shù)169.1 中間語言圖形表示可以修改構(gòu)造結(jié)點的函數(shù)，仍然使用這個語義規(guī)則構(gòu)造出有向無環(huán)圖。它首先檢查是否已經(jīng)存在一個結(jié)點和要構(gòu)造的結(jié)點相同，如果是就返回這個已經(jīng)存在的結(jié)點，否則就構(gòu)造并返回一個新的結(jié)點。例如，對mknode的修改如下：function mknode (op: OPKind,

16、lchild, rchild: SyntaxTree): SyntaxTreenode: SyntaxTree;begin for (每個已經(jīng)產(chǎn)生的語法樹的結(jié)點node) doif (node.operator = op and node.leftchild = lchild andnode.rightchild = rchild )then return node;return SyntaxTree(op, lchild, rchild);end;按照這個定義，從輸入a := (b + cd) + cd構(gòu)造的DAG如圖9.2(b) 。 編譯原理與技術(shù)179.1 中間語言字節(jié)代碼字節(jié)代碼通常就

17、是運行它的機器模型或體系結(jié)構(gòu)的指令系統(tǒng)，與機器的符號指令或匯編語言類似，設(shè)計時考慮機器的字節(jié)特性以及存儲方式、尋址方式、數(shù)據(jù)類型。 使用字節(jié)代碼作為中間語言最著名的例子是在1970末和1980初許多Pascal語言編譯器中的P-code，它的形式如同一個假想的棧式機器（稱為P-機器）的匯編代碼，從而省缺了寄存器。對于不同的實際機器需要為P-code構(gòu)造一個解釋程序，這樣，就可以使Pascal語言及其編譯方便地移植到新的平臺上。編譯原理與技術(shù)189.1 中間語言字節(jié)代碼作為例子，我們考慮把一個表達(dá)式x := 2a+(b3)轉(zhuǎn)換成P-code代碼（分號后面是注釋）：ldax; 把x的地址存入棧內(nèi)l

18、dc2; 加載常數(shù)2到臨時棧loda; 加載變量a的值到臨時棧Mpi ; 把棧頂?shù)膬蓚€數(shù)據(jù)2和a彈出，執(zhí)行整數(shù)乘法運算，即2a，結(jié)果存放在棧內(nèi)lodb; 加載變量b的值到臨時棧ldc3; 加載常數(shù)3到臨時棧Sbi ; 把棧頂?shù)膬蓚€數(shù)據(jù)b和3彈出，執(zhí)行整數(shù)減法運算，即b3，結(jié)果存放在棧內(nèi)Adi ; 把棧頂?shù)?a和b3結(jié)果彈出，完成整數(shù)加法，2a+(b3)，結(jié)果存放在棧頂Sto ; 把棧頂?shù)闹荡嫒霔ｍ斚碌刂匪赶虻淖兞看鎯^(qū)域中，同時彈出這兩個元素上述的計算順序正好對應(yīng)了表達(dá)式的后綴形式：x2ab3 :=由于P-code被設(shè)計成是可以直接執(zhí)行的，所以，它還隱含了一個特殊的運行時環(huán)，包括數(shù)據(jù)大小以及

19、很多P-機器的特殊信息。 編譯原理與技術(shù)199.1 中間語言字節(jié)代碼我們看一下如何使用語義規(guī)則把例9.3語言生成P-code。我們用綜合屬性pcode表示P-code串，用“|”表示在P-code串中插入一個換行。 文法規(guī)則語義規(guī)則S id = ES.pcode := “l(fā)da” | |E.pcode |“sto”E E1 + E2E.pcode := E1 .pcode | E2 .pcode |“adi”E E1 E2E.pcode := E1 .pcode | E2 .pcode |“mpi”E (E1)E. pcode := E1. pcodeE idE. pcode

20、:= ”lod” | E numE. pcode := ”ldc” | num.lexval編譯原理與技術(shù)209.1 中間語言三地址代碼三地址語句是由下列形式的指令x := y op z其中x、y和z是名字、常數(shù)或編譯其產(chǎn)生的臨時變量，op表示運算符如加法、減法、乘法或邏輯算符。它的含義是，對y和z的值施加op所代表的運算，結(jié)果存入x表示的地址。源語言的表達(dá)式2a+(b3)可以翻譯成的三地址代碼是：t1 := 2at2 := b3t3 := t1+t2其中t1、t2和t3是編譯器產(chǎn)生的臨時變量。三地址碼是語法樹或DAG的一種線性表示，其中新增的臨時變量名對應(yīng)樹的內(nèi)部結(jié)點。2a+(

21、b3)的分析樹如圖9.3所示 +*2a b圖9.3 2a+(b3)的語法樹編譯原理與技術(shù)219.1 中間語言三地址代碼把賦值語句翻譯成三地址代碼的語義規(guī)則綜合屬性E.place表示存放E值的名字，E. code表示三地址指令，函數(shù)gencode(p, :=, E.place)表示生成三地址語句p := E.place。函數(shù)newtemp在每次調(diào)用的時候，產(chǎn)生不同的臨時變量名。 文法規(guī)則語義規(guī)則S id = ES.code := E.code | gencode(, :=, E.place)E E1 + E2E.place := newtemp;E.code := E1 .taco

22、de |E2.code |gencode (E.place, :=, E1.place, +, E2.place)E E1 E2E.place := newtemp;E.code := E1.code |E2.tacode |gencode (E.place, :=, E1.place, , E2.place)E E1E.place := newtemp;E.code := E1. code | gencode (E.place, := , uminus, E1.place)E (E1)E.place := newtemp;E. tacode := E1. tacodeE idE.place

23、:= ;E.code := E numE. code := num.lexval編譯原理與技術(shù)229.1 中間語言三地址代碼 下面是本書用到的三地址指令形式為x := y op z的賦值語句，其中op是二目算術(shù)或邏輯運算。形式為x := op z的賦值語句，其中op是單目算術(shù)或邏輯運算。形式為x := y的賦值語句，它把y的值賦給x。形式為goto L的無條件轉(zhuǎn)移語句，即下一條將被執(zhí)行的語句是帶標(biāo)號L的三地址語句。形式為if x relop y goto L或if b goto L的條件轉(zhuǎn)移語句，第一中語句對x 和 y施加關(guān)系運算relop（如），如果關(guān)系成立則執(zhí)行標(biāo)號為L的三地

24、址語句，否則執(zhí)行后續(xù)語句；第二種形式中，b為布爾變量或常量，若b為真，則執(zhí)行標(biāo)號為L的語句，否則執(zhí)行后續(xù)語句。形式為param x和call p, n表示過程調(diào)用語句，其中x表示參數(shù)，n表示參數(shù)個數(shù)。源程序的過程調(diào)用語句p(x1, x2, ., xn)通常生成如下的三地址碼：param x1.param xncall p, n編譯原理與技術(shù)239.1 中間語言三地址代碼返回語句return x表示過程返回值x，其中x也可以不出現(xiàn)。形式為x := yi和xi := y的索引賦值，第一條語句把相對于地址y后面第i的單元的值賦給x；第而條語句把y的值賦給相對于地址x后面第i的單元里。形式為x :=

25、&y，x:= *y 和*x := y的地址指針賦值。第一個語句把y的存儲單元地址賦給x，假定y是一個名字或臨時變量，代表一個具有左值的表達(dá)式，如Ai, j；而x是指針變量或臨時變量，即x的右值是某個對象的值。第二條語句是把y的存儲單元里的值賦給x，其中y是指針變量或右值為地址的臨時變量。第三條語句把x所指向額對象的右值賦給y的左值。形式為read x的write x輸入和輸出語句，它們只有一個地址。沒有地址的停機語句halt。編譯原理與技術(shù)249.1 中間語言三地址指令的四元式實現(xiàn)三地址指令操作符運算數(shù)1運算數(shù)2結(jié)果書寫形式x := y op zopyzx(op, y, z, x)x := o

26、p zopzx(op, z, , x)x := y:=yx( :=, y, , x)goto LjumpL(jump, , , L)if x relop y goto LjropxyL(jrop, x, y, L)if b goto LjnzbL(jnz, b, , L)param xparamx(param, x, , )call p, ncallpn(call, p, n, )return xreturnx(return, , , x)x := yi=yix(=, yi, , x)xi := y=yxi(=, y, , xi)x := &y&yx(&, y, , x)x:= *yyx(,

27、y, , x)*x := y:=yx(:=, y, , x)read xreadx(read, , , x)write xwritex(write, , , x)halthalt(halt, , , )編譯原理與技術(shù)259.2 聲明語句的翻譯 過程中的聲明 例如，對于一個C+的聲明序列：int index;double sum;char token;如果該聲明在內(nèi)存中可以得到的首地址是1000，那么局部名字x的地址都可以按照下列公式計算：index的地址是 1000sum的地址是 1000+ index的字節(jié)寬度10041000 + 4token的地址是 1004+ sum的字節(jié)寬度10121

28、00 + 4 +8實際上，為聲明語句中的名字分配存儲的主要問題就是計算每個名字的相對地址，即相對于基址的偏移，再加上為該聲明分配的基址（例如過程活動記錄的首址），就可以在存儲器中訪問到每個名字。編譯原理與技術(shù)269.2 聲明語句的翻譯非終結(jié)符P產(chǎn)生一系列形如“T id”的聲明語句。全局變量offset記錄下一個可用的相對地址初始化offset為0。以后每次遇到一個新的名字，將該名字連同類型和當(dāng)前的offset填入符號表，然后使offset增加該名字所表示的數(shù)據(jù)的寬度。過程enter(name, type, offset)用來把名字為name的標(biāo)識符填入符號表。綜合屬性type和width分別表

29、示非終結(jié)符T的類型和寬度。屬性type的取值范圍是基本類型integer和real以及應(yīng)用類型構(gòu)造器pointer和array得到的結(jié)構(gòu)類型。假設(shè)整數(shù)的寬度是4，實數(shù)的寬度是8，指針類型的寬度是4，數(shù)組所占用的存儲單元個數(shù)是數(shù)組元素的個數(shù)乘以基類型元素的寬度。 文法規(guī)則語義動作P Doffset := 0D D1 ; D2D id: Tenter(, T.type, offset);offset := offset + T.widthT integerT. type := integer;T.width := 4T realT. type := real;T.width := 8

30、T array num of T1T. type := array(num.val, T1.type);T.width := num.val * T1.widthT T1T. type := pointer(T1.type);T.width := 4編譯原理與技術(shù)279.2 聲明語句的翻譯記錄作用域信息 考慮像Pascal和Ada這樣允許過程嵌套的語言，主要討論如何保存聲明的作用域信息（6.4）。所討論的文法如下：P D SD D; D | id: T | proc id; D; S第一條產(chǎn)生式提供程序的規(guī)則，在聲明D后面跟隨語句序列S。聲明語句允許嵌套地聲明過程。為了簡化討論的問題，我們不考

31、慮遞歸調(diào)用的過程，也不考慮過程的參數(shù)說明，這是因為參數(shù)可以類似于表9.6的局部變量的處理技術(shù)。在處理嵌套過程時為每個過程都建立一張獨立的符號表，每個符號表都有自己的符號表指針tableptr、基址base和自己的offset。這些符號表可以一邊掃描源程序一邊建立并且完成內(nèi)存分配。每遇到D proc id; D1; S時，就創(chuàng)建一張新的符號表，把D1中的所有說明都添在該符號表；用一個指針記錄包含D1的最近的外圍過程D的符號表，id也是其中的一個局部名字。在最近的外圍過程D的符號表中對于每個直接嵌入其中的過程，也都有一個指向它們符號表指針。編譯原理與技術(shù)289.2 聲明語句的翻譯表9.7給出了多趟

32、掃描含有嵌套過程的語法制導(dǎo)翻譯規(guī)則，它使用了兩個數(shù)據(jù)結(jié)構(gòu)：一個保存各外層過程的符號表指針的指針棧tblptr，一個對應(yīng)的存放外層過程相對地址的偏移棧offset。指針棧tblptr的棧頂top(tblptr)總是指向當(dāng)前層的符號表；偏移棧offset的棧頂保存了當(dāng)前層已經(jīng)處理的聲明的偏移之和。整個翻譯模式同時使用了下列操作：SymbolTable *mktable(SymbolTable *previous, integer base)創(chuàng)建一張新的符號表，填入基址，把參數(shù)指針previous放在該表的表頭，表示指向已經(jīng)創(chuàng)建好的一個符號表，比如剛好包圍嵌入過程的符號表；返回指向這張新表的指針。符

33、號表的信息還可以包含局部變量所需要的存儲單元個數(shù)等。void enter(SymbolTable *table, String name, DType type, Integer offset)在指針table指向的符號表中為變量名name建立一個新項，類型是type，在該表中的相對地址是offset。void addwidth(SymbolTable *table, Integer width)把符號表table的所有項的累加寬度記錄在該表的首部。void enterproc(SymbolTable *table, String name, SymbolTable *newtable) 在t

34、able指向的符號表中為過程名name建立一個新項，指針newtable指向它的符號表。編譯原理與技術(shù)299.2 聲明語句的翻譯對于P D S，首先要建立一張空的符號表，動作要在D S之前完成。為了使整個動作都在文法產(chǎn)生式的末尾，我們采取了的技術(shù)，引入一個非終結(jié)符M和產(chǎn)生式，以消除嵌入在產(chǎn)生式中的語義動作。M的語義動作是初始化外層符號表的指針棧tblptr和偏移棧offset：最外層過程沒有包圍的過程了，所以指針為空null，相對地址和基址都為0。這樣，P M D S的語義動作就是把當(dāng)前（棧頂）符號表top(tblptr)的所有項的累加寬度記錄在該表的首部，表示該過程的局部變量、

35、過程等聲明所需要的總的存儲單元數(shù)；之后，退掉指針棧tblptr和偏移棧offset的棧頂。對嵌入過程說明D proc id; D; S做了類似的語法處理，改成D proc id; N D1; S。首先，在掃描到嵌入的過程D1之前，需要為它建立一個空的符號表，讓它指向直接外圍過程的符號表，初始化這個新過程的偏移為0，它的基址就是直接外圍過程當(dāng)前所有條目（變量、過程）寬度的總和。這些都由對應(yīng)N 的語義動作完成。然后，執(zhí)行D proc id; N D1; S右部的語義動作：首先把D1產(chǎn)生的所有聲明的寬度存入它的符號表內(nèi)（此時放在棧頂?shù)亩际怯嘘P(guān)D1的值），退掉指針棧tblptr和偏移棧offset的棧

36、頂表示結(jié)束嵌入過程的處理，繼續(xù)處理外層過程的聲明：把D的當(dāng)前的條目寬度加上D1所有聲明的寬度，為這個嵌入過程的名字id建立符號表條目。 文法規(guī)則語義動作P M D Saddwidth(top(tblptr), top(offset);pop (tblptr); pop(offset)M t := mktable(nil, 0);push(t, tblptr); push(0, offset)D D1 ; D2D proc id; N D1; St := top (tblptr);wide := top(offset);addwidth ( t, wide);pop (tblptr); pop(

37、offset);top(offset) := top(offset) + wide;enterproc(top(tblptr), , t)D id:Tenter ( top(tblptr), , T.type, top(offset);top(offset) := top(offset) + T.widthN t := mktable(top(tblptr), top(offset);push(t, tblptr); push(wide, offset)編譯原理與技術(shù)309.2 聲明語句的翻譯program sort(input, output)var a: arr

38、ay1.10 of integer; x: integer; procedure readarray; var i: integer; begin . end;44tblptr棧頂offset棧頂1 掃描完sort局部變量的聲明時2、掃描過程完readarray局部聲明tblptr棧offset棧44tblptr棧頂offset棧頂nullaarray(1.10, integer)xinteger0404iintegerreadarray0sort00440nullaarray(1.10, integer)xinteger040sort00在符號表中，首部包含三個子域：左域是指向直接外圍過程符

39、號表的指針，主程序sort的為空null；中域保存該表的基址，右域記錄了該過程聲明所占存儲單元的總的個數(shù)（累加寬度之和）。符號表中記錄了變量名、類型及其在過程中的相對地址：例如，變量a在sort中的相對偏移就是基址0，而x的相對偏移是在分配完10個整型數(shù)（4個字節(jié)）之后的地址，即10440。當(dāng)掃描完readarray的局部變量聲明時（對應(yīng)圖9.4中步驟2），首先執(zhí)行就執(zhí)行N 對應(yīng)的動作，得到基址44，tblptr的棧頂是指向readarray符號表的指針；然后執(zhí)行D id:T對應(yīng)的動作，在這個符號表中存入i的信息，同時得到readarray符號表的局部聲明的累加寬度4。 編譯原理與技術(shù)319.

40、2 聲明語句的翻譯3、掃描完過程readarray48nullaarray(1.10, integer)xinteger040iintegerreadarray0sortreadarraytblptr棧頂offset棧頂00444program sort(input, output)var a: array1.10 of integer; x: integer; procedure readarray; var i: integer; begin . end;掃描完readarray過程時，用addwidth把對應(yīng)readarray的offset值4存入該過程符號表的首部，把指向readarr

41、ay的指針及其偏移量之和分別從指針棧tblptr和偏移棧offset的棧頂刪除，修改sort的當(dāng)前總偏移為48，最后在sort中添加過程readarray的條目，填入一個指向readarray符號表的指針。編譯原理與技術(shù)329.2 聲明語句的翻譯040484、掃描完程序sortnillaarray(1.10, integer)xinteger04044iintegerreadarray0sortreadarrayexchangequicksortexchangekintegerquicksortvintegerpartitioniintegerpartitionjinteger06444804

42、8568program sort(input, output)var a: array1.10 of integer; x: integer; procedure readarray; var i: integer; begin . end;procedure exchange(i, j: integer);begin . end;procrdure quicksort(m, n: integer);var k, v: integer;function partition(y,z: integer): integervar i, j: integer;begin . end;begin . e

43、nd quicksort ;begin . end sort;圖9.4中的步驟4示意了處理完整個程序后所建立的符號表。最終得到sort中聲明所占用的最大存儲單元數(shù)量是64（= 44+4+8+8）。 編譯原理與技術(shù)339.2 聲明語句的翻譯記錄中的域名現(xiàn)在，我們可以對表9.6的語言文法增添一個新的產(chǎn)生式，構(gòu)造程序語言的基本結(jié)構(gòu)類型，記錄類型：T record D end對記錄的處理類似于對過程的處理。我們?yōu)槊總€記錄建立一張符號表，保存每個域的名字及其類型等信息。由于在表9.7中的過程定義不影響域?qū)挼挠嬎?，因此，允許上述產(chǎn)生式的D包含過程定義，這樣做的目的是為了簡化翻譯模式 編譯原理與技術(shù)349.

44、2 聲明語句的翻譯當(dāng)編譯掃描到關(guān)鍵子record的時候，與非終結(jié)符L所對應(yīng)的動作是，為該記錄中的各個域名創(chuàng)建一張新的記錄符號表。把指向該表的指針壓入指針棧tblptr，并把相對地址0壓入偏移棧offset。根據(jù)表9.7可知，產(chǎn)生式D id:T的動作是把域名id的有關(guān)信息填入該記錄的符號表。當(dāng)記錄中的所有域名都被檢查之后，在offset的棧頂就存放著記錄中的所有數(shù)據(jù)對象的總的寬度。在表9.8中end之后的動作是把offset棧頂?shù)目偟挠驅(qū)挾却嫒胗涗涱愋蚑的綜合屬性width，T的類型屬性type值則是通過對指向本記錄符號表的指針使用類型構(gòu)造符record得到。 文法規(guī)則語義動作T record

45、L D endT.type := pointer (top(tblptr)；T.width := top (offset)L t := mktable (nil, 0);push(t, tblptr); push(0, offset)編譯原理與技術(shù)359.3 賦值語句的翻譯 賦值語句是命令式和面向?qū)ο笳Z言改變存儲器的內(nèi)容以及程序狀態(tài)的基本操作，它的一般語法定義是：V := E;V和E可以是簡單類型的表達(dá)式，也可以是數(shù)組元素、記錄中子域變量、指針變量的內(nèi)容或地址等。賦值語句的語義是：把右部表達(dá)式的值賦給左部變量，對于許多語言還要求左部變量與右部表達(dá)式的類型相容。賦值語句的執(zhí)行步驟包括： 計算右部

46、表達(dá)式E的值； 必要時對E的值進(jìn)行類型轉(zhuǎn)換，強制到V的類型； 計算做變量V的地址； 把E的值送入V的地址。這是設(shè)計翻譯賦值語句的基礎(chǔ)。 編譯原理與技術(shù)369.3 賦值語句的翻譯簡單算術(shù)表達(dá)式及賦值語句我們在三地址代碼中直接使用了表達(dá)式的名字，并將它理解為指向符號表中該名字的入口指針?，F(xiàn)在，我們使用函數(shù)lookup()在符號表中查找名為的標(biāo)識符的入口地址。表9.9給出了如何使用符號表把簡單表達(dá)式及賦值語句翻譯成三地址代碼的語義動作。其中E的屬性place表示E在符號表中的入口，使用輸出代碼的函數(shù)，emit(id.place, :=, E.place)表示把賦值語句的三

47、地址碼按順序地寫在一個輸出文件。文法規(guī)則語義規(guī)則S id : = Ep := lookup ();if p = null then errorelse emit (p, :=, E.place )E E1 + E2E.place := newtemp;emit (E.place, :=, E1.place, +, E2.place)E E1 E2E.place := newtemp;emit (E.place, :=, E1.place, , E2.place)E E1E.place := newtemp;emit (E.place, :=, uminus, E1.place)E

48、 (E1)E.place := E1. place;E idp := lookup ();if p = null then errorelse E.place := pE numE. place := num.lexval編譯原理與技術(shù)379.3 賦值語句的翻譯在嵌套結(jié)構(gòu)中查詢名字的函數(shù)lookup的一個實現(xiàn)。首先，設(shè)計使用的符號表的數(shù)據(jù)結(jié)構(gòu)SymbolTable（參考圖9.4），給出主要的結(jié)構(gòu)和子域如下：struct Iditem String name; DType type; Address offset struct SymbolTable SymbolTable *pr

49、evious; Integer base, offset; Idlist ids;/* 名字項的表 */ Proclist procs;/* 過程項的表 */假設(shè)符號表中的變量項放在表結(jié)構(gòu)類型Idlist的變量ids中，并且假設(shè)函數(shù)search（name, list）當(dāng)前過程的符號表中查詢name是否在局部標(biāo)識符表list中：如果在就返回指向名字是name的標(biāo)識符項，否則返回null。ditem *lookup ( String name, SymbolTable *table)SymbolTable *next, *p; next = table; while (next ! = null

50、) p = serach (name, next ids)； if p != null return p; next = next previous; return null;編譯原理與技術(shù)389.3 賦值語句的翻譯在翻譯規(guī)則中對中間代碼就有兩種表示方法：利用生成函數(shù)gencode把中間代碼存入符號的屬性code中，并可以利用并置符號把代碼段連接起來，形成更大的代碼段直至程序，隨時整理并輸出到文件上。這個方法更適合多趟掃描的編譯構(gòu)造，允許在多次分析源程序的過程中多次訪問和處理存在屬性內(nèi)的中間代碼。一邊分析和翻譯源程序的語句，一邊按照源程序的順序把中間代碼（用函數(shù)emit）寫在一個輸出文件中。這

51、個方法可以在一趟編譯掃描過程中同時完成代碼的翻譯，但是，沒有辦法對產(chǎn)生的代碼進(jìn)行優(yōu)化，因為函數(shù)emit通常是把中間代碼輸出在一個順序文件中。 編譯原理與技術(shù)399.3 賦值語句的翻譯數(shù)組元素的引用數(shù)組的有關(guān)信息，如分配的基址、維數(shù)、每個維的上下界、維數(shù)的大小、成員數(shù)據(jù)占用的存儲大小等，是存放在一個稱作數(shù)組向量的符號表中。我們主要研究如何計算靜態(tài)數(shù)組中一個數(shù)組元素的地址，并翻譯成三地址代碼。我們不討論諸如數(shù)組的下標(biāo)是否越界、類型是否合適等其它問題。 編譯原理與技術(shù)409.3 賦值語句的翻譯數(shù)組元素的引用假如一維數(shù)組A的下界是low，分配的相對地址是base，即Alow的相對地址，每個元素的寬度是

52、w，那么A的第i個元素Ai的起始地址是：base + ( i low)w(9.1)把它整理成iw + (base loww)這樣，(base loww)就可以在編譯時刻完成，從而減少了運行時的地址計算。編譯原理與技術(shù)419.3 賦值語句的翻譯二維數(shù)組的元素也必須轉(zhuǎn)化為一維方式存儲，通常有兩種方式存儲：以行為主或以列為主。對于多維數(shù)組的存儲，F(xiàn)ORTRAN使用以列為主，Pascal、C+和Java都以行為主。在行為主的兩維數(shù)組的情況下，Ai, j的地址可以用下列公式計算：base + (i low1)n2+(j low2)w其中l(wèi)ow1和low2分別是這兩維的下界，n2是第2維的大小，即若hig

53、h2是j值的上界，則有n2 = high2low2+1。假定i和j的值在編譯時不知道，而可以知道其它值，那么，把上式變換成(in2 + j )w +(base (low1n2)+low2)w)(9.2)同樣，后一項子表達(dá)式(base (low1n2)+low2)w)可以在編譯時計算。編譯原理與技術(shù)429.3 賦值語句的翻譯推廣到k維數(shù)組，得到Ai1, i2, .,ik的地址表達(dá)式如下：(.(i1n2 + i2 )n3 + i3).)nk + ik)w +base (.(low1n2 + low2 )n3 + low3).)nk + lowk)w(9.3)假定對所有的j，nj = highjlo

54、wj+1是固定的，那么，公式(9.3)的第2行就可以在編譯時計算出來，存放在數(shù)組A的信息域里Ai1, i2, .,ik地址的動態(tài)部分需要在運行時計算，必須設(shè)計出計算這個地址的代碼。下面，我們考慮如何計算數(shù)組引用的動態(tài)部分(.(i1n2 + i2 )n3 + i3).)nk + ik (9.4)它可以用下列遞推公式e1 = i1em = em-1nm + im (9.5)進(jìn)行計算，直到m=k為止。然后將ek乘以數(shù)組元素的寬度w，再加上公式(9.3)的第2行就可以得到數(shù)組引用元素的地址。 編譯原理與技術(shù)439.3 賦值語句的翻譯從(9.5)的遞推計算中可以看出，除了第一個下標(biāo)i1以外，其它每個em

55、的計算都要訪問數(shù)組的符號表項，以便得到各維的大小。如果在表9.9的文法中出現(xiàn)id的地方也允許出現(xiàn)下面產(chǎn)生式中L出現(xiàn)，則可以把數(shù)組元素引用加入到賦值語句中。L id Elist | idElist Elist, E | E如果僅用綜合屬性，在處理Elist Elist, E和Elist E的時候就訪問不到數(shù)組L的有關(guān)信息，因為這是與數(shù)組名id關(guān)聯(lián)的信息。因此把產(chǎn)生式等價地改寫成L Elist | idElist Elist, E | id E即數(shù)組名與最左下標(biāo)表達(dá)式連在一起，這樣在翻譯Elist的過程中都能知道符號表中相應(yīng)于數(shù)組名id的信息。要生成數(shù)組引用的三地址代碼，關(guān)鍵是把(9.5)的計算與

56、數(shù)組引用的文法聯(lián)系起來。編譯原理與技術(shù)449.3 賦值語句的翻譯對Elist設(shè)置如下的綜合屬性：array表示指向符號表中相應(yīng)數(shù)組名表項的指針，ndim保存已經(jīng)分析過的下標(biāo)表達(dá)式的個數(shù)，place保存根據(jù)下標(biāo)表達(dá)式計算的值，即公式(9.5)中em的值。函數(shù)esizeof(array)給出數(shù)組元素的寬度，limit(array,j)返回array所指示數(shù)組的第j維的維數(shù)nj，base(array)給出符號表中array所指示數(shù)組的基址，即公式(9.3)中的base，函數(shù)adrconst(array)表示公式(9.3)第2行的減號之后的值。左值L有兩個屬性，place和offset。當(dāng)L是簡單名字

57、時，L.offset為null，L.place是指向符號表中對應(yīng)此名字表項的指針；否則，L.place = base(array) adrconst(array)，表示公式(9.3)中第2行的值，L.offset表示某個數(shù)組元素的索引，等于Elist.placew。編譯原理與技術(shù)459.3 賦值語句的翻譯下面考慮在賦值語句中加入數(shù)組元素之后的一種翻譯模式，把語義動作加入到下列文法中：（1）S L: = E（2）E E1 + E2（3）E (E1)（4）E L（5）L Elist （6）L id（7）Elist Elist, E （8）Elist id E編譯原理與技術(shù)469.3 賦值語句的翻譯

58、若L是個簡單名字，則產(chǎn)生正常的賦值；否則，產(chǎn)生對L所指示地址的索引賦值：（1）S L: = Eif L.offset = null then emit (L.place, :=, E.place )else emit(L.place, , L.offset, , :=, E.place)算術(shù)表達(dá)式語義動作和表9.9一樣：（2）E E1 + E2 E.place := newtemp;emit (E.place, :=, E1.place, +, E2.place) （3）E (E1) E.lpace := E1.lpace 編譯原理與技術(shù)479.3 賦值語句的翻譯若L是個簡單名字，則產(chǎn)生正常的

59、賦值；否則，產(chǎn)生對L所指示地址的索引賦值：（1）S L: = Eif L.offset = null then emit (L.place, :=, E.place )else emit(L.place, , L.offset, , :=, E.place)算術(shù)表達(dá)式語義動作和表9.9一樣：（2）E E1 + E2 E.place := newtemp;emit (E.place, :=, E1.place, +, E2.place) （3）E (E1) E.lpace := E1.lpace 編譯原理與技術(shù)489.3 賦值語句的翻譯若一個數(shù)組引用L歸約到E時，即分析的源程序串中出現(xiàn)了a10或

60、b5,8這樣的數(shù)組引用的時候，則需要L的右值，可以用索引得到存儲單元地址L.placeL.offset的內(nèi)容：（4）E L if L.offset = nullthen E.place := L.placeelse beginE.place := newtemp;emit (E.place, :=, L.place, , L.offset, )end 編譯原理與技術(shù)499.3 賦值語句的翻譯下面計算在這個歸約中用到的L的屬性值：（5）L Elist L.place := newtemp; L.offset := newtemp;emit (L.place, :=, base(Elist.arr