第8章語法制導翻譯

和中間代碼生成語法分析的作用是判斷一個輸入是否為一個句子，并且同時獲得該句子的語法結構，即語法樹。例如在算術表達式的翻譯中，不僅要知道表達式中各個運算的先后次序，即語法結構，而且還要知道該表達式中的各個變量和常量的內存地址或值，要知道計算過程的中間結果所存放的內存地址或值，甚至還要知道其數據類型。這些信息都被稱為語義信息，而對語義信息進行相應的分析處理就叫做語義分析。因此，翻譯是一個語法分析和語義分析綜合在一起進行的過程。在編譯程序中使用了這樣的一種技術，就是在語法分析的同時進行語義分析的工作，并同步地完成相應語句的翻譯。這種技術就稱為語法制導翻譯。第5章教學內容屬性文法的概念；語法制導翻譯的概念；常用的中間代碼形式；程序設計語言的語法結構的自底向上的語法制導翻譯方法。一、屬性文法屬性文法是在上下文無關文法的基礎上為每個文法符號（終結符或非終結符）配備若干個相關的“值”（稱為屬性）。這些屬性代表與文法符號相關的信息，例如它的類型、值、代碼序列、符號表內容等等。屬性和變量一樣，可以進行計算和傳遞。屬性一般分為兩類：綜合屬性和繼承屬性。簡單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。屬性加工的過程即是語義處理的過程，對于文法的每一個產生式都配備了一組屬性的計算規則，則稱為語義規則。在一個屬性文法中，對應于每個產生式A都有一套與之相關聯的語義規則，每條語義規則的形式為：b:=f(c1,c2,…,ck)

這里f是一個函數，而且或者（1）b是A的一個綜合屬性并且c1,c2,…ck是產生式右邊文法符號的屬性；或者（2）b是產生式右邊某個文法符號的一個繼承屬性并且c1,c2,…ck是A或產生式右邊任何文法符號的屬性。在這兩種情況下，屬性b依賴于屬性c1,c2…,ck。要特別強掉的是：終結符只有綜合屬性，它由詞法分析器提供；非終結符既可以有綜合屬性也可以有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。一般來講，對出現在產生式右邊的繼承屬性和出現在產生式左邊的綜合屬性都必須提供一個計算規則，屬性計算規則中只能使用相應產生式的文法符號的屬性，這有利于產生式范圍內“封裝”屬性的依賴性。然而，出現在產生式左邊的繼承屬性和出現在產生式右邊的綜合屬性不由所給的產生式的屬性計算規則進行計算，它們由其它產生式的屬性規則計算,由屬性計算器的參數提供。語義規則所描述的工作可以包括屬性計算、靜態語義檢查、符號表操作、代碼生成等。語義規則可能產生副作用（如產生代碼），也可能不是變元的嚴格函數（如某個規則給出可用的下一個數據單元的地址）。這樣的語義規則通常寫成過程調用，或過程段。綜合屬性在語法樹中，一個結點的綜合屬性的值由其子結點的屬性值確定。因此，通常使用自底向上的方法在每一個結點處使用語義規則計算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S—屬性文法。繼承屬性在語法樹中，一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定。用繼承屬性來表示程序語言結構中的上下文依賴關系很方便。屬性文法的定義【定義】一個屬性文法AG是一個四元組，即AG=(G,A,R,B)，其中⑴G=(N,T,S,P)是一個前后文無關文法；⑵A=∪XN∪TA(X)是一個屬性的有限集合；⑶R=∪pPR(p)是一個語義規則式的有限集合；⑷B=∪pPB(p)是一個條件的有限集合；屬性文法的定義并且滿足以下兩個條件：1．對任意兩個符號的X和Y，若X≠Y，則A(X)∩A(Y)=；2．對于任何在L(G)的句子所對應的語法樹上出現的符號X，X的任意一個屬性X.a的計算，至多只有一條語義規則式可以應用。

屬性文法示例【例5．1】簡單臺式計算器的算術表達式的屬性文法：產生式集G:語義規則式集R:LE{print(E.val)}EE1+T{E.val=E1.val+T.val}ET{E.val=T.val}TT1

