4编译原理,陈意云,课后答案4

编译原理习题课(4)2023/7/314编译原理,陈意云,课后答案46.1使用Pascal的作用域规则，确定下面程序中用于名字a，b的每个出现的声明。程序输出整数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(续)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);

}

该程序经以前的某些C编译器编译后，运行结果为：

cp1=abcdefghij

cp2=ghij

试分析为什么cp2被修改2023/7/3144编译原理,陈意云,课后答案46.2(续)C语言中，字符串会添加‘\0’作为串的结束符，因此，串”12345”存储为”12345\0”，而串”12345\0abc\0”打印出来的只有12345常量区连续分配因而本题中”12345”和”abcdefghij”存储为

12345\0abcdefghij\0

cp1cp2

拷贝后结果为

abcdefghij\0fghij\0

cp1cp2现代编译器编译通过，执行时会出错。(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工作站上运行结果如下：

Sizeofdouble,long,char=8,4,1

Sizeofa,b=24,16

试分析为什么2023/7/3164编译原理,陈意云,课后答案46.3(续)数据对齐：为了寻址方便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)结果为20,162023/7/3174编译原理,陈意云,课后答案46.3(续)#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下的编译结果，根据所生成的汇编程序来解释程序中4个变量的存储分配、作用域、生成期和置初始值方式的区别

staticlongaa=10;

shortbb=20;

func(){

staticlongcc=30;

shortdd=40;

}

生成的汇编代码：2023/7/3194编译原理,陈意云,课后答案46.4(续).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(续).file"static.c“.version“01.01”gcc2_compiled:.data.align4.typeaa,@object.sizeaa,4aa: --aa分配在静态数据区，作用域为本文件，生存期为整个程序

.long10–aa静态置初值.globlbb--bb分配在静态数据区，作用域为全局，可以被其他文件引用，生存期为整个程序

.align2.typebb,@object.sizebb,2bb:.value20–bb静态置初值

.align4 .typecc.2,@object.sizecc.2,4cc.2:--cc分配在静态数据区，作用域为本文件，生存期为整个程序。源程序中在函数内部，为防止重名，需要重命名为cc.2.long30–cc静态置初值

.text .align4.globlfunc.typefunc,@functionfunc:pushl%ebpmovl%esp,%ebpsubl$4,%espmovw$40,-2(%ebp)--dd分配在栈上,生存期为func调用期，动态置初值.L1:leaveret.Lfe1:.sizefunc,.Lfe1-func.ident"GCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)”2023/7/31114编译原理,陈意云,课后答案46.5假定使用:(a)值调用;(b)引用调用;(c)值-结果调用;(d)换名调用。下面程序的结果分别是什么？

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:=5;y:=2;z:=2;

y:=y+1;z:=z+x; 对形参的调用不改变实参的值，结果a为2引用调用

t:=a+b;

a=a+1;

a=a+t; 结果a为8值-结果调用

t:=a+b;

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

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

t:=x;a:=y;a:=z; 结果为7换名调用

a:=a+1;

a:=a+(a+b); 结果为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上运行结果为：

Addressofi1,i2,i3=27777775460,27777775464,27777775470

Addressofj1,j2,j3=27777775444,27777775440,27777775434

从结果看func的3个形参地址逐渐升高，而3个局部变量地址逐渐降低。试说明为什么2023/7/31144编译原理,陈意云,课后答案46.6(续)C语言中，实参从右向左进栈，所以func(i1,i2,i3)按i3，i2，i1的顺序进栈而j1,j2,j3按声明的顺序分配2023/7/31154编译原理,陈意云,课后答案46.7下面的C程序中，printf的调用仅含格式控制串，运行时输出3个参数，分析之

main(){

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

}2023/7/31164编译原理,陈意云,课后答案46.7(续)C语言不做实参和形参个数类型是否一致的检查printf函数根据第一个参数—格式控制列表，到栈中取参数本题中虽然只传了格式控制列表，但是printf函数分析格式控制列表，认为程序员还传了3个整型数，因此继续去栈中取3个参数，并输出之。所以得到了三个不可预知值得整数。2023/7/31174编译原理,陈意云,课后答案46.8下面给出一个C程序及其在X86/Linux下的编译结果。从结果看，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);

}

运行结果：

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(续)C语言为了不保证实参和形参类型一致，因此为了尽可能保证得到正确结果，编译器在整型和实型做实参时，将他们提升为long和double传递。但是函数内部取参数时，仍按照原来的类型去取2023/7/31194编译原理,陈意云,课后答案46.8(续)main传参数时，提升数据类型func取参数时，按原来的数据类型i:short->int4字节j:short->int4字节f:long->double8字节e:long->double8字节i:short2字节j:short2字节f:long4字节e:long4字节2023/7/31204编译原理,陈意云,课后答案46.9一个C程序

