北大计算机考研资料编译原理答案r

1、5.1：对于输入的表达式(4*7+1)*2，根据表5.1的语法制导定义建立一棵带注释的分析树。解:5.4：下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结 果为整数，否则为实数。EàE+T | TTànum.num | numa):给出语法制导定义确定每个子表达式的类型b):扩充a)中的语法制导定义把表达式翻译成前缀形式，并且决定类型。试用一元运算符inttoreal把整型值转换为相等的实型值，以使得前缀表达式中两个运算对象是同类型的。解：a)产生式语义规则EàE1+TIF (E1.type=integer) and (T.type=i

2、nteger) THEN E.type:=integerELSE E.type:=realEàTE.type:=T.typeTànum.numT.type:=realTànumT.type:=integerb:)产生式语义规则EàE1+TIF (E1.type=integer) and (T.type=integer) THEN BEGIN E.type:=integer Print(+,E1.val,T.val) ENDELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=real

3、E1.val:=inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(+,E1.val,T.val)ENDEàTE.type:=T.typeE.val:=T.valTànum.numT.type:=realT.val:=num.num.lexvalTànumT.type:=integerT.val:=num.lexval5.5 令综合属性val给出在下面的文法中的S产生的二进制数的值(如，对于输入101.101，S.val

4、=5.625)；SàL.L | LLàLB | BBà0 | 1a): 试用各有关综合属性决定S.val解：产生式语义规则SàL1.L2Sà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:=15.6：重写例5.3中语法制导定义的基础文法，使类型信息只需通过综合属性传递。解：改写文法：DàL,id | LLàT idT

5、4;int | real 语法制导定义产生式语义规则DàL,idD.type:=L.typeAddtype(id.entry,L.type)DàLD.type:=L.typeLàT idL.type:=T.typeAddtype(id.entry,T.type)TàintT.type:=integerTàrealT.type:=real5.7：试从练习5.4(a)和(b)中的语法制导定义中消除左递归。解：a)产生式语义规则EàT RR.i:=T.typeE.Type:=R.sRà+ T R1IF (R.i=integer)

6、and (T.type=integer) THEN R1.i:=integer ELSER1.i :=realR.s:=R1.sRàR.s:=R.iTànum.numT.type:=realTànumT.type:=integerb)产生式语义规则EàT RR.i:=T.type R.j:=T.valE.Type:=R.s E.val:=R.tRà+T R1IF (R.i=integer) and (T.type=integer) THEN BEGINR1.i:=integerPrint(+,R.j,T.val)R1.j:=R.j+T.val

7、END ELSE BEGINR1.i :=real IF R.i=integer THEN Begin R.i:=realR.j:=inttoreal(R.j) End IF T.type=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(+,R.j,T.val)R1.j :=R.j+T.val ENDR.s:=R1.s R.t:=R1.tRàR.s:=R.i R.t:=R.jTànum.numT.type:=realT.val:=num.num.lexvalTànumT.type:

8、=integerT.val:=num.lexval其中属性s和i用于传递属性type，属性t和j用于传递属性val。5.9：假设说明是由下列文法生成的：Dàid LLà,id L | :TTàinteger | reala) 建立一个翻译模式，把每一个标志符的类型加在符号表中b) 从a)的翻译模式构造一个预翻译程序解：a)产生式翻译模式Dàid LD.Type:=L.Typeaddtype(id.entry, D.type)Là,id L1L.Type:=L1.Typeaddtype(id.entry, L.type)Là:TL.ty

9、pe:=T.typeTàintegerT.type:=integerTàrealT.type:=realb)Procedure D;beginIf lookahead=id then BeginMatch(id);D.type=L;addtype(id.entry,D.type) endelse errorendFunction L: DataType;BeginIf lookahead=, then Begin Match(,); If lookahead=id then begin match(id);L.Type=L; addtype(id.entry,L.type)

10、; return(L.type) end Else error EndElse if lookahead=: thenBeginMatch(:);L.Type=T;return(L.Type)endelse errorEndFunction T: DataType;BeginIf lookahead=integer thenBeginMatch(integer);return(integer)endelse If lookahead=real thenBeginMatch(real);return(real)endelse errorend5.10：下面的文法是表5.7中基础文法的无二义形式，

11、其中的花括号 只用于将盒子分组，并将在翻译过程中被消除。SàLLàLB | BBàB sub F | FFàL | texta):用上面的文法修改表5.7的语法制导定义b):把a)中的语法制导定义转化为翻译模式解a)：产生式语义规则SàLL.ps:=10S.ht:=L.htLàL1B L1.ps:=L.psB.ps:=L.psL.ht:=max(L1.ht,B.ht)LàBB.ps:=L.psL.ht:=B.htBàB1 sub FB1.ps:=B.psF.ps=:shrink(B.ps)B.ht=disp(B1.ht,F.ht)BàFF.ps=B.psB.ht=F.htFàLL.ps=F.psF.ht=L.htFàtextF.ht=text.h * F.ps b)：产生式翻译模式Sà LL.ps:=10S.ht:=L.htLà L1 B L1.ps:=L.psB.ps:=L.psL.ht=max(L1.ht,B.ht)Là BB.ps:=L