*F{T.val=T1.val×F.val}TF{T.val=F.val}F(E){F.val=E.val}Fdigit{F.val=digit.lexval}

示例

在該描述中，每個非終結符都有一個屬性：一個整數值的稱作val的屬性。按照語義規則對每個產生式來說，它的左部E，T，F的屬性值的計算來自它右部的非終結符，這種屬性稱作綜合屬性。單詞digit僅有綜合屬性，它的值是由詞法分析程序提供的。和產生式LE相聯的語義規則是一個過程，打印由E產生的表達式的值。我們可以理解為L的屬性是空的或是虛的。設表達式為3*5+4，則語義動作打印數值19LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹LR分析器可以改造為一個翻譯器，在對輸入串進行語法分析的同時對屬性進行計算。LR分析器增加語義棧。#X1…XmI0I1…Im

語義棧

-X1.VAL…Xm

.VALSLR(1)分析表digit+*()＃ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5狀態ACTIONGOTO步驟分析棧棧頂狀態,輸入符剩余輸入串10#-Action[0,2]=S5移進22+3*5#205#2--Action[5,+]=r6用F→digit歸約，執行語義動作F.val=2+3*5#303#F-2Action[3,+]=r4用T→F歸約，執行語義動作T.val=F.val+3*5#LR分析：增加語義棧歸約時進行語義動作。給出２＋３*５的分析和計值過程。步驟分析棧棧頂狀態,輸入符剩余輸入串402#T-2Action[2,+]=r2用E→T歸約，執行語義動作E.val=T.val+3*5#501#E-2Action[1,+]=S6移進++3*5#6016#E+-2-Action[6,3]=S5移進33*5#70165#E+3-2--Action[5,*]=r6用F→digit歸約，執行語義動作F.val=3

*5#80163

#E+F-2-3Action[3,*]=r4用T→F歸約，執行語義動作T.val=F.val

*5#90169#E+T-2-3Action[9,*]=S7移進*

*5#1001697#E+T*-2-3-Action[7,5]=S5移進5

5#11016975#E+T*5-2-3--Action[5,#]=r6用F→digit歸約,執行語義動作F.val=5#120169710#E+T*F-2-3-5Action[10,#]=r3用T→T*F歸約,執行語義動作T.val=T.val×F.val＝3×5＝15

#130169#E+T-2-15Action[9,#]=r1用E→E+T歸約,執行語義動作E.val=E.val＋T.val＝2＋15＝17

#1401#E-17Action[1,#]=acc成功接收輸入串#二.語義分析的任務

編譯程序的任務是把源程序翻譯成目標程序，這個目標程序必須和源程序的語義等同，也就是說，盡管它們的語法結構完全不同，但它們所表達的結果應完全相同。通常，在詞法分析程序和語法分析程序對源程序的語法結構進行分析之后，要么由語法分析程序直接調用相應的語義子程序進行語義處理，要么首先生成語法樹或該結構的某種表示，再進行語義處理。編譯中的語義處理是指兩個功能：審查每個語法結構的靜態語義，即驗證語法結構合法的程序是否真正有意義。有時把這個工作稱為靜態語義分析或靜態審查。如果靜態語義正確，語義處理則要執行真正的翻譯，即，要么生成程序的一種中間表示形式（中間代碼），要么生成實際的目標代碼。

