4編譯原理,陳意云,課后答案4

編譯原理習(xí)題課(4)2023/7/314編譯原理,陳意云,課后答案46.1使用Pascal的作用域規(guī)則，確定下面程序中用于名字a，b的每個出現(xiàn)的聲明。程序輸出整數(shù)1,2,3,4 programa(inputoutput);

procedureb(u,v,x,y:integer);

vara:recorda,b:integerend;

b:recordb,a:integerend;

begin

withadobegina:=u;b:=vend;

withbdobegina:=x;b:=yend;

writeln(a.a,a.b,b.a,b.b)

end;

begin

b(1,2,3,4)

end.2023/7/3124編譯原理,陳意云,課后答案46.1(續(xù))witha a—record

a:=u a—a.a

b:=v b—a.b

withb b—record

a:=x a—b.a

b:=y b—b.b2023/7/3134編譯原理,陳意云,課后答案46.2考慮下面的C程序

main(){

char*cp1,*cp2;

cp1=“12345”;

cp2=“abcdefghij”;

strcpy(cp1,cp2);

printf(“cp1=%s\ncp2=%s\n”,cp1,cp2);

}

該程序經(jīng)以前的某些C編譯器編譯后，運(yùn)行結(jié)果為：

cp1=abcdefghij

cp2=ghij

試分析為什么cp2被修改2023/7/3144編譯原理,陳意云,課后答案46.2(續(xù))C語言中，字符串會添加‘\0’作為串的結(jié)束符，因此，串”12345”存儲為”12345\0”，而串”12345\0abc\0”打印出來的只有12345常量區(qū)連續(xù)分配因而本題中”12345”和”abcdefghij”存儲為

12345\0abcdefghij\0

cp1cp2

拷貝后結(jié)果為

abcdefghij\0fghij\0

cp1cp2現(xiàn)代編譯器編譯通過，執(zhí)行時會出錯。(GCC:段錯誤/VC非法訪問)2023/7/3154編譯原理,陳意云,課后答案46.3一個C程序如下：

typedefstruct_a{

charc1;

longI;

charc2;

doublef;

}a;

typedefstruct_b{

charc1;

charc2;

longl;

doublef;

}b;

main(){

printf(“Sizeofdouble,long,char=%d,%d,%d\n”,sizeof(double),sizeof(long),sizeof(char));

printf(“Sizeofa,b=%d,%d\n”,sizeof(a),sizeof(b));

}

該程序在SPARC/Solaris工作站上運(yùn)行結(jié)果如下：

Sizeofdouble,long,char=8,4,1

Sizeofa,b=24,16

試分析為什么2023/7/3164編譯原理,陳意云,課后答案46.3(續(xù))數(shù)據(jù)對齊：為了尋址方便A：

char OXXX

long OOOO

char OXXXXXXX

double OOOOOOOOB:

char O

char OXX

long OOOO

double OOOOOOOO可以用gcc–S命令查看編譯后的匯編碼

VC下可以在debug模式下，菜單欄View->DebugWindows中Dissassenbly查看編譯后的匯編碼GCC:(GNU)3.2.2(RedHatLinux3.2.2-5)結(jié)果為20,162023/7/3174編譯原理,陳意云,課后答案46.3(續(xù))#include<stdio.h>

staticstruct_a{

charc1;

longi;

charc2;

doublef;

}a={'A',1,'B',1.0};VC6下，Debug模式Memory窗口查看

GCC:(GNU)3.2.220030222(RedHatLinux3.2.2-5)|A|1|B|1.0|2023/7/3184編譯原理,陳意云,課后答案46.4下面給出一個C程序及其在X86/Linux下的編譯結(jié)果，根據(jù)所生成的匯編程序來解釋程序中4個變量的存儲分配、作用域、生成期和置初始值方式的區(qū)別

staticlongaa=10;

shortbb=20;

func(){

staticlongcc=30;

shortdd=40;

}

生成的匯編代碼：2023/7/3194編譯原理,陳意云,課后答案46.4(續(xù)).file"static.c“.version“01.01”gcc2_compiled:.data.align4.typeaa,@object.sizeaa,4aa:.long10.globlbb.align2.typebb,@object.sizebb,2bb:.value20.align4 .typecc.2,@object.sizecc.2,4cc.2:.long30.text .align4.globlfunc.typefunc,@functionfunc:pushl%ebpmovl%esp,%ebpsubl$4,%espmovw$40,-2(%ebp).L1:leaveret.Lfe1:.sizefunc,.Lfe1-func.ident"GCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)”2023/7/31104編譯原理,陳意云,課后答案46.4(續(xù)).file"static.c“.version“01.01”gcc2_compiled:.data.align4.typeaa,@object.sizeaa,4aa: --aa分配在靜態(tài)數(shù)據(jù)區(qū)，作用域?yàn)楸疚募?，生存期為整個程序

