编译原理课后习题答案 27页

'第一章1．解答：程序设计语言：程序设计语言是遵守一定规范的、描述“计算”（Computing）过程的形式语言。一般可以划分为低级语言和高级语言两大类。低级语言是面向机器的语言，它是为特定的计算机系统设计的语言，机器指令、汇编语言是低级语言。高级语言是与具体计算机无关的“通用”语言，它更接近于人类的自然语言和数学表示，例如FORTRAN、Pascal、C等等我们熟悉的语言是高级语言。语言处理程序：由于目前的计算机只能理解和执行机器语言，因此必须有一个程序将用程序设计语言书写的程序等价（执行效果完全一致）地转换为计算机能直接执行的形式，完成这一工作的程序称为“语言处理程序”。它一般可分为解释程序和翻译程序两大类。翻译程序： 翻译程序(Translator)是一种语言处理程序，它将输入的用程序设计语言书写的程序（称为源程序）转换为等价的用另一种语言书写的程序（称为目标程序）。若源语言是汇编语言，目标程序是机器语言，称这种翻译程序为汇编程序。若源语言是高级语言，目标程序是低级语言，称这种翻译程序为编译程序。解释程序：解释程序（Interpreter）是一种语言处理程序，它对源程序逐个语句地进行分析，根据每个语句的含义执行语句指定的功能。2．解答：编译程序的总框图见图1.2。其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果是单词符号。语法分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序”。语义分析及中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。编译程序可以根据不同的需要选择不同的中间代码形式，有的编译程序甚至没有中间代码形式，而直接生成目标代码。优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种机器无关的表示形式，只有把它再翻译成与机器硬件直接相关的机器能识别的语言，即目标程序，才能在机器上运行。表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格打交道。 出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户Chapter21．试写出VT＝{0，1}上下述集合的正则表达式：⑴所有以1开始和结束的符号串。⑵恰含有3个1的所有符号所组成的集合。⑶集合{01，1}。⑷所有以111结束的符号串。解答：⑴1(0|1)*1|1⑵0*10*10*10*⑶01|1⑷(0|1)*1112．⑴试写出非负整数集的正则表达式。⑵试写出以非5数字为头的所有非负整数集的正则表达式。解答：⑴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中所示的有限状态自动机M最小化。分析：只能对确定的有限状态自动机进行最小化，本题的自动机已经是确定的。最小化采用状态分离法，具体做法如下：①进行0等价类的划分：Q划分为Qf与Q－Qf②若已进行了k等价划分，即Q已被划分成（Q1，Q2，…Qn），再进行k＋1划分，对Qi（i＝1…n），若q、q’ÎQi，使得对某一个aÎVT，d（q，a）ÎQj和d（q’，a）ÎQl，j≠l或d（q，a）存在而d（q’，a）不存在或反之。则将Qi划分为二个子集Qi1，Qi2，使qÎQi1，q’ÎQi2。③重复②直至无法进一步划分为止。对最后划分得到的状态子集中每一个子集，选择该子集中任何一个状态作为该状态子集的代表，然后修改原来的有限状态自动机的状态转换函数d，凡在d作用下转向某状态子集中任何一个状态的一律改成转向该状态子集的代表。若一个状态子集中某一状态是原来的开始状态，则该状态子集的代表就是新的有限状态自动机的开始状态。同理，若一个状态子集中的状态均是最终状态，则该状态子集的代表就是新的有限状态自动机的最终状态。④抹去可能存在的无用状态与不可及状态。解答：此有限状态自动机的状态转换表如表3.1所示：表2.1M的状态转换表 ab^ABC BDC CBE DDFAcceptEGEAcceptFGEAcceptGDFAccept由此看出：此有限状态自动机是确定的。最小化：初始划分由2个子集组成，即：（{A,B,C},{D,E,F,G}） 集合{D,E,F,G}不需要进一步划分，考察子集{A,B,C}。由于d（B,a）=DÎ{D,E,F,G}，而d（A,a）＝d（C,a）＝BÎ{A,BC}，因此Q可进一步划分为：（{A,C},{B},{D,E,F,G}）。由于d（A,b）＝CÎ{A,C}，而d（C，b）＝EÎ{D,E,F,G}。因此Q可进一步划分为：（{A},{C},{B},{D,E,F,G}）。这时不能再划分了，得到的最小化的有限状态自动机如表3.2所示：表2.2最小化的有限状态自动机 ab^ABC CBE BDC DDDAccept4．某程序语言的无（正负）符号常数可以用下面正则表达式R来表示：  （D+E|D+.D+E|E|.D+E）((+|-)D|D)D*|D+|D*.D+⑴试把它转换成确定性有限状态自动机。⑵把上述有限状态自动机最小化。⑶在上述有限状态自动机中添加相应动作，取出无（正负）符号常数。分析：从正则表达式构造有限状态自动机可以分两步进行。①画一条从结点X到结点Y的有向弧，有向弧上标以正则表达式R。结点X为标以“－”的初始状态，结点Y为标以“＋”的最终状态。从这一有向图出发反复应用图3.2所示的替代规则，直至所有有向弧都以VT中的符号或标记e为止。 图2.23条替代规则②消除应用①所得到的传递图中的ε弧，可以分为两步：首先消除ε环路，其次消除其他ε弧。a)ε环路的消除方法：i．将ε环路的诸项合并为一个顶点。ii．修改各个相关的有向弧。iii．若ε环路中某一状态是最终（或初始）状态，则新顶点是最终（或初始）状态。b)其它ε弧的消除有两种方法：1）子集法：即计算ε-Closure（T），其表示从状态集T中任何一状态沿ε弧可以到达的状态全体。其要点是：从初始状态q0的X=ε-Closure（q0）开始，按如下方法构造状态集：i．令Set＝{X}；ii．若Set中还有未考察过的状态子集Xi，则对于每一输入符号aÎVT，求T=ε-Closure（move（Xi,a）），Set=Set∪{T}（其中move(Xi,a)={q|qÎδ(p,a),pÎXi}）。重复执行（2），直至不存在这样的Xi。这样得到的Set即为消除ε弧后的确定的有限状态机（DFA）。DFA的初始状态就是ε-Closure（q0），最终状态由那些至少含有一个最终状态的状态子集组成。2）逐步消除法：其要点是找到类似于图2.3所示，但从B再无ε弧引出的ε弧。图2.3逐步消除法删除状态A到状态B的ε弧，对每一条从状态B到状态C标记为ai的弧，增加1条从状态A到状态C标记为ai 的弧。若B是最终状态，则让A为最终状态。重复上述过程直至消除全部的ε弧，这样得到的一般是不确定的有限状态自动机（NFA）。解答：⑴图3.4给出了从正则表达式R构造有限状态自动机M的过程。图2.4替代规则的应用过程应用子集法消除?弧：ε-Closure（x）={x,2}，令A1＝{x,2}，计算：ε-Closure（move（A1，D））＝ε-Closure（{7,10,2,1}）={7,10,2,1,y}ε-Closure（move（A1，·））=ε-Closure（{5,3}）={5,3}ε-Closure（move（A1，E））＝ε-Closure（{4}）={4}令A2＝{7,10,2,1,y}，A3＝{5,3}，A4＝{4}，计算：ε-Closure（move（A2，D））＝{7,10,2,1,y}ε-Closure（move（A2，· ））＝{8,3}ε-Closure（move（A2，E））＝{4}ε-Closure（move（A3，D））＝{5,6,3,y}ε-Closure（move（A4，D））＝{12,y}ε-Closure（move（A4，＋））＝{11}ε-Closure（move（A4，－））＝{11}令A5＝{8,3}，A6＝{5,6,3,y}，A7={12,y}，A8＝{11}，计算：ε-Closure（move（A5，D）＝{8,9,3,y}ε-Closure（move（A6，D）＝{5,6,3,y}ε-Closure（move（A6，E）＝{4}ε-Closure（move（A7，D）＝{12,y}ε-Closure（move（A8，D）＝{12,y}令A9＝{8,9,3,y}，计算：ε-Closure（move（A9，D）＝{8,9,3,y}ε-Closure（move（A9，E）＝{4}得到的DFAM’的初始状态是A1，最终状态集由A2，A6，A7，A9组成。图2.5是M’的状态转换图，M’的状态转换表如表2.3所示。表2.3M’的状态转换表 DE·+-^A1A2A4A3   A2A2A4A5  AcceptA3A6     A4A7  A8A8 A5A9     A6A6A4   AcceptA7A7    AcceptA8A7     A9A9A4   Accept图2.5M’的状态转换图⑵采用状态分离法：  初始时分成2个子集，即：({A1,A3,A4,A5,A8},{A2,A6,A7,A9})  考察子集{A2,A6,A7,A9}，它进一步可分成：（{A6,A9},{A2},{A7}）  考察子集{A1,A3,A4,A5,A8}，它进一步分成：（{A4},{A1},{A8},{A3,A5}）  不能再进一步划分了，得到的最小化的有限状态自动机如图2.6所示：图2.6最小化的有限状态自动机⑶由于数的表示和具体的机器有着内在联系，这里仅将此无（正负）符号常数的十进制数部分和指数部分分别存入2个工作单元。设立下述工作单元：此常数的十进制数部分     number此常数的指数部分         exp小数点位数               n此常数指数部分正负号     expsign这4个工作单元进入有限状态自动机的模拟程序时被初始化为0。函数过程getchar，其功能是读入下一个字符到工作单元char中。 函数过程value，其功能是求出存放在工作单元char中数字字符的值。经过加工后的状态矩阵如表2.4所示：表2.4加工后的状态矩阵D·E+-^A1#1,A2#2,A3#2,A4   A2#3,A2#2,A3#2,A4  #10,AcceptA3#4,A6     A4#5,A7  #6,A8#7,A8 A6#4,A6 #2,A4  #11,AcceptA7#8,A7    #12,AcceptA8#9,A7     矩阵中元素A1，A2，….，A7表示应该转换的下一个状态。＃1，＃2，….，＃12表示应该执行的语义子程序。各语义子程序的代码归结如下：＃1：number:=value（char）;getchar;＃2：getchar;＃3：number:=number*10+value（char）;getchar;＃4：n:=n+1;number:=number*10+value（char）;getchar;＃5：expsign:=1;exp:=value（char）;getchar;＃6：expsign:=1;getchar;＃7：expsign=-1;getchar;＃8：exp:=exp*10+value（char）;getchar;＃9：exp:=value（char）;getchar;＃10：按硬件要求构造无（正负）符号数；＃11：exp:=-n;按硬件要求构造无（正负）符号数；＃12：ifexpsign=-1thenexp:=-exp;exp=exp-n;按硬件要求构造无（正负）符号数；5.设要识别的单词有限集是{STEP,SWITCH,STRING}，相应正则表达式是STEP|SWITCH|STRING，试把它转换成确定性有限状态自动机。解答：6．设VT＝{a,b}，试构造下述正则表达式的确定性有限状态自动机：⑴a(a|b)*baa⑵(a|b)*bbb*  解答：⑴由此正则表达式构造的有限状态自动机M1的状态转换图如图2.7所示：图2.7有限状态自动机M1的转换图确定化（表3.5）：表3.5M1的确定化 Q’da’db’^[1][2]  [2][2][2,3] [2,3][2,4][2,3] [2,4][2,5][2,3] [2,5][2][2,3]A对应的状态转换图如图3.8所示：图2.8DFAM1的状态转换图⑵由正则表达式构造的有限状态自动机M2的状态转换图如图2.9所示：图2.9M2的状态图确定化（表2.6）：表2.6M2的确定化Q’da’db’^[1][1][1,2] [1,2][1][1,2,3] [1,2,3][1][1,2,3] 对应的状态转换图如图2.10所示：图2.10DFAM2的状态转换图9．对于下列的状态转换矩阵： ab^　SAS AAB BBBZ ab^SAS ABAZBBB ⑴分别画出相应的状态转换图。⑵用自然语言分别描述它们所识别的输入串的特征。解答：⑴表1所对应的状态转换图如图2.11所示： 图2.11表3.6对应的状态转换图表2所对应的状态转换图如图2.12所示：图2.12表3.7对应的状态转换图⑵表1所识别的输入串是：以b*aa*b开头的后接任意多个a或b的{a,b}上的字符串。   表2所识别的输入串是：仅含有一个a的{a,b}上的字符串。10.将习题图2.1所示的非确定的有限状态自动机确定化和最小化。习题图2.1非确定的有限状态自动机M解答：确定化（表2.8）：表2.8M的确定化ab^[S][A]  [A][B,C][A] [B,C][A] Z令B＝[B,C]对应的状态转换图如图2.14所示：图2.14DFAM的状态转换图确定化的M已是最小化的。11.消除传递图T（习题图2.2）中的e弧。习题图2.2传递图T解答：i）先消除e环路，合并状态2和3，得到的传递图T’如图3.16所示：图2.16消除?环路的传递图T’ii）采用逐步消除法去除其他e弧，最终得到的传递图T’’如图2.17所示： 图2.17消除所有e弧的传递图Chapter32．设有文法G1[]：→→|ÞÞÞÞÞ0Þ02Þ028028的最右推导：ÞÞÞ8Þ8Þ28Þ28Þ0284321的最左推导：ÞÞÞÞÞÞ4Þ43Þ432Þ43214321的最右推导：ÞÞÞ1Þ1Þ21Þ21Þ321Þ321Þ43213．证明文法G[]是二义性文法：→ifthenelse|ifthen|s→0|1分析：只要找出该文法的一个二义性句子即可证明。解答：句子if0thenif1thenselses对应如下两棵不同的推导树：图3.1句子if0thenif1thenselses的推导树（1）图3.1句子if0thenif1thenselses的推导树（2）4．设有文法G[]：→-|→/|→i|()⑴试写出i/(i-i-i)的推导树。⑵试写出（-i）/的短语、简单短语和句柄。分析：只要给出句型（句子）对应的推导树就容易求出短语、简单短语和句柄。解答：⑴i/(i-i-i)的推导树如下： 图3.3句子i/(i-i-i)的推导树⑵（-i）/的推导树如下：图3.4句子（-i）/的推导树短语：，i，-i，（-i），（-i）/简单短语：，i句柄：5．对布尔矩阵求B+。解答：利用Warshall算法求解的结果如下： 7．对表结构语言G[]：→a|Ù|()→,|⑴试给出(a,(a,a))的最左和最右推导。⑵指出(((a,a),Ù,(a)),a)的最右推导，以及规约的每一步的句柄。⑶给出(((a,a),Ù,(a)),a)的推导树自下而上的构造过程。分析：本题是要让读者明确，自下而上构造推导树的过程是最右推导(规范推导)的逆过程，这一过程正是自底向上句法分析的过程，其要点是找句柄、归约。解答：⑴句子(a,(a,a))的最左推导为： Þ()Þ(,)Þ(,)Þ(a,)Þ(a,())Þ(a,(,))Þ(a,(,)Þ(a,(a,)Þ(a,(a,a))最右推导为：Þ()Þ(,)Þ(,())Þ(,(,))Þ(,(,a))Þ(,(,a))Þ(,(a,a))Þ(,(a,a))Þ(a,(a,a))⑵句子(((a,a),Ù,(a)),a)的最右推导及归约的每一步句柄如表3.1所示：表3.1句子(((a,a),Ù,(a)),a)的最右推导过程最右推导每一步归约时的句柄(()() ((,), ((,a)a ((,a) (((),a)() (((,),a), (((,()),a)() (((,()),a) (((,(a)),a)a (((,,(a)),a), (((,Ù,(a)),a)Ù (((,Ù,(a)),a) ((((),Ù,(a)),a)() ((((,),Ù,(a)),a), ((((,a),Ù,(a)),a)a ((((,a),Ù,(a)),a) ((((a,a),Ù,(a)),a)a⑶句子(((a,a),Ù,(a)),a)的推导树如图3.5所示: 图3.5句子(((a,a),Ù,(a)),a)的推导树构造过程如图3.6所示:图3.6句子(((a,a),Ù,(a)),a)的推导树自下而上的构造过程Chapter4（略）Chapter51.考察算术表达式翻译文法T1：T1=({+,*,(,),C},{,,

},{C,ADD,MUL},R,)其中R由下面规则组成：→+,ADD →,→*