通常包括：類型檢查。控制流檢查。控制流語句必須使控制轉移到合法的地方。例如，在C語言中break語句使控制跳離包括該語句的最小while、for或switch語句。如果不存在包括它的語句，則報錯。一致性檢查。在很多場合要求對象只能被定義一次。例如Pascal語言規定同一標識符在一個分程序中只能被說明一次，同一case語句的標號不能相同，枚舉類型的元素不能重復出現等等。相關名字檢查。有時，同一名字必須出現兩次或多次。例如，Ada語言程序中，循環或程序塊可以有一個名字，出現在這些結構的開頭和結尾，編譯程序必須檢查這兩個地方用的名字是相同的。名字的作用域分析。三、中間代碼翻譯為中間語言的好處：（1）便于進行與機器無關的代碼優化；（2）使編譯程序改變目標機更容易；（3）使編譯程序的結構在邏輯上更為簡單明確，以中間語言為界面，編譯前端和后端的接口更清晰。編譯程序所使用的中間代碼有多種形式。常見的有逆波蘭式、三元式和樹形、四元式表示。1.逆波蘭式逆波蘭式是最簡單的一種中間代碼表示形式，早在編譯程序出現之前，它就用于表示算術表達式，是波蘭邏輯學家盧卡西維奇發明的。這種表示法將運算對象寫在前面，把運算符號寫在后面，比如把a+b寫成ab+，把a*b寫成ab*，用這種表示法表示的表達式也稱做后綴式。示例中綴算術表達式逆波蘭式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+d*eabc*de*+=a=b*(c+b)*d/eabcb+*d*e/=后綴表示法表示表達式，其最大的優點是易于計算機處理表達式。常用的算法是使用一個棧，自左至右掃描算術表達式（后綴表示），每掃描到運算對象，就把它推進棧；掃描到運算符，若該運算符是二目的，則對棧頂部的兩個運算對象實施該運算，并將運算結果代替這兩個運算對象而進棧；若是一目運算符，則對棧頂元素執行該運算，并以運算結果代替該元素進棧，最后的結果留在棧頂。由于后綴式表示上的簡潔和計值的方便，特別適用于解釋執行的程序設計語言的中間表示，也方便具有堆棧體系的計算機的目標代碼生成。2.三元式和樹形表示另一類中間代碼形式是三元式。把表達式及各種語句表示成一組三元式。每個三元式由三個部分組成，分別是：(算符op，第一運算對象ARG1，第二運算對象ARG2)運算對象可能是源程序中的變量，也可能是某個三元式的結果，用三元式的編號表示。對于一目算符op，只需選用一個運算對象，不妨規定只用ARG1。至于多目算符，可用若干個相繼的三元式表示。

示例【例如】a=b*c+d*e的三元式表示為：

（1）（*，b，c）

（2）（*，d，e）

（3）（+，（1），（2））

（4）（＝，（3），a）樹形表示樹形表示是三元式表示的翻版。bc**+ade=3.四元式四元式是一種比較普遍采用的中間代碼形式。四元式的四個組成成分是：算符op第一運算對象ARG1第二運算對象ARG2運算結果RESULT運算對象和運算結果有時指用戶自己定義的變量，有時指編譯程序引進的臨時變量。示例四元式形式：

(op,arg1,arg2,result)【例如】a=b*c+d*e的四元式為：

（1）（*，b，c，T1）

（2）（*，d，e，T2）

（3）（+，

T1，T2，

T3）

（4）（=，T3，－，

a）四元式表示很類似于三地址指令，確實，有時把這類中間表示稱為“三地址代碼”，因為這種表示可看作一種虛擬三地址機的通用匯編碼，即這種虛擬機的每條“指令”包含操作符和三個地址，兩個是為運算對象的，一個是為結果的。這種表示對于代碼優化和目標代碼生成都較有利。示例為了更直觀，也把四元式的形式寫成簡單賦值形式或更易理解的形式：result＝arg1oparg2【例如】把上述四元式序列寫成：（1）t1=b*c（2）t2=b*d

（3）t3=t1+t2

（4）a=t3（jump，－，－，L）寫成gotoL（jrop，B，C，L）寫成ifBropCgotoL例如:A+B*(C-D)+E/(C-D)^N四、簡單賦值語句的翻譯語義過程GEN表示產生一個四元式，并且填入四元式表中。語義過程Newtemp表示生成一個臨時變量，每調用一次，生成一新的臨時變量。語義變量E．place，表示存放E值的變量名在符號表的登錄項或一整數碼（若此變量是一個臨時變量）。語義變量Entry(id)回送標識符id在符號表中的入口地址。簡單賦值語句的屬性文法產生式語義規則

