编译原理陈意云课后答案宣讲教育课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,luanj,*,编译原理陈意云课后答案.宣讲PPT讲座,3.1,考虑文法S-(L)|aL-L,S|S(a)建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树(b)为(a)的两个句子构造最左推导(c)为(a)的两个句子构造最右推导(d)这个文法产生的语言是什么,12/5/2025,2,luanj,3.1(续)-(a,(a,a),S=(L),=(L,S),=(S,S),=(a,S),=(a,(L),=(a,(L,S),=(a,(S,S)=(a,(a,S),=(a,(a,a),S,(,L,),L,S,S,a,(L )L,S,S,a,a,S=(L),=(L,S),=(L,(L),=(L,(L,S),=(L,(L,a),=(L,(S,a),=(L,(a,a)=(S,(a,a),=(a,(a,a),12/5/2025,3,luanj,3.1(续)-(a,(a,a),(a,a),S,(,L,),L,S,S,a,S=(L),=(L,S),=(S,S),=(a,S),=(a,(L),=(a,(L,S),=(a,(S,S)=(a,(L),S),=(a,(L,S),S),=(a,(S,S),S),=(a,(a,S),S),=(a,(a,a),S),=(a,(a,a),(L),=(a,(a,a),(L,S),=(a,(aa),(S,S),=(a,(a,a),(a,S),=(a,(a,a),(a,a),(,L,),L,S,(,L,),L,S,S,a,a,(,L,),L,S,S,a,a,S,S=(L),=(L,S),=(L,(L),=(L,(L,S),=(L,(L,(L),=(L,(L,(L,S),=(L,(L,(L,a),=(L,(L,(S,a),=(L,(L,(a,a),=(L,(S,(a,a),=(L,(L),(a,a),=(L,(L,S),(a,a),=(L,(L,a),(a,a),=(L,(S,a),(a,a),=(L,(a,a),(a,a),=(S,(a,a),(a,a),=(a,(a,a),(a,a),12/5/2025,4,luanj,3.1(续),描述的语言：括号匹配的串，串中的各项由”,”隔开，项可以是括号匹配的子串或a,12/5/2025,5,luanj,3.2,考虑文法S-aSbS|bSaS|,(a)为句子abab构造两个不同的最左推导，以说明此文法二义(b)为abab构造对应的最右推导(c)为abab构造对应的分析树,(d)这个文法产生的语言是什么,12/5/2025,6,luanj,3.2(续),(1)S=a,S,bS=ab,S,=ab,a,S,bS,=abab,S,=abab(2)S=a,S,bS=a,b,S,aS,bS=aba,S,bS=abab,S,=abab,S=aSb,S,=a,S,b=a,bSa,S,b=ab,S,ab=abab(2),S,a,S,b,S,a,S,b,S,S,a,S,b,S,b,S,a,S,(1),(2),描述的语言是a,b数目相等的串,12/5/2025,7,luanj,3.4,文法R-R,|,R|RR|R,*,|(R)|a|b产生字母表(a,b)上所有不含,的正规式该文法是二义的(a)证明该文法产生字母表a,b上的所有正规式(b)为该文法写一个等价的非二义文法。(c)按照上面的两个文法构造ab|b*a的分析树,12/5/2025,8,luanj,3.4(续),证明该文法产生字母表a,b上的所有正规式证明：1）该文法产生的串是字母表a,b上的正规式R-a和R-b产生a,b,而a,b是a,b上的符号，因此是正规式。若R1，R2产生正规式,，,则：,R-R1R2产生正规式,R-R1|R2产生正规式,|,R-R1*产生正规式,*,R-(R1)产生正规式,(,),2),字母表a,b上的所有正规式都可由此文法产生字母表a,b上的任一正规式(其中,为正规式),必为以下形式之一：,，可由R-RR产生,|,，可由R-R|R产生,*，可,由R-R*产生,(,)，可,由R-(R)产生 a,可,由R-a产生 b,可,由R-b产生因而，,该文法产生字母表a,b上的所有正规式,12/5/2025,9,luanj,3.4(续),该文法没有体现运算符,|,、,*,、()、并置的优先级，因而是二义的。,R=,R,|,R,=,a,|,R=a,|,R,*,=a,|,b,*,R=,R,*,=,R,|,R,*,=,a,|,R,*,=a,|,b,*,E-E,|,T|TT-TF|FF-F,*,|(E)|a|b,E,=,E,|,T,=E,|,F,=E,|,F,*,=E,|,b,*,=,T,|,b,*,=,F,|,b,*,=,a,|,b,*,12/5/2025,10,luanj,3.4(续)-ab|b*a,二义的 非二义的,R,R,|,R,R R,a,b,R R,a,R,*,b,R,R R,a,R,*,R,|,R,b,R R,b,a,E,E,|,T,T F,T,T F,F,a,b,F,F,*,b,a,12/5/2025,11,luanj,3.5,下面的条件语句文法,stmt-,if,expr,then,stmt|matched_stmt,matched_stmt-,if,expr,then,matched_stmt,else,stmt|,other,试图消除悬空else的二义性。请证明此文法仍是二义的。,12/5/2025,12,luanj,3.5(续),由于matched_stmt不能保证then和else的配对，因而存在二义性,句型,if,expr,then,if,expr,then,matched_stmt,else,if,expr,then,matched_stmt,else,stmt存在两个不同的最左推导,期望的是：,if,expr,then,if,expr,then,matched_stmt,else,if,expr,then,matched_stmt,else,stmt,12/5/2025,13,luanj,3.5(续),一种推导，和期望的不一样,stmt,=matched_stmt=,if,expr,then,matched_stmt,else,stmt=,if,expr,then,if,expr,then,matched_stmt,else,stmt,else,stmt=,if,expr,then,if,exprthen,matched_stmt,else,if,expr,then,stmt,else,stmt=,if,expr,then,if,expr,then,matched_stmt,else,if,expr,then,matched_stmt,else,stmt,if,expr,then,if,expr,then,matched_stmt,else if,expr,then,matched_stmt,else,stmt,12/5/2025,14,luanj,3.5(续),另一种推导,stmt=,if,expr,then,stmt=,if,expr,then,matched_stmt=,if,expr,then,if,expr,then,matched_stmt,else,stmt=,if,expr,then,if,expr,then,matched_stmt,else,matched_stmt=,if,expr,then,if,expr,then,matched_stmt,else,if,expr,then,matched_stmt,else,stmt,if,expr,then,if,expr,then,matched_stmt,else,if,expr,then,matched_stmt,else,stmt,12/5/2025,15,luanj,3.8(a),消除3.1的左递归12/5/2025,16,luanj,3.8(a)(续),S-(L)|aL-L,S|S,只有直接左递归S-(L)|aL-SLL-,SL|,12/5/2025,17,luanj,3.10,构造下面文法的LL(1)分析表D-TLT-,int,|,real,L-,id,RR-,id,R|,12/5/2025,18,luanj,3.10(续),先计算FIRST和FOLLOWFIRST(D)=FIRST(T)=,int,real,FIRST(L)=,id,FIRST(R)=,FOLLOW(D)=FOLLOW(L)=$FOLLOW(T)=,id,FOLLOW(R)=$,12/5/2025,19,luanj,3.10(续),int,real,id,$,D,D-TL,D-TL,T,T-,int,T-,real,L,L-,id,R,R,R-,id,R,R-,12/5/2025,20,luanj,3.11,下面文法是否LL(1)文法？说明理由S-AB|PQ,x,A-xy,B-,bc,P-,d,P|,Q-,a,Q|,12/5/2025,21,luanj,3.11(续),不是LL(1)文法,LL(1)文法：对于产生式A-,|,本题中，FIRST(AB)=x,FIRST(PQx)=d,a,x不满足条件(1),12/5/2025,22,luanj,3.15,(a)用3.1的文法构造(a,(a,a)的最右推导说出每个右句型的句柄,(b)给出对应(a)的最右推导的移进-归约分析器的步骤,(c)对照(b)的移进-归约，给出自下而上构造分析树的步骤。,12/5/2025,23,luanj,3.15(续)(a)(b),S=,(L),=(,L,S,),=(L,(L),),=(L,(,L,S,),=(L,(L,a,),=(L,(,S,a),=(L,(,a,a)=(,S,(a,a),=(,a,(a,a),栈,输入,动作,$,(a,(a,a)$,移进,$(,a,(a,a)$,移进,$(a,(a,a)$,归约:S-a,$(S,(a,a)$,归约:L-S,$(L,(a,a)$,移进,$(L,(a,a)$,移进,$(L,(,a,a)$,移进,$(L,(a,a)$,归约:S-a,12/5/2025,24,luanj,3.15(续)(a)(b)续上表,S=,(L),=(,L,S,),=(L,(L),),=(L,(,L,S,),=(L,(L,a,),=(L,(,S,a),=(L,(,a,a)=(,S,(a,a),=(,a,(a,a),栈,输入,动作,$(L,(S,a)$,归约:L-S,$(L,(L,a)$,移进,$(L,(L,a)$,移进,$(L,(L,a,)$,归约:S-a,$(L,(L,S,)$,归约:L-L,S,$(L,(L,)$,移进,$(L,(L),)$,归约:S-(L),$(L,S,)$,归约:L-L,S,12/5/2025,25,luanj,3.15(续)(a)(b)续上表,S=,(L),=(,L,S,),=(L,(L),),=(L,(,L,S,),=(L,(L,a,),=(L,(,S,a),=(L,(,a,a)=(,S,(a,a),=(,a,(a,a),栈,输入,动作,$(L,)$,移进,$(L),$,归约:S-(L),$S,$,接受,12/5/2025,26,luanj,3.15(续)(c),栈,输入,动作,$,(a,(a,a)$,移进,$(,a,(a,a)$,移进,$(a,(a,a)$,归约:S-a,$(S,(a,a)$,归约:L-S,$(L,(a,a)$,移进,$(L,(a,a)$,移进,$(L,(,a,a)$,移进,$(L,(a,a)$,归约:S-a,(a ,(a ,a )$,S,L,S,12/5/2025,27,luanj,3.15(续)(c),栈,输入,动作,$(L,(S,a)$,归约:L-S,$(L,(L,a)$,移进,$(L,(L,a)$,移进,$(L,(L,a,)$,归约:S-a,$(L,(L,S,)$,归约:L-L,S,$(L,(L,)$,移进,$(L,(L),)$,归约:S-(L),$(L,S,)$,归约:L-L,S,(a ,(a ,a )$,S,L,S,L,S,L,S,L,12/5/2025,28,luanj,3.15(续)(c),(a ,(a ,a )$,S,L,S,L,S,L,S,L,栈,输入,动作,$(L,)$,移进,$(L),$,归约:S-(L),$S,$,接受,S,12/5/2025,29,luanj,谢谢！,12/5/2025,30,luanj,