《编译原理习题》PPT课件.ppt

上传人：牧羊曲112

文档编号：5569011

上传时间：2023-07-29

格式：PPT

页数：106

大小：567KB

《《编译原理习题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《编译原理习题》PPT课件.ppt（106页珍藏版）》请在三一办公上搜索。

1、1,编译原理习题,2003.4,2,目录,chap 1 基本知识chap 3 词法分析chap 4 语法分析chap 5 语法制导翻译chap 6 运行时刻环境chap 7 中间代码生成chap 8 代码生成,3,第一章练习,1.1 文法 S(L)|a L L,S|S(a)指出文法的终结符号,非终结符号,开始符号.,文法的四个组成部分:终结符号 VT:语言不可再分的基本符号非终结符号VN:语法范畴(语法概念)开始符号 S:最终感兴趣的语法范畴产生式 P:定义语法范畴的一种书写形式,终结符号:(,)a 非终结符号:S L开始符号:S,元语言符号:表示“定义为”|表示“或”,4,(b)给出句

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

3、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,(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,7,(d)构造各个句子的最右推导.最右推导(规范推导)(e)这个文法产生的语言是什么?a(a)(a,a)(a,a),a).a和数据元素为a的广义表全体,8,1.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有两个不同的最左推导,该句子是二义性的.所以此文法是二义性的.,9,(b)对于句子abab构造两个相应的最右推导.S aSbS aSb abSaSb abSab abab rm rm rm rm rm S aSbS aSbaSbS aSbaSb aSbab a

5、bab 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组成的字符串.,10,1.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,11,(b)试对于句子 not(true or false)构造一棵分析树.,bexpr bterm bfactor not bfactor(bexpr)bexpr or bterm bterm bfactor bfactor false true,12,(c)试说明此文法产生的语言是全体布尔表达式.,13,练习:长度为n的字符串,分别有多少个前缀,后缀,子串,真前缀,子序列?,前缀:n+1后缀:n+1子串:1+n+(n-1)+.+1=1+n(n+1)/2真前缀:n子序列:1+Cn1+Cn2+Cn3+.+Cnn=2n,14,E E+T T*F i,给出句型E+T*i的短

7、语,直接短语和句柄,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,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符号串全体.,16,(d)0*10*10*10*,(e)(00|11)*(01

9、序排列.,(a|A)*(b|B)*(c|C)*.(z|Z)*,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),19,(e)带有偶数个0和奇数个1的由0和1组成的符号串全体.,E为带有偶数个0和1的由0和1组成的符号串全体.即(00|11)*(01|10)

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)*)*,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,21,3.6 给出接受下列在字母表0，1上的DFA。（a）所有以00结束的符号串的集合；,(1|0)*00,22,（b）所有具有三个0的符号串的集合。,1*

11、01*01*01*,23,3.7 构造等价于下列正规表达式的有限自动机.(a)10|(0|11)0*1,24,(b)(0|1)*|(11)*,25,3.8 给定右线性文法G:S 0S|1S|1A|0B A 1C|B 0C|1 C 0C|1C|0|1 试求一个等价的左线性文法G.,26,(d)(a|b)*abb(a|b)*,27,3.13 对于下列正规表达式构造最小状态的DFA.(b)(a|b)*a(a|b)(a|b),28,4.4 考虑文法 R R|R|RR|R*|(R)|a|b(a)试说明此文法生成在符号a和b之上的所有正规表达式.(b)试说明此文法是二义性的.(c)试构造一个等价的无二义性

12、文法.,(b)句子a|aa的两种最左推导.句子aa*的两种最左推导.,29,4.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 if e1 then if e2 then s1 else if e3 then s2 else s3,30,4.3 对于下面的每一个语言设计一个文法。试问其中哪些语

13、言是正规的？(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|0B1,31,(d)所有形如xy而xy的由0和1组成的符号串。,S 0E|1E|LBRE 00E|01E|10E

15、溯的递归下降分析器.问能否构造一个预测分析器.,procedure match(t:token);begin ifkahead=t thenend;procedure S;begin if match,34,4.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 bfac

16、tor 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,$,),35,(1)bexpr bterm bexpr(2)bexpr or bterm bexpr(3)bexpr(4)b