S→id=E{GEN（=，E.Place，_，Entry(id)）}E→E1+E2{E.place=Newtemp；GEN(+,E1.place,E2.place,E.place)}E→E1*E2{E．place=Newtemp；GEN(*,E1.place,E2.place,E.Place)}E→－E1{E.place=Newtemp；GEN(@,E1.place,_,E.place)}E→（E1）{E.place=E1.place}E→id{E.place=Entry(id)}a=b*c+d*e的翻譯過程a=b*c+d*e

E(c)EE(b)E(d)E(e)T11.(*,b,c,T1)ET22.(*,d,e,T2)ET33.(+,T1,T2,T3)S4.(=,T3,_,a)（1）（*，b，c，T1）

（2）（*，d，e，T2）

（3）（+，T1，T2，T3）

（4）（=，T3，_，a）a=b*c+d*e的翻譯結果a=-b*(c+d)的翻譯過程略。類型轉換的語義處理實際上，在一個表達式中可能會出現各種不同類型的變量或常數。即編譯程序還應執行這樣的語義動作：對表達式中的運算對象應進行類型檢查，如不能接受不同類型的運算對象的混合運算，則應指出錯誤；如能接受混合運算，則應進行類型轉換的語義處理。例如，算術表達式可以進行實型量與整型量的混合運算，并且約定，當兩個不同類型的量進行運算時，必須首先將整型量轉換為實型量。語義變量語義變量E．type表示E的類型信息；為區別整型加（乘）和實型加（乘），把+（*）分別寫作+i（*

i）和+r（*

r）。用一目算符itr表示將整型運算對象轉換成實型。示例產生式：E→E1*E2語義動作：｛E．place=Newtemp；

ifE1.type=intANDE2.type＝int{

GEN（*i，E1.place，E2.place，E.place,）；

E．type=int}

elseifE1.type=realANDE2.type=real{

GEN(*r,E1．place,E2．place,E.place);

E.type=real}示例elseifE1.type＝int/*andE2.type=real*/{t=Newtemp；

GEN（itr，E1.place，_，t）；

GEN（*r，t，E2.place，E.place,）

E.type=real}

else/*E1·type＝realandE2．type＝int*/

{t=Newtemp；

GEN（itr，E2.place，_，t）；

GEN（*r，E1.place，t，E.place,） E．type=real｝}五、布爾表達式的翻譯程序設計語言中的布爾表達式有兩個作用。一是計算邏輯值，二是用做改變控制流語句中的條件表達式，如在if-then，if-then-else，或是while-do語句中那樣。布爾表達式是由布爾算符and，or和not施于布爾變量或關系表達式而成。即布爾表達式的形式為E1ropE2，其中E1和E2都是算術表達式，rop是關系符，如＜＝，＜，＝，〉＝，≠等等。只考慮簡單的布爾表達式文法：

E→EandE|EorE|notE|idropid|id并且按通常習慣，約定布爾算符的優先順序（從高到低）為not、and、or，并且and和or服從左結合。布爾表達式的翻譯方法通常，計算布爾表達式的值有兩種辦法，第一種辦法，如同計算算術表達式一樣，計算出各部分的真假值，最后計算出整個表達式的值。例如，用數值1表示true，用0表示false。那么布爾表達式1or（not0and0）or0的計算過程是：

1or（not0and0）or0

＝1or（1and0）or0

＝1or0or0

＝1or0

＝1布爾值的翻譯方案E→E1orE2｛E.place=Newtemp；GEN（or，E1.place，E2.place，E.place）｝E→E1andE2｛E.place=Newtemp；

GEN（and，E1.place，E2.place，E.place）｝E→notE1｛E.place=Newtemp；

