第4章靜態(tài)語義分析(3)計算機(jī)科學(xué)與技術(shù)學(xué)院國家示范性軟件學(xué)院1聲明語句的作用:

為可執(zhí)行語句提供信息，以便于其執(zhí)行。

(操作對象的性質(zhì)，如數(shù)據(jù)類型、值、作用域等)對聲明語句的處理，主要是將所需要的信息正確地填寫進(jìn)合理組織的符號表中。4.5.1變量聲明與翻譯4.5.3過程聲明與翻譯4.5聲明語句的翻譯課堂中討論的內(nèi)容：2<1>變量的類型定義與聲明

類型定義：為編譯器提供存儲空間大小(寬度)的信息；變量聲明(定義)：為變量分配存儲空間；復(fù)合類型的定義&變量聲明：

定義與聲明在一起;定義與聲明分離。1.簡單類型(基本類型)變量的存儲空間大小是預(yù)先確定的，如int可以占4個字節(jié)，double可以占8個字節(jié)，char可以占1個字節(jié)等。2.復(fù)合類型變量的存儲空間大小，需要編譯器根據(jù)具體的類型定義進(jìn)行計算而定。4.5.1變量的聲明類型定義與變量聲明分離：typePlayer=array[1..3]ofinteger;

Matrix=array[1..24]ofarray[1..8]ofchar;varc,p:Player;winner:boolean;display:Matrix;movect:integer;3類型定義與變量聲明在一起：varc,p:array[1..3]ofinteger;display:array[1..24]ofarray[1..8]ofchar;例：Pascal程序中的類型定義與變量聲明：C程序（例4.28）：typedefintPlayer[3];Playerc,p;------------------intc[3],p[3];4.5.1變量的聲明4變量聲明的文法注：(5)是數(shù)組類型的聲明，(6)是指針類型的聲明；數(shù)組元素的類型、指針?biāo)笇ο蟮念愋涂梢允?/p>

任意合法類型。2.[num]

等價于

[..num]3.數(shù)組寬度：num

*sizeof(T)4.指針寬度：常數(shù)G4.6D→D;D (1)|id:T (2)T→int (3)|real (4)|array[num]ofT(5)

|^T (6)幾點(diǎn)說明：1.int/real的寬度：常數(shù)<2>變量聲明的語法制導(dǎo)翻譯4.5.1變量的聲明5A:array[d1]ofarray[d2]of...array[dn]ofintT→array[num]ofT(5)此文法所描述的多維數(shù)組“以行為主”存儲。一個N維數(shù)組的聲明形式：A2: array[2]of array[3]ofintA2[1]A2[2]A2[1,1]A2[1,2]A2[1,3]A2[2,1]A2[2,2]A2[2,3]4.5.1變量的聲明①文法符號屬性的設(shè)計②必要的輔助程序的設(shè)計③語義規(guī)則的設(shè)計61.全局量offset：記錄當(dāng)前變量存儲地址(偏移量,初值為0)2.屬性.type、.width：變量的類型、所占據(jù)的存儲空間大小3.過程enter(name,type,offset)：為type類型的變量name

建立符號表條目，并為變量分配存儲空間(位置)offset4.array(n,type)生成數(shù)組類型，pointer(type)生成指針類型(1)D→D;D(2)D→id:T(3)T→int(4)T→real(5)T→array[num]ofT1(6)T→^T1{enter(,T.type,offset);offset=offset+T.width;}{T.type=integer;T.width=4;}{T.type=real;T.width=8;}{T.type=array(num.val,T1.type);T.width=num.val*T1.width;}{T.type=pointer(T1.type);T.width=8;}

4.5.1變量的聲明7例4.27

變量聲明的翻譯(LR分析)：

