编译原理-陈意云--课后答案.ppt

编译原理习题课编译原理习题课(4)栾 俊5/26/20245/26/20241.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.5/26/20242.6.1(续续)with aarecorda:=uaa.ab:=vba.bwith bbrecorda:=xab.ab:=ybb.b5/26/20243.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被修改5/26/20244.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 非法访问)5/26/20245.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试分析为什么5/26/20246.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,165/26/20247.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 20030222(Red Hat Linux 3.2.2-5)|A|1|B|1.0|5/26/20248.6.4下面给出一个C程序及其在X86/Linux下的编译结果，根据所生成的汇编程序来解释程序中4个变量的存储分配、作用域、生成期和置初始值方式的区别static long aa=10;short bb=20;func()static long cc=30;short dd=40;生成的汇编代码：5/26/20249.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)”5/26/202410.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)”5/26/202411.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.5/26/202412.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);结果为95/26/202413.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从结果看func的3个形参地址逐渐升高，而3个局部变量地址逐渐降低。试说明为什么5/26/202414.6.6(续续)C语言中，实参从右向左进栈，所以func(i1,i2,i3)按i3，i2，i1的顺序进栈而j1,j2,j3按声明的顺序分配5/26/202415.6.7下面的C程序中，printf的调用仅含格式控制串，运行时输出3个参数，分析之main()printf(“%d%d%dn”);5/26/202416.6.7(续续)C语言不做实参和形参个数类型是否一致的检查printf函数根据第一个参数格式控制列表，到栈中取参数本题中虽然只传了格式控制列表，但是printf函数分析格式控制列表，认为程序员还传了3个整型数，因此继续去栈中取3个参数，并输出之。所以得到了三个不可预知值得整数。5/26/202417.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,85/26/202418.6.8(续续)C语言为了不保证实参和形参类型一致，因此为了尽可能保证得到正确结果，编译器在整型和实型做实参时，将他们提升为long和double传递。但是函数内部取参数时，仍按照原来的类型去取5/26/202419.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字节5/26/202420.6.9一个C程序func(c,l)char c;long l;func(c,l);在x86/Linux上编译生成的汇编代码如下，请说明char和long在参数传递和存储分配上的区别5/26/202421.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)”5/26/202422.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 google “AT&TASM”5/26/202423.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-恢复压栈前状态5/26/202424.6.10从例6.5可以看到,C程序执行时只用到了控制链,不需要使用访问链.为什么Parscal程序执行时需要使用访问链,而C程序不需要?5/26/202425.6.10(续续)PASCAL允许过程嵌套，执行时，可以访问非全局且非局部的变量，所以需要访问链帮助确定数据所在活动记录在栈中的位置而C不允许过程嵌套，只能访问全局和局部变量，所以不需要访问链。5/26/202426.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.5/26/202427.6.11(续续)factf,nfactor访问链nfactor访问链nfactor访问链n1225/26/202428.6.12在下面假想的程序中,第(11)行语句f:=a调用函数a,a传递函数addm作为返回值.(a)画出该程序执行的活动树.(b)假定非局部名字使用静态作用域,为什么该程序在栈式分配情况下不能正确工作?(c)在堆分配策略下,该程序的输出是什么?5/26/202429.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)end5/26/202430.6.12(续续)活动树如右图在执行addm时，只有ret，b和addm的活动记录，a的已释放。如果是静态作用域，n对应的是第(4)行中的m，他处于a的活动记录中，而此时a的已释放。堆分配结果是2retabaddm5/26/202431.6.13为什么C语言允许函数类型(的指针)作为函数的返回值类型,而Pascal语言却不允许?5/26/202432.6.13(续续)参考6.12课本P2025/26/202433.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试说明原因.5/26/202434.6.14(续续)参数逆序进栈，因此，f(n)先被执行，而f(n)执行结束时，n值已经被改写为0，此时再将n值压栈，因而输出“0 factorial is 120”5/26/202435.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;5/26/202436.6.15(续续)程序运行时陷入死循环的原因是由于指向分配给i的存储单元引起的。循环体执行一次便停止时由于p指向分配给i的高位字节引起的。C语言的实现是采用栈式分配，使得函数addr和函数loop的活动记录先后从同样的存储单元开始分配，从而长整数k和i先后分配在同样的存储单元，因此p指向分配给i的存储单元。SPARC/SUN 工作站上整数的存放方式是低地址放高位字节，而高地址放低位字节。另外，活动记录栈是从高地址向低地址方向增长。当k改为短整型且p改为短整型指针后，那么p指向由i的两个低位字节组成的短整数。执行(*p)-使得这两个字节构成的短整数等于-1。而从整个4个字节看时，是65535，远大于10。所以循环体执行一次便停止。5/26/202437.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)试分析为什么会出现这样的运行错误.5/26/202438.6.16(续续)数组越界访问。出现短错误，说明控制链被破坏func可以返回main说明func的返回地址没有被破坏，而main不能返回，说明main的返回地址被破坏本题Red Hat Linux 3.2.2/GCC:(GNU)3.2.2下结果为12345678段错误main返回地址被破坏5/26/202439.6.17一个过程作为实在参数传递,它被激活时的计算环境有三种可能的规定.第一种是使用词法环境,即该过程激活时的计算环境是依据其定义点的静态作用域得到.Pascal和C都是使用这种方式.第二种是使用传递环境,即该过程激活时的计算环境是依据其作为实在参数的调用点的静态作用域得到.第三种可能是使用活动环境,即该过程激活时的计算环境是依据其激活点的静态作用域得到.我们以下面的Pascal程序为例来解释.考虑该程序第(11)行f作为实在参数传递的情况,对应上面三种规定,第(8)行的非局部名m分别在第(6)(10)和(13)行的作用域内.在这三种情况下,该程序的输出分别是什么?5/26/202440.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.5/26/202441.6.17(续续)词法环境：定义点m值为0，结果为2传递环境：第11行，c的过程体把f作为参数传给b，此时m值为7，因此结果为9；活动环境：第4行，在b的过程体中，h(2)激活f，此时m值为3，因此结果为5；5/26/202442.谢谢！谢谢！5/26/202443.