编译原理陈意云张昱编著课后答案PPT学习教案

《编译原理陈意云张昱编著课后答案PPT学习教案》由会员分享，可在线阅读，更多相关《编译原理陈意云张昱编著课后答案PPT学习教案（106页珍藏版）》请在装配图网上搜索。

1、会计学1编译原理陈意云张昱编著课后答案编译原理陈意云张昱编著课后答案2第1页/共106页3第一章 练习1.1 文法 S (L)|a L L,S|S(a)指出文法的终结符号,非终结符号,开始符号.文法的四个组成部分:终结符号 VT:语言不可再分的基本符号 非终结符号VN:语法范畴(语法概念)开始符号 S:最终感兴趣的语法范畴 产生式 P:定义语法范畴的一种书写形式终结符号:(,)a 非终结符号:S L开始符号:S元语言符号:表示“定义为”|表示“或”第2页/共106页4(b)给出句子的分析树分析树:(推导树)表示一个句型的推导 (a,(a,a)S(L )L ,S S (L )a S a第3页/共

2、106页5(c)给出句子的最左推导 给出每次推导后得到的句型的短语,直接短语最左推导 :推导中任何一步 都是对中的最左非终结 lm 符号进行替换的推导.短语 是文法的句型(S*)S*A且A+则是关于A的句型的短语.直接短语 是文法的句型(S*)S*A且A 则是关于A的句型的直接短语.句柄:一个句型的最左直接短语称为句柄.第4页/共106页6 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,

3、(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,(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 第5页/共106页7(d)构造各个句子的最右推导.最右推导(规范推导)(e)这个文法产生的语言是什么?a (a)(a,a)(a,a),a).a和数据元素为a的广义表全体第6页/共106页81.2 考虑文法 S aSbS|bSaS|(a)试说明此文法是二义性的.(定义1.5)如果一文法的句子存在两棵分析树,则该句子

4、是二义性的.如果一文法包含二义性的句子,则这个文法是二义性的.可以从句子abab有两个不同的最左推导来说明.S aSbS abS abaSbS ababS abab lm lm lm lm lm S aSbS abSaSbS abaSbS ababS abab lm lm lm lm lm 句子abab有两个不同的最左推导,该句子是二义性的.所以此文法是二义性的.第7页/共106页9(b)对于句子abab构造两个相应的最右推导.S aSbS aSb abSaSb abSab abab rm rm rm rm rm S aSbS aSbaSbS aSbaSb aSbab abab rm rm r

5、m rm rm(c)对于句子abab构造两个相应的分析树.S S a S b S a S b S b S aS a S b S (d)此文法产生的语言是什么?由相同个数的a和b组成的字符串.第8页/共106页101.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 开始符

6、号:bexpr第9页/共106页11(b)试对于句子 not(true or false)构造一棵分析树.bexpr bterm bfactor not bfactor (bexpr )bexpr or bterm bterm bfactor bfactor false true第10页/共106页12(c)试说明此文法产生的语言是全体布尔表达式.第11页/共106页13练习:长度为n的字符串,分别有多少个前缀,后缀,子串,真前缀,子序列?前缀:n+1后缀:n+1子串:1+n+(n-1)+.+1=1+n(n+1)/2真前缀:n子序列:1+Cn1+Cn2+Cn3+.+Cnn=2n第12页/共10

7、6页14 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句柄:F第13页/共106页15第三章 练习3.3 试描述下列正规表达式所表示的语言:(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符号串全体.第1

8、4页/共106页16(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)*第15页/共106页173.4 对于下列语言分别写出它们的正规表达式:(a)英文字母组成的所有符号串,要求符号串中顺序包含 五个元音字母.令letter=非元音的英文字母 letter*(a|A)letter*(e|E)letter*(i|I)letter*(o|O)letter*(

9、u|U)letter*(b)英文字母组成的所有符号串,要求符号串中的字母依 照字典序排列.(a|A)*(b|B)*(c|C)*.(z|Z)*第16页/共106页18(c)没有重复出现的数字的数字符号串全体.(d)最多有一个重复出现的数字的数字符号串全体令 ri=i|,i=0,1,2,.,9 R0|R1|R2|.|R9记为 Ri i(0,1,2.,9)P(0,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)第17页/共106页19(e)带有偶数个0和奇数个1的由

10、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)*)*第18页/共106页20练习:1.令A,B和C是任意正规式,证明以下关系成立:A|A=A (A*)*=A*A*=|AA*(AB)*A=A(BA)*(A|B)*=(A*B*)*=(A*|B*)*A=b|aA当且仅当A=a*b第19页/共106页213.6 给出接受下列

11、在字母表0，1上的DFA。（a）所有以00结束的符号串的集合；AstartB0C010NFA等价于A1startBC00011DFA(1|0)*00第20页/共106页22（b）所有具有三个0的符号串的集合。1*01*01*01*AstartB0C01DFA11B01第21页/共106页233.7 构造等价于下列正规表达式的有限自动机.(a)10|(0|11)0*100011AstartD1BEC1NFA 0 1A D BCD D EBC E DE /1010AstartBC0DEDFA1第22页/共106页24(b)(0|1)*|(11)*0|111AstartCBEDNFA 0 1ABDE

12、 ABDE ABCDEABCDE ABDE ABCDE11Astart0BDFA01Astart最小化DFA0第23页/共106页253.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 S1 B S0 S S0|S1|第24页/共106页26(d)(a|b)*abb(a|b)*1st

13、art2a4ba3bbba由正规表达式构造NFA1start12a14b13bbaaba124a134bba由NFA得到DFAABCDEFB C D E F A B C D E ABaDbCbabaab最小化DFA第25页/共106页273.13 对于下列正规表达式构造最小状态的DFA.(b)(a|b)*a(a|b)(a|b)a1start2a43babNFAbaAstartBabHGaCDaaaEFabaaabbbb最小化DFA第26页/共106页284.4 考虑文法 R R|R|RR|R*|(R)|a|b(a)试说明此文法生成在符号a和b之上的所有正规表达式.(b)试说明此文法是二义性的.

14、(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|b第27页/共106页294.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 e3 then s2 else s3

15、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 s3第28页/共106页304.3 对于下面的每一个语言设计一个文法。试问其中哪些语言是正规的？(a)使得在每一

16、个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|0B1第29页/共106页31(d)所有形如xy而xy的由0和1组成的符号串。S 0E|1E|LBRE 00E|01E|10E|11E|B I I1B

17、|OO1B|IO1C|OI1CC IO1C|OI1C|I1 O OI1O1I IO1I1I I I1O1O OO1L I 1LLO 0LI1R R1O1R R0LR 所有形如xy而x=y的由0和1组成的符号串。S 0S0|1S1|第30页/共106页324.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|第31页/共106页33对于文法S aSbS|bSaS|构造一个带

18、有回溯的递归下降分析器.问能否构造一个预测分析器.procedure match(t:token);begin ifkahead=t thenend;procedure S;begin if match第32页/共106页344.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

19、 and bfactor bterm|bfactor not 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,$,)第33页/共106页35(1)bexpr bterm bexpr(2)bexpr or bterm

20、bexpr(3)bexpr (4)bterm bfactor bterm(5)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

21、)=or,$,)Follow(bfactor)=or,and,$,)or and 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 第34页/共106页36试说明没有一个左递归文法可以是LL(1)的。(1)直接左递归文法中存在产生式:A A1|A2|.|Am|1|2|.|n,其中 1 2.n均不以A开头 First(Ai)F

