编译原理课后习题答案ch9

《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站1第9章符号表第1题：根据你所了解的某个FORTRAN语言的实现版本，该语言的名字作用域有哪几种?答案：FORTRAN中，名字作用域有四种：1在BLOCKDATA块中定义的标识符，其作用域是整个程序。2在COMMON块中定义的标识符，其作用域是声明了该COMMON块的所有例程（包括函数和过程）。3在例程中定义的标识符（包括哑变量），其作用域是声明该标识符的例程。4在例程中用SAVE定义的标识符，其作用域是声明该标识符的例程，且在退出该例程时，该标识符的值仍保留（即内部静态量）。第2题：C语言中规定变量标识符的定义可分为extern,externstatic,auto,localstatic和register五种存储类：(1)对五种存储类所定义的每种变量，分别说明其作用域。(2)试给出适合上述存储类变量的内存分配方式。(3)符号表中登录的存储类属性，在编译过程中支持什么样的语义检查。答案：(1)extern定义的变量，其作用域是整个C语言程序。externstatic定义的变量，其作用域是该定义所在的C程序文件。auto定义的变量，其作用域是该定义所在的例程。localstatic定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保留。register定义的变量，其作用域与auto定义的变量一样。这种变量的值，在寄存器有条件时，可存放在寄存器中，以提高运行效率。(2)对extern变量，设置一个全局的静态公共区进行分配。对externstatic变量，为每个C程序文件，分别设置一个局部静态公共区进行分配。对auto和register变量，设定它们在该例程的动态区中的相对区头的位移量。而例程动态区在运行时再做动态分配。对localstatic变量，为每个具有这类定义的例程，分别设置一个内部静态区进行分配。(3)实施标识符变量重复定义合法性检查，及引用变量的作用域范围的合法性检查。《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站2第3题：对分程序结构的语言，为其符号表建立重名动态下推链的目的是什么?概述编译过程中重名动态下推链的工作原理。答案：重名动态下推链的目的是，保证在合法重名定义情况下，提供完整确切的符号表项，从而保证引用变量的上下文合法性检查和非法重名定义检查。其工作原理是：当发生合法重名定义时，将上层重名表项下推到链中，而在符号标中原重名表项处登录当前重名定义的符号属性；在退出本层时，将昀近一次下推的表项，回推登录到符号表中原重名表项处。第4题：某BASIC语言的变量名字表示为字母开头的字母或数字两个字节的标识符，该语言的符号表拟采用杂凑法组织，请为其设计实现一个有效散列的杂凑算法，并为解决散列冲突，设计实现一个再散列算法。答案：可采用下列散列杂凑算法（设表长为N）散列地址=MOD（（第一字节值+第二字节值），N）。发生冲突时再散列的方法：在该冲突处开始，向下寻找第一个空表项，若找到则该表项地址为再散列地址；若找不到空表项，则循环到表头开始，向下寻找第一个空表项，一直到发生冲突处为止，若找到空表项则该表项地址为再散列地址，否则表示符号表已满，编译系统给出符号表溢出信息，终止编译。《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站3附加题问题1：利用Pascal的作用域规则，试确定在下面的Pascal程序中的名字a和b的每一次出现所应用的说明。programm(input,output);proceduren(u,v,x,y:integer);varm:recordm,n:intergerend;n:recordn,m:intergerend;beginwithmdobeginm:=u;n:=vend;withndobeginm:=x;n:=yend;writeln(m.m,m.n,n.m,n.n)end;beginm(1,2,3,4)end.答案：图中用蓝色数字下标相应标明。programm1(input,output);proceduren1(u,v,x,y:integer);varm2:recordm3,n2:intergerend;n3:recordn4,m4:intergerend;beginwithm2dobeginm3:=u;n2:=vend;withn3dobeginm4:=x;n4:=yend;writeln(m2.m3,m2.n2,n3.m4,n3.n4)end;beginm1(1,2,3,4)end.问题2：当一个过程作为参数被传递时，我们假定有以下三种与此相联系的环境可以考虑，下面的Pascal程序是用来说明这一问题的。一种是词法环境（lexicalenvironment），如此这样的一个过程的环境是由这一过程定义之处的各标识符的联编所构成；一种是传递环境（passingenvironment），是由这一过程作为参数被传递之处的各标识《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站4符的联编所构成；另一种是活动环境（activationenvironment），是由这一过程活动之处的各标识符的联编所构成。试考虑在第（11）行上的作为一个参数被传递的函数f。利用对于f的词法环境、传递环境和活动环境，在第（8）行上的非局部量m将分别处在第（6）行、（10）行和（3）行上的m的说明的作用域中。（a）图示出每个过程的活动记录。（b）试为此程序画出活动树。（c）试给出程序的输出。(1)programparam(inout,output);(2)procedureb(functionh(n:integer):integer);(3)varm:integer;(4)beginm:=3;writeln(h(2))end{b};(5)procedurec;(6)varm:integer;(7)functionf(n:integer):integer;(8)beginf:=m+nend{f};(9)procedurer;(10)varm:integer;(11)beginm:=7;b(f)end{r};(12)beginm:=0;rend{c};(13)begin(14)c(15)end.答案：（a）词法环境paramammn=2mcrbf,f访问链控制链访问链控制链访问链控制链访问链控制链访问链控制链《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站5传递环境活动环境paramc访问链bf,控制链mn=2访问链访问链控制链访问链控制链访问链m控制链控制链rmfparamammn=2mcrbf,f访问链控制链访问链控制链访问链控制链访问链控制链访问链控制链《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站6（b）活动树（c）词法环境：2；传递环境：9；活动环境：5。问题3：己知程序段：BEGINintegeri;read(i);write(value=,func(i));...ENDintegerprocedurefunc(N)integerN；BEGINIFN==0THENfunc=1;ELSEIFN==1,THENfunc=1；ELSEfunc=N*func(N-1)END;求当输入i=3时，本程序执行期间对运行栈的存储分配图。答案：paramcrb(f)f(2)访问链paramfunc访问链funcN=1控制链N=2func控制链控制链控制链访问链N=3访问链《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站7问题4：某语言允许过程嵌套定义和递归调用(如Pascal语言)，若在栈式动态存储分配中采用嵌套层次显示表display解决对非局部变量的引用问题，试给出下列程序执行到语句“b：＝10；”时运行栈及display表的示意图。varx，y；PROCEDUREP；vara;PROCEDUREq；varb：BEGIN{q}b：＝10；END{q};PROCEDUREs;varc，d；PROCEDUREr;vare,f;BEGIN{r}callq；END{r}；BEGIN{s}callr；END{s}；BEGIN{p}calls;END{p}；BEGIN{main}callp；END{main}．《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站8答案：《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站9问题5：试问下面的程序将有怎样的输出？分别假定：（a）传值调用（call-by-value）；（b）引用调用（call-by-reference）；（c）复制恢复（copy-restore）；（d）传名调用（call-by-name）。programmain(input,output);procedurep(x,y,z);beginy:=y+1;z:=z+x;end;begina:=2;b:=3;p(a+b,a,a);printaend.答案：1)．传地址：所谓传地址是指把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一对应的单元，称为形式单元。形式单元将用来存放相应的实在参数的地址。当调用一个过程时，调用段必须领先把实在参数的地址传递到一个为被调用段可以拿得到的地方。当程序控制转入被调用段之后，被调用段首先把实参地址捎进自己相应的形式单元中，过程体对形式参数的任何引用1或赋值都被处理成对形式单元的间接访问。当调用段工作完毕返回时，形式单元(它们都是指示器)所指的实在参数单元就持有所指望的值。2)．传结果：和“传地址”相似(但不等价)的另一种参数传递力法是所谓“传结果”。这种方法的实质是，每个形式参数对应有两个申元，第1个单元存放实参的地址，第2个单元存放实参的值。在过程体中对形参的任何引用或赋值都看成是对它的第2个单元的直接访问。但在过程工作完毕返回前必须把第2个单元的内容行放到第1个单元所指的那个实参单元之中。3)．传值：所谓传值，是一种简单的参数传递方法。调用段把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始丁作时，首先把这些值抄入形式中元中，然后就好像使用局部名一样使用这些形式单元。如果实在参数不为指示器，那末，在被调用段中无法改变实参的值。4)．传名：所谓传名，是一种特殊的形——实参数结合方式。解释“传名”参数的意义：过程调用的作用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形式参数都替换成相应的实在参数(文字替换)。它与采用“传地址”或“传值”的方式所产生的结果均不相同。(a)2；(b)8；(c)7；(d)9。《编译原理》课后习题答案第九章盛威网（）专业的计算机学习网站10问题6：下面程序的结果是120，但是如果把第11行的abs(1)改成1的话，则程序结果是1,分析为什么会有这样不同的结果。intfact(){staticinti=5;if(i==0){return(i);}else{i=i-1;return((i+abs(1))*fact());/*第11行*/}}main(){printf(factorof5=%d\n,fact());}答案：(1)i是静态变量，所有地方对i的操作都是对同一地址空间的操作，所以每次递归进入fact函数后，上一层对i的赋值仍然有效。值得注意的是，每次递归时，(i+abs(1)*fact()中(i+abs(1))的值都先于fact算出。所以，第1次递归时，所求值为5*fact,第2次递归时，所求值为4*fact，第3次递归时，所求值为3*fact，如此类推，第5次递归时所求值为1*fact,而此时fact值为1。这样一来，实质上是求一个阶乘函数5