,

MUL→

,

→(),

→C,C其相应输入文法是LR(1)。试对该输入文法的下推自动机控制表作适当改动，构造翻译下推自动机的控制表，使该翻译下推自动机把任何一个由C,+,*组成的中缀表达式翻译成后缀表达式。分析：设翻译文法中的翻译规则形如：→x，y把自底向上的下推自动机改造成相应的下推翻译自动机的方法很简单：只需规定，当下推自动机应用产生式i进行规约的同时，输出y中的输出符号。解答：输入文法的LR(1)状态集如表5.1。表5.1输入文法的LR(1)状态集状态T项目集文法符号BGOTO（T，B）0*[→·^,Ù]1[→·+,^/+]1[→·,^/+]2[→·*

,^/+/*]2[→·

,^/+/*]

3[

→·(),^/+/*](4[

→·C,^/+/*]C51*[→·^]^Accept*[→·+,^/+]+62*[→·,^/+]^/+#2*[→·*

,^/+/*]*73*[→

·,^/+/*]^/+/*#44*[

→(·),^/+/*]8[→·+,)/+]8[→·,)/+]9[→·*

,)/+/*]9[→·

,)/+/*]

10[

→·(),)/+/*](11[

→·C,)/+/*]C125*[

→C·,^/+/*]^/+/*#66*[→+·,^/+]13[→·*

,^/+/*]13[→·

,^/+/*]

3[

→·(),^/+/*](4[

→·C,^/+/*]C57*[→*·

,^/+/*]

14[

→·(),^/+/*](4[

→·C,^/+/*]C58*[

→(·),^/+/*])15*[→·+,)/+]+169*[→·,)/+])/+#2*[→·*

,)/+/*]*1710*[→

·,)/+/*])/+/*#4 11*[

→(·),)/+/*]18[→·+,)/+]18[→·,)/+]9[→·*

,)/+/*]9[→·

,)/+/*]

10[

→·(),)/+/*](11[

→·C,)/+/*]C1212*[

→C·,)/+/*])/+/*#613*[→+·,^/+]^/+#1*[→·*

,^/+/*]*714*[→*

·,^/+/*]^/+/*#315*[

→()·,^/+/*]^/+/*#516*[→+·,)/+]19[→·*

,)/+/*]19[→·

,)/+/*]

10[

→·(),)/+/*](11[

→·C,)/+/*]C1217*[→*·

,)/+/*]

20[

→·(),)/+/*](11[

→·C,)/+/*]C1218*[

→(·),)/+/*])21*[→·+,)/+]+1619*[→+·,)/+])/+#1*[→·*

,)/+/*]*1720*[→*

·,)/+/*])/+/*#321*[

→()·,)/+/*])/+/*#5翻译下推自动机的控制表如表5.2所示：表5.2翻译下推自动机的控制表状态T动作表（Action）转向表（Goto）+*()C^

0  S4 S5 1231S6    Acc   2R#2S7   R#2   3R#4R#4   R#4   4  S11 S12 89105R#6,GEN(C)R#6,GEN(C)   R#6,GEN(C)   6  S4 S5  1337  S4 S5   148S16  S15     9R#2S17 R#2     10R#4R#4 R#4     11  S11 S12 1891012R#6,GEN(C)R#6,GEN(C) R#6,GEN(C)     13R#1,GEN(ADD)S7   R#1,GEN(ADD)   14R#3,GEN(MUL)R#3,GEN(MUL)   R#3,GEN(MUL)   15R#5R#5   R#5    16  S11 S12  191017  S11 S12   2018S16  S21     19R#1,GEN(ADD)S17 R#1,GEN(ADD)     20R#3,GEN(MUL)R#3,GEN(MUL) R#3,GEN(MUL)     21R#5R#5 R#5     1.考察下述文法G[]：→i:=→+→*→()→i试写出各产生式的语义子程序。解答：让非终结符带有属性.type指出数据类型，属性.val存放运算结果。→i:={ifi.type=.typethen  GEN(:=,.val,i.val); elseifi.type=realAND.type=intthen  begin      T:=NEWTEMP;      GEN(float,.val,T);      GEN(:=,T,i.val);  end. elseifi.type=intAND.type=realthen  begin      T:=NEWTEMP;      GEN(int,.val,T);      GEN(:=,T,i.val);  end.elseerror.      }→E1>+{.val:=NEWTEMP; if.type=intAND.type=intthen   begin       .type:=int;       GEN(int+,.val,.val,.val);   end. elseif.type=realAND.type=realthen   begin       .type:=real;       GEN(real+,.val,.val,.val);   end. elseif.type=intAND.type=realthen   begin       .type:=real;       T:=NEWTEMP;       GEN(float,.val,T);       GEN(real+,T,.val,.val);   end. elseif.type=realAND.type=intthen   begin       .type:=real;       T:=NEWTEMP;       GEN(float,.val,T);       GEN(real+,.val,T,.val);   end. elseerror.}→*{.val:=NEWTEMP; if.type=intAND.type=intthen    begin       .type:=int;       GEN(int*,.val,.val,.val);   end. elseif.type=realAND.type=realthen   begin       .type:=real;       GEN(real*,.val,.val,.val);   end. elseif.type=intAND.type=realthen   begin       .type:=real;       T:=NEWTEMP;       GEN(float,.val,T);       GEN(real*,T,.val,.val);   end. elseif.type=realAND.type=intthen   begin       .type:=real;       T:=NEWTEMP;       GEN(float,.val,T);       GEN(real*,.val,T,.val);   end. elseerror.}→(){.val:=.val; .type:=.type;}→i{.val:=i.val; .type:=i.type;}Chapter6（略）Chapter71.考察下面程序段：procedurep(x,y,z)  begin    y:=y+1;    z:=z+x;  end;begin  a:=2;  b:=3;  p(a+b,a,a);  write(a);end;若参数通信分别是：⑴按名⑵按值方式，上述程序执行后，输出a的值分别是多少？解答：⑴按名调用的特点是：在被调用过程执行时，用实参替换形参，然后执行替换后的程序，因此本程序相当于执行如下程序段：  a:=2；  b:=3；  a:=a+1；   a:=a+a+b；输出a的值是9。⑵按值调用的特点是：传送的是实在参数的当时值，该值成为形参的初值，是一种单向的行为，它并不改变实参的值。所以a的值不变，仍是2。 2.考察下面C程序：main()  int…;P1(…)  {…    P2(…)；    …  }  P2(…)  {…    P3(…)；    …  }  P3(…)  {…}{…P1(…)；…}试说明，该程序执行时，运行栈中调用记录的变化情况。解答：程序流进入过程P1时，栈空间中各调用记录的布局如图7.2所示。 图7.2程序流进入过程P1时各调用记录的布局程序流进入过程P2时，栈空间中各调用记录的布局如图7.3所示。图7.3程序流进入过程P2时各调用记录的布局程序流进入过程P3时，栈空间中各调用记录的布局如图7.4所示。图7.4程序流进入过程P3时各调用记录的布局3.下标变量地址计算可以采用另一种方法：直接生成计算下标变量地址的中间代码。考察下述和下标变量有关的产生式： ①→i[②→1,③→]试写出相应求下标变量地址的语义子程序。解答：由于在处理数组定义时，已经将数组的维数n，每一维的上下界Ui、Li，长度di以及数组元素存贮首地址stp，address(a[0,…,0])均存放在数组的信息向量表中。为得到这些数据，用属性id.dim表示数组的维数，函数limit(id,j)返回dj，函数getaddr(id)返回假头地址address(a[0,…,0])，过程Mark_indirect(T)表示在T中添加间址标记。各产生式的语义子程序为：①→i[{.dim:=1；.array:=i.array；/*i.array表示数组名*/.val:=.val；}②→1,{.dim:=1.dim+1；D:=Newtemp；GEN(*,1.val,limit(.array,.dim),D)；GEN(+,D,.val,D)；.val:=D；.array:=1.array;}③→]{Checkdim(.dim,.array.dim)；/*检查维数的正确性*/L:=Newtemp；GEN(+,getaddr(.array),.val,L)；Mark_indirect(L)；.val:=L；}4.过程语句：①→calli()②→1,③→的中间代码采用下面形式：（call,i.VAL,.VAL,…,.VAL）试写出生成上述形式的中间代码的语义子程序。解答：让带有属性：.que（队头）和.tail（队尾）。＃1的语义子程序为：fetch(.que,.tail);Gen(call,i.VAL,.VAL,…,.VAL);＃2的语义子程序为：.que=1.que;.tail=1.tail;Append(.tail,.val);＃3的语义子程序为：MakeQueue(.que,.tail);Append(.tail,.val); 5.考察下面Pascal程序：ProgramP(input,output);  vara,b:integer；      c1:array[1…10]ofreal；   Proceduref1(x,y:integer)；    vard,e:integer；        c2:array[1…20]ofreal；    Proceduref2；      varu,v:real；      begin        …      end；    begin      …      f2；   end；  Proceduref3；    varh1,h2:integer；    begin      …      f1(h1,h2)；    end；begin  … f3；end.⑴给出程序流进入过程f1和f2时区头地址表的内容。⑵给出程序流进入f2时运行栈中的主要内容。解答：本题中过程的嵌套和调用关系可示意性地由图7.5表示。图7.5过程的嵌套和调用关系⑴当程序流进入f1时，区头地址表的内容有以下两项：过程f1的调用记录首址P过程的调用记录首址当程序流进入f2时，区头地址表的内容有以下三项：过程f2的调用记录首址过程f1的调用记录首址P过程的调用记录首址(2)程序流进入f2时，运行栈的主要内容如图7.6所示。 图7.6程序流进入f2时运行栈的情形Chapter81.考察下述文法G[]：→i:=→+→*→()→i试写出各产生式的语义子程序。解答：让非终结符带有属性.type指出数据类型，属性.val存放运算结果。→i:={ifi.type=.typethen  GEN(:=,.val,i.val); elseifi.type=realAND.type=intthen  begin      T:=NEWTEMP;      GEN(float,.val,T);      GEN(:=,T,i.val);  end. elseifi.type=intAND.type=realthen  begin      T:=NEWTEMP;      GEN(int,.val,T);      GEN(:=,T,i.val);  end.elseerror.       }→E1>+{.val:=NEWTEMP; if.type=intAND.type=intthen   begin       .type:=int;       GEN(int+,.val,.val,.val);   end. elseif.type=realAND.type=realthen   begin       .type:=real;       GEN(real+,.val,.val,.val);   end. elseif.type=intAND.type=realthen   begin       .type:=real;       T:=NEWTEMP;       GEN(float,.val,T);       GEN(real+,T,.val,.val);   end. elseif.type=realAND.type=intthen   begin       .type:=real;       T:=NEWTEMP;       GEN(float,.val,T);       GEN(real+,.val,T,.val);   end. elseerror.}→*{.val:=NEWTEMP; if.type=intAND.type=intthen   begin       .type:=int;       GEN(int*,.val,.val,.val);   end. elseif.type=realAND.type=realthen   begin       .type:=real;       GEN(real*,.val,.val,.val);   end. elseif.type=intAND.type=realthen   begin       .type:=real;       T:=NEWTEMP;       GEN(float,.val,T);       GEN(real*,T,.val,.val);   end. elseif.type=realAND.type=intthen   begin       .type:=real;       T:=NEWTEMP;       GEN(float,.val,T);       GEN(real*,.val,T,.val);   end. elseerror.}→(){.val:=.val; .type:=.type;}→i{.val:=i.val; .type:=i.type;}2.试写出第二类if语句翻译的语义动作子程序。解答：设条件语句的产生式为： →ifthen1else2语义可描述为:t:=;ifØtthengotoL1;1;gotoL2;L1:2;L2:让带有属性.type和属性.false、.true（分别指出了假链与真链的链首地址）。运用拆因子技术，把产生式改造为→if→then1→else2各产生式的语义子程序如下：→if{CheckBool(.type);TLT:=NewTL;GEN(LABEL,TLT);Backpatch(.true,TLT);.false:=.false;}→then1{.TL:=NewTL;GEN(BR,.TL);TLF:=NewTL;GEN(LABEL,TLF);Backpatch(.false,TLF);}→else2{GEN(LABEL,.TL);}3.考察Pascal中下面形式定义的for语句：→forV:=todo假定上述形式的for语句等价于：begint1:=e1;t2:=e2;ift1≤t2thenbeginV:=t1;L1:;V:=succ(V);ifV≤t2thengotoL1;endend试写出符合上述规定的语义动作子程序。解答：将产生式拆因子为2个产生式：→forV:=to→do各产生式的语义动作子程序如下：→forV:=to{check(V.type,.type,.type);.next:=NEWTL;GEN(BR>,.val,.val,.next);GEN(:=,.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.考察下面关于整型量和实型量说明的产生式：①→intid②→realid③→,id当用第一个产生式进行归约时，相关的语义子程序应该在该标识符id所对应的登记项登录与整型量相关的信息。假定这一工作由enter_desc完成。产生式1的语义子程序应是：enter_desc(id.val,int);.desc:=int;试写出其他2个产生式的语义动作子程序，并给出enter_desc的具体代码。解答：产生式2的语义动作子程序为：enter_desc(id.val,real);.desc:=real;产生式3的语义动作子程序为：enter_desc(id.val,.desc);.desc:=.desc;5.设有某程序语言的循环语句的产生式→fori:=downtodo其语义是：T1:=;T2:=;i:=T1;L1:ifi-T2<0thengotoL2;;i:=i-1;gotoL1;L2;试写出相应的属性翻译文法及语义动作子程序。解答：将产生式拆因子为：→fori:=downto→do各产生式的语义子程序为：→fori:=downto{CheckType(i.type,.type,.type)；i.val:=.val；.i:=i.val；.TL1:=NewTL；GEN(LABEL,.TL1)；.TL2=NewTL；GEN(BR<,.i,.val,.TL2)；}→do{GEN(-,.i,1,.i)；GEN(BR,.TL1)；GEN(LABEL,.TL2)；} Chapter93.设有算术表达式a+b*c-(c*b+a-e)，要求：⑴写出该表达式的四元组中间代码。⑵把上述四元组中间代码理解成一个基本块，构造该基本块所对应的DAG图。⑶由DAG图重新产生该表达式优化后的四元组中间代码。解答：⑴该表达式的四元组中间代码如下：①(*,b,c,T1)②(+,a,T1,T2)③(*,c,b,T3)④(+,T3,a,T4)⑤(-,T4,e,T5)⑥(-,T2,T5,T6)⑵该基本块p所对应的DAG图如图9.1所示：图9.1基本块p所对应的DAG图⑶根据DAG重写基本块必须满足的约束条件是：DAG中各节点计算时，其子节点已经完成计算。所以重写序列为1、2、3、4、5、6、7、8根据DAG图重写基本块p：①(*,b,c,T1)②(;=,T1,T3)③(+,T1,a,T2)④(:=,T2,T4)⑤(-,T2,e,T5)⑥(-,T2,T5,T6)四元组②和④是无用赋值，可以删除，优化后的四元组为：①(*,b,c,T1)②(+,T1,a,T2)③(-,T2,e,T5) ④(-,T2,T5,T6)4.试将下面程序段划分成基本块并画出相应数据流图：⑴i:=100；L1:ifi<0thengotoL2；…a:=i*6；…i:=i-1；…gotoL1；L2:⑵i:=0；j:=10；L:i:=i+1；a:=4*iifi>=jthengotoL；解答：程序段⑴的各基本块为：p1：i:=100；p2：L1:ifi<0thengotoL2；p3：…    a:=i*6；    …    i:=i-1；    …    gotoL1；p4：L2:相应的程序流图如图9.2所示。图9.2程序段⑴的程序流图程序段⑵的各基本块为：p1：i:=0；    j:=10；p2：L:i:=i+1；    a:=4*i    ifi>=jthengotoL；相应的程序流图如图9.3所示。 图9.3程序段⑵的程序流图5.试写出习题4中程序段优化后的中间代码。解答：a)程序段⑴的中间代码最初为：(:=,100,i)(LABEL,L1)(BR<,i,0,L2)   …(*,i,6,a)   …(-,i,1,i)   …(BR,L1)(LABEL,L2)代码优化：1）运算强度减弱因为在循环中有：a:=i*6而a在循环中不改变值，每循环一次，变量i减1，于是可以将乘法改为减法：a:=a-62)删除归纳变量i是循环的基本归纳变量，a是与i同族的归纳变量，且有线性关系：a:=i*6因此，i<0可以用a<0替代。优化后的中间代码为：(:=,600,a)(LABEL,L1)(BR<,a,0,L2)   …(-,a,6,a)(BR,L1)(LABEL,L2)b)程序段⑵的中间代码最初为：(:=,0,i)(:=,10,j)(LABEL,L)(+,i,1,i)(*,i,4,a)(BR>=,i,j,L)代码优化：1）常数合并j初始赋值为10，期间又没其它赋值，所以i>=j可改写为：i>=102)删除无用赋值j在今后没有被引用过，所以(:=,10,j)成为无用赋值，可以删除。3）运算强度减弱因为在循环中有：a:=4*i而a在循环中不改变值，每循环一次，变量i加1，于是可以将乘法改为加法：a:=a+4 4)删除归纳变量i是循环的基本归纳变量，a是与i同族的归纳变量，且有线性关系：a:=4*i因此，i<10可以用a<40替代。优化后的中间代码为：(:=,0,a)(LABEL,L)(+,a,4,a)(BR>=,a,40,L) '