a:array[10]ofint;x:int符號表aarray(10,integer)0xinteger404.5.1變量的聲明(1)D→D;D(2)D→id:T(3)T→int(4)T→real(5)T→array[num]ofT1(6)T→^T1{enter(,T.type,offset);offset=offset+T.width;}{T.type=integer;T.width=4;}{T.type=real;T.width=8;}{T.type=array(num.val,T1.type);T.width=num.val*T1.width;}{T.type=pointer(T1.type);T.width=8;}

8序號歸約用的產(chǎn)生式 語義處理結(jié)果(1)T1→int T1.type=integerT1.width=4(2)T2→array[num]ofT1 T2.type=array(10,integer) T2.width=10*4=40(3)D1→id:T2 enter(a,array(10),0)offset=40(4)T3→int T3.type=integerT3.width=4(5)D2→id:T3 enter(x,integer,40)offset=44(6)D3→D1;D2無4.5.1變量的聲明91．過程（procedure）：

過程頭(做什么)＋過程體(怎么做)；函數(shù):有返回值的過程。主程序:被運(yùn)行時系統(tǒng)調(diào)用的過程。2．過程的三種形式：過程定義、過程聲明和過程調(diào)用。過程定義=過程頭+過程體過程聲明=過程頭本節(jié)重點(diǎn)討論過程的規(guī)格說明、過程體內(nèi)聲明的處理本節(jié)將過程定義和過程聲明統(tǒng)稱為過程聲明。4.5.3過程的定義與聲明10若過程引用在前、定義在后(或在其他源文件)，則必須在調(diào)用點(diǎn)之前先聲明該過程。若過程定義在前、引用在后，則聲明可省略。procedure

swap(x,y:inoutinteger)--規(guī)格說明

is --過程體開始

temp:integer;--體中的聲明

begintemp:=x;x:=y;y:=temp;--可執(zhí)行語句

endswap; --過程體結(jié)束例：Ada過程聲明定義：聲明與調(diào)用：procedureswap(x,y:inoutinteger);--過程聲明swap(a,b); --過程調(diào)用4.5.3過程的定義與聲明先聲明后引用原則：11直觀上，出現(xiàn)在賦值號左邊和右邊的量分別稱為左值和右值。 如C語句： a=2實質(zhì)上，左值:一個量的內(nèi)存地址(必須具有存儲空間)。右值:一個量的值(可以僅有值而沒有存儲空間)。形象地講，左值是容器，右值是內(nèi)容。

左值與右值

4.5.3過程的定義與聲明12(1)constinttwo=2; //聲明一個值為2的常量two(2)intx; //聲明一個整型變量

x(3)intmax(inta,intb);

//聲明一個返回整數(shù)的函數(shù)max

//返回a和b中的較大者(4)x=two; //

將x的值修改為

2(5)x=two+x;

//

將x的值修改為

4(6)x=max(two,x)+x; //

將x的值修改為

8(7)4=x;

//錯誤：字面量不能作為左值(8)two=x; //錯誤：常量不能作為左值(9)max(two,x)=two; //錯誤：函數(shù)返回值不能作為左值(10)x+two=x+two; //錯誤：表達(dá)式的值不能作為左值4.5.3過程的定義與聲明

左值與右值

13形參與實參聲明時的參數(shù)稱為形參(parameter或formalparameter)調(diào)用時的參數(shù)稱為實參(argument或actualparameter)常見的參數(shù)傳遞形式：（不同的語言提供不同的形式）值調(diào)用（call/passbyvalue）引用調(diào)用（call/passbyreference）復(fù)寫－恢復(fù)（copy-incopy-out）換名調(diào)用（call/passbyname）參數(shù)傳遞方式的本質(zhì)區(qū)別：實參是代表左值?右值?實參本身的正文?4.5.3過程的定義與聲明

參數(shù)傳遞14實參的特點(diǎn)：任何可以作為右值的對象均可作為實參。參數(shù)傳遞和過程內(nèi)對參數(shù)的使用原則：①過程定義中，形參被當(dāng)作局部量看待，并在過程內(nèi)部為形參分配存儲單元；②調(diào)用過程前，首先計算實參并將其值（實參的右值）放入(copy)形參的存儲單元；③過程內(nèi)部對形參單元中的數(shù)據(jù)直接訪問。值調(diào)用的特點(diǎn)：過程內(nèi)部對形參的修改，