func(c,l)

charc;longl;

{

func(c,l);

}

在x86/Linux上编译生成的汇编代码如下，请说明char和long在参数传递和存储分配上的区别2023/7/31214编译原理,陈意云,课后答案46.9(续).file"parameter.c“.version“01.01”gcc2_compiled.:.text.align4.globlfunc.typefunc,@functionfunc:pushl%ebp--将老的基址指针压栈

movl%esp,%ebp--将当前栈顶指针作为基址

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(续)SomeAT&TASMSyntax寄存器：

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

b(byte,8-bit)

w(word,16-bits)

l(long,32-bits)movsbl：

movs：符号扩展指令

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(续)movl8(%ebp),%eax --取cmovb%al,-1(%ebp) --取其字节值，存入分配的存储单元movl12(%ebp),%eax--取lpushl%eax --l压栈movsbl-1(%ebp),%eax--取c，并转换成longpushl%eax --c压栈callfunc --调用funcaddl$8,%esp --恢复压栈前状态2023/7/31244编译原理,陈意云,课后答案46.10从例6.5可以看到,C程序执行时只用到了控制链,不需要使用访问链.为什么Parscal程序执行时需要使用访问链,而C程序不需要?2023/7/31254编译原理,陈意云,课后答案46.10(续)PASCAL允许过程嵌套，执行时，可以访问非全局且非局部的变量，所以需要访问链帮助确定数据所在活动记录在栈中的位置

而C不允许过程嵌套，只能访问全局和局部变量，所以不需要访问链。2023/7/31264编译原理,陈意云,课后答案46.11下面是求阶乘的Pascal程序.画出程序第三次进入函数factor时的活动记录栈和静态链.

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(续)factf,nfactor访问链nfactor访问链nfactor访问链n1222023/7/31284编译原理,陈意云,课后答案46.12在下面假想的程序中,第(11)行语句f:=a调用函数a,a传递函数addm作为返回值.

(a)画出该程序执行的活动树.

(b)假定非局部名字使用静态作用域,为什么该程序在栈式分配情况下不能正确工作?

(c)在堆分配策略下,该程序的输出是什么?2023/7/31294编译原理,陈意云,课后答案46.12(续)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(续)活动树如右图在执行addm时，只有ret，b和addm的活动记录，a的已释放。如果是静态作用域，n对应的是第(4)行中的m，他处于a的活动记录中，而此时a的已释放。堆分配结果是2retabaddm2023/7/31314编译原理,陈意云,课后答案46.13为什么C语言允许函数类型(的指针)作为函数的返回值类型,而Pascal语言却不允许?2023/7/31324编译原理,陈意云,课后答案46.13(续)参考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));

}

该程序的运行结果不是我们所期望的

5factorialis120

而是

0factorialis120

试说明原因.2023/7/31344编译原理,陈意云,课后答案46.14(续)参数逆序进栈，因此，f(n)先被执行，而f(n)执行结束时，n值已经被改写为0，此时再将n值压栈，因而输出“0factorialis120”2023/7/31354编译原理,陈意云,课后答案46.15下面程序在SPARC/SUN工作站上运行时陷入死循环,试说明原因.如果将第7行的long*p改成short*p,并且将第22行longk改成shortk后,loop中的循环体执行一次便停止了.试说明原因.

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(续)程序运行时陷入死循环的原因是由于ｐ指向分配给i的存储单元引起的。循环体执行一次便停止时由于p指向分配给i的高位字节引起的。C语言的实现是采用栈式分配，使得函数addr和函数loop的活动记录先后从同样的存储单元开始分配，从而长整数k和i先后分配在同样的存储单元，因此p指向分配给i的存储单元。SPARC/SUN工作站上整数的存放方式是低地址放高位字节，而高地址放低位字节。另外，活动记录栈是从高地址向低地址方向增长。当k改为短整型且p改为短整型指针后，那么p指向由i的两个低位字节组成的短整数。执行(*p)--使得这两个字节构成的短整数等于-1。而从整个4个字节看时，是65535，远大于10。所以循环体执行一次便停止。2023/7/31374编译原理,陈意云,课后答案46.16一个C语言程序

main()

{

func();

printf(“Returnfromfunc\n”);

}

func()

{

chars[4];

strcpy(s,”12345678”);

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

}

在X86/Linux操作系统上的运行结果如下:

12345678

Returnfromfunc

Segmentationfault(coredumped)

试分析为什么会出现这样的运行错误.2023/7/31384编译原理,陈意云,课后答案46.16(续)数组越界访问。出现短错误，说明控制链被破坏func可以返回main说明func的返回地址没有被破坏，而main不能返回，说明main的返回地址被破坏本题RedHatLinux3.2.