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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理习题,2003.4,1,目录,chap 1,基本知识,chap 3,词法分析,chap 4,语法分析,chap 5,语法制导翻译,chap 6,运行时刻环境,chap 7,中间代码生成,chap 8,代码生成,2,第一章 练习,1.1,文法,S,(L)|a,L,L,S|S,(a),指出文法的终结符号,非终结符号,开始符号,.,文法的四个组成部分,:,终结符号,V,T,:,语言不可再分的基本符号,非终结符号,V,N,:,语法范畴,(,语法概念,),开始符号,S:,最终感兴趣的语法范畴,产生式,P,:,定义语法范畴的一种书写形式,终结符号,:(,)a,非终结符号,:S L,开始符号,:S,元语言符号,:,表示“定义为”,|,表示“或”,3,(b),给出句子的分析树,分析树,:(,推导树,),表示一个句型的推导,(a,(a,a),S,(L ),L ,S,S (L ),a S,a,4,(c),给出句子的最左推导,给出每次推导后得到的句型的短语,直接短语,最左推导,:,推导中任何一步,都是对,中的最左非终结,lm,符号进行替换的推导,.,短语,是文法的句型,(S,*,),S,*,A,且,A,+,则,是关于,A,的句型,的短语,.,直接短语,是文法的句型,(S,*,),S,*,A,且,A,则,是关于A,的句型,的直接短语,.,句柄,:,一个句型的最左直接短语称为句柄,.,5,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,(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,的广义表全体,7,1.2,考虑文法,S,aSbS,|,bSaS,|,(a),试说明此文法是二义性的,.,(,定义,1.5),如果一文法的句子存在两棵分析树,则该,句子是二义性的,.,如果一文法包含二义性的句子,则这个,文法是二义性的,.,可以从句子,abab,有两个不同的最左推导来说明,.,S,aSbS,abS,abaSbS,ababS,abab,lm lm lm lm lm,S,aSbS,abSaSbS,abaSbS,ababS,abab,lm lm lm lm lm,句子,abab,有两个不同的最左推导,该句子是二义性的,.,所以此文法是二义性的,.,8,(b),对于句子,abab,构造两个相应的最右推导,.,S,aSb,S,a,S,b,abSa,S,b,ab,S,ab,abab,rm,rm,rm,rm,rm,S,aSb,S,aSbaSb,S,aSba,S,b,a,S,bab,abab,rm,rm,rm,rm,rm,(c),对于句子,abab,构造两个相应的分析树,.,S S,a S b S a S b S,b S a,S a S b S,(d),此文法产生的语言是什么,?,由相同个数的,a,和,b,组成的字符串,.,9,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,开始符号,:,bexpr,10,(b),试对于句子,not(true or false),构造一棵分析树,.,bexpr,bterm,bfactor,not,bfactor,(,bexpr,),bexpr,or,bterm,bterm,bfactor,bfactor,false,true,11,(c),试说明此文法产生的语言是全体布尔表达式,.,12,练习,:,长度为,n,的字符串,分别有多少个,前缀,后缀,子串,真前缀,子序列,?,前缀,:n+1,后缀,:n+1,子串,:1+n+(n-1)+.+1=1+n(n+1)/2,真前缀,:n,子序列,:1+C,n,1,+C,n,2,+C,n,3,+.+,C,n,n,=2,n,13,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,14,第三章 练习,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,符号串全体,.,15,(d)0,*,1,0,*,1,0,*,1,0,*,(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,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),最多有一个重复出现的数字的数字符号串全体,令,r,i,=i|,i=0,1,2,.,9,R,0,|R,1,|R,2,|.|R,9,记为,R,i,i,(0,1,2.,9),P(0,1,2.,9),表示,0,1,2.,9,的全排列,r,i,0,r,i,1,.r,i,9,i,0,i,1,.i,9,P(0,1,2.,9),i ,r,i0,r,i1,.r,i9,i,(0,1,2.,9),i,0,i,1,.i,9,P(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,是任意正规式,证明以下关系成立,:,A|A=A,(A,*,),*,=A,*,A,*,=,|AA,*,(AB),*,A,=A(BA),*,(A|B),*,=(A,*,B,*)*=(,A,*,|B,*,),*,A=,b|aA,当且仅当,A=a,*,b,20,3.6,给出接受下列在字母表,0,，,1,上的,DFA,。,（,a,）,所有以,00,结束的符号串的集合；,A,start,B,0,C,0,1,0,NFA,等价于,A,1start,B,C,0,0,0,1,1,DFA,(1|0),*,00,21,（,b,）,所有具有三个,0,的符号串的集合。,1,*,01,*,01,*,01,*,A,start,B,0,C,0,1,DFA,1,1,B,0,1,22,3.7,构造等价于下列正规表达式的有限自动机,.,(a)10|(0|11)0,*,1,0,0,0,1,1,A,start,D,1,B,E,C,1,NFA,0 1,A D BC,D D E,BC E D,E /,1,0,1,0,A,start,BC,0,D,E,DFA,1,23,(b)(0|1),*,|(11),*,0|1,1,1,A,start,C,B,E,D,NFA,0 1,ABDE ABDE ABCDE,ABCDE ABDE ABCDE,1,1,A,start,0,B,DFA,0,1,A,start,最小化,DFA,0,24,3.8,给定右线性文法,G:,S,0S|1S|1A|0B,A 1C|,B 0C|1,C 0C|1C|0|1,试求一个等价的左线性文法,G.,0,0,0,1,1,S,start,B,1,A,C,f,状态转移图,1,0,0,1,0,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|,25,3.9-3.11,(d)(a|b),*,abb(a|b,),*,1,start,2,a,4,b,a,3,b,b,b,a,由正规表达式构造,NFA,1,start,12,a,14,b,13,b,b,a,a,b,a,124,a,134,b,b,a,由,NFA,得到,DFA,A,B,C,D,E,F,B,C,D,E,F,A B C D E,A,B,a,D,b,C,b,a,b,a,a,b,最小化,DFA,26,3.13,对于下列正规表达式构造最小状态的,DFA.,(b)(a|b),*,a(a|b)(a|b),a,1,start,2,a,4,3,b,a,b,NFA,ba,A,start,B,a,b,H,G,a,C,D,a,a,a,E,F,a,b,a,a,a,b,b,b,b,最小化,DFA,27,4.4,考虑文法,R,R|R|RR|R,*,|(R)|a|b,(a),试说明此文法生成在符号,a,和,b,之上的所有正规表达式,.,(,b),试说明,此文法是二义性的,.,(,c),试构造,一个等价的无二义性文法,.,(b),句子,a|aa,的两种最左推导,.,句子,aa,*,的两种最左推导,.,R,R R,a R *,a,R,R *,R R,a a,(c),消除,二义性,R,R|S|S,S ST|T,T U,*,|U,U(R)|a|b,28,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,S,MS,if,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,S,if,E,then,S,e1,MS,if,E,then,MS,else,S,e2,other,MS,s1,if,E,then,MS,else,S,e3,other,MS,s2,other,s3,29,4.3,对于下面的每一个语言设计一个文法。试问其中哪些语言是正规的？,(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|1,C 0C|0,S,A|B,A 0|0A|A0|10A|01A|A10|A01|1A0|0A1,B 0|0B|B0|10B|01B|B10|B01|1B0|0B1,30,(d),所有形如,xy,而,x,y,的,由,0,和,1,组成的符号串。,S,0E|1E|LBR,E 00E|01E|10E|11E|,B I I,1,B|OO,1,B|IO,1,C|OI,1,C,C IO,1,C|OI,1,C|,I,1,O OI,1,O,1,I IO,1,I,1,I I I,1,O,1,O OO,1,L I 1L,LO 0L,I,1,R R1,O,1,R R0,LR ,所有形如,xy,而,x,=y,的,由,0,和,1,组成的符号串。,S,0S0|1S1|,31,4.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|,32,4.7,对于文法,S,aSbS,|,bSaS,|,构造一个带有回溯的递归下降分析器,.,问能否构造一个预测分析器,procedure,match(t:token,);,begin,ifkahead,=t then,end;,procedure S;,begin,if match,33,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,bterm,bterm,and,bfactor,bterm,|,bfactor,not,bfactor,|(,bexpr,)|,true,|,false,2.,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),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,false,First(,bexpr,)=or,First(,bterm,)=and,Follow(,bexpr,)),Follow(,bexpr,)=$,),Follow(,bterm,)=or,$,),Follow(,bterm,)=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,35,4.11,试说明没有一个左递归文法可以是,LL(1),的。,(1),直接左递归文法中存在产生式,:,A A,1,|A,2,|.|,A,m,|,1,|,2,|.|,n,其中,1,2,.,n,均不以,A,开头,First(A,i,)First(,j,)=First(,j,),若,j,*,First(A,i,),Follow(A,)=First(,i,),不是,LL(1),文法,.,(2),间接左递归文法中存在产生式集合,:,A B,1,1,|,1,|,2,|.|,n,B,1,B,2,2,.,B,m,A,First(B,1,1,)=,First(A,m,.,1,),First(,j,)First(B,1,1,),j=1,.,n,First(,j,)First(B,1,1,),j=1,.,n,若,j,*,First(B,1,1,),Follow(A,)=First(,m,.,1,),不是,LL(1),文法,.,36,4.12,试说明没有一个,LL(1),文法可以是二义性的。,若有一个,LL(1),文法是二义性的,则存在句子,w,有两种不同的最左推导,:,S*A ,1,*w,S*A ,2,*w,对于文法中的产生式,A ,1,|,2,其中,1,2,First(,1,)First(,2,)=,First(w,),与,LL(1),文法矛盾,.,37,4.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 0,g 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 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),$),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,的,最左终结符,.,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,(,true,false or,and,not,),true,false,bterm,and,not,(,true,false and,not,),true,false,bfactor,not,(,true,false not,),true,false,40,4.18,给出文法,LR(0),项目集族及相应的识别活前缀的自动机的状态转移图,.,S,S C,cC,S CC C d,I,0,:,S,.S,S,.CC,C .,cC,C .d,I,1,:,S,S,.,I,2,:,S,C.C,C .,cC,C .d,I,3,:,C,c.C,C .,cC,C .d,I,4,:,C d.,I,5,:,S,CC.,I,6,:,C,cC,.,I,0,I,1,S,C,I,2,c,I,3,C,I,5,d,I,4,c,d,C,I,6,c,d,start,41,4.19,利用图,4.31,画出文法,4.27,的识别活前缀的自动机的状态转移图,.(P.200),I,0,:,S,.S,S,.,iSeS,S .,iS,S .a,I,1,:,S,S,.,I,2,:,S,i.Ses,S,i.S,S,.,iSeS,S .,iS,S .a0,I,3,:,S a.,I,4,:,S,iS,.eS,S,iS,.,I,5,:,S,iSe.S,S,.,iSeS,S .,iS,S .a,I,6,:,S,iSeS,.,i,I,0,I,1,S,a,I,3,i,I,2,S,I,4,i,start,e,I,5,S,I,6,a,a,42,4.21,考虑文法,S,A S|b,A,S A|a,(1),构造文法的,LR(0),项目集规范族及相应的,DFA.,(2),如果把每一个,LR(0),项目看成一个状态,并从每个形如,B,.X,的状态出发画一条标记为,X,的弧到状态,B,X.,且从,从每个形如,B,.A,的状态出发画一条标记为的弧到所有形如,A.,的状态,.,这样就得到了一个,NFA.,说明这个,NFA,和,(1),的,DFA,是等价的,.,(3),构造文法的,SLR,分析表,.,(4),对于输入串,bab,给出,SLR,分析器的动作,.,(5),构造文法的,LR(1),分析表和,LALR,分析表,.,43,I,0,:,S,.S,S,.AS,S .b,A .SA,A .a,I,1,:(I,0,S),S,S,.,A S.A,A .SA,A .a,S,.AS,S .b,I,2,:,(I,0,A)(I,2,A)(I,6,A),S,A.S,S,.AS,S .b,A .SA,A .a,I,3,:,(I,0,b),(I,1,b),(I,2,b)(I,5,b)(I,6,b)(I,7,b),S,b.,I,4,:,(I,0,a)(I,1,a)(I,2,a),(I,5,a)(I,6,a)(I,7,a),A a.,I,5,:(I,1,S),(I,5,S)(I,7,S),A S.A,A .SA,A a,S,.AS,S .b,I,6,:(I,1,A)(I,5,A),(I,7,A),A,SA.,S,A.S,S,.AS,S .b,A .SA,A .a,I,7,:(I,2,S)(I,6,S),S,AS.,A S.A,A .SA,A .a,S,.AS,S .b,44,First(S,)=,First(S,)=,First(A,)=b,a,Follow(S,)=$,Follow(S,)=a,b,$,Follow(A,)=a,b,SLR,分析表,STATE ACTION GOTO,a b$S A,0 s4 s3 1 2,1 s4 s3 acc 5 6,2 s4 s3 7 2,3 r3,r3,r3,4 r5,r5,5 s4 s3 5 6,6 s4/r4 s3/r4 7 2,7 s4/r2 s3/r2 r2 5 6,SLR,分析表存在移入,-,归约冲突,.,为消除二义性，假设,a,的优先级高于,b,，则遇到,a,时移入，遇到,b,时归约。,输入串,bab,SLR,分析器的动作,:,栈 输入 动作,0,bab,$shift3,0b3,ab,$reduce S b,0S1,ab,$shift4,0S1a4 b$reduce A a,0S1A6 b$,shift-reduce,collision,输入串,bab,SLR,分析器的动作,:,栈 输入 动作,0,bab,$shift3,0b3,ab,$reduce S b,0S1,ab,$shift4,0S1a4 b$reduce A a,0S1A6 b$reduce A SA,0A2 b$shift3,0A2b3$reduce S b,0A2S7$reduce S AS,0S1$accept,45,LR(1),项目集规范族,I,0,:,S,.S,$,S,.AS,$/a/b,S .b,$/a/b,A .SA,a/b,A .a,a/b,I,1,:(I,0,S),S,S,.,$,A S.A,a/b,A .SA,a/b,A .a,a/b,S,.AS,a/b,S .b,a/b,I,2,:,(I,0,A)(I,2,A),S,A.S,$/a/b,S,.AS,$/a/b,S .b,$/a/b,A .SA,a/b,A .a,a/b,I,3,:,(I,0,b)(I,2,b),S,b.,$/a/b,I,4,:,(I,0,a)(I,1,a)(I,2,a)(I,5,a),(I,6,a)(I,8,a)(I,9,a)(I,10,a),A a.,a/b,I,5,:(I,1,S)(I,5,S)(I,8,S)(I,10,S),A S.A,a/b,A .SA,a/b,A .a,a/b,S,.AS,a/b,S .b,a/b,I,6,:(I,1,A)(I,5,A)(I,8,A)(I,10,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/b,I,7,:(I,1,b)(I,5,b)(I,6,b),(I,8,b)(I,9,b)(I,10,b),S,b.,a/b,I,8,:(I,2,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,I,9,:(I,6,A)(I,9,A),S,A.S,a/b,S,.AS,a/b,S .b,a/b,A .SA,a/b,A .a,a/b,I,10,:(I,6,S)(I,9,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,46,STATE ACTION GOTO,a b$S A,0 s4 s3 1 2,1 s4 s7 acc 5 6,2 s4 s3 8 2,3 r3,r3,r3,4 r5,r5,5 s4 s7 5 6,6 s4/r4 s7/r4 10 9,7 r3,r3,8 s4/r2 s7/r2 r2 5 6,9 s4 s7 10 9,10 s4/r2 s7/r2 5 6,LR(1),分析表,该文法的,LR(1),分析表中存在移入,-,归约冲突，文法具有二义性。,为消除二义性，假设,a,的优先级高于,b,，则遇到,a,时移入，遇到,b,时归约。,s4,r4,r2,47,该文法不是,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,48,4.22,构造文法,S,a S S b|a S S S|c,的,LR(0),项目集规范族及识别活前缀的自动机,.,I,0,:,S,.S,S,.,aSSb,S .,aSSS,S .c,I,1,:,S,S,.,I,2,:,S,a.SSb,S,a.SSS,S,.,aSSb,S .,aSSS,S .c,I,3,:,S c.,I,4,:,S,aS.Sb,S ,aS.SS,S,.,aSSb,S .,aSSS,S .c,I,5,:,S,aSS.b,S ,aSSS,S,.,aSSb,S .,aSSS,S .c,I,6,:,S,aSSb,.,I,7,:,S,aSSS,.,I,0,I,1,S,c,I,3,a,I,2,S,I,4,start,S,I,5,b,I,6,a,c,a,a,c,c,S,I,7,49,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),I,0,:,E,.E,E,.E+T,E .T,T .TF,T .F,F .F*,F .a,F .b,I,1,:,E,E,.,E,E.+T,I,2,:,E,T.T,T.F,F .F*,F .a,F .b,I,3,:,T F.,F F.*,I,4,:,F,a.,I,5,:,F,b.,I,6,:,E,E+.T,T .TF,T .F,F .F*,F .a,F .b,I,7,:,T,TF.,F F.*,I,8,:,F F*.,I,9,:,E,E+T.,T T.F,F .F*,F .a,F .b,action,goto,+*a b$E T F,0 s4 s5 1 2 3,1 s6,acc,2 r2 s4 s5 r2 7,3 r4 s8 r4,r4,r4,4 r6,r6,r6,r6,r6,5 r7,r7,r7,r7,r7,6 s4 s5 9 3,7 r3 s8 r3,r3,r3,8 r5,r5,r5,r5,r5,9 r1 s4 s5 r1 7,Follow(E,)=+,$,Follow(T,)=+,$,a,b,Follow(E,)=+,$,*,a,b,50,4.26,证明每一个,LL(1),文法都是,LR(1),文法,.,51,4.27,证明下面文法是,LL(1),的但不是,SLR(1),文法,.,S,A a A b|B b B a,A ,B ,First(AaAb,)=a,First(BbBa,)=b,First(AaAb,),First(BbBa,)=,文法是,LL(1),的,.,构造,SLR(1),项目集,:,I,0,:,S,.S,S,.,AaAb,S,.,BbBa,A .,B .,Follow(A,)=,Follow(B,)=a,b,存在归约,-,归约冲突,该文法不,是,SLR(1),文法,.,52,4.28,证明任何一个,LR(1),文法都是无二义文法,.,53,4.29,证明任何,SLR(1),文法都是,LR(1),文法,.,假设文法,G,是,SLR(1),文法,则,对于文法的状态,i:,对于,A,.X,XV,T,XFollow(B,),i,中没有项目,B.,对于,A,.,和,B.,Follow(A,),Follow(B,)=,构造,G,的,LR(1),项目集,若,G,是,LR(1),文法,则项目集,i,必须满足条件,:,(1),对于,A,.X,a,XV,T,XFollow(B,),i,中没有项目,B.,X.(,显然成立,),(2),没有,A,.,a,和,B.,a,的两个项目,.,由,closure(I,),的构造,A,.B,a,B.,First(a,),可得知,项目,A,.,的向前搜索符号,Follow(A,),对于一个项目集中的不同归约项目,A,2.,搜索符,A,B,3.,搜索符,A,搜索符,A,搜索符,A=,不存在归约,-,归约冲突,所以条件,(2),成立,.,54,4.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),I,0,:,S,.S$,S,.E$,E .E+T$/+,E .T$/+,T .(E)$/+,T .a$/+,I,1,:,S,S.$,I,2,:,S,E.$,E,E.+T$/+,I,3,:,E T.$/+,I,4,:,T (.E)$/+,E .E+T )/+,E .T )/+,T .(E)/+,T .a )/+,I,5,:,T a.$/+,I,6,:,E E+.T$/+,T .(E)$/+,T .a$/+,I,7,:,T (E.)$/+,E E.+T )/+,I,8,:,E T.)/+,I,9,:,T (.E)/+,E .E+T )/+,E .T )/+,T .(E)/+,T .a )/+,I,10,:,T a.)/+,I,11,:,E E+T.$/+,I,12,:,T (E).$/+,I,13,:,E E+.T )/+,T .(E)/+,T .a )/+,I,14,:,T (E.),/+,E E.+T )/+,I,15,:,E E+T.)/+,I,16,:,T (E).)/+,LR(1),项目集规范族,:,55,action,goto,+()a$S E T,0,s4 s5 1 2 3,1,acc,2,s6 r1,3,r3,r3,4,s9 s10 7 8,5,r5,r56,s4 s5 11,7,s13 s12,8,r3,r3,9,s9 s5 14 8,10,r5,r5,11,r2,r2,12,r4,r4,13,s9 s10 15,14,s13 s16,15,r2 r2,16,r4 r4,LR(1),分析表,:,56,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 16,11 15 r2,r2,r2,12 16 r4,r4,r4,LALR(1),分析表不存在冲突,所以该文法是,LALR(1),文法,.,57,证明文法,G:,ad,bd,ae ,be,c ,c,是,LR(1),文法,但不是,LALR(1),文法,.,58,5.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,=1,T,.val,=4 *,F,.val,=7,digit.lexval,=1,F,.val,=4,digit.lexval,=7,digit.lexval,=4,（,lex,表示是从词法分析来的）,59,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,+,60,(b),E,T R,(,E,nptr,),T,R,(,E