编译原理(第2版)陈意云+张昱编著课后答案.ppt

《编译原理(第2版)陈意云+张昱编著课后答案.ppt》由会员分享，可在线阅读，更多相关《编译原理(第2版)陈意云+张昱编著课后答案.ppt（107页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理(第2版)陈意云+张昱编著课后答案目录chap 1 基本知识chap 3 词法分析chap 4 语法分析chap 5 语法制导翻译chap 6 运行时刻环境chap 7 中间代码生成chap 8 代码生成2 S (L)(L,S)(S,S)(a,S)(a,(L)短语 (L)L,S S a a (L,S)S,S a,S a,(L)(S,S)(a,S)(a,(L)(L)直接 (L)L,S S a a 短语 (L)(a,(L,S)(a,(S,S)(a,(a,S)(a,(a,a)短语 a a a a a,(L,S)a,(S,S)a,(a,S)a,(a,a)(a,(L,S)(a,(S,S)(a,(

2、a,S)(a,(a,a)L,S S a a (L,S)S,S a,S a,a (S,S)(a,S)(a,a)直接 a a a a短语 L,S S a a a 6(d)构造各个句子的最右推导.最右推导(规范推导)(e)这个文法产生的语言是什么?a (a)(a,a)(a,a),a).a和数据元素为a的广义表全体71.2 考虑文法 S aSbS|bSaS|(a)试说明此文法是二义性的.(定义1.5)如果一文法的句子存在两棵分析树,则该句子是二义性的.如果一文法包含二义性的句子,则这个文法是二义性的.可以从句子abab有两个不同的最左推导来说明.S aSbS abS abaSbS ababS abab

3、 lm lm lm lm lm S aSbS abSaSbS abaSbS ababS abab lm lm lm lm lm 句子abab有两个不同的最左推导,该句子是二义性的.所以此文法是二义性的.8(b)对于句子abab构造两个相应的最右推导.S aSbS aSb abSaSb abSab abab rm rm rm rm rm S aSbS aSbaSbS aSbaSb aSbab abab rm rm rm rm rm(c)对于句子abab构造两个相应的分析树.S S a S b S a S b S b S aS a S b S (d)此文法产生的语言是什么?由相同个数的a和b组成的

4、字符串.91.3 考虑文法 bexpr bexpr or bterm|bterm bterm bterm and bfactor|bfactor bfactor not bfactor|(bfactor)|true|false(a)请指出此文法的终结符号,非终结符号和开始符号.终结符号:or,and,not,(,),true,false 非终结符号:bexpr,bterm,bfactor 开始符号:bexpr10(b)试对于句子 not(true or false)构造一棵分析树.bexpr bterm bfactor not bfactor (bexpr )bexpr or bterm bt

5、erm bfactor bfactor false true11(c)试说明此文法产生的语言是全体布尔表达式.12练习:长度为n的字符串,分别有多少个前缀,后缀,子串,真前缀,子序列?前缀:n+1后缀:n+1子串:1+n+(n-1)+.+1=1+n(n+1)/2真前缀:n子序列:1+Cn1+Cn2+Cn3+.+Cnn=2n13 E E +T T *F i给出句型E+T*i的短语,直接短语和句柄 E E +T F T *F 给出句型F+T*F的短语,直接短语和句柄短语:i,T*i,E+T*i直接短语:i句柄:i短语:F,T*F,F+T*F直接短语:F,T*F句柄:F14第三章 练习3.3 试描述

6、下列正规表达式所表示的语言:(a)0(0|1)*0(b)(|0)1*)*由0和1组成且以0开始和结束的符号串全体.(c)(0|1)*0(0|1)(0|1)由0和1组成的符号串全体.由0和1组成且以000,001,010或011结束的符号串全体.长度大于等于3且倒数第3个字符为0的01符号串全体.15(d)0*10*10*10*(e)(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*有且只有3个1的0、1字符串全体.带有偶数个0和偶数个1的由0和1组成的符号串全体.带有偶数个a和偶数个b的符号串全体.(aa|bb)|(ab|ba)(aa|bb)*(ab|ba)*16

7、3.4 对于下列语言分别写出它们的正规表达式:(a)英文字母组成的所有符号串,要求符号串中顺序包含 五个元音字母.令letter=非元音的英文字母 letter*(a|A)letter*(e|E)letter*(i|I)letter*(o|O)letter*(u|U)letter*(b)英文字母组成的所有符号串,要求符号串中的字母依 照字典序排列.(a|A)*(b|B)*(c|C)*.(z|Z)*17(c)没有重复出现的数字的数字符号串全体.(d)最多有一个重复出现的数字的数字符号串全体令 ri=i|,i=0,1,2,.,9 R0|R1|R2|.|R9记为 Ri i(0,1,2.,9)P(0,

8、1,2.,9)表示0,1,2.,9的全排列 ri0ri1.ri9 i0i1.i9P(0,1,2.,9)i ri0ri1.ri9i(0,1,2.,9)i0i1.i9P(0,1,2.,9)18(e)带有偶数个0和奇数个1的由0和1组成的符号串全体.E为带有偶数个0和1的由0和1组成的符号串全体.即(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*E 1 E|E 0 E 1 E 0 E(f)不包含子串011的由0和1组成的符号串全体.(g)不包含子序列011的由0和1组成的符号串全体1*0*10*|1*(0*|(10)*)*19练习:1.令A,B和C是任意正规式,证明以

9、下关系成立:A|A=A (A*)*=A*A*=|AA*(AB)*A=A(BA)*(A|B)*=(A*B*)*=(A*|B*)*A=b|aA当且仅当A=a*b203.6 给出接受下列在字母表0，1上的DFA。（a）所有以00结束的符号串的集合；AstartB0C010NFA等价于A1startBC00011DFA(1|0)*0021（b）所有具有三个0的符号串的集合。1*01*01*01*AstartB0C01DFA11B01223.7 构造等价于下列正规表达式的有限自动机.(a)10|(0|11)0*100011AstartD1BEC1NFA 0 1A D BCD D EBC E DE /10

10、10AstartBC0DEDFA123(b)(0|1)*|(11)*0|111AstartCBEDNFA 0 1ABDE ABDE ABCDEABCDE ABDE ABCDE11Astart0BDFA01Astart最小化DFA0243.8 给定右线性文法G:S 0S|1S|1A|0B A 1C|B 0C|1 C 0C|1C|0|1 试求一个等价的左线性文法G.000,11SstartB1ACf状态转移图100,10,1左线性文法G:f A1|B0|C1|C0 A S1 B S0 C A1|B0|C1|C0 S S0|S1|图中状态C和f可合并,得到左线性文法G:C A1|B0|C1|C0 A

11、 S1 B S0 S S0|S1|253.9-3.11(d)(a|b)*abb(a|b)*1start2a4ba3bbba由正规表达式构造NFA1start12a14b13bbaaba124a134bba由NFA得到DFAABCDEFB C D E F A B C D E ABaDbCbabaab最小化DFA263.13 对于下列正规表达式构造最小状态的DFA.(b)(a|b)*a(a|b)(a|b)a1start2a43babNFAbaAstartBabHGaCDaaaEFabaaabbbb最小化DFA274.4 考虑文法 R R|R|RR|R*|(R)|a|b(a)试说明此文法生成在符号a

12、和b之上的所有正规表达式.(b)试说明此文法是二义性的.(c)试构造一个等价的无二义性文法.(b)句子a|aa的两种最左推导.句子aa*的两种最左推导.RR Ra R *a R R *R R a a(c)消除二义性 R R|S|S S ST|T T U*|U U(R)|a|b284.5 dangling-else文法:stmt if expr then stmt|matched-stmt matched-stmt if expr then matched-stmt else stmt|other 试说明此文法是二义性的。句子 if e1 then if e2 then s1 else if e

13、3 then s2 else s3 if e1 then if e2 then s1 else if e3 then s2 else s3 S MSif E then MS else S e1 if E then MS else S MS e2 other if E then S other s1 e3 MS s3 other s2 Sif E then S e1 MSif E then MS else S e2 other MS s1 if E then MS else S e3 other MS s2 other s3294.3 对于下面的每一个语言设计一个文法。试问其中哪些语言是正规的？

14、(a)使得在每一个0后至少立即跟随一个1的由0和1组成的符号串的全体。(b)具有相同数目的0和1的由0和1组成的符号串的全体。(c)具有不同数目的0和1的由0和1组成的符号串的全体。S 1S|01S|(1|01)*S 0S1S|1S0S|非正规语言S SAS S 0S1S|1S0S|A B|C 非正规语言B 1B|1C 0C|0S A|BA 0|0A|A0|10A|01A|A10|A01|1A0|0A1B 0|0B|B0|10B|01B|B10|B01|1B0|0B130(d)所有形如xy而xy的由0和1组成的符号串。S 0E|1E|LBRE 00E|01E|10E|11E|B I I1B|O

15、O1B|IO1C|OI1CC IO1C|OI1C|I1 O OI1O1I IO1I1I I I1O1O OO1L I 1LLO 0LI1R R1O1R R0LR 所有形如xy而x=y的由0和1组成的符号串。S 0S0|1S1|314.5(a)给出一个上下文无关产生式的集合，使它与A B*a(C|D)生成同样的 符号串集合。A B a E B B B|E C|D (b)是否可以把E T|E+T写为：E T+T 是否可以把E T|E+T|E-T写为：E T(+|-T)E T+T 等价于 E T T T+TT|324.7对于文法S aSbS|bSaS|构造一个带有回溯的递归下降分析器.问能否构造一个

16、预测分析器.procedure match(t:token);begin ifkahead=t thenend;procedure S;begin if match334.9 对于文法 bexpr bexpr or bterm|bterm bterm bterm and bfactor|bfactor bfactor not bfactor|(bexpr)|true|false 构造一个预测分析器。1.消除左递归bexpr bterm bexpr bexpr or bterm bexpr|bterm bfactor btermbterm and bfactor bterm|bfactor no

17、t bfactor|(bexpr)|true|false2.First(bexpr)=First(bterm)=First(bfactor)=not,(,true,false First(bexpr)=or,First(bterm)=and,Follow(bexpr)=$,)Follow(bexpr)=$,)Follow(bterm)=or,$,)Follow(bterm)=or,$,)Follow(bfactor)=or,and,$,)34(1)bexpr bterm bexpr(2)bexpr or bterm bexpr(3)bexpr (4)bterm bfactor bterm(5)

18、bterm and bfactor bterm (6)bterm (7)bfactor not bfactor(8)bfactor (bexpr)(9)bfactor true(10)bfactor falseFirst(bexpr)=First(bterm)=First(bfactor)=not,(,true,falseFirst(bexpr)=or,First(bterm)=and,Follow(bexpr)=$,)Follow(bexpr)=$,)Follow(bterm)=or,$,)Follow(bterm)=or,$,)Follow(bfactor)=or,and,$,)or an

19、d not true false ()$bexpr (1)(1)(1)(1)synch synch bexpr (2)(3)(3)bterm synch (4)(4)(4)(4)synch synch bterm (6)(5)(6)(6)bfactor synch synch (7)(9)(10)(8)synch synch 354.11试说明没有一个左递归文法可以是LL(1)的。(1)直接左递归文法中存在产生式:A A1|A2|.|Am|1|2|.|n,其中 1 2.n均不以A开头 First(Ai)First(j)=First(j)若 j*,First(A i)Follow(A)=Firs

20、t(i),不是LL(1)文法.(2)间接左递归文法中存在产生式集合:A B1 1|1|2|.|n B1 B2 2 .Bm A First(B1 1)=First(A m.1)First(j)First(B1 1),j=1,.,n First(j)First(B1 1),j=1,.,n 若 j*,First(B1 1)Follow(A)=First(m.1),不是LL(1)文法.364.12试说明没有一个LL(1)文法可以是二义性的。若有一个LL(1)文法是二义性的,则存在句子w 有两种不同的最左推导:S*A 1 *w S*A 2 *w 对于文法中的产生式 A 1|2,其中1,2 First(1

21、)First(2)=First(w)与LL(1)文法矛盾.374.15 文法 S (L)|a L L,S|S的算符优先关系由表4.20给出。建立与表相应的算符优先函数并用算符优先分析法分析句子(a,(a,a)及(a,(a,a),(a,a)。算符优先关系表 a (),$a (=),$算符优先函数 a (),$f 2 0 2 2 0g 3 3 0 1 0句子(a,(a,a)的分析过程栈 输入 动作$(a,(a,a)$(shift$(a,(a,a)$(a shift$(a ,(a,a)$a,reduce$(S ,(a,a)$(,shift$(S,(a,a)$,(shift$(S,(a,a)$(a s

22、hift$(S,(a ,a)$a,reduce$(S,(S ,a)$(,shift$(S,(S,a)$,a shift$(S,(S,a )$a)reduce$(S,(S,S )$,)reduce$(S,(L )$(=)shift$(S,(L)$)reduce$(S,S )$,)reduce$(L )$(=)shift$(L)$)$reduce$S$accept 384.16 试为下列各文法建立算符优先关系表。(a)S a S b S|b S a S|a b$a =b =$acc设G是一个运算符文法,R和S是G中任何两个终结符,定义:(1)R=S当且仅当G中存在产生式 .RS.或 .RS.(2)

23、RS当且仅当G中存在产生式 .R.,其中 +S.或+S.(3)RS当且仅当G中存在产生式 .S.,其中 +.R 或+.R最左终结符:S.或 S.,S是的最左终结符 .,则的最左终结符是的最左终结符对于文法中 R.的产生式,R 的最左终结符.39(b)bexpr bexpr or bterm|bterm bterm bterm and bfactor|bfactor bfactor not bfactor|(bexpr)|true|false or and not ()true false$or (=true false$acc 最左终结符 最右终结符bexpr or,and,not,(,tru

24、e,false or,and,not,),true,falsebterm and,not,(,true,false and,not,),true,falsebfactor not,(,true,false not,),true,false404.18 给出文法LR(0)项目集族及相应的识别活前缀的自动机的状态转移图.S S C cC S CC C d I0:S .S S .CC C .cC C .dI1:S S.I2:S C.C C .cC C .dI3:C c.C C .cC C .dI4:C d.I5:S CC.I6:C cC.I0I1SCI2cI3CI5dI4cdCI6cdstart41

25、4.19 利用图4.31画出文法4.27的识别活前缀的自动机的状态转移图.(P.200)I0:S .S S .iSeS S .iS S .aI1:S S.I2:S i.Ses S i.S S .iSeS S .iS S .a0I3:S a.I4:S iS.eS S iS.I5:S iSe.S S .iSeS S .iS S .aI6:S iSeS.iI0I1SaI3iI2SI4istarteI5SI6aa424.21 考虑文法 S A S|b A S A|a(1)构造文法的LR(0)项目集规范族及相应的DFA.(2)如果把每一个LR(0)项目看成一个状态,并从每个形如B.X的状态出发画一条标记

26、为X的弧到状态BX.,且从从每个形如B.A的状态出发画一条标记为的弧到所有形如A.的状态.这样就得到了一个NFA.说明这个NFA和(1)的DFA是等价的.(3)构造文法的SLR分析表.(4)对于输入串bab,给出SLR分析器的动作.(5)构造文法的LR(1)分析表和LALR分析表.43I0:S .S S .AS S .b A .SA A .aI1:(I0,S)S S.A S.A A .SA A .a S .AS S .bI2:(I0,A)(I2,A)(I6,A)S A.S S .AS S .b A .SA A .aI3:(I0,b)(I1,b)(I2,b)(I5,b)(I6,b)(I7,b)S

27、 b.I4:(I0,a)(I1,a)(I2,a)(I5,a)(I6,a)(I7,a)A a.I5:(I1,S)(I5,S)(I7,S)A S.A A .SA A .a S .AS S .bI6:(I1,A)(I5,A)(I7,A)A SA.S A.S S .AS S .b A .SA A .aI7:(I2,S)(I6,S)S AS.A S.A A .SA A .a S .AS S .b44First(S)=First(S)=First(A)=b,aFollow(S)=$Follow(S)=a,b,$Follow(A)=a,bSLR分析表STATE ACTION GOTO a b$S A0 s4

28、 s3 1 21 s4 s3 acc 5 62 s4 s3 7 2 3 r3 r3 r34 r5 r5 5 s4 s3 5 66 s4/r4 s3/r4 7 27 s4/r2 s3/r2 r2 5 6SLR分析表存在移入-归约冲突.为消除二义性，假设a的优先级高于b，则遇到a时移入，遇到b时归约。输入串bab,SLR分析器的动作:栈 输入 动作0 bab$shift30b3 ab$reduce S b0S1 ab$shift40S1a4 b$reduce A a0S1A6 b$shift-reduce collision 输入串bab,SLR分析器的动作:栈 输入 动作0 bab$shift3

29、0b3 ab$reduce S b0S1 ab$shift40S1a4 b$reduce A a0S1A6 b$reduce A SA0A2 b$shift30A2b3$reduce S b0A2S7$reduce S AS0S1$accept45LR(1)项目集规范族I0:S .S,$S .AS,$/a/b S .b,$/a/b A .SA,a/b A .a,a/bI1:(I0,S)S S.,$A S.A,a/b A .SA,a/b A .a,a/b S .AS,a/b S .b,a/bI2:(I0,A)(I2,A)S A.S,$/a/b S .AS,$/a/b S .b,$/a/b A .

30、SA,a/b A .a,a/bI3:(I0,b)(I2,b)S b.,$/a/bI4:(I0,a)(I1,a)(I2,a)(I5,a)(I6,a)(I8,a)(I9,a)(I10,a)A a.,a/bI5:(I1,S)(I5,S)(I8,S)(I10,S)A S.A,a/b A .SA,a/b A .a,a/b S .AS,a/b S .b,a/bI6:(I1,A)(I5,A)(I8,A)(I10,A)A SA.,a/b S A.S,a/b S .AS,a/b S .b,a/b A .SA,a/b A .a,a/bI7:(I1,b)(I5,b)(I6,b)(I8,b)(I9,b)(I10,b)

31、S b.,a/bI8:(I2,S)S AS.,$/a/b A S.A,a/b A .SA,a/b A .a,a/b S .AS,a/b S .b,a/bI9:(I6,A)(I9,A)S A.S,a/b S .AS,a/b S .b,a/b A .SA,a/b A .a,a/bI10:(I6,S)(I9,S)S AS.,a/b A S.A,a/b A .SA,a/b A .a,a/b S .AS,a/b S .b,a/b46STATE ACTION GOTO a b$S A0 s4 s3 1 21 s4 s7 acc 5 62 s4 s3 8 2 3 r3 r3 r34 r5 r5 5 s4 s

32、7 5 66 s4/r4 s7/r4 10 97 r3 r38 s4/r2 s7/r2 r2 5 69 s4 s7 10 910 s4/r2 s7/r2 5 6 LR(1)分析表该文法的LR(1)分析表中存在移入-归约冲突，文法具有二义性。为消除二义性，假设a的优先级高于b，则遇到a时移入，遇到b时归约。s4r4r247该文法不是LR(1)文法.具有二义性.对于句子abab,存在两颗不同的分析树.SASaASSA bbaSASaSAbbaAS484.22 构造文法 S a S S b|a S S S|c 的LR(0)项目集规范族及识别活前缀的自动机.I0:S .S S .aSSb S .aSS

33、S S .cI1:S S.I2:S a.SSb S a.SSS S .aSSb S .aSSS S .cI3:S c.I4:S aS.Sb S aS.SS S .aSSb S .aSSS S .cI5:S aSS.b S aSS.S S .aSSb S .aSSS S .cI6:S aSSb.I7:S aSSS.I0I1ScI3aI2SI4startSI5bI6acaaccSI7494.25 证明下面文法是SLR(1)文法,并构造其SLR分析表.E E+T (1)F F*(5)E T (2)F a (6)T T F (3)F b (7)T F (4)I0:E .E E .E+T E .T T

34、.TF T .F F .F*F .a F .bI1:E E.E E.+TI2:E T.T T.F F .F*F .a F .bI3:T F.F F.*I4:F a.I5:F b.I6:E E+.T T .TF T .F F .F*F .a F .bI7:T TF.F F.*I8:F F*.I9:E E+T.T T.F F .F*F .a F .b action goto +*a b$E T F0 s4 s5 1 2 31 s6 acc2 r2 s4 s5 r2 73 r4 s8 r4 r4 r4 4 r6 r6 r6 r6 r6 5 r7 r7 r7 r7 r7 6 s4 s5 9 37 r3

35、 s8 r3 r3 r3 8 r5 r5 r5 r5 r5 9 r1 s4 s5 r1 7 Follow(E)=+,$Follow(T)=+,$,a,bFollow(E)=+,$,*,a,b504.26 证明每一个LL(1)文法都是LR(1)文法.514.27 证明下面文法是LL(1)的但不是SLR(1)文法.S A a A b|B b B a A B First(AaAb)=aFirst(BbBa)=bFirst(AaAb)First(BbBa)=文法是LL(1)的.构造SLR(1)项目集:I0:S .S S .AaAb S .BbBa A .B .Follow(A)=Follow(B)=a

36、,b存在归约-归约冲突,该文法不是SLR(1)文法.524.28 证明任何一个LR(1)文法都是无二义文法.534.29 证明任何SLR(1)文法都是LR(1)文法.假设文法G是SLR(1)文法,则对于文法的状态i:对于A.X,XVT,XFollow(B),i中没有项目B.对于A.和B.,Follow(A)Follow(B)=构造G的LR(1)项目集,若G是LR(1)文法,则项目集i必须满足条件:(1)对于A.X,a,XVT,XFollow(B),i中没有项目B.,X.(显然成立)(2)没有A.,a和B.,a的两个项目.由closure(I)的构造A.B,a,B.,First(a)可得知,项目

37、A.的向前搜索符号Follow(A)对于一个项目集中的不同归约项目A2.搜索符A,B3.,搜索符A搜索符A 搜索符A=不存在归约-归约冲突,所以条件(2)成立.544.31 为下面的文法构造它的LR(1)项目集规范族,并判断它是否为LR(1)文法?若是,构造它的分析表.S E S S S E (1)E E+T|T E E+T(2)E T (3)T (E)|a T (E)(4)T a (5)I0:S .S$S .E$E .E+T$/+E .T$/+T .(E)$/+T .a$/+I1:S S.$I2:S E.$E E.+T$/+I3:E T.$/+I4:T (.E)$/+E .E+T )/+E

38、.T )/+T .(E)/+T .a )/+I5:T a.$/+I6:E E+.T$/+T .(E)$/+T .a$/+I7:T (E.)$/+E E.+T )/+I8:E T.)/+I9:T (.E)/+E .E+T )/+E .T )/+T .(E)/+T .a )/+I10:T a.)/+I11:E E+T.$/+I12:T (E).$/+I13:E E+.T )/+T .(E)/+T .a )/+I14:T (E.)/+E E.+T )/+I15:E E+T.)/+I16:T (E).)/+LR(1)项目集规范族:55 action goto +()a$S E T0 s4 s5 1 2

39、 31 acc2 s6 r13 r3 r3 4 s9 s10 7 85 r5 r56 s4 s5 117 s13 s12 8 r3 r39 s9 s5 14 8 10 r5 r511 r2 r2 12 r4 r413 s9 s10 1514s13 s16 15r2 r216r4 r4LR(1)分析表:56LALR(1)分析表:action goto +()a$S E T 0 s4 9 s5 10 1 2 3 8 1 acc 2 s6 13 r1 3 8 r3 r3 r3 4 9 s4 9 s5 10 7 14 3 8 5 10 r5 r5 r5 6 13 s4 9 s5 10 11 15 7

40、14 s6 13 s12 1611 15 r2 r2 r212 16 r4 r4 r4LALR(1)分析表不存在冲突,所以该文法是LALR(1)文法.57证明文法G:ad bd ae be c c是LR(1)文法,但不是LALR(1)文法.585.1 对于输入的表达式(4*7+1)*2,根据表5.1的语法制导定义建立一棵带注释的分析树.L E.val=58 n T.val=58 T.val=29 *F.val=2 F.val=29 digit.lexval=2 (E.val=29 )E.val=28 +T.val=1 T.val=28 F.val=1T.val=4 *F.val=7 digit

41、.lexval=1F.val=4 digit.lexval=7digit.lexval=4（lex表示是从词法分析来的）595.2 试根据 (a)表5.3中的语法制导定义，和 (b)图5.17的翻译模式来建立表达式(a)+(b)的分析树和语法树.(a)E T (E nptr )E +T T (E )(E )T nptr T nptr id ididentry to aidentry to a+60(b)E T R (E nptr )T R (E )+T i R s T nptr R (E )id Tnptr R id identry to aidentry to a+615.4 E E+T|T

42、 T num.num|num(a)给出一个语法制导定义以确定每个子表达式的类型.5.7(b)扩充(a)中的语法制导定义把表达式翻译成前缀形式,并且决定 类型.(a)E E1+T if (E1.type=real or T.type=real)then E.type=real else E.type=integer E T E.type=T.type;T num.num T.type=real;T num T.type=integer;62(b)S E S.type=E.type;S.code=E.code;E E1+T if (E1.t ype=real and T.type=integer)

43、then begin E.type=real;E.code=+|E1.code|inttoreal(T.code)end else if (E1.t ype=integer and T.type=real)then begin E.type=real;E.code=+|inttoreal(E1.code)|T.code end else begin E.type=E1.t ype;E.code=+|E1.code|T.code end E T E.type=T.type;E.code=T.code T num.num T.type=real;T.code=(num.num).lexval T

44、num T.type=integer;T.code=num.lexval63 E T E.type=T.type;E.code=T.code T num.num T.type=real;T.code=(num.num).lexval T num T.type=integer;T.code=num.lexval64 S t c E t c E t c +T t c E t c +T t c num.num T t c num num 655.5 S L.L|L L L B|B B 0|1(a)试用各有关综合属性决定S.val.引入L的属性b记录2的L的位数次幂值S L1.L2 S.val=L1.

45、val+L2.val/L2.b;S L S.val=L.val;L L1 B L.val=L1.val*2+B.val;L.b=L.b*2;L B L.val=B.val;L.b=2;B 0 B.val=0;B 1 B.val=1;66 S val L v .L b v L v B v L b v B v B v 0 L b v B v 1 1 B v 0 167(b)试用一个语法制导定义来决定S.val,在这个定义中B仅有综合 属性c,给出由B生成的位对于最后的数值的分担额.引入B的继承属性i,综合属性cS L1.L2 L1.i=20;L2.i=2-1;S.val=L1.val+L2.val

46、S L L.i=20;S.val=L.val;L L1 B if L.i=20 then begin L1.i=L.i*2;B.i=L.i end else begin L1.i=L.i;L.s=L1.s/2;B.i=L1.s end L.val=L1.val+B.c L B B.i=L.i;L.s=L.i/2;L.val=B.cB 0 B.c=B.i*0B 1 B.c=B.i*168 S val i L v .i L s vi L v i B c i L s v i B ci B c 0 i L s v i B c 1 1 i B c 0 1695.6 重写例5.3中语法制导定义的基础文法,

47、使类型信息只需用综合属性来传递.D T LL L1,id|idT intT real改写为:D L id addtype(id.entry,L.type)L L1 id,L.type=L1.type;addtype(id.entry,L1.type)L T L.type=T.typeT int T.type=intT real T.type=real D L id L id ,T int705.7 试从5.4(a)和(b)中的语法制导定义中消除左递归.(a)E T F F.it=T.t;E.t=F.t F +TF1 F1.t=F.it and T.t;F.t=F1.t F F.t=F.it T

48、 num.num T.t=false;T num T.t=true;E tTt it F tnum +Tt it F t num.num 71(b)E T F F.it=T.t;E.t=F.t;F.ic=T.c;E.c=F.c F +TF1 if F.it=real and T.t=integer then begin F1.it=real;F1.ic=+|F.ic|inttoreal(T.c);end else if F.it=integer and T.t=real then begin F1.it=real;F1.ic=+|inttoreal(F.ic)|T.c;end else beg

49、in F1.it=F.it;F1.ic=+|F.ic|T.c;end F.t=F1.it;F.c=F1.ic;F F.t=F.it;F.c=F.ic;T num.num T.t=real;T.c=num.num.lexval;T num T.t=integer;T.c=num.lexval;72 E t c T t c it icF t c num +T t c it icF t c num.num 735.9 假设说明是由下列文法产生的:D L id L ,id L1|:T T integer|real(a)建立一个翻译模式,把每一个标识符的类型加入到符号表中.(b)从(a)中的翻译模式构造

50、一个与翻译程序.(a)D L id addtype(id.entry,L.type L ,id L1 L.type=L1.type addtype(id.entry,L.type L :T L.type=T.type T integer T.type=0 T real T.type=1 用整数0表示整型,1表示实型.74(b)procedure D;var Ltype:integer;begin match(id);Ltype:=L();addtype(id.entry,Ltype)end;function L():integer;var Ltype:integer;begin if look