编译原理(习题课)(二)

编译原理朱雪峰博士计算机科学与技术系Tel:89733787(O)Email:xuefeng.zhu@cup.edu.cn1第六题（P36第11题）解：分析L2，要求b和c的个数一样多，因此可以使用一个非终结符去生成bncn串，而用另外一个非终结符去生成ai，nn因此，可以模拟L1使用一个非终结符去生成bc，而用另外一个非终结符去生成ai。L2的文法：S→ABA→aA|εB→bBc|bc2第六题（P36第11题）nnmmnnmm解：分析L3，可以将abab分成两段考虑，即ab和ab，然后使用两个非终结符分别去产生它们。L3的文法：S→ABA→aAb|εB→aBb|ε3第六题（P36第11题）解：L4不能采用分段处理的方式，它要求中间的0和1的个数相同，而且一前一后的1和0的个数相同。对于这种文法我们可以采用从里向外扩展的方式进行，即先用一个非终结符生成处于中间的m个0和m个1，然后，使用另外一个非终结符在该串的基础上扩充前后的n个1和n个0。L4:A→0A1|εS→1S0|A4第七题（P64第7题）7.构造下列正规式相应的DFA①1(0|1)*101②1(1010*|1(010)*1)*0③0*10*10*10*④(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*5第七题（P64第7题①）6第七题（P64第7题①）状态01{X}0ø{1,2,3}1{1,2,3}1{2,3}2{2,3,4}3{2,3}2{2,3}2{2,3,4}3{2,3,4}3{2,5,3}4{2,3,4}3{2,3,5}4{2,3}2{2,3,4,Y}5{2,3,4,Y}5{2,5,3}4{2,4,3}37状态01{X}0ø{1,2,3}1第七题（P64第7题①）{1,2,3}1{2,3}2{2,3,4}3{2,3}2{2,3}2{2,3,4}3{2,3,4}3{2,5,3}4{2,3,4}3{2,3,5}4{2,3}2{2,3,4,Y}5{2,3,4,Y}5{2,5,3}4{2,4,3}38第七题（P64第7题①）á初始划分：{{0,1,2,3,4},{5}}，{0,1,2,3,4}0={2,4,_},{0,1,2,3,4}1={1,3,5}。由于0不能接受字符0，需要把状态0划分出来；另外，只有状态4读入字符1后进入状态5，因此将状态4划分出来，划分的结果为4个集合：{{0},{1,2,3},{4},{5}}。á对于集合{1,2,3}，由于{1,2,3}0={2,4}，因此需要对{1,2,3}进一步划分，划分结果为5个集合：{{0},{1,2},{3},{4},{5}}。检查集合{1,2}，由于{1,2}0={2},{1,2}1={3}，不需要进一步的划分。所以最终划分结果为5个集合：{{0},{1,2},{3},{4},{5}}9第七题（P64第7题①）10第七题（P64第7题②）1(1010*|1(010)*1)*011第七题（P64第7题②）状态01状态01{1}ø{2}{4,7,9}ø{5,8,2}{2}{9}{3,6}{5,2,9}{5,2,9}{3,6}{9}øø{3,6,8}{4,7,6}{2}{3,6}{4,7}{2}{4,7,6}{7}{5,8,2}{4,7}ø{5,8,2}{7}ø{8}{5,8,2}{5,2,6,9}{3,6}{8}{6}ø{5,2,6,9{5,2,7,9}{3,6,2}{6}{7}{2}{5,2,7,9}{5,2,9}{3,6,8}{3,6,2}}{4,7,9}{3,6,2}12第七题（P64第7题②）13第七题（P64第7题③）0*10*10*10*14第七题（P64第7题④）(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*15第七题（P64第7题④）状态01{1}{2}{3}{2}{1,4}ø{3}ø{1,4}{1,4}{2,5}{3,7}{2,5}{1,4}{6}{3,7}{6}{1,4}{6}{8,10}{9,12}{8,10}{6}{11,4}{9,12}{11,4}{6}{11,4}{13,5}{14,7}{5,13}{11,4}{6}{14,7}{6}{11,4}16第七题（P64第7题④）17第八题（P64第8题）8.给出下面正规 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式：①以01结尾的二进制数串；②能被5整除的十进制整数；③包含奇数个1或奇数个0的二进制数串；④英文字母组成的所有符号串，要求符号串中的字母依照字典序排列；⑤没有重复出现的数字的数字符号串的全体；⑥最多有一个重复出现的数字的数字符号串的全体；⑦不包含子串abb的由a和b组成的符号串的全体。18第八题（P64第8题）解：（1）本题要求的是二进制串，即由0和1构成的串，并且必须以01结尾，所以本题可以分两部分去完成，一部分实现由0和1构成的任意串，一部分即01，然后将它们连接到一起就可以了，因此答案为(1|0)*01。19第八题（P64第8题）（2）本题要求的是十进制整数，也就是由0~9这10个数字组成的字符串，并且不能以0开头（整数0除外），要求能够被5整除，则该串必须以0或5结尾。可以分成两种情况：一种情况是该整数只有1位，则该整数有0和5两种可能；另一种情况是该整数有多位，则该整数可以分为3部分来考虑。一是第一位必须不为0，二是最后一位必须为0或5，三是中间部分可有可无，并且可以由0~9之间任意数字构成，所以本题的正规表达式为：(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)|(0|5)20第八题（P64第8题）（3）由于0和1在二进制串中的奇数出现具有对偶性，因此我们只考虑一种情况，另一种情况可以类似求得，考虑包含奇数个0的字符串：由于只关心0的个数的奇偶性，我们可以把二进制串分成多段来考虑，第一段为二进制串的开始到第一个0为止，这一段包含1个0，并且0的前面有0个或多个1；对于剩下的二进制串按照每段包含两个0的方式去划分，即以0开始，以0结尾，中间可以有0个或多个1.如果一个二进制串被这样划分完后，剩下的部分如果全部是全1串（这些全1串在前面划分的串之间或最后），则该二进制串就具有奇数个0，所以该二进制串可以这样描述：以第一段（1*0）开始，后面由全1串（1*）以及包含两个0的串（01*0）组成，所以包含奇数个0的正规式为：1*0(1|01*0)*。本题答案为1*0(1|01*0)*|0*1(0|10*1)*21第八题（P64第8题）（4）(a|A)*(b|B)*…(z|Z)*22第八题（P64第8题）（5）令ri=i|ε（i=0,1,2,…,9）R记为∑iR0|R1|R2|…|R9i∈(0,1,2,L,9)令P(0,1,2,…,9）表示i=0,1,2,…,9的全排列rrr其中∑i0i1Li9i0,i1,Li9∈P(0,1,L,9)23第八题（P64第8题）（6）∑irrr其中i,i,i∈P(0,1,,9)∑i0i1Li901L9Li∈(0,1,2,L,9)24第八题（P64第8题）(7)直接写出满足条件的正规表达式。考虑满足条件的字符串：在串的开始部分可以有0个或多个b，但是一旦a出现以后，要么后面还是a，要么后面只能跟一个b然后还得跟a，由此我们得到满足条件的正规式为：b*(a|ab)*25第九题（P64第12题）12.将图3.18的(a)和(b)分别确定化和最小化。26第九题（P64第12题）解：图(a)中为一个NFA，所以需要先将其确定化。得到DFA，然后再将其最小化。第一步：确定化，得到DFA。确定化的结果见左表所列。给状态编号，得到右表所列的状态转换矩阵。状态ab状态ab{0}{0,1}{1}012{0,1}{0,1}{1}112{1}{0}ø2027第九题（P64第12题）解：根据状态转换矩阵得到如图所示的DFA28第九题（P64第12题）解：第二步：最小化。首先将状态划分成两个集合{0,1}和{2}，由于{0,1}a={1}、{0,1}b={2}，所以{0,1}和{2}就是最后的分划，因此得到如下图所示的最小化的DFA。29第九题（P64第12题）解：图(b)中所示为一个DFA，不需要确定化，因此只需最小化即可。首先将状态划分为两个集合{{0,1},{2,3,4,5}}，由于{0,1}a={1}、{0,1}b={2,4}和{2,3,4,5}a={1,3,0,5}、{2,3,4,5}b={2,3,4,5}，所以可以进一步划分为{{0,1},{2,4},{3,5}}。然后有{0,1}a={1}、{0,1}b={2,4}、{2,4}a={1,0}、{2,4}b={3,5}、{3,5}a={3,5}、{3,5}b={2,4}，因此，最后划分结果就是{{0,1},{2,4},{3,5}}30第九题（P64第12题）解：最小化后的DFA如下图所示：31第十题（P65第14题）14.构造一个DFA，它接受∑={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。32第十题（P65第14题）第一步：写出正规表达式。根据题意，该DFA接受的字符串由0和1组成，并且每个1的后面都有0直接跟在右边，因此，可以将该字符串理解为由0和10构成的串，则相应的正规表达式就是(0|10)*第二步：构造NFA。首先得出图1。然后按照P50的替换规则对图1进行分解后得到如图2所示的NFA。33第十题（P65第14题）(0|10)*XY1NFA34第十题（P65第14题）第三步：确定化，得到DFA。确定化的结果见左表所列，给状态编号，得到如右表所列的状态转换矩阵。状态01状态01{X,1,Y}{1,Y}{2}012{1,Y}{1,Y}{2}112{2}{1,Y}ø2135第十题（P65第14题）根据状态转换矩阵得到的DFA如下图所示：36第十题（P65第14题）第四步，使用P57的方法对该DFA进行最小化。最小化分0析过程如下：1初始分划：{0,1}、{2}010由于{0,1}0={1}，DFA{0,1}1={2}最小化后的DFA如下图所示，该DFA即为所求。37第十一题（P81第1题）1.考虑下面文法G1：S→a|∧|(T)T→T,S|S①消去G1的左递归。然后，对每个非终结符，写出不带回溯的递归子程序。②经改写后的文法是否是LL(1)的？给出它的预测分析表。38第十一题（P81第1题）解：（1）按照T、S的顺序消除左递归，得到文法：G’(S)：S→a|∧|(T)T→ST’T’→,ST’|ε对每个非终结符，写出不带回溯的递归子程序（略，不讲）39第十一题（P81第1题）（2）首先计算每个非终结符的FIRST集合和FOLLOW集合（P78和P79页计算FIRST和FOLLOW的算法）FIRST(S)={a,∧,(}#∊FOLLOW(S)FIRST(T)={a,∧,(})∊FOLLOW(T)FIRST(T’)/{ε}⊆FOLLOW(S)FIRST(T’)={,,ε}FOLLOW(T)⊆FOLLOW(T’)FOLLOW(T)⊆FOLLOW(S)FOLLOW(S)={#,,,)}FOLLOW(T)={)}FOLLOW(T’)={)}40第十一题（P81第1题）（2）构造预测分析表如下：P79页构造分析表M的算法a∧(),#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T→εT→,ST’从表中可以看出没有多重入口，所以改造后的文法是LL(1)文法41第十二题（P81第2题）2.对下面的文法G：E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧①计算这个文法的每个非终结符的FIRST和FOLLOW。②证明这个文法是LL(1)的。③构造它的预测分析表。④构造它的递归下降分析程序。42第十二题（P81第2题）（1）计算每个非终结符的FIRST集合和FOLLOW集合：FIRST(E)={(,a,b,∧}FIRST(E’)={+,ε}FIRST(T)={(,a,b,∧}FIRST(T’)={(,a,b,∧,ε}FIRST(F)={(,a,b,∧}FIRST(F’)={*,ε}FIRST(P)={(,a,b,∧}43第十二题（P81第2题）á计算每个非终结符的FIRST集合#∊FOLLOW(E)和FOLLOW集合：)∊FOLLOW(E)FOLLOW(E)={),#}FIRST(E’)/{ε}⊆FOLLOW(T)FIRST(T’)/{ε}⊆FOLLOW(F)FOLLOW(E’)={),#}FIRST(F’)/{ε}⊆FOLLOW(P)FOLLOW(T)={(+,),#}FOLLOW(E)⊆FOLLOW(E’)FOLLOW(E)⊆FOLLOW(T)FOLLOW(T’)={+,),#}FOLLOW(T)⊆FOLLOW(T’)FOLLOW(F)={(,a,b,∧,+,),#}FOLLOW(T)⊆FOLLOW(F)FOLLOW(F)⊆FOLLOW(F’)FOLLOW(F’)={(,a,b,∧,+,),#}FOLLOW(F)⊆FOLLOW(P)FOLLOW(P)={*,(,a,b,∧,+,),#}FOLLOW(E’)⊆FOLLOW(E)FOLLOW(T’)⊆FOLLOW(T)44第十二题（P81第2题）（2）根据P73，可以证明这个文法是LL(1)的。或根据第(3)步构造的预测分析表无多重入口，也可证明。45第十二题（P81第2题）（3）构造预测分析表如下：+*()ab∧#EE→TE’E→TE’E→TE’E→TE’E’E’→+EE’→εE’→εTT→FT’T→FT’T→FT’T→FT’T’T’→εT’→TT’→εT’→TT’→TT’→TT’→εFF→PF’F→PF’F→PF’F→PF’F’F’→εF’→*F’F’→εF’→εF’→εF’→εF’→εF’→εPP→(E)P→aP→bP→∧46第十二题（P81第2题）（4）构造它的递归下降分析程序。（略，不讲）47第十三题（P82第3题）（选作，不讲）48第十四题（P133第1题）1.令文法G1为：E→E+T|TT→T*F|FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。49第十四题（P133第1题）解：因为E⇒E+T⇒E+T*F，所以E+T*F是该文法的一个句型。短语：E+T*F、T*F直接短语：T*F句柄：T*F50第十五题（P133第2题）2.考虑下面的 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 结构文法G2：S→a|∧|(T)T→T,S|S①给出(a,(a,a))和(((a,a),∧,(a)),a)的最左和最右推导。②指出(((a,a),∧,(a)),a)的MATCH_ word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 _1715549909471_1归约及每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。51第十五题（P133第2题）解：①最左推导和最右推导过程（略）最左推导指每一步都是对最左的非终结符进行替换，最右推导是指每一步都是对最右的非终结符进行替换。②规范归约过程及每一步的句柄，“移进-归约”过程，以及语法树的自下而上构造过程等均可按照语法树进行。具体过程非常繁杂简单，略，不讲。52第十六题（P133第3题）3.考虑下面的表格结构文法G2：S→a|∧|(T)T→T,S|S①计算文法G2的FIRSTVT和LASTVT。②计算G2的优先关系。G2是一个算符优先文法吗？③计算G2的优先函数。④给出输入串(a,(a,a))的算符优先分析过程。53第十六题（P133第3题）①计算FIRSTVT和LASTVT集合根据P91规则(1)，我们有a、∧、(∊FIRSTVT(S)；,∊FIRSTVT(T)。根据规则(2)，我们有：FIRSTVT(S)⊆FIRSTVT(T)。因此，我们有：FIRSTVT(S)={a,∧,(}，FIRSTVT(T))={,,a,∧,(}同理，我们有：LASTVT(S)={a,∧,)}，LASTVT(T))={,,a,∧,)}54第十六题（P133第3题）②计算该文法的优先关系a∧(),#根据文法我们有：(⋖FIRSTVT(T)、a⋗⋗⋗LASTVT(T)⋗)、∧⋗⋗⋗,⋖FIRSTVT(S)、(⋖⋖⋖≖⋖LASTVT(T)⋗,、)⋗⋗⋗#⋖FIRSTVT(S)、LASTVT(S)⋗#、,⋖⋖⋖⋗⋗#≖#、(≖)。#⋖⋖⋖≖因此，G2是算符优先文法55第十六题（P133第3题）③方向图如下图，优先函数56第十六题（P133第3题）③优先函数a∧(),#f662642g77723257第十六题（P133第3题）④输入串(a,(a,a))的算符优先分析过程栈输入字符串动作#(a,(a,a))#预备#(a,(a,a))#移进#(a,(a,a))#移进#(S,(a,a))#归约#(T,(a,a))#归约？#(T,(a,a))#移进#(T,(a,a))#移进#(T,(a,a))#移进#(T,(S,a))#归约#(T,(T,a))#归约？58第十六题（P133第3题）④输入串(a,(a,a))的算符优先分析过程栈输入字符串动作#(T,(T,a))#移进#(T,(T,a))#移进#(T,(T,S))#归约#(T,(T))#归约#(T,(T))#移进#(T,S)#归约#(T)#归约#(T)#移进#S#归约acc59第十七题（P134第5题）5.考虑文法S→AS|bA→SA|a①列出这个文法的所有LR(0)项目。②构造这个文法的LR(0)项目集规范族及识别活前缀的DFA。③这个文法是SLR的吗？若是，构造出它的SLR分析表。④这个文法是LALR或LR(1)的吗？60第十七题（P134第5题）①文法的所有LR(0)项目如下：0.S’→.S1.S’→S.2.S→.AS3.S→A.S4.S→AS.5.S→.b6.S’→b.7.A→.SA8.A→S.A9.A→SA.10.A→.a11.A→a.61A.②通过.I6:A→SAI3:S→S..I:A→S.AS→ASA→SA5S.CLOSU..S→ASA→SASS→AS...AS→bA→aS→b.RE和S→.ASA→.SAA→SAab.S→.bA→.aA→aGO函数SA构造的SASA.LR(0)项..I4:S→ASI7:S→ASI0:S→S..S→.ASA→SAS→AS.目集规.AS→.bSS→ASS→b..A→.SAS→bA→SA...A→SA范族及A→aA→aA→.abab识别活aba前缀的..bI1:A→aI2:S→bbDFA如a下图所a示：62第十七题（P134第5题）③I3、I6和I7包含“移进-归约”冲突。I3：FOLLOW(S’)={#}，不包含a、b。I6：FOLLOW(S)={#,a,b}包含a、b，“移进-归约”冲突无法消解。I7：FOLLOW(A)={a,b}包含a、b，“移进-归约”冲突无法消解。所以不是SLR文法。63第十七题（P134第5题）④构造LR(1)项目集规范族如图所示：对于状态5，因为包含项目[A→SA.,a/b]，所以遇到搜索符号a或b时，应该用A→SA归约。又因为状态5包含项目[A→.a,a/b]，所以遇到搜索符号a时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。（当然也不是LALR文法）6465第十八题（P135第8题）（选作，不讲）66第二十题（P164第1题）1.按照表6.1所示的属性文法，构造表达式(4*7+1)*2的附注语法树。6768第二十一题（P164第2题）2.对表达式((a)+(b)):①按照表6.4所示的属性文法构造该表达式的抽象语法树；②按照图6.17所示的翻译模式，构造该表达式的抽象语法树。69第二十一题（P164第2题）①按表6.4所列的属性文法，表达式((a)+(b))带注释的语法分析树如图所示。其中，构造出的抽象语法树用实线表示，语法分析树用虚线表示，语法分析树之中的E和T标识的结点中用综合属性nptr来保存指向抽象语法树中该非终结符号对应的结点的指针（图中用带箭头的虚线表示）。7071第二十一题（P164第2题）②按图6.17所示的翻译模式，表达式((a)+(b))带注释的语法分析树如图所示。7273第二十二题（P164第5题）5.下列文法对整形常数和实型常数施用加法运算符+生成表达式；当两个整型数相加时，结果仍为整型数，否则，结果为实型数：E→E+T|TT→num.num|num①试给出确定每个子表达式结果类型的属性文法；②扩充(1)的属性文法，使之把表达式翻译成后缀形式，同时也能确定结果的类型。应该注意施用一元运算符inttoreal把整型数转换成实型数，以便使后缀形如加法运算符的两个操作数具有相同的类型。74第二十二题（P164第5题）解：确定每个子表达式结果类型的属性文法是比较容易定义的。关键是如何扩充此属性文法，使之把表达式翻译成后缀形式。我们将不在name或num.num向T归约的时候输出该运算对象，而是把运算对象的输出放在T或E+T向E归约的时候。75第二十二题（P164第5题）解：这是因为考虑输出类型转换算符inttoreal的动作可能在E+T向E归约的时候进行，如果这时两个运算对象都在前面name或num.num向T归约的时候已经输出，需要为第1个运算对象输出类型转换符时就已经为时太晚。另外需要注意的是，在E+T向E归约时，该加法运算的第1个运算对象已经输出。所以E→E+T的语义规则不需要有输出E运算对象的动作。76第二十二题（P164第5题）（1）为文法符号E和T配以综合属性type，用来表示它们的类型。类型值分别用int和real来表示。确定每个子表达式结果类型的属性文法如下：产生式语义规则E→E+TE.type:=ifE1.type=intandT.type=intthenintelserealE→TE.type:=T.typeT→num.numT.type:=realT→numT.type:=int77第二十二题（P164第5题）（2）下面属性文法将表达式的后缀表示打印输出，其中lexeme属性表示单词的拼写。产生式语义规则E→E1+TifE1.type=realandT.type=intthenbeginE.type:=real;print(T.lexeme);print(‘inttoreal’)endifE1.type=intandT.type=realthenbeginE.type:=real;print(‘inttoreal’);print(T.lexeme)endelsebeginE.type:=E1.type;print(T.lexeme)end;print(‘+’);78第二十二题（P164第5题）（2）下面属性文法将表达式的后缀表示打印输出，其中lexeme属性表示单词的拼写。产生式语义规则E→TE.type:=T.type;print(T.lexeme)T→num1.num2T.type:=real;T.lexeme:=num1.lexeme|“.”|num2.lexemeT→numT.type:=int;T.lexeme:=num.lexeme79第二十三题（P164第7题）7.下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：S→L.L|LL→LB|BB→0|1试设计求S.val的属性文法，其中，已知B的综合属性c，给出由B产生的二进位的结果值。例如，输入101.101时，S.val=5.625，其中第一个二进位的值是4，最后一个二进位的值是。0.12580第二十三题（P164第7题）解：假设一个二进制数为：am…a1a0.bn…b1b0，其中，ai(i=0、1、…、m)和bj(j=0、1、…、n)为二进制数字，则该二进制数的十进制值为：m10-1-n-n-1am*2+…+a1*2+a0*2+bn*2+…b1*2+b0*2=m10n10)n+1am*2+…+a1*2+a0*2+(bn*2+…b1*2+b0*2/2根据此 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 ，我们在语法制导翻译时，对二进制数字串L，不仅要计算其值L.val，还要计算其长度L.length（二进制数字个数）。如果L为小数部分，则其值L.val要除以2L.length。81第二十三题（P164第7题）解：因此，我们所设计的属性文法如下：产生式语义动作S’→S{print(S.val)}L2.lengthS→L1.L2{S.val:=L1.val+L2.val/2}S→L{S.val:=L.val}L→L1B{L.val:=L1.val*2+B.c}{L.length:=L1.length+1}L→B{L.val:=B.c;L.length:=1}B→1{B.c:=1}B→0{B.c:=0}82第二十四题（P165第11题）选做题（略）83第二十五题（P165第12题）选做题（略）84第二十六题（P217第1题）1.给出下面表达式的逆波兰表示（后缀式）：a*(-b+c)notAornot(CornotD)a+b*(c+d/e)(AandB)or(notCorD)-a+b*(-c+d)(AorB)and(CornotDandE)if(x+y)*z=0then(a+b)↑celsea↑b↑c85第二十六题（P217第1题）解：ab@c+*AnotCDnotornotorabcde/+*+ABandCnotDorora@bc@d+*+ABorCDnotEandorandxy+z*0=ab+c↑abc↑↑if_then_else86第二十七题（P217第3题）3.请将表达式-(a+b)*(c+d)-(a+b+c)分别表示为三元式、间接三元式和四元式序列。87第二十七题（P217第3题）三元式序列：四元式序列：(1)(+,a,b)(1)(+,a,b,T1)(2)(@,(1),_)(2)(@,T1,_,T2)(3)(+,c,d)(3)(+,c,d,T3)(4)(*,(2),(3))(4)(*,T2,T3,T4)(5)(+,a,b)(5)(+,a,b,T5)(6)(+,(5),c)(6)(+,T5,c,T6)(7)(-,(4),(6))(7)(-,T4,T6,T7)88第二十七题（P217第3题）间接三元式序列：间接码表(1)(+,a,b)(1)(2)(@,(1),_)(2)(3)(3)(+,c,d)(4)(4)(*,(2),(3))(1)(5)(+,(1),c)(5)(6)(-,(4),(5))(6)89第二十八题（P218第4题）4.按7.3节所说的办法，写出下面赋值语句A:=B*(-C+D)的自下而上语法制导翻译过程。给出所产生的三地址代码。90第二十八题（P218第4题）S→id:=E{p:=lookup(id.name);ifp≠nilthenemit(p‘:=’E.place)elseerror}E→E1+E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘+’E2.place)}E→E1*E2{E.place:=newtemp;emit(E.place‘:=’E1.place‘*’E2.place)}E→-E1{E.place:=newtemp;emit(E.place‘:=’‘uminus’E1.place)}E→(E1){E.place:=E1.place}E→id{p:=lookup(id.name);ifp≠nilthenE.place:=pelseerror}91第二十八题（P218第4题）根据语法分析树，最终生成的四元式序列如下：T1:=@CT2:=T1+DT3:=B*T2A:=T392第二十九题（P218第5题）5.按7.3.2所给的翻译模式，把下列赋值语句翻译为三地址代码：A[i,j]:=B[i,j]+C[A[k,l]]+D[i+j]9394第二十九题（P218第5题）所得结果如下：T1:=i*20T8:=k*20T15:=T7+T14T1:=T1+jT8:=T8+lT16:=i+jT2:=A-84T9:=A-84T17:=D-4T3:=4*T1T10:=4*T8T18:=4*T16T4:=i*20T11:=T9[T10]T19:=T17[T18]T4:=T4+jT12:=C-4T20:=T15+T19T5:=B-84T13:=4*T11T2[T3]:=T20T6:=4*T4T14:=T12[T13]95T7:=T5[T6]