.long10–aa靜態(tài)置初值.globlbb--bb分配在靜態(tài)數(shù)據(jù)區(qū)，作用域?yàn)槿?，可以被其他文件引用，生存期為整個程序

.align2.typebb,@object.sizebb,2bb:.value20–bb靜態(tài)置初值

.align4 .typecc.2,@object.sizecc.2,4cc.2:--cc分配在靜態(tài)數(shù)據(jù)區(qū)，作用域?yàn)楸疚募?，生存期為整個程序。源程序中在函數(shù)內(nèi)部，為防止重名，需要重命名為cc.2.long30–cc靜態(tài)置初值

.text .align4.globlfunc.typefunc,@functionfunc:pushl%ebpmovl%esp,%ebpsubl$4,%espmovw$40,-2(%ebp)--dd分配在棧上,生存期為func調(diào)用期，動態(tài)置初值.L1:leaveret.Lfe1:.sizefunc,.Lfe1-func.ident"GCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)”2023/7/31114編譯原理,陳意云,課后答案46.5假定使用:(a)值調(diào)用;(b)引用調(diào)用;(c)值-結(jié)果調(diào)用;(d)換名調(diào)用。下面程序的結(jié)果分別是什么？

programmain(input,output);

vara,b:integer;

procedurep(x,y,z:integer);

begin

y:=y+1;

z:=z+x;

end;

begin

a:=2;

b:=3;

p(a+b,a,a);

printa;

end.2023/7/31124編譯原理,陳意云,課后答案46.5(續(xù))值調(diào)用

x:=5;y:=2;z:=2;

y:=y+1;z:=z+x; 對形參的調(diào)用不改變實(shí)參的值，結(jié)果a為2引用調(diào)用

t:=a+b;

a=a+1;

a=a+t; 結(jié)果a為8值-結(jié)果調(diào)用

t:=a+b;

x:=t;y:=a;z:=a

y:=y+1;z:=z+x;

t:=x;a:=y;a:=z; 結(jié)果為7換名調(diào)用

a:=a+1;

a:=a+(a+b); 結(jié)果為92023/7/31134編譯原理,陳意云,課后答案46.6一個C程序如下:

func(i1,i2,i3)

longi1,i2,i3;

{

longj1,j2,j3;

printf(“Addressofi1i2i3=%o,%o,%o\n”,&i1,&i2,&i3);

printf(“Addressofj1j2j3=%o,%o,%o\n”,&j1,&j2,&j3);

}

main(){

longi1,i2,i3;

func(i1,i2,i3);

}

該程序在X86/Linux上運(yùn)行結(jié)果為：

Addressofi1,i2,i3=27777775460,27777775464,27777775470

Addressofj1,j2,j3=27777775444,27777775440,27777775434

從結(jié)果看func的3個形參地址逐漸升高，而3個局部變量地址逐漸降低。試說明為什么2023/7/31144編譯原理,陳意云,課后答案46.6(續(xù))C語言中，實(shí)參從右向左進(jìn)棧，所以func(i1,i2,i3)按i3，i2，i1的順序進(jìn)棧而j1,j2,j3按聲明的順序分配2023/7/31154編譯原理,陳意云,課后答案46.7下面的C程序中，printf的調(diào)用僅含格式控制串，運(yùn)行時輸出3個參數(shù)，分析之

main(){

printf(“%d%d%d\n”);

}2023/7/31164編譯原理,陳意云,課后答案46.7(續(xù))C語言不做實(shí)參和形參個數(shù)類型是否一致的檢查printf函數(shù)根據(jù)第一個參數(shù)—格式控制列表，到棧中取參數(shù)本題中雖然只傳了格式控制列表，但是printf函數(shù)分析格式控制列表，認(rèn)為程序員還傳了3個整型數(shù)，因此繼續(xù)去棧中取3個參數(shù)，并輸出之。所以得到了三個不可預(yù)知值得整數(shù)。2023/7/31174編譯原理,陳意云,課后答案46.8下面給出一個C程序及其在X86/Linux下的編譯結(jié)果。從結(jié)果看，func的四個局部變量i1，j1，f1，e1的地址間隔和他們的類型一致，而形參i，j，f，e的地址間隔和他們的類型不一致，試分析原因

func(i,j,f,e)

shorti,j;floatf,e;