17、term bfactor bterm(5)bterm and bfactor bterm(6)bterm(7)bfactor not bfactor(8)bfactor(bexpr)(9)bfactor true(10)bfactor false,First(bexpr)=First(bterm)=First(bfactor)=not,(,true,falseFirst(bexpr)=or,First(bterm)=and,Follow(bexpr)=$,)Follow(bexpr)=$,)Follow(bterm)=or,$,)Follow(bterm)=or,$,)Follow(bfact

18、or)=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,36,4.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

19、)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)文法.,37,4.12试说明没有一个LL(1)文法可以是二义性的。若有一个LL(1)文法是二义性的,则存在句子w 有两种不同的最左推导:S*A 1*w S*A 2*w 对于文法中的产生式 A 1|2

20、,其中1,2 First(1)First(2)=First(w)与LL(1)文法矛盾.,38,4.15 文法 S(L)|a L L,S|S的算符优先关系由表4.20给出。建立与表相应的算符优先函数并用算符优先分析法分析句子(a,(a,a)及(a,(a,a),(a,a)。,算符优先关系表 a(),$a(=),$,句子(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 shift$(S,(a,a)$a,reduce

21、$(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,39,4.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)R.R.,其中+S.或+S.(3)RS当且仅当G中存在产生式

22、.S.,其中+.R 或+.R,最左终结符:S.或 S.,S是的最左终结符.,则的最左终结符是的最左终结符对于文法中 R.的产生式,R的最左终结符.,40,(b)bexpr bexpr or bterm|bterm bterm bterm and bfactor|bfactor bfactor not bfactor|(bexpr)|true|false,41,4.18 给出文法LR(0)项目集族及相应的识别活前缀的自动机的状态转移图.S S C cC S CC C d,42,4.19 利用图4.31画出文法4.27的识别活前缀的自动机的状态转移图.(P.200),I0:S.S S.iSeS S

23、.iS S.aI1:S S.I2:S i.Ses S i.S S.iSeS S.iS S.a0,I3:S a.I4:S iS.eS S iS.I5:S iSe.S S.iSeS S.iS S.aI6:S iSeS.,43,4.21 考虑文法 S 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)

24、对于输入串bab,给出SLR分析器的动作.(5)构造文法的LR(1)分析表和LALR分析表.,44,I0: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 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)

25、(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.b,45,First(S)=First(S)=First(A)=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 6,SLR分析表存在移入-归约

26、冲突.为消除二义性，假设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$shift30b3 ab$reduce S b0S1 ab$shift40S1a4 b$reduce A a0S1A6 b$reduce A SA0A2 b$shift30A2b3$reduce S b0A2S7$reduce S AS

27、0S1$accept,46,LR(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.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/b,I5:(I1,S)(I5,S)(I8,S)(

28、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)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/b,I9:(I6,A)(I9,A)S A.S,a/b S.AS,a/b S.b,a/b A.SA,a/b A.a,a/

29、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,47,STATE 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，

30、则遇到a时移入，遇到b时归约。,s4,r4,r2,48,该文法不是LR(1)文法.具有二义性.对于句子abab,存在两颗不同的分析树.,S,A,S,a,A,S,S,A,b,b,a,S,A,S,a,S,A,b,b,a,A,S,49,4.22 构造文法 S a S S b|a S S S|c 的LR(0)项目集规范族及识别活前缀的自动机.,50,4.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),Follow(E)=+,$Follow(T)=+,$,a,bFollow(E)=+,$,*,a,

31、b,51,4.26 证明每一个LL(1)文法都是LR(1)文法.,52,4.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,b存在归约-归约冲突,该文法不是SLR(1)文法.,53,4.28 证明任何一个LR(1)文法都是无二义文法.,54,4.29 证明任何SLR(1)文法都是LR(1)文法.,假设文法G是

32、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)可得知,项目A.的向前搜索符号Follow(A)对于一个项目集中的不同归约项目A2.搜索符A,B3.,搜索符A搜索符A 搜索符A=不存在归约-归约冲突,所以条件(2)成立.,55,4.31

33、为下面的文法构造它的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.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)

34、/+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)项目集规范族:,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 s10 1514s1

