编译原理陈意云课后答案市公开课一等奖百校联赛获奖课件.pptx

编译原理习题课编译原理习题课(4)栾 俊10/10/10/10/第1页6.1使用Pascal作用域规则，确定下面程序中用于名字a，b每个出现申明。程序输出整数1,2,3,4 program a(input output);procedure b(u,v,x,y:integer);var a:record a,b:integer end;b:record b,a:integer end;begin with a do begin a:=u;b:=v end;with b do begin a:=x;b:=y end;writeln(a.a,a.b,b.a,b.b)end;begin b(1,2,3,4)end.10/10/第2页6.1(续续)with aarecorda:=uaa.ab:=vba.bwith bbrecorda:=xab.ab:=ybb.b10/10/第3页6.2考虑下面C程序 main()char*cp1,*cp2;cp1=“12345”;cp2=“abcdefghij”;strcpy(cp1,cp2);printf(“cp1=%s n cp2=%s n”,cp1,cp2);该程序经以前一些C编译器编译后，运行结果为：cp1=abcdefghij cp2=ghij 试分析为何cp2被修改10/10/第4页6.2(续续)C语言中，字符串会添加0作为串结束符，所以，串”12345”存放为”123450”，而串”123450abc0”打印出来只有12345常量区连续分配因而本题中”12345”和”abcdefghij”存放为1 2 3 4 5 0 a b c d e f g h i j 0cp1 cp2拷贝后结果为a b c d e f g h i j 0 f g h i j 0cp1 cp2当代编译器编译经过，执行时会犯错。(GCC:段错误/VC 非法访问)10/10/第5页6.3一个C程序以下：typedef struct _a char c1;long I;char c2;double f;a;typedef struct _b char c1;char c2;long l;double f;b;main()printf(“Size of double,long,char=%d,%d,%dn”,sizeof(double),sizeof(long),sizeof(char);printf(“Size of a,b=%d,%dn”,sizeof(a),sizeof(b);该程序在SPARC/Solaris工作站上运行结果以下：Size of double,long,char=8,4,1Size of a,b=24,16试分析为何10/10/第6页6.3(续续)数据对齐：为了寻址方便A：charOXXXlongOOOOcharOXXX XXXXdoubleOOOO OOOOB:charOcharOXXlongOOOO doubleOOOO OOOO能够用gcc S命令查看编译后汇编码VC下能够在debug模式下，菜单栏View-Debug Windows中 Dissassenbly查看编译后汇编码GCC:(GNU)3.2.2(Red Hat Linux 3.2.2-5)结果为20,1610/10/第7页6.3(续续)#include static struct _achar c1;long i;char c2;double f;a =A,1,B,1.0;VC6下，Debug模式Memory窗口查看GCC:(GNU)3.2.2 0222(Red Hat Linux 3.2.2-5)|A|1|B|1.0|10/10/第8页6.4下面给出一个C程序及其在X86/Linux下编译结果，依据所生成汇编程序来解释程序中4个变量存放分配、作用域、生成期和置初始值方式区分static long aa=10;short bb=20;func()static long cc=30;short dd=40;生成汇编代码：10/10/第9页6.4(续续).file static.c“.version“01.01”gcc2_compiled:.data .align 4 .type aa,object .size aa,4aa:.long 10.globl bb .align 2 .type bb,object .size bb,2bb:.value 20 .align 4 .type cc.2,object .size cc.2,4cc.2:.long 30 .text .align 4.globl func .type func,functionfunc:pushl%ebp movl%esp,%ebp subl$4,%esp movw$40,-2(%ebp).L1:leave ret.Lfe1:.size func,.Lfe1-func .ident GCC:(GNU)egcs-2.91.66 19990314/Linux(egcs-1.1.2 release)”10/10/第10页6.4(续续).file static.c“.version“01.01”gcc2_compiled:.data .align 4 .type aa,object .size aa,4aa:-aa分配在静态数据区，作用域为本文件，生存期为整个程序 .long 10 aa静态置初值.globl bb -bb分配在静态数据区，作用域为全局，能够被其它文件引用，生存期为整个程序 .align 2 .type bb,object .size bb,2bb:.value 20 bb静态置初值 .align 4 .type cc.2,object .size cc.2,4cc.2:-cc分配在静态数据区，作用域为本文件，生存期为整个程序。源程序中在函数内部，为预防重名，需要重命名为cc.2 .long 30 cc静态置初值 .text .align 4.globl func .type func,functionfunc:pushl%ebp movl%esp,%ebp subl$4,%esp movw$40,-2(%ebp)-dd分配在栈上,生存期为func调用期，动态置初值.L1:leave ret.Lfe1:.size func,.Lfe1-func .ident GCC:(GNU)egcs-2.91.66 19990314/Linux(egcs-1.1.2 release)”10/10/第11页6.5假定使用:(a)值调用;(b)引用调用;(c)值-结果调用;(d)换名调用。下面程序结果分别是什么？program main(input,output);var a,b:integer;procedure p(x,y,z:integer);begin y:=y+1;z:=z+x;end;begin a:=2;b:=3;p(a+b,a,a);print a;end.10/10/第12页6.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:=ay:=y+1;z:=z+x;t:=x;a:=y;a:=z;结果为7换名调用a:=a+1;a:=a+(a+b);结果为910/10/第13页6.6一个C程序以下:func(i1,i2,i3)long i1,i2,i3;long j1,j2,j3;printf(“Address of i1 i2 i3=%o,%o,%on”,&i1,&i2,&i3);printf(“Address of j1 j2 j3=%o,%o,%on”,&j1,&j2,&j3);main()long i1,i2,i3;func(i1,i2,i3);该程序在X86/Linux上运行结果为：Address of i1,i2,i3=27777775460,27777775464,27777775470Address of j1,j2,j3=27777775444,27777775440,27777775434从结果看func3个形参地址逐步升高，而3个局部变量地址逐步降低。试说明为何10/10/第14页6.6(续续)C语言中，实参从右向左进栈，所以func(i1,i2,i3)按i3，i2，i1次序进栈而j1,j2,j3按申明次序分配10/10/第15页6.7下面C程序中，printf调用仅含格式控制串，运行时输出3个参数，分析之main()printf(“%d%d%dn”);10/10/第16页6.7(续续)C语言不做实参和形参个数类型是否一致检验printf函数依据第一个参数格式控制列表，到栈中取参数本题中即使只传了格式控制列表，不过printf函数分析格式控制列表，认为程序员还传了3个整型数，所以继续去栈中取3个参数，并输出之。所以得到了三个不可预知值得整数。10/10/第17页6.8下面给出一个C程序及其在X86/Linux下编译结果。从结果看，func四个局部变量i1，j1，f1，e1地址间隔和他们类型一致，而形参i，j，f，e地址间隔和他们类型不一致，试分析原因func(i,j,f,e)short i,j;float f,e;short i1,j1;float f1,e1;printf(“Address of i,j,f,e=%o,%o,%o,%on”,&i,&j,&f,&e);printf(“Address of i1,j1,f1,e1=%o,%o,%o,%on”,&i1,&j1,&f1,&e1);printf(“Address of short,int,long,float,double=%d,%d,%d,%d,%dn”,sizeof(short),sizeof(int),sizeof(long),sizeof(float),sizeof(double);main()short i,j;float f,e;func(i,j,f,e);运行结果：Address of i,j,f,e=35777772536,35777772542,35777772544,35777772554Address of i1,j1,f1,e1=35777772426,35777772426,35777772424,35777772420,35777772414Size of short,int,long,float,double=2,4,4,4,810/10/第18页6.8(续续)C语言为了不确保实参和形参类型一致，所以为了尽可能确保得到正确结果，编译器在整型和实型做实参时，将他们提升为long和double传递。不过函数内部取参数时，仍按照原来类型去取10/10/第19页6.8(续续)main传参数时，提升数据类型func取参数时，按原来数据类型i:short-int4字节j:short-int4字节f:long-double8字节e:long-double8字节i:short 2字节j:short 2字节f:long 4字节e:long 4字节10/10/第20页6.9一个C程序func(c,l)char c;long l;func(c,l);在x86/Linux上编译生成汇编代码以下，请说明char和long在参数传递和存放分配上区分10/10/第21页6.9(续续).file parameter.c“.version“01.01”gcc2_compiled.:.text .align 4.globl func .type func,functionfunc:pushl%ebp -将老基址指针压栈 movl%esp,%ebp -将当前栈顶指针作为基址 subl$4,%esp -分配空间 movl 8(%ebp),%eax movb%al,-1(%ebp)movl 12(%ebp),%eax pushl%eax movsbl-1(%ebp),%eax pushl%eax call func addl$8,%esp.L1:leave ret.Lfe1:.size func,.Lfe1-func .ident GCC:(GNU)egcs-2.91.66 19990314/Linux(egcs-1.1.2 release)”10/10/第22页6.9(续续)Some AT&T ASM Syntax 存放器：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:plz 谷歌 “AT&TASM”10/10/第23页6.9(续续)movl 8(%ebp),%eax-取cmovb%al,-1(%ebp)-取其字节值，存入分配存放单元movl 12(%ebp),%eax-取lpushl%eax-l压栈movsbl-1(%ebp),%eax-取c，并转换成longpushl%eax-c压栈call func-调用funcaddl$8,%esp-恢复压栈前状态10/10/第24页6.10从例6.5能够看到,C程序执行时只用到了控制链,不需要使用访问链.为何Parscal程序执行时需要使用访问链,而C程序不需要?10/10/第25页6.10(续续)PASCAL允许过程嵌套，执行时，能够访问非全局且非局部变量，所以需要访问链帮助确定数据所在活动统计在栈中位置而C不允许过程嵌套，只能访问全局和局部变量，所以不需要访问链。10/10/第26页6.11下面是求阶乘Pascal程序.画出程序第三次进入函数factor时活动统计栈和静态链.program fact(input,output);var f,n:integer;function factor(n:integer):integer;beginif n=0 then factor:=1else factor:=n*(factor(n-1)end;begin n:=5;f:=factor(n);write(f)end.10/10/第27页6.11(续续)factf,nfactor访问链nfactor访问链nfactor访问链n12210/10/第28页6.12在下面假想程序中,第(11)行语句f:=a调用函数a,a传递函数addm作为返回值.(a)画出该程序执行活动树.(b)假定非局部名字使用静态作用域,为何该程序在栈式分配情况下不能正确工作?(c)在堆分配策略下,该程序输出是什么?10/10/第29页6.12(续续)(1)program retret(input,output);(2)var f:function(integer):integer;(3)function a a:function(integer):integer(4)var m:integer;(5)function addmaddm(n:integer):integer(6)begin return m+n end;(7)begin m:=0;return addm end;(8)procedure b b(g:function(integer):integer);(9)begin writeln(g(2)end;(10)begin(11)f:=a;b(f)(12)end10/10/第30页6.12(续续)活动树如右图在执行addm时，只有ret，b和addm活动统计，a已释放。假如是静态作用域，n对应是第(4)行中m，他处于a活动统计中，而此时a已释放。堆分配结果是2retabaddm10/10/第31页6.13为何C语言允许函数类型(指针)作为函数返回值类型,而Pascal语言却不允许?10/10/第32页6.13(续续)参考6.12书本P20210/10/第33页6.14一个C语言程序以下:int n;int f(int g)int m;m=n;if(m=0)return 1;elsen=n-1;return m*f(n);main()n=5;printf(“%d factorial is%dn”,n,f(n);该程序运行结果不是我们所期望 5 factorial is 120而是 0 factorial is 120试说明原因.10/10/第34页6.14(续续)参数逆序进栈，所以，f(n)先被执行，而f(n)执行结束时，n值已经被改写为0，此时再将n值压栈，因而输出“0 factorial is 120”10/10/第35页6.15下面程序在SPARC/SUN工作站上运行时陷入死循环,试说明原因.假如将第7行 long*p改成 short*p,而且将第22行 long k改成short k后,loop中循环体执行一次便停顿了.试说明原因.main()addr();loop();long*p;loop()long i,j;j=0;for(i=0;i10;i+)(*p)-;j+;addr()long k;k=0;p=&k;10/10/第36页6.15(续续)程序运行时陷入死循环原因是因为指向分配给i存放单元引发。循环体执行一次便停顿时因为p指向分配给i高位字节引发。C语言实现是采取栈式分配，使得函数addr和函数loop活动统计先后从一样存放单元开始分配，从而长整数k和i先后分配在一样存放单元，所以p指向分配给i存放单元。SPARC/SUN 工作站上整数存放方式是低地址放高位字节，而高地址放低位字节。另外，活动统计栈是从高地址向低地址方向增加。当k改为短整型且p改为短整型指针后，那么p指向由i两个低位字节组成短整数。执行(*p)-使得这两个字节组成短整数等于-1。而从整个4个字节看时，是65535，远大于10。所以循环体执行一次便停顿。10/10/第37页6.16一个C语言程序 main()func();printf(“Return from func n”);func()char s4;strcpy(s,”12345678”);printf(“%sn”,s);在X86/Linux操作系统上运行结果以下:12345678 Return from func Segmentation fault(core dumped)试分析为何会出现这么运行错误.10/10/第38页6.16(续续)数组越界访问。出现短错误，说明控制链被破坏func能够返回main说明func返回地址没有被破坏，而main不能返回，说明main返回地址被破坏本题Red Hat Linux 3.2.2/GCC:(GNU)3.2.2下结果为12345678段错误main返回地址被破坏10/10/第39页6.17一个过程作为实在参数传递,它被激活时计算环境有三种可能要求.第一个是使用词法环境,即该过程激活时计算环境是依据其定义点静态作用域得到.Pascal和C都是使用这种方式.第二种是使用传递环境,即该过程激活时计算环境是依据其作为实在参数调用点静态作用域得到.第三种可能是使用活动环境,即该过程激活时计算环境是依据其激活点静态作用域得到.我们以下面Pascal程序为例来解释.考虑该程序第(11)行f作为实在参数传递情况,对应上面三种要求,第(8)行非局部名m分别在第(6)(10)和(13)行作用域内.在这三种情况下,该程序输出分别是什么?10/10/第40页6.17(续续)(1)program param(input,output);(2)procedure b(function h(n:integer):integer);(3)var m:integer;(4)begin m:=3;writeln(h(2)end;b(5)procedure c;(6)var m:integer;(7)function f(n:integer):integer;(8)begin f:=m+n end;f(9)procedure r;(10)var m:integer;(11)begin m:=7;b(f)end;r(12)begin m:=0;r end;c(13)begin(14)c(15)end.10/10/第41页6.17(续续)词法环境：定义点m值为0，结果为2传递环境：第11行，c过程体把f作为参数传给b，此时m值为7，所以结果为9；活动环境：第4行，在b过程体中，h(2)激活f，此时m值为3，所以结果为5；10/10/第42页谢谢！谢谢！10/10/第43页