GEN（not，E1.place，_，E.place）｝E→（E1）｛E.place=E1.place｝E→id1ropid2{E.place=Newtemp；GEN(jrop,Entry(id1),Entry(id2),E.place)}E→id{E.place=Entry(id)}另一種計算方法是采取某種優化措施，只計算部分表達式:AorB，若A的值為1，則無需計算B的值，因為不管B的值為何結果，AorB的值都為1。AandB，若A的值為0，則無需計算B的值，因為不管B的值為何結果，AandB的值都為0。控制語句中布爾表達式的翻譯條件控制語句ifEthenS1elseS2的目標代碼結構如下：E的代碼S1的代碼S2的代碼真假“真”出口與“假”出口布爾表達式E的作用僅在于控制對S1和S2的選擇，而無須最終保留E值，故作為轉移條件的布爾表達式E，可賦予它兩種出口：“真”出口E.TC→S1“假”出口E.FC→S2作為轉移條件的布爾表達式E，可翻譯為如下的四元式序列：（jnz,A,_,p)表示ifAgotop(jrop,A1,A2,p)表示ifA1ropA2gotop(j,_,_,p)表示gotop示例【例如】條件語句ifAorB＜CthenS1elseS2

可翻譯為：(1)(jnz,A,_,(5))(2)(j,_,_,(3))(3)(j＜,B,C,(5))(4)(j,_,_,(p+1))(5)關于S1的四元式序列……(p)(j,_,_,(q))(p+1)關于S2的四元式序列……(q)如何確定一個表達式的真假出口考慮E為E1orE2的形式：若E1為真，則E為真，所以E1的真出口就是整個E的真出口。若E1為假，則必須計算E2，E2代碼的第一個四元式標號就是E1的假出口，而E2的真出口和假出口就是整個E的真出口和假出口。如何確定一個表達式的真假出口考慮E為E1andE2的形式：若E1為假，則E為假，所以E1的假出口就是整個E的假出口。若E1為真，則必須計算E2，E2代碼的第一個四元式標號就是E1的真出口，而E2的真出口和假出口就是整個E的真出口和假出口。考慮E為notE1的形式：只需調換E1的真假出口即可得到E的真假出口。拉鏈為了記錄需回填地址的四元式，常采用一種“拉鏈”的辦法。把需回填E．TC的四元式拉成一條鏈子，把需回填E．FC的四元式拉成一條鏈子，分別稱做"真"鏈和"假"鏈。示例若有四元式序列：（10）…gotoE．TC…（20）…gotoE．TC…（30）…gotoE．TC則把需回填E.TC的四元式(10)，(20)和(30)鏈成:（10）…goto（0）…（20）…goto（10）…（30）…goto（20）把地址（30）稱作鏈首，0為鏈尾標志，即地址（10）為鏈尾。自底向上分析中的一種翻譯方案E→E1orE2(1)EA→E1or{Backpatch(E1.

FC,NXQ);EA.TC

=E1.TC}(1’)E→EAE2{E

.FC

=E2.FC;

E

.

TC=Merg(EA.

TC,E1.TC)}【說明】Backpatch(p,t):將p鏈接的四元式的第四元都回填t；Merg(p1,p2):將以p1和p2為鏈首的兩條鏈合并為一條鏈，返回時的函數值作為合并后的鏈首。E→E1andE2(2)EB→E1and{Backpatch(E1

.

TC,NXQ);EB.

FC

=E1.FC}(2’)E→EBE2{E

.

TC

=E2.TC;

E

.

FC=Merg(EB.FC,E1.FC)}(3)E→notE1{E.TC=E1.FC;E.FC=E1.TC}(4)E→(E1){E.TC=E1.TC; E.FC=E1.FC}(5)E→id1ropid2{E.TC=NXQ; E.FC=NXQ+1; GEN(jrop，Entry(id1)，Entry(id2)，0); GEN(j，_，_，0)}(6)E→id{E.TC=NXQ；E.FC=NXQ＋1; GEN(jnz，Entry(id)，_，0); GEN(j，_，_，0)}六、控制語句的翻譯考慮ifthen，ifthenelse和whiledo語句的翻譯。G[S]：S→ifEthenS

|ifEthenSelseS

|whileEdoS

|beginLend

|A

L→L；S

|S其中各非終結符號的意義是：S--語句

L--語句串A--賦值句E--布爾表達式1.條件語句if的翻譯考慮if語句的翻譯。產生式S→ifEthenS

|ifEthenSelseS