{

shorti1,j1;floatf1,e1;

printf(“Addressofi,j,f,e=%o,%o,%o,%o\n”,&i,&j,&f,&e);

printf(“Addressofi1,j1,f1,e1=%o,%o,%o,%o\n”,&i1,&j1,&f1,&e1);

printf(“Addressofshort,int,long,float,double=%d,%d,%d,%d,%d\n”,sizeof(short),sizeof(int),sizeof(long),sizeof(float),sizeof(double));

}

main(){

shorti,j;floatf,e;

func(i,j,f,e);

}

運(yùn)行結(jié)果：

Addressofi,j,f,e=35777772536,35777772542,35777772544,35777772554

Addressofi1,j1,f1,e1=35777772426,35777772426,35777772424,35777772420,35777772414

Sizeofshort,int,long,float,double=2,4,4,4,82023/7/31184編譯原理,陳意云,課后答案46.8(續(xù))C語言為了不保證實(shí)參和形參類型一致，因此為了盡可能保證得到正確結(jié)果，編譯器在整型和實(shí)型做實(shí)參時，將他們提升為long和double傳遞。但是函數(shù)內(nèi)部取參數(shù)時，仍按照原來的類型去取2023/7/31194編譯原理,陳意云,課后答案46.8(續(xù))main傳參數(shù)時，提升數(shù)據(jù)類型func取參數(shù)時，按原來的數(shù)據(jù)類型i:short->int4字節(jié)j:short->int4字節(jié)f:long->double8字節(jié)e:long->double8字節(jié)i:short2字節(jié)j:short2字節(jié)f:long4字節(jié)e:long4字節(jié)2023/7/31204編譯原理,陳意云,課后答案46.9一個C程序

func(c,l)

charc;longl;

{

func(c,l);

}

在x86/Linux上編譯生成的匯編代碼如下，請說明char和long在參數(shù)傳遞和存儲分配上的區(qū)別2023/7/31214編譯原理,陳意云,課后答案46.9(續(xù)).file"parameter.c“.version“01.01”gcc2_compiled.:.text.align4.globlfunc.typefunc,@functionfunc:pushl%ebp--將老的基址指針壓棧

movl%esp,%ebp--將當(dāng)前棧頂指針作為基址

subl$4,%esp--分配空間

movl8(%ebp),%eaxmovb%al,-1(%ebp)movl12(%ebp),%eaxpushl%eaxmovsbl-1(%ebp),%eax

pushl%eaxcallfuncaddl$8,%esp.L1:leaveret.Lfe1:.sizefunc,.Lfe1-func.ident"GCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)”2023/7/31224編譯原理,陳意云,課后答案46.9(續(xù))SomeAT&TASMSyntax寄存器：

8個32-bit寄存器%eax，%ebx，%ecx，%edx，%edi，%esi，%ebp，%esp；操作符源目的-1(%ebp)：基址：%ebp，偏移：-1加在指令后的符號表示操作數(shù)的長度：

b(byte,8-bit)

w(word,16-bits)

l(long,32-bits)movsbl：

movs：符號擴(kuò)展指令

movsbl意味著movs（from）byte（to）long；movbw意味著movs（from）byte（to）word；movswl意味著movs（from）word（to）long。More:plzgoogle“AT&T

ASM”2023/7/31234編譯原理,陳意云,課后答案46.9(續(xù))movl8(%ebp),%eax --取cmovb%al,-1(%ebp) --取其字節(jié)值，存入分配的存儲單元movl12(%ebp),%eax--取lpushl%eax --l壓棧movsbl-1(%ebp),%eax--取c，并轉(zhuǎn)換成longpushl%eax --c壓棧callfunc --調(diào)用funcaddl$8,%esp --恢復(fù)壓棧前狀態(tài)2023/7/31244編譯原理,陳意云,課后答案46.10從例6.5可以看到,C程序執(zhí)行時只用到了控制鏈,不需要使用訪問鏈.為什么Parscal程序執(zhí)行時需要使用訪問鏈,而C程序不需要?2023/7/31254編譯原理,陳意云,課后答案46.10(續(xù))PASCAL允許過程嵌套，執(zhí)行時，可以訪問非全局且非局部的變量，所以需要訪問鏈幫助確定數(shù)據(jù)所在活動記錄在棧中的位置

而C不允許過程嵌套，只能訪問全局和局部變量，所以不需要訪問鏈。2023/7/31264編譯原理,陳意云,課后答案46.11下面是求階乘的Pascal程序.畫出程序第三次進(jìn)入函數(shù)factor時的活動記錄棧和靜態(tài)鏈.

programfact(input,output);

varf,n:integer;

functionfactor(n:integer):integer;

begin

ifn=0thenfactor:=1

elsefactor:=n*(factor(n-1))

end;

beginn:=5;f:=factor(n);write(f)