不影響實參（還是原來的值）。53

參數(shù)傳遞<1>值調(diào)用15voidswap(intx,inty){inttemp=x;x=y;y=temp;}值調(diào)用舉例，C程序：

參數(shù)傳遞<1>值調(diào)用intmain(){inta=1;b=2;printf("before:a=%db=%d\n",a,b);

swap(a,b);printf("after:a=%db=%d\n",a,b);return0;}16實參的特點(diǎn)：必須是左值。參數(shù)傳遞和過程內(nèi)對參數(shù)的使用原則：①

過程定義中，形參被當(dāng)作局部量看待，并在過程內(nèi)部為形參分配存儲單元；②

調(diào)用過程前，將實參變量的地址放進(jìn)(copy)形參的存儲單元；③

過程內(nèi)把形參單元中的數(shù)據(jù)當(dāng)作地址，間接訪問。引用調(diào)用的特點(diǎn)：過程內(nèi)部對形參的修改，

實質(zhì)上是對實參的修改。35

參數(shù)傳遞<2>引用調(diào)用17#include<iostream>usingnamespacestd;voidswap(intx,inty){inttemp=x;x=y;y=temp;}intmain(){inta=1,b=2;cout<<"before:a="<<a<<"b="<<b<<endl;

swap(a,b);cout<<"after:a="<<a<<"b="<<b<<endl;return0;}&&

參數(shù)傳遞<2>引用調(diào)用值調(diào)用舉例，C++程序：voidswap(int&x,int&y){inttemp=x;x=y;y=temp;}swap(a,b);18intmain(){inta(1),b(2);printf("before:a=%db=%d\n",a,b);

swap(&a,&b);printf("after:a=%db=%d\n",a,b);return0;}voidswap(int*x,int*y){inttemp=*x;*x=*y;*y=temp;}例：C沒有引用調(diào)用，但可用值調(diào)用模擬引用調(diào)用的效果：

參數(shù)傳遞<2>引用調(diào)用usingnamespacestd;intmain(){

add_one(a);cout<<"a="<<a<<endl;return0;}19#include<iostream>inta=2;引用調(diào)用的副作用（程序?qū)嵗┍疽猓篴=3

2+1結(jié)果：voidadd_one(int&x){}a=a+2;x=x+1;<3>復(fù)寫-恢復(fù)調(diào)用

參數(shù)傳遞a=5Why?

參數(shù)傳遞20<3>復(fù)寫-恢復(fù)調(diào)用實參的特點(diǎn)：必須是左值。參數(shù)傳遞和過程內(nèi)對參數(shù)的使用原則：①過程定義中，形參被當(dāng)作局部量看待，并在過程內(nèi)部為形參分配單元；②調(diào)用過程前，首先計算實參并將值(實參的右值)放入形參的存儲單元(復(fù)寫，copy-in)；③

過程內(nèi)部對形參單元中的數(shù)據(jù)直接訪問；④過程返回前，將形參的右值放回實參的存儲單元(恢復(fù)，copy-out)。3值調(diào)用21proceduretestisa:integer;begina:=2;add_one(a);put_line('a=',a);//輸出是？

endtest;procedureadd_one(x:inoutinteger)isbegina:=a+2;//結(jié)果？x:=x+1;//結(jié)果？endadd_one;復(fù)寫-恢復(fù)調(diào)用舉例，Ada程序：

參數(shù)傳遞<3>復(fù)寫-恢復(fù)調(diào)用a:2

4x:2

3a=322換名調(diào)用由Algol60的復(fù)寫規(guī)則定義：①過程被看作宏，對過程的調(diào)用進(jìn)行宏展開(宏替換)：－用過程體替換過程調(diào)用，－用實參的文本替換體中的形參。②

