《编译原理课后习题答案1.pdf》由会员分享，可在线阅读，更多相关《编译原理课后习题答案1.pdf（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 1i.解答：程序设计语言：程序设计语言是遵守一定规范的、描 述“计算”（C o m p u t i n g）过程的形式语言。一般可以划分为低级语言和高级语言两大类。低级语言是面向机器的语言，它是为特定的计算机系统设计的语言，机器指令、汇编语言是低级语言。高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示，例 如F O R TR A N、P a s c a l、C等等我们熟悉的语言是高级语言。语言处理程序：由于目前的计算机只能理解和执行机器语言，因此必须有一个程序将用程序设计语言书写的程序等价（执行效果完全一致）地转换为计算机能直接执行的形式，完成这一工
2、作的程序称为“语言处理程序”。它一般可分为解释程序和翻译程序两大类。翻译程序：翻译程序（Tr a n s l a t o r）是一种语言处理程序，它将输入的用程序设计语言书写的程序（称为源程序）转换为等价的用另种语言书写的程序（称为目标程序）。若源语言是汇编语言，目标程序是机器语言，称这种翻译程序为汇编程序。若源语言是高级语言，目标程序是低级语言，称这种翻译程序为编译程序。解释程序：解释程序（I n t e r p r e t e r）是一种语言处理程序，它对源程序逐个语句地进行分析，根据每个语句的含义执行语句指定的功能。2 .解答：编译程序的总框图见图1.2。其中词法分析器，又称扫描器，它接
3、受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号。语吟 -,iBHWfc目4sm语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。语义分析及中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。优化器对中间代码进行优化处理。i般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际卜.是对中间代
4、码进行等价替换，使程序在执行时能更快，并占用更小的空间。目标代码生成器把中间代码翻译成目标程序。中间代码一般是 种机器无关的表示形式，只有把它再翻译成与机器硬件直接相关的机器能识别的语言，即目标程序，才能在机器上运行。表格管理模块保持系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格打交道。出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反
5、映给用户Chapter 21 .试写出VT=0,1 上下述集合的正则表达式：所有以1开始和结束的符号串。恰含有3个1的所有符号所组成的集合。(3)集合 0 1,1。所 有 以1 1 1结束的符号串。解答：(1)1(0|1)*1|1 0*1 0*1 0*1 0*0 1|1(4)(0|1)*1 1 12 .试写出非负整数集的正则表达式。试写出以非5数字为头的所有非负整数集的正则表达式。解答：(1)0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)0|(1|2|3|4|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*3 .试将2.8中所示的有限状态自动机
6、M最小化。分析：只能对确定的有限状态自动机进行最小化，本题的自动机已经是确定的。最小化采用状态分离法，具体做法如下：进行0等价类的划分：Q划分为Qr与Q-Q,若已进行了 k等价划分，即Q已被划分成(Q“Q”-Q,),再进行k+1划分，对Q；(i =l n),若q、q e Q；,使得对某一个a e V“8 (q,a)e Q,和5 (q ,a)GQ jl或3 (q,a)存在而3 (q ,a)不存在或反之。则将Q,划分为二个子集 Qu,Qi 2)使 qe Qi”q e Qi 2重复直至无法进一步划分为止。对最后划分得到的状态子集中每一个子集，选择该子集中任何一个状态作为该状态子集的代表，然后修改原来
7、的有限状态自动机的状态转换函数3,凡在b作用下转向某状态子集中任何个状态的律改成转向该状态子集的代表。若一个状态子集中某一状态是原来的开始状态，则该状态子集的代表就是新的有限状态自动机的开始状态。同理，若一个状态子集中的状态均是最终状态，则该状态子集的代表就是新的有限状态自动机的最终状态。抹去可能存在的无用状态与不可及状态。解答：此有限状态自动机的状态转换表如表3.1所示：表2.1 M的状态转换表ab1ABCBDCCBE1)1)FAcceptEGEAcceptFGEAcceptGI)FAccept由此看出：此有限状态自动机是确定的。最小化：初始划分由2个子集组成，即:(A,B.C,D,E,F,
8、G)集合 D,E,F,G 不需要进一步划分，考察子集 A,B,C。由于8 (B,a)=D e D,E,F,G),而B (A,a)=8 (C,a)=B e A,B C,因此Q可进一步划分为:(A,C,B,(D,E,F,G)由于5 (A,b)=CG A,C,而5 (C,b)=E e D,E,F,G 0因此 Q 可进一步划分为：(A,C,B,D,E,F,G)。这时不能再划分了，得到的最小化的有限状态自动机如表3.2所示:表2.2最小化的有限状态自动机aBCBBDDD：)1CECDAccept4.某程序语言的无(正负)符号常数可以用下面正则表达式R来表示:(D*E|D+.D+E|E|.D*E)(+|-
9、)D|D)D*|D+|D*.D+试把它转换成确定性有限状态自动机。把上述有限状态自动机最小化。在上述有限状态自动机中添加相应动作，取出无(正负)符号常数。分析：从正则表达式构造有限状态自动机可以分两步进行。画 条从结点X到结点Y的有向弧，有向弧上标以正则表达式R。结点X为标以“一”的初始状态，结点Y为标以“+”的最终状态。从这一有向图出发反复应用图3.2所示的替代规则，直至所有有向弧都以VT中的符号或标记为止。CP1 2-*1 CQO w图2.2 3条替代规则消除应用所得到的传递图中的弧，可以分为两步：首先消除环路，其次消除其他 弧。a)环路的消除方法：i .将环路的诸项合并为一个顶点。i i
10、 .修改各个相关的有向弧。i i i .若环路中某一状态是最终(或初始)状态，则新顶点是最终(或初始)状态。b)其它e弧的消除有两种方法：1)子集法：即计算机C l o s u r e (T),其表示从状态集T中任何状态沿 弧可以到达的状态全体。其要点是：从初始状态q 0的X=-C l o s u r e (q0)开始，按如下方法构造状态集：i .令 S e t=X；i i .若S e t中还有未考察过的状态子集Xj,则对于每一输入符号a e V 求T=-C l o s u r e (m o v e (X a),S e t=S e t U T(其中m o v e(XM=q|q e 6(p,a)
11、,p e Xi)。重复执行(2),直至不存在这样的X,。这样得到的S e t即为消除弧后的确定的有限状态机(D F A)o D F A的初始状态就是。C l o s u r e (q0),最终状态由那些至少含有一个最终状态的状态子集组成。2)逐步消除法：其要点是找到类似于图2.3所示，但从B再无弧引出的 弧。图2.3逐步消除法删除状态A到状态B的 弧，对 每 条从状态B到状态C标记为a,的弧，增加1条从状态A到状态C标记为a j的弧。若B是最终状态，则让A为最终状态。重复上述过程直至消除全部的弧，这样得到的一般是不确定的有限状态自动机（NFA）。解答：图3.4给 出 从正则表达式R构造有限状态
12、自动机M的过程。图2.4替代规则的应用过程应用子集法消除?弧:e-Closure令 Al=x,2,计算:-Closure(move(A l,D)=-Closure(7,10,2,1)=7,10,2,l,y!e-Closure(move(A l,)=e-Closure(5,3)=5,3-Closure(move(A l,E)=e-Closure(4)=4令 A2=7,10,2,l,y,A3=5,3，A 4=4,计算:-Closure(move(A2,D)=7,10,2,1,y-Closuremove(A2,)=8,3E-Closure(move(A2,e-Closure(move(A3,e-Cl
13、osure(move(A4,e-Closure(move(A4,-Closure(move(A4,E)=4D)=5,6,3,yD)=12,y+)=11-)=1 1 令A5=8,3,A6=5,6,3,y,A7=12,y,A 8=11,计算:e-Closure(move(A5,D)=8,9,3,ye-Closure(move(A6,-Closurc(move(A6,-Closure(move(A7,-Closurc(move(A8,D)=5,6,3,yE)=4D)=12,yD)=12,y令 A9=8,9,3,y,计算:e-Closure(move(A9,D)=8,9,3,y-Closure(mov
14、e(A9,E)=4得到的DFAM，的初始状态是A l,最终状态集由A2,A6,A7,A9组成。图2.5是 M，的状态转换图，M，的状态转换表如表2.3所示。表 2.3 M，的状态转换表D!*+-1A 1A 2A 4A 3A 2A 2A 4A 5A c c e p tA3A 6A 4A 7A 8A 8A 5A 9A6A6A 4A c c e p tA 7A 7A c c e p tA 8A 7A9A9A 4A c c e p t图2.5 M，的状态转换图采用状态分离法：初始时分成 2 个子集，即：(A1,A3,A4,A5,A8,A2,A6,A7,A9)考察子集 A2,A6,A7,A9,它进一步可
15、分成：(A6,A9,A2,A7)考察子集 A1,A3,A4,A5,A8,它进一步分成：(A4,A1,A8,A3A5)不能再进步划分了，得到的最小化的有限状态自动机如图2.6所示：由于数的表示和具体的机器有着内在联系，这里仅将此无(正负)符号常数的上进制数部分和指数部分分别存入2 个工作单元。设立下述工作单元：此常数的十进制数部分 n um ber此常数的指数部分 ex p小数点位数 n此常数指数部分正负号 ex p si gn这 4 个工作单元进入有限状态自动机的模拟程序时被初始化为0。函数过程getc har,其功能是读入下一个字符到工作单元c har中。函数过程v a lu e,其功能是求
16、出存放在工作单元char中数字字符的值。经过加工后的状态矩阵如表2.4 所示：表2.4 加工后的状态矩阵D+-A1#1,A2#2,A3#2,A4A2#3,A2#2,A3#2,A4#10,AcceptA3#4,A6A4#5,A7#6,A8#7,A8A6#4,A6#2,A4#11,AcceptA7#8,A7#12,AcceptA8#9,A7矩阵中元素Al,A2,A7表示应该转换的下个状态。#1,#2,#1 2 表示应该执行的语义子程序。各语义子程序的代码归结如下：#1 ：numbei*:=value(char);getchar;#2：getchar;#3：number:=nuiTiber*10+v
17、alue(char);getchar;#4：n:=n+1;number:=number*10+value(char);getchar;#5：expsign:=l;exp:=value(char);getchar;#6：expsign:=1 ;getchar;#7：expsign=l;getchar;#8：exp:=exp*10+value(char);getchar;#9：exp:=value(char);getchar;#10：按硬件要求构造无(正负)符号数；#11：exp:=-n;按硬件要求构造无(正负)符号数；#12：if expsign=-l then exp:=-exp;exp=ex
18、p-n;按硬件要求构造无(正负)符号数；5.设要识别的单词有限集是STEP,SWITCH,STRING,相应正则表达式是STEP|SWITCH|STRING,试把它转换成确定性有限状态自动机。解答：6.设V T=a,b,试构造下述正则表达式的确定性有限状态自动机：(1)a(a|b)*baa(2)(a|b)*bbb*解答：(D 由此正则表达式构造的有限状态自动机M l的状态转换图如图2.7所示:图2.7 有限状态自动机M l的转换图确定化(表3.5)：表 3.5 M l的确定化Q 6 a3 b，1JJ口2 3 2,3 2,4 2,3 2,4 2,5 2,3 2,5：2 .2,3 A对应的状态转换
19、图如图3.8所示:图2.8 DFAM1的状态转换图(2)由正则表达式构造的有限状态自动机M2的状态转换图如图2.9所示：图2.9 M2的状态图确定化(表2.6)：表2.6 M2的确定化Q 3屋3 b，11 1 1,2 1,2 1 1,2,3 1,2,3 1 1,2,3 图2.1 0 D F AM2的状态转换图9.对于下列的状态转换矩阵:ab1SASAABBBBZab1sASABAZBBB分别画出相应的状态转换图。用自然语言分别描述它们所识别的输入串的特征。解答：表1所对应的状态转换图如图2.1 1所示：图2.1 1表3.6对应的状态转换图表2所对应的状态转换图如图2.1 2所示:图2.1 2表
20、3.7对应的状态转换图 表1所识别的输入串是：以b*aa*b开头的后接任意多个a或b的 a,b上的字符串。表2所识别的输入串是：仅 含 有 个a的 a,b上的字符串。1 0 .将习题图2.1所示的非确定的有限状态自动机确定化和最小化。习题图2.1非确定的有限状态自动机M解答：确 定 化（表2.8）：表2.8 M的确定化ab1S A A B.C A B,C Alz令B =B,C 对应的状态转换图如图2.1 4所示:图2.1 4 D F A M的状态转换图确定化的M已是最小化的。1 1.消除传递图T （习题图2.2）中的e弧。习题图2.2传递图T解答：i）先消除 环路，合并状态2和3,得到的传递图
21、T，如图3.1 6所示：图2.1 6消除?环路的传递图T，ii）采用逐步消除法去除其他 弧，最终得到的传递图T”如图2.1 7所示：图2.17消除所有 弧的传递图Chapter 32.设有文法G1：-|D-0|l|2|-|9试写出028和4321的最左推导和最右推导过程。分析：在每一步的推导中，都是对最左的那个非终结符用相应的产生式的右部来替换，这样的推导称为最左推导。类似地，如果每 步的推导中都是对最右的那个非终结符用相应的产生式的右部来替换，这样的推导称为最右推导，最右推导又称规范推导。解答：028的最左推导：=XD=0=02028028的最右推导：=8=8=28=28=0284321的最
22、左推导：=4=43=432=43214321的最右推导：=xN=1 =1 =21 =21 =321 =321 =43213.证明文法GS刁是二义性文法：ifthenelse|ifthen|sr0|l分析：只要找出该文法的一个二义性句子即可证明。解答：句子if 0 then if 1 then s else s对应如下两棵不同的推导树：if thoi rfgg I.1 I0,sif bea I II s图 3.1 句子 if 0 then if 1 then s else s 的推导树（1）图 3.1 句子 if 0 then if 1 then s else s 的推导树(2)4 .设有文法G
23、E刁：|/|-i|()试写出i/(i年i)的推导树。试写出(-i)/VF的短语、简单短语和句柄。分析：只要给出句型(句子)对应的推导树就容易求出短语、简单短语和句柄。解答：i/(i-i-i)的推导树如下：图3.3句 子i/(i-i-i)的推导树 F-i)F的推导树如下:e-iV-T6图3.4句 子(-i)/的推导树短语：,i,-i,(-i),(-i)/简单短语:,i句柄：5.对布尔矩阵1001、1010 to010001000000100100 0 0 0 0 0 1J求B+o解答：利用Wa r s ha l l算法求解的结果如解m i n*m m-oooooom iltjOOOOOl77.对
24、表结构语言G ：-a|A|(),|试给出(a,(a,a)的最左和最右推导。指出(a,a),人,(a),a)的最右推导，以及规约的每一步的句柄。给出(a,a)八(a),a)的推导树自下而上的构造过程。分析：本题是要让读者明确，自下而上构造推导树的过程是最右推导(规范推导)的逆过程，这一过程正是自底向上句法分析的过程，其要点是找句柄、归约。解答：句子(a,(a,a)的最左推导为：表3.1句子(a,a),八,(a)的最右推导过程=()=(,)=(,)=(a,)=(a,()=(a,(,)=(a,(,)=(a,(a ,)=(a,(a,a)最右推导为：=()=(,)=(,()=(,(,)=(,(,a)=(
25、,(,a)=(,(a,a)=(,(a,a)=(a,(a,a)句子(a,a)八(a),a)的最右推导及归约的每一步句柄如表3.1所示：最右推导每一步归约时的句柄(T T(T,S,(T,a)a(S,a)(T,a)T(T,S,a),(T,T),a)T(T,S),a)(T,(a),a)a(T,(a),a),(T,A,(a),a)A(S,A,(a),a)(T,A,(a),a)(,S,A,(a),a),(T,a),A,(a),a)a(S,a),A,(a),a)(a,a),A,(a),a)a句子(a,a)八(a),a)的推导树如图3.5所示:图3.5 句子(a,a),A,(a),a)的推导树构造过程如图3.
26、6所示:图3.6 句子(a,a),A,(a),a)的推导树自下而上的构造过程Chapter 4(略)Chapter 51.考察算术表达式翻译文法T l：T1 =(+,*,G),C,C,ADD,MUL,R,)其中R 由下面规则组成：+,ADD,-*,MULT),一C,C其相应输入文法是LR(1)。试对该输入文法的下推自动机控制表作适当改动，构造翻译下推自动机的控制表，使该翻译下推自动机把任何一个由C,+,*组成的中缀表达式翻译成后缀表达式。分析：设翻译文法中的翻译规则形如：v A -x,y把自底向上的下推自动机改造成相应的下推翻译自动机的方法很简单：只需规定，当下推自动机应用产生式i进行规约的同
27、时，输出y中的输出符号。解答：输入文法的LR(1)状态集如表5.1。表5.1输入文法的LR(1)状态集状态T项目集文法符号BGO TO (T,B)0*E，-1,A1 f +,/+1-,1/+2-*,_ L/+/*2-,1/+/*3 f E,1/+/*(4 f C,/+/*c51*-1Accept*-+,1/-+62*-,1/+/+42*-*,!_/+/*东73*-*,1/+/*1/+/*#44*-(E,1/+/*8-+,)/+8-,)/+9-*,)/+/*9 f.,)/+/*10 f E,)/+/*(11-c,)/+/*c125*-C-,1/+/*1/+/*#66*-+,/+13-*,1/+/
28、*13T A ,/+/*3一 E,/+/*(4 Pf C,/+/*c57*-*,!_/+/*14PA E,/+/*(1 f C,/+/*c58*-E ),1/+/*)15*-+,)/+169*-,)/+)/+#2*-*,)/+/*1710*-*,)/+/*)/+/*#41 1*-*(E,)/+/*1 8-+,)/+1 8-,)/+9-*,)/+/*9-,)/+/*1 0f E ,)/+/*(1 1-C,)/+/*c1 21 2*-C ,)/+/*)/+/*#61 3*-+,1/-1/+#1*-*,I/+/*71 4*-*,/+/*_!_/+/*#31 5*-E ,1/+/*_!_/+/*#51
29、 6*-*+,)/+1 9-*,)/+/*1 9 ,)/+/*1 0-E ,)/+/*(1 1-C,)/+/*c1 21 7*-*,)/+/*2 0-E ,)/+/*(1 1-c,)/+/*c1 21 8*P f(E),)/+/*)2 1*+,)/+1 61 9*-+,)/+)/+#1*-*,)/+/*1 72 0*-*,)/+/*)1,*#32 1*-E),)/+/*)/+/*#5翻译下推自动机的控制表如表5.2 所示:表 5.2 翻译下推自动机的控制表状态T动作表(Ac t io n)转向表(Go t o)+*()c10Sis51231SBAc c2R#2S;R#23R#4R#1R4 44
30、S.)S12891 05R#6,GEN(C)R#6,GEN(C)R#6,GEN(C)6S51 337s”S51 48Sl 6Sl 59R#2s -R#21 0RH 4I 件4R#41 1SuS121 891 01 2R#6,GEN(C)R#6,GEN(C)R#6,GEN(C)1 3R#1,GEN(ADD)s；R#1,GEN(ADD)1 4R#3,GEN (MU L)R#3,GEN(MU L)R#3,GEN (MU L)1 5R4 5R4 5R4 516SnS12191017S22018S1619R#1,GEN(ADD)S17R#1,GEN(ADD)20R#3,GEN(MUL)R#3,GEN(M
31、UL)R#3,GEN(MUL)21R#5R#5R#52.考察下述文法GvS：i:=-*+*-()-i试写出各产生式的语义子程序。解答：让非终结符E带有属性.ty p e指出数据类型，属性E.v a l存放运算结果。-i:=if i.type=.type thenGEN(:=,.val,i.val);else if i.type=real AND.type=int thenbeginT:=NEWTEMP;GEN(float,.val,T);GEN(:=,T,i.val);end.else if i.type=int AND.type=rcal thenbeginT:=NEWTEMP;GEN(in
32、t,.val,T);GEN(:=,T,ival);end.else error.-E +.val:=NEWTEMP;if.type=int AND.type=int thenbegin.type:=int;GEN(int+,vE】.vaL.val,.val);end.else if.type=real AND.type=real thenbegin.type:=real;GEN(real+,Ei.val,.val,.val);end.else if.type=int AND.type=real thenbegin.type:=real;T:=NEWTEMP;GEN(float,.val,T);
33、GEN(real+,T,.val,.val);end.else if.type=real AND.type=int thenbegin.type:=real;T:=NEWTEMP;GEN(float,.val,T);GEN(real+,.val,T,.val);end.else error.)-*.val:=NEWTEMP;if.type=int AND.type=int thenbegin.type:=int;GEN(int*,.val,.val,.val);end.else if.type=real AND.type=real thenbegin.type:=real;GEN(real*,
34、Ei.val,.val,.val);end.else if.type=int AND.type=real thenbegin.type:=real;T:=NEWTEMP;GEN(float,.val,T);GEN(real*,T,.val,.val);end.else if.type=real AND.type=int thenbegin.type:=real;T:=NEWTEMP;GEN(float,.val,T);GEN(real*,.val,T,.val);end.else error.)-().val:=.val;.type:=.type;)-i.val:=i.val;.type:=i
35、.type;Chapter 6(略)Chapter 7i.考察下面程序段：procedure p(x,y,z)beginy：=y+i;z:=z+x;end;begina:=2;b:=3;p(a+b,a,a);write(a);end;若参数通信分别是：按名按值方式，上述程序执行后，输出a的值分别是多少？解答：按名调用的特点是：在被调用过程执行时，用实参替换形参，然后执行替换后的程序，因此本程序相当于执行如下程序段：a:=2；b:=3；a:=a+l；a:=a+a+b；输出a 的值是9。按值调用的特点是：传送的是实在参数的当时值，该值成为形参的初值，是一种单向的行为，它并不改变实参的值。所以a 的
36、值不变，仍是2。2.考察下面C 程序：m a i n()i n tP(.).P2()；P2(-)(P3();P3()P(.J；试说明，该程序执行时，运行栈中调用记录的变化情况。解答：程序流进入过程P1时，栈空间中各调用记录的布局如图7.2所示。图7.2 程序流进入过程P,时各调用记录的布局程序流进入过程P?时，栈空间中各调用记录的布局如图7.3所示。I l l取过程,用汜g 口 糜,用 谈 一Miin过程调用记录(苗隽向图 7.3程序流进入过程P,时各调用记录的布局程序流进入过程P3时，栈空间中各调用记录的布局如图7.4所示。P,过程调用记录P 1过程,用口录一P期,用 记 录Main返程调用
37、巳录图7.4 程序流进入过程P3时各调用记录的布局3.下标变量地址计算可以采用另一种方法：直接生成计算下标变量地址的中间代码。考察下述和下标变量有关的产生式:i-1 ,一试写出相应求下标变量地址的语义子程序。解答：由于在处理数组定义时，已经将数组的维数n,每一维的上下界Ui、L i,长 度d i以及数组元素存贮首地址stp,addrcss(aO,0)均存放在数组的信息向量表中。为得到这些数据，用属性id.dim表示数组的维数，函数limit(id,j)返回dj,函数getaddr(id)返回假头地址address(a0,.,0),过程Mark_indirect(T)表示在T中添加间址标记。各产
38、生式的语义子程序为：-i.dim:=l；.array:=i.array；/*i.array 表示数组名*/.val:=.val；f ,.dim:=.dim+l；D:=Newtemp；GEN(*,1.val,limit(.array,.dim),D)；GEN(+,D,.val,D)；.val:=D；.array:=,.array;)W-vSUB_V刁Checkdim(.dim,.array.dim)；/*检查维数的正确性*/L:=Newtemp；GEN(+,getaddr(.array),.val,L);Markindirect(L)；.val:=L；4.过程语句：一call i(Eist)1
39、,的中间代码采用下面形式：(call,i.VAL,.VAL,.,.VAL)试写出生成上述形式的中间代码的语义子程序。解答：让带有属性:.que(队头)和.tail(队尾)。#1的语义子程序为：fetch(.que,.tail);Gen(call,i.VAL,.VAL,.,.VAL);#2的语义子程序为：.que=.que;.tail=,.tail;Append(.tail,.val);#3的语义子程序为：MakeQueue(.que,.tail);Append(.tail,.val);5.考察下面Pascal程序：Program P(input,output);var a,b:integer；
40、cl:array1.10 of real；Procedure fl(x,y:integer)；var d,e:integer；c2:arrayl.20 of real；Procedure f2；var u,v:real；beginend；beginf2;end；Procedure f3；var hl,h2:integer；beginfl(hl,h2)；end；beginf3;end.给出程序流进入过程f l 和 f2 时区头地址表的内容。给出程序流进入f2 时运行栈中的主要内容。解答：本题中过程的嵌套和调用关系可示意性地由图7.5表示。CaUQCall3图 7.5 过程的嵌套和调用关系当程序流
41、进入n 时，区头地址表的内容有以下两项：过程门的调用记录首址一p 过程的调用记录首址 一当程序流进入f2 时，区头地址表的内容有以J 三项：过程f 2 的调用记录首址一过程f l 的调用记录首址一P 过程的调用记录首址(2)程序流进入f2 时，运行栈的主要内容如图7.6 所示。oldsp诞 Q语 僦 的 策 耐 U2 AM酸晌餐与元杰oidap.廉 万 画 画 买 赋 茶 oidsp过程闫的区头侬t表政姐cl的亘回响正血与元诲-UifiLilMlSWS_ aid ap_一 诞。雁 瀛 魂图7.6程序流进入f2时运行栈的情形Chapter 81.考察下述文法G：-i:=-+*-()i试写出各产生
42、式的语义子程序。解答：让非终结符在 带有属性(E.type指出数据类型，属性.val存放运算结果。-i:=if i.type=.type thenGEN(:=,.val,i.val);else if i.type=real AND.type=int thenbeginT:=NEWTEMP;GEN(float,.val,T);GEN(:=T,i.val);end.else if i.type=int AND.type=real thenbeginT:=NEWTEMP;GEN(int,.val,T);GEN(:=,T,i.val);end.else error.)-E1+.val:=NEWTEMP
43、;if.type=int AND.type=int thenbegin.type:=int;GEN(int+,.val,.val,.val);end.else if.type=real AND.type=real thenbegin.type:=real;GEN(real+,.val,.val,.val);end.else if.type=int AND.type=real thenbegin.type:=real;T:=NEWTEMP;GEN(float,vE、val,T);GEN(reai+,T,.val,.val);end.else if.type=real AND.type=int t
44、henbegin.type:=real;T:=NEWTEMP;GEN(float,.val,T);GEN(real+,.val,T,.val);end.else error.)-*.val:=NEWTEMP;if.type=int AND.type=int thenbegin.type:=int;GEN(int*,.val,.val,.val);end.else if.type=real AND.type=real thenbegin.type:=real;GEN(real*,vE、.val,.val,.val);end.else if.type=int AND.type=real thenb
45、egin.type:=real;T:=NEWTEMP;GEN(float,.val,T);GEN(real*,T,.val,.val);end.else if.type=real AND.type=int thenbegin.type:=real;T:=NEWTEMP;GEN(float,.val,T);GEN(real*,.val,T,.val);end.else error.-*().val:=.val;.type:=.type;)-i.val:=i.val;.type:=i.type;2.试写出第二类if语句翻译的语义动作子程序。解答：设条件语句的产生式为：if then I else
46、2语义可描述为：t:=;if it then goto LI;goto L2;L1:2;L2:让vE带有属性.type和属性.false、.true(分别指出了假链与真链的链首地址)。运用拆因子技术，把产生式改造为if then)else 2各产生式的语义子程序如下：-ifCheckBool(.type);TLT:=NewTL;GEN(LABELJLT);Backpatch(.true,TLT);.false:=.false;then.TL:=NewTL;GEN(BR,.TL);TLF:=NewTL;GEN(LABEL,TLF);Backpatch(.false,TLF);else 2(GEN
47、(LABEL,.TL);3.考察Pascal中下面形式定义的fbr语句：一fbr V:=vEJ to do 假定上述形式的fbr语句等价于：begintl:=el;t2:=e2;iftlt2 thenbeginV:=tl;LI:；V:=succ(V);ifVt2 then goto LI;endend试写出符合上述规定的语义动作子程序。解答：将产生式拆因子为2个产生式：+fbr V:=to 一vfbrl do 各产生式的语义动作子程序如下：fbr V:=to check(V.type,.type,.type);.next:=NEWTL;GEN(BR,.val,.val,.next);GEN(:
48、=.val,V.val);.TL:=NEWTL;GEN(LABEL,.TL);.val:=V.val;.f=.val;)-*do GEN(succ,.val,.val);GEN(BR.val,.f；.TL);GEN(LABEL,.next);4.考察下面关于整型量和实型量说明的产生式：int id real id,id当用第一个产生式进行归约时;相关的语义子程序应该在该标识符id所对应的登记项登录与整型量相关的信息。假定这一工作由enter_desc完成。产生式1的语义子程序应是：enter_desc(id.val,int);.desc:=int;试写出其他2个产生式的语义动作子程序，并给出e
49、nter_desc的具体代码。解答：产生式2的语义动作子程序为：enter_desc(id.val,real);.desc:=real;产生式3的语义动作子程序为：enterdescCid.valD.desc);.desc:=.desc;5.设有某程序语言的循环语句的产生式fbr i:=downto do 其语义是：Tj：=;T2:=;i:=%；LI:if i-T2Vo then goto L2;；i:=i-l;goto LI;L2;试写出相应的属性翻译文法及语义动作子程序。解答：将产生式拆因子为：vfbr一fbr v=downto do 各产生式的语义子程序为：fbr i:=vE】downt
50、o CheckType(i.type,vEJ.type,vE2.type)；i.val:=vE、vaI；.i:=i.val；.TL 1 :=N e w T L；GEN(LABEL,.TLl)；.TL2=Ne w TL；GEN(BR,.i,.v al,.TL2)；+d o GEN(-,.i,l,.i):GEN(BR,.TLl)；GEN(LABEL,.TL2)；Chapter 93.设有算术表达式a+b*c-(c*b+a-e),要求:写出该表达式的四元组中间代码。把上述四元组中间代码理解成一个基本块，构造该基本块所对应的D A G图。由D A G图重新产生该表达式优化后的四元组中间代码。解答：该表