22、irst(j)=First(j)若 j*,First(A i)Follow(A)=First(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)文法.第35页/共106页37试说明没有一个LL(1)文法可以是二义性的。若有一个LL(1)文法是二义性的,则存在句子w 有两种不同的最

23、左推导:S*A 1 *w S*A 2 *w 对于文法中的产生式 A 1|2,其中1,2 First(1)First(2)=First(w)与LL(1)文法矛盾.第36页/共106页384.15 文法 S (L)|a L L,S|S的算符优先关系由表给出。建立与表相应的算符优先函数并用算符优先分析法分析句子(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)$

24、a,reduce$(S ,(a,a)$(,shift$(S,(a,a)$,(shift$(S,(a,a)$(a shift$(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 第37页/共106页394.16 试为下列各文法建立算符优先关系表。(a)S a S b S|b S a S|a b$a

25、=b =$acc设G是一个运算符文法,R和S是G中任何两个终结符,定义:(1)R=S当且仅当G中存在产生式 .RS.或 .RS.(2)RS当且仅当G中存在产生式 .R.,其中 +S.或+S.(3)RS当且仅当G中存在产生式 .S.,其中 +.R 或+.R最左终结符:S.或 S.,S是的最左终结符 .,则的最左终结符是的最左终结符对于文法中 R.的产生式,R 的最左终结符.第38页/共106页40(b)bexpr bexpr or bterm|bterm bterm bterm and bfactor|bfactor bfactor not bfactor|(bexpr)|true|false

26、or and not ()true false$or (=true false$acc 最左终结符 最右终结符bexpr or,and,not,(,true,false or,and,not,),true,falsebterm and,not,(,true,false and,not,),true,falsebfactor not,(,true,false not,),true,false第39页/共106页414.18 给出文法LR(0)项目集族及相应的识别活前缀的自动机的状态转移图.S S C cC S CC C d I0:S .S S .CC C .cC C .dI1:S S.I2:S

27、C.C C .cC C .dI3:C c.C C .cC C .dI4:C d.I5:S CC.I6:C cC.I0I1SCI2cI3CI5dI4cdCI6cdstart第40页/共106页424.19 利用图画出文法的识别活前缀的自动机的状态转移图.(P.200)I0:S .S S .iSeS S .iS S .aI1:S S.I2:S S S .iSeS S .iS S .a0I3:S a.I4:S iS.eS S iS.I5:S S .iSeS S .iS S .aI6:S iSeS.iI0I1SaI3iI2SI4istarteI5SI6aa第41页/共106页434.21 考虑文法 S

28、 A S|b A S A|a(1)构造文法的LR(0)项目集规范族及相应的DFA.(2)如果把每一个LR(0)项目看成一个状态,并从每个形如B.X的状态出发画一条标记为X的弧到状态BX.,且从从每个形如B.A的状态出发画一条标记为的弧到所有形如A.的状态.这样就得到了一个NFA.说明这个NFA和(1)的DFA是等价的.(3)构造文法的SLR分析表.(4)对于输入串bab,给出SLR分析器的动作.(5)构造文法的LR(1)分析表和LALR分析表.第42页/共106页44I0:S .S S .AS S .b A .SA A .aI1:(I0,S)S S.A .SA A .a S .AS S .bI

29、2:(I0,A)(I2,A)(I6,A)S S .AS S .b A .SA A .aI3:(I0,b)(I1,b)(I2,b)(I5,b)(I6,b)(I7,b)S b.I4:(I0,a)(I1,a)(I2,a)(I5,a)(I6,a)(I7,a)A a.I5:(I1,S)(I5,S)(I7,S)A .SA A .a S .AS S .bI6:(I1,A)(I5,A)(I7,A)A SA.S S .AS S .b A .SA A .aI7:(I2,S)(I6,S)S AS.A .SA A .a S .AS S .b第43页/共106页45First(S)=First(S)=First(A)=

30、b,aFollow(S)=$Follow(S)=a,b,$Follow(A)=a,bSLR分析表STATE ACTION GOTO a b$S A0 s4 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$

31、reduce A a0S1A6 b$shift-reduce collision 输入串bab,SLR分析器的动作:栈 输入 动作0 bab$shift30b3 ab$reduce S b0S1 ab$shift40S1a4 b$reduce A a0S1A6 b$reduce A SA0A2 b$shift30A2b3$reduce S b0A2S7$reduce S AS0S1$accept第44页/共106页46LR(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 .

32、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 .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

33、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)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/b第4

34、5页/共106页47STATE 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 s7 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时归约。s4r4r2第46页/共106页48该文法不是LR(1)文法.具有二义性.对于句子abab,存在两颗

35、不同的分析树.SASaASSAbbaSASaSAbbaAS第47页/共106页494.22 构造文法 S a S S b|a S S S|c 的LR(0)项目集规范族及识别活前缀的自动机.I0:S .S S .aSSb S .aSSS 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.I0I1ScI3aI2SI4startSI5bI6ac

36、aaccSI7第48页/共106页504.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 .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

37、 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 s8 r3 r3 r3 8 r5 r5 r5 r5 r5 9 r1 s4 s5 r1 7 Follow(E)=+,$Follow(T)=+,$,a,bFollow(E)=+,$,*,a,b第49页/共106页514.26 证明每一个LL(1)文法都是LR(1)文法.第50页/共106页524.27 证明下面文法是LL(1)的但不是SLR(1)文

38、法.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,b存在归约-归约冲突,该文法不是SLR(1)文法.第51页/共106页534.28 证明任何一个LR(1)文法都是无二义文法.第52页/共106页544.29 证明任何SLR(1)文法都是LR(1)文法.假设文法G是SLR(1)文法,则对于文法的状态i:对于A.X,XVT,XFollow(B),i中没有项

39、目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)可得知,项目A.的向前搜索符号Follow(A)对于一个项目集中的不同归约项目A2.搜索符A,B3.,搜索符A搜索符A 搜索符A=不存在归约-归约冲突,所以条件(2)成立.第53页/共106页554.31 为下面的文法构造它的LR(1)项目集规范族,并判断它是否为LR(1)文法?

40、若是,构造它的分析表.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 .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 .

41、(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)项目集规范族:第54页/共106页56 action goto +()a$S E T0 s4 s5 1 2 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 s1

42、0 1514s13 s16 15r2 r216r4 r4LR(1)分析表:第55页/共106页57LALR(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 14 s6 13 s12 1611 15 r2 r2 r212 16 r4 r4 r4LALR(1)分析表不存在冲突,所以该文法是LALR(1)文法.第56页/共106页58证明文法G:ad bd ae be

43、 c c是LR(1)文法,但不是LALR(1)文法.第57页/共106页595.1 对于输入的表达式(4*7+1)*2,根据表的语法制导定义建立一棵带注释的分析树.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.lexval=1F.val=4 digit.lexval=7digit.lexval=4（lex表示是从词法分析来的）第58页/共106页605.2 试根据 (a)表中的语

44、法制导定义，和 (b)图的翻译模式来建立表达式(a)+(b)的分析树和语法树.(a)E T (E nptr )E +T T (E )(E )T nptr T nptr id ididentry to aidentry to a+第59页/共106页61(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+第60页/共106页625.4 E E+T|T T num.num|num(a)给出一个语法制导定义以确定每个子表达式的类型.(b)扩充(a)中的语法制导定义把表达式翻译成前

45、缀形式,并且决定 类型.(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;第61页/共106页63(b)S E S.type=E.type;S.code=E.code;E E1+T if (E1.t ype=real and T.type=integer)then begin E.type=real;E.code=+|E1.code|)end else if (E1.

46、t ype=integer and T.type=real)then begin E.type=real;E.code=+|inttoreal(E1 end else begin E.type=E1.t ype;E.code=+|E1 end E T ;E.code=T.code T num.num T.type=real;T.code=(num.num).lexval T num T.type=integer;T.code=第62页/共106页64 E T ;E.code=T.code T num.num T.type=real;T.code=(num.num).lexval T num T

47、.type=integer;T.code=第63页/共106页65 S t c E t c E t c +T t c E t c +T t c T t c num num 第64页/共106页665.5 S L.L|L L L B|B B 0|1(a)试用各有关综合属性决定.引入L的属性b记录2的L的位数次幂值S L1.L2 =L1.val+L2.val/L2.b;S L =;L L1 B =L1.val*2+;L.b=L.b*2;L B =;L.b=2;B 0 =0;B 1 =1;第65页/共106页67 S val L v .L b v L v B v L b v B v B v 0 L

48、b v B v 1 1 B v 0 1第66页/共106页68(b)试用一个语法制导定义来决定,在这个定义中B仅有综合 属性c,给出由B生成的位对于最后的数值的分担额.引入B的继承属性i,综合属性cS L1.L2 L1.i=20;L2.i=2-1;=L1.val+L2.valS L L.i=20;=;L L1 B if L.i=20 then begin L1 end else begin L1.i=L.i;L.s=L1.s/2;B.i=L1.s end =L1.val+B.c L B B.i=L.i;L.s=L.i/2;B 0 B.c=B.i*0B 1 B.c=B.i*1第67页/共106页

49、69 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 1第68页/共106页705.6 重写例中语法制导定义的基础文法,使类型信息只需用综合属性来传递.D T LL L1,id|idT intT real改写为:D L id ,L.type)L L1 id,L.type=L1.type;,L1.type)T int T.type=intT real T.type=real D L id L id ,T int第69页/共106页715.7 试从(a)和(b)中的语法制导定义中消除左递归

50、.(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 num.num T.t=false;T num T.t=true;E tTt it F tnum +Tt it F t 第70页/共106页72(b)E T F F.it=T.t;E.t=F.t;=T.c;E.c=F.c F +TF1 if F.it=real and T.t=integer then begin F1.it=real;F1.ic=+|);end else if F.it=integer and T.t=real then begi

51、n F1.it=real;F1.ic=+|)|T.c;end else begin F1.it=F.it;F1.ic=+|T.c;end F.t=F1.it;F.c=F1.ic;F F.t=F.it;F.c=;T num.num T.t=real;T.c=num.num.lexval;T num T.t=integer;T.c=;第71页/共106页73 E t c T t c it icF t c num +T t c it icF t c 第72页/共106页745.9 假设说明是由下列文法产生的:D L id L ,id L1|:T T integer|real(a)建立一个翻译模式,把

52、每一个标识符的类型加入到符号表中.(b)从(a)中的翻译模式构造一个与翻译程序.(a)D L id ,L.type L ,id L1 L.type=L1.type ,L.type L :T L.type=T.type T integer T.type=0 T real T.type=1 用整数0表示整型,1表示实型.第73页/共106页75(b)procedure D;var Ltype:integer;begin match(id);Ltype:=L();,Ltype)end;function L():integer;var Ltype:integer;begin if lookahead=

53、,then begin match(,);match(id);Ltype:=L();end else if lookahead=:then begin match(:);Ltype:=T();end;return Ltypeend;funtion T():integer;begin if lookahead=integer then begin match(integer);return 0 end else if lookahead=real then begin match(real);return 1 endend第74页/共106页765.10 下面的文法是表中基础文法的无二义形式.S

54、 L L LB|B B B sub F|F F L|text(a)用上面的文法修改表中的语法制导定义.S L L L1B L1.ps=;=;L.ht=max(L1.ht,B.ht)L B =B B1 sub F B1.ps=;=);B.ht=disp(B1.ht,F.ht)B F =F L =F text F.ht=text.h*第75页/共106页77(b)把(a)中的语法制导定义转化为翻译模式.S =10 L S.ht=L.ht L L1.ps=L1 =B L.ht=max(L1.ht,B.ht)L =B L.ht=B.ht B B1.ps=B1 sub =)F B.ht=disp(B1.

55、ht,F.ht)B =F B.ht=F.ht F =L F.ht=L.ht F text F.ht=text.h*第76页/共106页785.12 从5.10(b)中消除左递归.L =B L.ps=;L.iht=B.ht L L.ht=L.ht L =L.ps B L1.ps=L.ps L1.iht=max(B.ht,L.iht L1 L.ht=L1.ht L L.ht=L.iht L L1 B|B 转化为:L B L L B L L ps L htps B ht ps iht L ht ps B ht ps iht L ht 第77页/共106页79B B1 sub F|F转化为:B F B

56、 B sub F B B B =F B.ps=;B.iht=F.ht B B.ht=B.ht B sub =shrink(B.ps)F B1.ps=B.ps B1.iht=disp(B1.ht,F.ht)B1 B.ht=B1.iht B B.ht=B.iht ps B htps F ht ps iht B ht sub ps F ht ps iht B ht 第78页/共106页805.14 证明:在一个LL(1)文法的任何位置加上可区别的标记非终结符号,结果得到一个LR(1)文法.设文法G是LL(1)文法,则G中的每一个非终结符号A的任何两个不同的产生式A|,下列条件成立:1.FIRST()

57、FIRST()=;2.若*,那么FIRST()FOLLOW(A)=;不妨设=Y1.Yn,在产生式A|的任何位置加上可区别的标记非终结符号,得到 A ,=M1Y1 M2Y2.MnYn Mn+1 M1 M2 .Mn+1 则:1.FIRST()=FIRST(),FIRST()FIRST()=;2.若*,*也成立,FIRST()FOLLOW(A)=;因此,得到的文法仍然是LL(1)文法.第79页/共106页815.14 考虑对LR(1)文法 L L b|a 的下面的修改:L M L b|a M (a)问在输入符号串abbb的分析树中,自底向上分析程序以怎样的 顺序使用产生式.(b)说明这一经过修改的文

58、法不是LR(1)文法.(a)符号串abbb的最右推导为:rm rm rm rm rm L MLb MMLbb MMMLbbb MMMabbb MMabbb LMLb LMLb LMLb L a M rm rm Mabbb abbb M M (b)构造该文法的LR(1)项目集:I0:L .L,$L .M L b,$L .a,$M .,a在状态I0中,对于符号a存在移入-归约冲突,所以不是LR(1)文法.第80页/共106页82(a)把表中的语法制导定义转化为翻译模式.S L BL B B1 M B2B B1 sub N B2B textM N =L.sS.ht=B.htL.s=10B1.ps=M

59、.i=B2.ps=M.sM.ht=max(B1.ht,B2.ht)B1.ps=N.i=B2.ps=N.sM.ht=disp(B1.ht,B2.ht)B.ht=text.h*M.s=M.iN.s=shrink(N.i)第81页/共106页835.17(b)修改翻译模式,使继承属性ps的值出现在分开的栈中.在处理过程中消除标记非终结符号M.增加栈ps_val,栈顶指针ps_topS L B S.ht=B.ht;L ;ps_stack.push(10)BB1B2 B.ht =max(B1.ht,B2.ht)B B1 sub N B2 B.ht=disp(B1.ht,B2.ht);B text B.h

60、t=text.h*()N ps_stack.Push()第82页/共106页846.2 program main(input,output);procedure p(x,y,z);begin y:=y+1;z:=z+x;end;begin a:=2;b:=3;p(a+b,a,a);print aend.(a)call-by-value 2(b)call-by-reference p(5,a,a)8(c)copy-restore p(5,2,2)y:=y+1;3 z:=z+x;7 3 or 7(d)call-by-name a:=a+1;a:=a+a+b;9第83页/共106页856.4(1)p

61、rogram param(input,output);(2)procedure b(function h(n:integer):integer);(3)var m:integer;(4)begin m:=3;writeln(h(2);end b;(5)procedure c;(6)var m:integer;(7)function f(n:integer):integer;(8)begin f:=m+n end;(9)procedure r;(10)var m:integer;(11)begin m:=7;b(f)end;(12)begin m:=0;r end;(13)begin(14)c(

62、15)end.活动树:Param|c|r|b|f第84页/共106页86(a)词法环境Paramcaccesslinkmraccesslinkmbaccesslinkmfaccesslinkm(b)传递环境Paramcaccesslinkmraccesslinkmbaccesslinkmfaccesslinkm(c)活动环境Paramcaccesslinkmraccesslinkmbaccesslinkmfaccesslinkm 输出:2 输出:9 输出:5第85页/共106页877.2 翻译算术表达式-(a+b)*(c+d)+(a+b+c)为(a)四元式(b)三元式(c)间接三元式t1:=a

63、+bt2:=-t1t3:=c+dt4:=t2*t3t5:=t1+ct6:=t4+t5OParg1arg2result+abt1uminust1t2+cdt3*t2t3t4+t1ct5+t4t5t6OParg1arg2(0)+ab(1)uminus(0)(2)+cd(3)*(1)(2)(4)+(0)c(5)+(3)(4)第86页/共106页887.3 把下列C语言程序的可执行语句翻译为：main()int i;int a10;while(i=10)ai=0;(a)一棵语法树(b)后缀式(c)三地址代码 while =assigni 10 ai 0后缀式：i 10=ai 0 assign whil

64、e(c)L0:if i=10 goto L1 goto L2 L1:ai:=0 goto L0 L2:第87页/共106页897.4 修改图中计算说明语句中的名字的类型及相对地址的翻译模式，以允许在形如D id:T 的说明中可以用一串名字表来代替单个名字。D id,D1 enter(id.name,D1.type,offset);offset:=offset+D1.width;D.type:=D1.type;D.width:=D1.width;D id:T enter(id.name,T.type,offset);offset:=offset+T.width;D.type:=T.type;D.

65、width:=T.width;第88页/共106页907.8 将下列赋值语句译成三地址代码。Ai,j:=Bi,j+CAk,l+Di+jlow1=2;low2=4;n1=10;n2=20;w=4(low1*n2)+low2)*w=(2*20)+4)*4=176t1:=i*20t1:=t1+jt2:=A-176t3:=4*t1t4:=i*20t4:=t4+jt5:=B-176t6:=4*t4t7:=t5t6t8:=k*20t8:=t8+lt9:=A-176t10:=t8*4t11:=t9t10t12:=C-4t13:=4*t11t14:=t12t13t15:=i+jt16:=D-4t17:=4*t

66、15t18:=t16t17t19:=t7+t14t20:=t19+t18t2t3:=t20第89页/共106页917.9 Pascal语言中，语句 for v:=initial to final do stmt 与下列代码序列有相同含义：begin t1:=initial;t2:=final;if t1=t2 then begin v:=t1;stmt while v t2 do begin v:=succ(v);stmt end end 第90页/共106页92(a)试考虑下述Pascal程序 program forloop(input,output);var i,initial,final:integer;begin read(initial,final);for i:=initial to final do writeln(i)end.对于initial=MAXINT-5和final=MAXINT，问此程序将做些什么？其中MAXINT为目标机器允许的最大整数。输出从MAXINT-5 到MAXINT 之间的六个整数(b)试构造一个程序翻译Pascal的for 语句为三地址代码的语法