應(yīng)區(qū)分被調(diào)用過程的局部名和調(diào)用過程的局部名。③

當(dāng)需要保持實參的完整性時，可以為實參加括弧。C/C++中的換名調(diào)用：用

#define給出宏定義，并在預(yù)處理階段進(jìn)行宏替換(但預(yù)處理不關(guān)心上述②)。

經(jīng)過宏替換之后的程序中，已經(jīng)不存在(宏)過程的調(diào)用與參數(shù)傳遞，它的特點(diǎn)是運(yùn)行速度快。

參數(shù)傳遞<4>換名調(diào)用23//換名調(diào)用演示程序……奇怪的副作用

BUG#include<stdio.h>intmain(){inta=1,b[]={0,0};printf("before:a=%db=%d,%d\n",a,b[0],b[1]);swap(a,b[a]);//expect:a=0,b[1]=1printf("after:a=%db=%d,%d\n",a,b[0],b[1]);return0;}//#defineswap(x,y){inttemp=x;x=y;y=temp;}//宏定義正文替換的結(jié)果（C示例）：{inttemp=a;a=b[a];b[a]=temp;}//宏展開10b[0]=1

參數(shù)傳遞<4>換名調(diào)用24與換名調(diào)用一樣高效（避免了函數(shù)調(diào)用）；不存在換名調(diào)用的副作用、可能的BUG。//宏定義#defineswap(x,y){inttemp=x;x=y;y=temp;}C++的編程建議：內(nèi)聯(lián)函數(shù)//普通函數(shù)voidswap(int&x,int&y){inttemp=x;x=y;y=temp;}

參數(shù)傳遞<4>換名調(diào)用//內(nèi)聯(lián)函數(shù)inline

voidswap(int&x,int&y){inttemp=x;x=y;y=temp;}25與程序塊類似，在允許嵌套定義過程的程序設(shè)計語言中，相同的名字可以同時出現(xiàn)在不同的作用域中，因此有必要討論如何設(shè)計符號表來存放它們。此處討論的過程作用域，也遵守（§4.4給出的）

靜態(tài)作用域規(guī)則和

最近嵌套規(guī)則。<1>過程(名)的作用域