end.2023/7/31274編譯原理,陳意云,課后答案46.11(續(xù))factf,nfactor訪問鏈nfactor訪問鏈nfactor訪問鏈n1222023/7/31284編譯原理,陳意云,課后答案46.12在下面假想的程序中,第(11)行語句f:=a調(diào)用函數(shù)a,a傳遞函數(shù)addm作為返回值.

(a)畫出該程序執(zhí)行的活動樹.

(b)假定非局部名字使用靜態(tài)作用域,為什么該程序在棧式分配情況下不能正確工作?

(c)在堆分配策略下,該程序的輸出是什么?2023/7/31294編譯原理,陳意云,課后答案46.12(續(xù))programret(input,output); varf:function(integer):integer; functiona:function(integer):integervarm:integer;functionaddm(n:integer):integerbeginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2))end;beginf:=a;b(f)end2023/7/31304編譯原理,陳意云,課后答案46.12(續(xù))活動樹如右圖在執(zhí)行addm時，只有ret，b和addm的活動記錄，a的已釋放。如果是靜態(tài)作用域，n對應(yīng)的是第(4)行中的m，他處于a的活動記錄中，而此時a的已釋放。堆分配結(jié)果是2retabaddm2023/7/31314編譯原理,陳意云,課后答案46.13為什么C語言允許函數(shù)類型(的指針)作為函數(shù)的返回值類型,而Pascal語言卻不允許?2023/7/31324編譯原理,陳意云,課后答案46.13(續(xù))參考6.12課本P2022023/7/31334編譯原理,陳意云,課后答案46.14一個C語言程序如下:

intn;

intf(intg){

intm;

m=n;

if(m==0) return1;

else{

n=n-1;returnm*f(n);

}

}

main(){

n=5;printf(“%dfactorialis%d\n”,n,f(n));

}

該程序的運(yùn)行結(jié)果不是我們所期望的

5factorialis120

而是

0factorialis120

試說明原因.2023/7/31344編譯原理,陳意云,課后答案46.14(續(xù))參數(shù)逆序進(jìn)棧，因此，f(n)先被執(zhí)行，而f(n)執(zhí)行結(jié)束時，n值已經(jīng)被改寫為0，此時再將n值壓棧，因而輸出“0factorialis120”2023/7/31354編譯原理,陳意云,課后答案46.15下面程序在SPARC/SUN工作站上運(yùn)行時陷入死循環(huán),試說明原因.如果將第7行的long*p改成short*p,并且將第22行l(wèi)ongk改成shortk后,loop中的循環(huán)體執(zhí)行一次便停止了.試說明原因.

main(){

addr();

loop();

}

long*p;

loop(){

longi,j;

j=0;

for(i=0;i<10;i++){

(*p)--;

j++;

}

}

addr(){

longk;

k=0;

p=&k;

}2023/7/31364編譯原理,陳意云,課后答案46.15(續(xù))程序運(yùn)行時陷入死循環(huán)的原因是由于ｐ指向分配給i的存儲單元引起的。循環(huán)體執(zhí)行一次便停止時由于p指向分配給i的高位字節(jié)引起的。C語言的實(shí)現(xiàn)是采用棧式分配，使得函數(shù)addr和函數(shù)loop的活動記錄先后從同樣的存儲單元開始分配，從而長整數(shù)k和i先后分配在同樣的存儲單元，因此p指向分配給i的存儲單元。SPARC/SUN工作站上整數(shù)的存放方式是低地址放高位字節(jié)，而高地址放低位字節(jié)。另外，活動記錄棧是從高地址向低地址方向增長。當(dāng)k改為短整型且p改為短整型指針后，那么p指向由i的兩個低位字節(jié)組成的短整數(shù)。執(zhí)行(*p)--使得這兩個字節(jié)構(gòu)成的短整數(shù)等于-1。而從整個4個字節(jié)看時，是65535，遠(yuǎn)大于10。所以循環(huán)體執(zhí)行一次便停止。2023/7/31374編譯原理,陳意云,課后答案46.16一個C語言程序

main()

{

func();

printf(“Returnfromfunc\n”);

}

func()

{

chars[4];

strcpy(s,”12345678”);

printf(“%s\n”,s);

}

在X86/Linux操作系統(tǒng)上的運(yùn)行結(jié)果如下:

12345678

Returnfromfunc

Segmentationfault(coredumped)

試分析為什么會出現(xiàn)這樣的運(yùn)行錯誤.2023/7/31384編譯原理,陳意云,課后答案46.16(續(xù))數(shù)組越界訪問。出現(xiàn)短錯誤，說明控制鏈被破壞func可以返回main說明func的返回地址沒有被破壞，而main不能返回，說明main的返回地址被破壞本題RedHatLinux3.2.