兩個問題布爾式E的"真、"假"出口尚待回填E.TC,E.FC。ifEthenS1elseS2elseS3在翻譯完S2之后，S1后的無條件轉移目標仍無法確定，因為它不僅要跨越S2還應跨越S3。即轉移目標的確定和語句所處的環境密切相關。故也可象處理布爾表達式一樣，讓非終結符S（和L）含有一項語義值S．CHAIN（和L．CHAIN）。也是一條鏈，它把所有那些四元式串在一起，這些四元式期待在翻譯完S（L）之后回填轉移目標。真正的回填工作將在處理S的外層環境的某一適當時候完成。單分支條件語句的目標結構ifEthenS1的目標代碼結構如下：E的代碼S1的代碼E.TCE.FCS1.CHAINS.CHAIN多分支條件語句的目標結構ifEthenS1elseS2的目標代碼結構如下：E的代碼S1的代碼S2的代碼E.TCE.FCjmp0S1.CHAINS2.CHAINS.CHAIN翻譯方案ifEthenS1

C→ifEthen{Backpatch(E

.

TC,NXQ);C.CHAIN=E.FC}S→CS1{S

.

CHAIN=Merg(C.CHAIN,S1.CHAIN)}ifEthenS1elseS2C→ifEthen{Backpatch(E

.

TC,NXQ);C.CHAIN=E.FC}TP→CS1else{q=NXQ;GEN(j,_,_,0);Backpatch(C.CHAIN,NXQ);TP

.

CHAIN=Merg(S1.CHAIN,q)}S→TPS2{S

.

CHAIN=Merg(TP.CHAIN,S2.CHAIN)}2.循環語句的翻譯whileEdoS1的目標代碼結構如下：E的代碼S1的代碼E.TCE.FCS1.CHAINS.CHAINjmphead翻譯方案W→while{W

.quad=NXQ}Wd→WEdo{Backpatch(E

.

TC,NXQ); Wd.CHAIN=E.FC; Wd.quad=W.quad}S→WdS1{Backpatch(S1.CHAIN,

Wd.quad);GEN(j,_,_,Wd.quad);S

.

CHAIN=Wd.quad}第一個四元式的地址示例while（A＜B）doif（C＜D）thenX=Y+Z將被翻譯成如下的一串四元式：

100(j＜,A,B,102)

101(j,_,_,107)

102(j＜,C,D,104)

103(j,_,_,100)

104(+,Y,Z,T1)

105(=,T1,_,X)

106(j,_,_,100)1073.for循環語句fori=E1stepE2untilE3doS1為了簡單起見，假定E2總是正的。在這種假定下，上述循環句的意義等價于：

i=E1；

gotoOVER；

AGAIN：i=i+E2；

OVER：ifi≤E3then

beginS1；gotoAGAINend；七、簡單說明語句的翻譯程序設計語言中的說明語句旨在定義各種形式的有名實體，如常量、變量、數組、記錄(結構)、過程、子程序等等，說明語句的種類也多，對象說明、變量說明、類型說明、過程說明等等。編譯程序把說明語句中定義的名字和性質登記在符號表中，用以檢查名字的引用和說明是否一致。許多說明語句的翻譯并不生成相應的目標代碼。過程說明和動態數組的說明有相應的代碼。簡單說明句的文法程序設計語言中最簡單的說明句的語法描述為：D→integer〈namelist〉|real〈namelist〉〈namelise〉→〈namelist〉，id|id即使用關鍵字integer和real定義一串名字的性質。對這種說明句的翻譯是指在符號表中登錄該名和性質。翻譯方案語義變量D.type：用以記錄說明句所引入的名字的性質(int還是real)；語義過程enter(id,A)：把名字id和類型A登錄在符號表中。(1)D→integerid{enter(id,int);

D.type=int}

(2)D→realid{enter(id,real);

D.type=real}