35、3 s16 15r2 r216r4 r4,LR(1)分析表:,57,LALR(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 r4,LALR(1)分析表不存在冲突,所以该文法是LALR(1)文法.,58,证明文法G:ad bd ae be c c是LR(1)文法,但不是LALR(1

36、)文法.,59,5.1 对于输入的表达式(4*7+1)*2,根据表5.1的语法制导定义建立一棵带注释的分析树.,60,5.2 试根据(a)表5.3中的语法制导定义，和(b)图5.17的翻译模式来建立表达式(a)+(b)的分析树和语法树.(a),E T(E nptr)E+T T(E)(E)T nptr T nptr id id,id,entry to a,id,entry to a,+,61,(b),E T R(E nptr)T R(E)+T i R s T nptr R(E)id Tnptr R id,id,entry to a,id,entry to a,+,62,5.4 E E+T|T T

37、 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;,63,(b)S E S.type=E.type;S.code=E.code;E E1+T if(E1.t ype=real and T.type=integer)t

38、hen 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 nu

39、m T.type=integer;T.code=num.lexval,64,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.lexval,65,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,66,5.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.

40、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;,67,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 1,68,(b)试用一个语法制导定义来决定S.val,在这个定义中B仅有综合属性c,给出由B生成的位对于最后的数值的分担额.,引入B的继承属性i,综合属性cS L1.L2 L1.i=20;L2.i=2-1;S.val=L1.val+L2.

41、valS 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*1,69,70,5.6 重写例5.3中语法制导定义的基础文法,使类型信息只需用综合属性来传递.D T LL L1,id|idT intT real,改写为:D L id addtype(id.entry,L.ty

42、pe)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 int,71,5.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 num.num T.t=false;T num T.t=true;,E tTt it F tnum+Tt it F t num.num,72,(

43、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 begin 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.i

44、c;T num.num T.t=real;T.c=num.num.lexval;T num T.t=integer;T.c=num.lexval;,73,E t c T t c it icF t c num+T t c it icF t c num.num,74,5.9 假设说明是由下列文法产生的:D L id L,id L1|:T T integer|real(a)建立一个翻译模式,把每一个标识符的类型加入到符号表中.(b)从(a)中的翻译模式构造一个与翻译程序.,(a)D L id addtype(id.entry,L.type L,id L1 L.type=L1.type addtype

45、(id.entry,L.type L:T L.type=T.type T integer T.type=0 T real T.type=1 用整数0表示整型,1表示实型.,75,(b)procedure D;var Ltype:integer;begin match(id);Ltype:=L();addtype(id.entry,Ltype)end;function L():integer;var Ltype:integer;begin if lookahead=,then begin match(,);match(id);Ltype:=L();end else if lookahead=:t

46、hen 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,76,5.10 下面的文法是表5.7中基础文法的无二义形式.S L L LB|B B B sub F|F F L|text(a)用上面的文法修改表5.7中的语法制导定义.,S L L.ps=10;S.h

47、t=L.ht L L1B L1.ps=L.ps;B.ps=L.ps;L.ht=max(L1.ht,B.ht)L B B.ps=L.ps;L.ht=B.ht B B1 sub F B1.ps=B.ps;F.ps=shrink(B.ps);B.ht=disp(B1.ht,F.ht)B F F.ps=B.ps;B.ht=F.ht F L L.ps=F.ps;F.ht=L.ht F text F.ht=text.h*F.ps,77,(b)把(a)中的语法制导定义转化为翻译模式.,S L.ps=10 L S.ht=L.ht L L1.ps=L.ps L1 B.ps=L.ps B L.ht=max(L1.

48、ht,B.ht)L B.ps=L.ps B L.ht=B.ht B B1.ps=B.ps B1 sub F.ps=shrink(B.ps)F B.ht=disp(B1.ht,F.ht)B F.ps=B.ps F B.ht=F.ht F L.ps=F.ps L F.ht=L.ht F text F.ht=text.h*F.ps,78,5.12 从5.10(b)中消除左递归.,L B.ps=L.ps B L.ps=L.ps;L.iht=B.ht L L.ht=L.ht L B.ps=L.ps B L1.ps=L.ps L1.iht=max(B.ht,L.iht L1 L.ht=L1.ht L L.

49、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,79,B B1 sub F|F转化为:B F B B sub F B B,B F.ps=B.ps F B.ps=B.ps;B.iht=F.ht B B.ht=B.ht B sub F.ps=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

50、B ht,80,5.14 证明:在一个LL(1)文法的任何位置加上可区别的标记非终结符号,结果得到一个LR(1)文法.,设文法G是LL(1)文法,则G中的每一个非终结符号A的任何两个不同的产生式A|,下列条件成立:1.FIRST()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(