搜索
《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站1第8章语法制导翻译和中间代码生成第1题给出下面表达式的逆波兰表示(后缀式)：(1)a*(-b+c)(2)if(x+y)*z=0thens=(a+b)*celses=a*b*c∶∶答案：给出下面表达式的逆波兰表示(后缀式)：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else运算）如果写成这样：xy+z*0=sab+c*:=sabc**:=￥，则是错误的，因为写表达式和赋值语句的中间代码序列，或是写它们的代码生成过程，必须注意按照算符优先序进行，这实际上是按照LR分析过程进行的。例如：写出赋值语句a:=a+b*c*(d+e)的四元式中间代码,当前四元式序号为100。不能写成：100(+,d,e,t1)101(*,b,c,t2)102(*,t2,t1,t3)103(+,a,t3,t4)104(:=,t4,-,a)应该写成：100(*,b,c,t1)101(+,d,e,t2)102(*,t1,t2,t3)103(+,a,t3,t4)104(:=,t4,-,a)第2题请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式、四元式序列、树形、逆波兰，当前序号为100。答案：三元式：100(+,a,b)101(+,c,d)102(*,(1),(2))《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站2103(-,(3),/)104(+,a,b)105(+,(5),c)106(-(4),(6))间接三元式：间接三元式序列间接码表100(+，a,b)(100)101(+，c,d)(101)102(*，(1),(2))(102)103(-，(3),/)(103)104(+，(1),c)(100)(104)105(-，(4),(1))(105)或者：间接三元式：100(+，a,b)101(+，c,d)102(*，(1),(2))103(-，(3),/)104(+，(1),c)105(-，(4),(1))间接码表：100101102103100104105四元式：100(+,a,b,t1)101(+,c,d,t2)102(*,t1,t2,t3)103(-,t3,/,t4)104(+,a,b,t5)105(+,t5,c,t6)106(-,t4,t6,t7)树形：《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站3逆波兰：ab+cd+*-ab+c+-［典型例题］：写出ifAandBandCDthenifABthenF:=1elseF:=0elseG:=G+1;的四元式序列,翻译过程中,采用then与else的昀近匹配原则。(1)(jnz,A,_,3)/*AandBandCD的四元式*/(2)(j,_,_,13)(3)(jnz,B,_,5)(4)(j,_,_,13)(5)(j,C,D,7)(6)(j,_,_,13)(7)(j,A,B,9)/*AB的四元式*/(8)(j,_,_,11)(9)(:=,1,_,F)/*F:=1*/(10)(j,_,_,14)(11)(:=,0,_,F)/*F:=0*/(12)(j,_,_,14)(13)(:=,G,1,G)(14)［典型例题］：写出WHILEACANDBDDOIFA=1THENC:=C+1ELSEWHILEA=DDOA:=A+2;的四元式序列。(100)(j,A,C,102)(101)(j,-,-,114)(102)(j,B,D,104)《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站4(103)(j,-,-,114)(104)(j=,A,1,106)(105)(j,-,-,109)(106)(+,C,1,T)(107)(:=,T,-,C)(108)(j,-,-,100)(109)(j=,A,D,111)(110)(j,-,-,100)(111)(+,A,2,T)(112)(:=,T,-,A)(113)(j,-,-,109)(114)《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站5第3题采用语法制导翻译思想，表达式E的“值”的描述如下：产生式语义动作(0)S′→E{printE.VAL}(1)E→E1+E2{E.VAL=E∶1.VAL+E2.VAL}(2)E→E1*E2{E.VAL=E∶1.VAL*E2.VAL}(3)E→(E1){E.VAL=E∶1.VAL}(4)E→n{E.VAL=n.LEXVAL}∶如采用LR分析方法，给出表达式(5*4+8)*2的语法树并在各结点注明语义值VAL。答案：《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站6采用语法制导翻译思想，表达式E的“值”的描述如下：产生式语义动作(0)S′→E{printE.VAL}(1)E→E1+E2{E.VAL=E∶1.VAL+E2.VAL}(2)E→E1*E2{E.VAL=E∶1.VAL*E2.VAL}(3)E→(E1){E.VAL=E∶1.VAL}(4)E→n{E.VAL=n.LEXVAL}∶假如终结符n可以是整数或实数，算符+和*的运算对象类型一致，语义处理增加“类型匹配检查”，请给出相应的语义描述。答案：(0)S′→E{iferror≠1thenprintE.VAL}(1)E→E1+E2{ifE1.TYPE=intANDE2.TYPE=intthenbeginE.VAL:=E1.VAL+E2.VAL;E.YTPE:=int;endelseifE1.TYPE=realANDE2.TYPE=realthenbeginE.VAL:=E1.VAL+E2.VAL;E.YTPE:=real;endelseerror=1}(2)E→E1*E2{ifE1.TYPE=intANDE2.TYPE=intthenbeginE.VAL:=E1.VAL*E2.VAL;;E.YTPE:=int;endelseifE1.TYPE=realANDE2.TYPE=realthenbeginE.VAL:=E1.VAL*E2.VAL;;E.YTPE:=real;endelseerror=1}(3)E→(E1){E.VAL:=E1.VAL;E.TYPE:=E1.TYPE}(4)E→n{E.VAL:=n.LEXVAL;E.TYPE:=n.LEXTYPE}《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站7第5题令S.val为下面的文法由S生成的二进制数的值(如，对于输入101.101，S.val=5.625)；SÆL.L|LLÆLB|BBÆ0|1按照语法制导翻译的方法，对每个产生式给出相应的语义规则。（中国科学院计算所1995年）答案：加入新的开始符号S`和规则S`ÆS，得到增广文法。语法制导定义如下：产生式语义规则S`ÆSprint(S.val)SÆL1.L2S.val:=L1.val+L2.val/2L2.lengthSÆLS.val:=L.valLÆL1BL.val:=L1.val*2+B.valL.length:=L1.length+1LÆBL.val:=B.valL.length:=1BÆ0B.val:=0BÆ1B.val:=1如果题目是S::=L.L|LL::=LB|BB::=0|1则写成:S`::=S{print(S.val);}S::=L1.L2{S.val:=L1.val+L2.val/2L2.length;}S::=L{S.val:=L.val;}L::=L1B{L.val:=L1.val*2+B.val;L.length:=L1.length+1;}L::=B{L.val:=B.val;L.length:=1;}B::=0{B.val:=0;}B::=1{B.val:=1;}《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站8第6题下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为实数。EÆE+T|TTÆnum.num|num（１）给出语法制导定义确定每个子表达式的类型。（２）把表达式翻译成前缀形式，并且决定类型。试用一元运算符inttoreal把整型值转换为相等的实型值，以使得前缀表达式中两个运算对象是同类型的。答案：（１）设type是综合属性，代表各非终结符的“类型”属性语法制导定义产生式语义规则EÆE1+TIF(E1.type=integer)and(T.type=integer)THENE.type:=integerELSEE.type:=realEÆTE.type:=T.typeTÆnum.numT.type:=realTÆnumT.type:=integer（２）设code为综合属性，代表各非终结符的代码属性type为综合属性，代表各非终结符的类型属性inttoreal把整型值转换为相等的实型值vtochar将数值转换为字符串《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站9语法制导定义产生式语义规则S→EprintE.codeEÆE1+TIF(E1.type=integer)and(T.type=integer)THENbeginE.type:=integerE.code='+'||E1.code||T.code;endELSEbeginE.type:=realIFE1.type=integerTHENbeginE1.type:=realE1.val:=inttoreal(E1.val)E1.code=vtochar(E1.val)endIFT.type:=integerTHENbeginT.type:=realT.val:=inttoreal(T.val)T.code=vtochar(T.val)endE.code='+'||E1.code||T.code;EndEÆTE.type:=T.typeE.val:=T.valE.code=vtochar(E.val)TÆnum.numT.type:=realT.val:=num.num.lexvalT.code=vtochar(T.val)TÆnumT.type:=integerT.val:=num.lexvaT.code=vtochar(T.val)《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站10第7题假设变量的说明是由下列文法生成的：DÆiLLÆ,iL|:TTÆinteger|real建立一个语法制导定义，把每一个标志符的类型加在符号表中。答案：type为综合属性，代表类型属性，函数addtype实现向符号表中i对应项填类型信息。语法制导定义产生式语义动作DÆiLD.Type:=L.Typeaddtype(i.entry,D.type)LÆ,iL1L.Type:=L1.Typeaddtype(i.entry,L.type)LÆ:TL.type:=T.typeTÆintegerT.type:=integerTÆrealT.type:=real《编译原理》课后习题答案第八章盛威网（）专业的计算机学习网站11附加题问题1：请将下列语句while(ABdoif(CD)thenX:=Y+Z翻译成四元式答案：假定翻译的四元式序列从（100）开始：（100）ifABgoto（102）（101）goto（107）（102）ifCDgot（104）（103）goto（100）（104）T=Y+Z∶（105）X=T∶（106）goto（100）（107）问题2：对于输入的表达式(4*7+1)*2，根据下表的语法制导定义建立一棵带注释的分析树。val:表示非终结符的整数值,综合属性,lexval是单词d