作用域信息的保存26funcsort(){vara:VArray<Int,$10>;varx:Int=0;…funcreadarray(){vari:Int=0;…a[i]…}funcexchange

(i:Int,j:Int){…a[i]…}funcquicksort(m:Int,n:Int):Unit{vari:

Int;varv:Int;funcpartition(lo:Int,hi:Int){vari:Int=lo;varj:Int=hi;……}//endpartition()……}//endquicksort()readarray();quicksort(0,a.size-1);}//endsort()

作用域信息的保存例4.34

快排序程序（倉頡語言版）：

27//省略形參、數(shù)據(jù)類型、操作性語句funcsort：

vara;varx;funcreadarray：

vari;funcexchange;funcquicksort：vari;varv;funcpartition:vari;varj;

作用域信息的保存定義4.4

設(shè)主程序(最外層過程)的嵌套深度dmain=1，<1>若過程A內(nèi)直接嵌套定義過程B，則dB

=dA

+1；<2>變量的嵌套深度=變量聲明時所在過程的嵌套深度。過程及其中變量的嵌套深度過程 變量嵌套深度sort a,xreadarray i exchange quicksort i,v partition i,j 1222328//省略形參、數(shù)據(jù)類型、操作性語句funcsort：

vara;varx;funcreadarray：

vari;funcexchange;funcquicksort：vari;varv;funcpartition:vari;varj;

作用域信息的保存過程及其中變量的嵌套深度過程 變量嵌套深度sort a,xreadarray i exchange quicksort i,v partition i,j 12223過程嵌套關(guān)系的直觀表示在將名字存到符號表的同時，如何體現(xiàn)作用域信息？29名字作用域信息的保存，可以用具有嵌套結(jié)構(gòu)的符號表來實現(xiàn)：

(1)每個過程對應(yīng)一個符號表，即樹中的一個結(jié)點(diǎn)。

(2)嵌套關(guān)系用樹中的父子關(guān)系表示：父子結(jié)點(diǎn)之間可以用雙向鏈表連接，其中正向的鏈(父

子）指示過程之間的嵌套關(guān)系，而逆向的鏈(子

父)用來實現(xiàn)按作用域?qū)γ值脑L問。過程嵌套關(guān)系的直觀表示符號表嵌套關(guān)系的直觀表示(a,x)(i,v)(i)(i,j)<2>符號表中保存作用域信息符號表樹（樹型符號表）30例4.35

忽略參數(shù)的快排序程序的符號表：雙向鏈表：正向

－嵌套定義關(guān)系逆向

－可見性關(guān)系思考：參數(shù)如何處理？(a,x)(i,v)(i)(i,j)<2>符號表中保存作用域信息31P→D (1)D→D;D (2)|id:T (3)|funcid;D;S (4)

問題：如何在處理產(chǎn)生式(1)和(4)的語言結(jié)構(gòu)時正確地構(gòu)造并填寫符號表信息（雙向鏈表）？修改文法，使得在分析D之前生成符號表（LR分析）：P→

M

D (1)D→D;D (2)|id:T (3)G4.9|funcid;N

D;S (4)M→ε

(5)N→ε (6)G4.8

（忽略了參數(shù)）(a)簡化的過程定義文法<3>語法制導(dǎo)翻譯生成符號表32全程量：有序?qū)＃╰blptr,offset）其中，tblptr保存指向符號表結(jié)點(diǎn)的指針，

offset保存對應(yīng)過程的所有局部量

的存儲空間大小。棧上的操作：push(t,o)、pop、top(分量名)符號表嵌套關(guān)系的直觀表示(a,x)(i,v)(i)(i,j)(b)全程量、屬性與語義函數(shù)<3>語法制導(dǎo)翻譯生成符號表33全程量：有序?qū)＃╰blptr,offset）其中，tblptr保存指向符號表結(jié)點(diǎn)的指針，

offset保存對應(yīng)過程的所有局部量

的存儲空間大小。棧上的操作：push(t,o)、pop、top(分量名)語義函數(shù)/過程：1.函數(shù)mktable(previous)：建立一個新的符號表結(jié)點(diǎn)，并返回指向該結(jié)點(diǎn)的指針。參數(shù)previous是逆向鏈，指向該結(jié)點(diǎn)的父親(即直接外層的符號表結(jié)點(diǎn))。<3>語法制導(dǎo)翻譯生成符號表(b)全程量、屬性與語義函數(shù)342.過程enter(table,name,type,offset)：

在table指向的符號表中，為變量name建立對應(yīng)的條目，包括名字的類型、存儲位置等。3.過程addwidth(table,width)：

計算table指向的符號表中

所有變量條目的累加寬度，

并記錄在該表的頭部。<3>語法制導(dǎo)翻譯生成符號表(b)全程量、屬性與語義函數(shù)354.過程enterproc(table,name,newtable)：

在table指向的符號表中，為過程name建立對應(yīng)的條目。

參數(shù)newtable是正向鏈，指向過程name自身的符號表。<3>語法制導(dǎo)翻譯生成符號表(b)全程量、屬性與語義函數(shù)父結(jié)點(diǎn)子結(jié)點(diǎn)36(1)P→MD(2)M→ε(3)D→D;D(4)D→id:T(5)D→funcid;ND1;S(6)N→ε

{t=mktable(null);push(t,0);}{t=mktable(top(tblptr));push(t,0);}{enter(top(tblptr),,T.type,top(offset));top(offset)=top(offset)+T.width;}{t=top(tblptr);addwidth(t,top(offset));

pop;

enterproc(top(tblptr),,t);}{addwidth(top(tblptr),top(offset));pop;}(