(3)D→D1,id{enter(id,D1.type);

D.type=D1.type}八、數組元素訪問的翻譯討論包括數組元素的表達式和賦值語句的翻譯問題。一個數組是由同一類型數據所組成的某種n維矩形結構。沿著每一維的距離稱為一個下標。每維的下標只能在該維的上、下限之內變動。數組的每個元素是矩形結構中的一個點，它的位置可通過給出每維的下標來確定。數組的存儲數組的存儲表示有多種形式，最簡單的一種是把整個數組按行（或按列）存放在一片連續存儲區中。例如，若A是一個2×3的二維數組，每個元素占一個單元，那么，所謂按行和按列的存儲方式分別如圖所示。有些程序語言，如FORTRAN，要求以列為序存放數組；另一些，如PL／l，要求以行為序；還有一些則取決于編譯程序設計者的意愿。數組按列存放A[1,1]A[1,2]A[1,3]A[2,1]A[2,2]A[2,3]數組按行存放A[1,1]A[2,1]A[1,2]A[2,2]A[1,3]A[2,3]計算數組元素的地址數組元素的地址計算和數組的存儲方式密切相關。在以行為序的情形下，如何計算數組元素的地址。例如，假定A是一個10×20的二維數組，各維的下限為1，每個元素占用一個機器字（令存儲器是以字編址的），數組的首地址，即A［l，1］的地址為a，那么，數組元素A［i，j］的地址為a十（i—1）×20十（j—l）或等價地表示成（a－21）＋（20×i＋j）以行為序計算數組元素的地址設A是一個ALGOLn維數組arrayA[l1：u1，l2：u2，…，ln：un]令di＝ui一1i十1，i＝1，2，…，n，a為數組的首地址，即A[l1，l2，…，ln]的地址。元素A[i1，i2，…，in]的地址D為：D＝a+(i1-l1)d2d3…dn+(i2-l2)d3d4…dn+…+(in-1-ln-1)dn+(in-ln)經因子分解后得D＝CONSPART＋VARPART其中CONSPART＝a－CC＝(…((l1d2+l2)d3+13)d4+…+ln－1)dn+lnVARPART＝(…((i1d2+i2)d3+i3)d4+…+in－1)dn+in數組元素引用的中間代碼1.將產生兩組計算數組元素地址的四元式。一組計算VARPART，并將它放在某個臨時單元T中；另一組計算CONSPART，并把它放在另一個臨時單元T1中。同時用Ti[T]表示數組元素的地址。數組元素引用的中間代碼2.對應“數組元素引用”（引用其值）和“對數組元素賦值”有兩個相應的四元式：“變址取數”和“變址存數”。“變址取數”的四元式是：（＝［］，T1［T］，_，X）即X＝T1［T］“變址存數”的四元式是：（［］＝，X1，_，T1［T］）即T1［T］＝X賦值語句中數組元素的翻譯含數組元素的賦值語句的文法為：A→V＝EV→i［<elist>］|i<elist＞→<elist>，E|EE→E＋E|（E）|V為了產生計算VARPART的四元式序列，需要如下的語義變量和過程：elist．ARRAY：表示數組名在符號表中的位置，即數組名的符號表入口。elist．DIM：下標的個數（數組維數）計數器。elist．PLACE：記存業已形成的VARPART的中間結果單元名字在符號表中的位置，或是一個臨時變量的整數碼。LIMIT（ARRAY，k）：這是一個函數過程，它給出數組ARRAY的第k維長度dk。其中，ARRAY是數組名在符號表中的位置。

說明每個變量V有兩項語義值（屬性），V．PLACE和V．OFFSET。若V是一個簡單變量名i，則V．PLACE就是指此名的符號表入口，而V．OFFSET將為null。若V是一個下標變量名i，則V．PLACE就是指保存CONSPART的臨時變量名的整數碼，而V．OFFSET則指保存VARPART的臨時變量名的整數碼。注意，null是一個特殊值，它是區分簡單變量名和下標變量名的標志。翻譯方案（1）A→V＝E｛IF（V.OFFSET=null）THEN／*V是一個簡單變量名*／GEN(=,E.PLACE,_,V.PLACE)ELSEGEN([]=,E.PLACE,_,V.PLACE[V.OFFSET])｝此處，若V是一個下標變量，那么，我們產生“變址存數”的四元式。（2）E→E1＋E2｛T＝Newtemp；GEN(+,