编译原理陈意云课后答案

编译原理习题课(2),栾俊luanj4/30/2020,2020/4/30,luanj,2,3.1,考虑文法S-(L)|aL-L,S|S(a)建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树(b)为(a)的两个句子构造最左推导(c)为(a)的两个句子构造最右推导(d)这个文法产生的语言是什么,2020/4/30,luanj,3,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)=(L,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a),2020/4/30,luanj,4,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,(a,a),(S,S)=(a,(a,a),(a,S)=(a,(a,a),(a,a),(L),L,S,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),2020/4/30,luanj,5,3.1(续),描述的语言：括号匹配的串，串中的各项由”,”隔开，项可以是括号匹配的子串或a,2020/4/30,luanj,6,3.2,考虑文法S-aSbS|bSaS|(a)为句子abab构造两个不同的最左推导，以说明此文法二义(b)为abab构造对应的最右推导(c)为abab构造对应的分析树(d)这个文法产生的语言是什么,2020/4/30,luanj,7,3.2(续),(1)S=aSbS=abS=abaSbS=ababS=abab(2)S=aSbS=abSaSbS=abaSbS=ababS=ababS=aSbS=aSb=abSaSb=abSab=abab(2),S,aSbS,aSbS,S,aSbS,bSaS,(1),(2),描述的语言是a,b数目相等的串,2020/4/30,luanj,8,3.4,文法R-R|R|RR|R*|(R)|a|b产生字母表(a,b)上所有不含的正规式该文法是二义的(a)证明该文法产生字母表a,b上的所有正规式(b)为该文法写一个等价的非二义文法。(c)按照上面的两个文法构造ab|b*a的分析树,2020/4/30,luanj,9,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上的所有正规式,2020/4/30,luanj,10,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|bE=E|T=E|F=E|F*=E|b*=T|b*=F|b*=a|b*,2020/4/30,luanj,11,3.4(续)-ab|b*a,二义的非二义的,R,R|R,RR,a,b,RR,a,R*,b,R,RR,a,R*,R|R,b,RR,b,a,E,E|T,TF,T,TF,F,a,b,F,F*,b,a,2020/4/30,luanj,12,3.5,下面的条件语句文法stmt-ifexprthenstmt|matched_stmtmatched_stmt-ifexprthenmatched_stmtelsestmt|other试图消除悬空else的二义性。请证明此文法仍是二义的。,2020/4/30,luanj,13,3.5(续),由于matched_stmt不能保证then和else的配对，因而存在二义性句型ifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmt存在两个不同的最左推导期望的是：ifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmt,2020/4/30,luanj,14,3.5(续),一种推导，和期望的不一样stmt=matched_stmt=ifexprthenmatched_stmtelsestmt=ifexprthenifexprthenmatched_stmtelsestmtelsestmt=ifexprthenifexprthenmatched_stmtelseifexprthenstmtelsestmt=ifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmtifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmt,2020/4/30,luanj,15,3.5(续),另一种推导stmt=ifexprthenstmt=ifexprthenmatched_stmt=ifexprthenifexprthenmatched_stmtelsestmt=ifexprthenifexprthenmatched_stmtelsematched_stmt=ifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmtifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmt,2020/4/30,luanj,16,3.8(a),消除3.1的左递归,2020/4/30,luanj,17,3.8(a)(续),S-(L)|aL-L,S|S只有直接左递归S-(L)|aL-SLL-,SL|,2020/4/30,luanj,18,3.10,构造下面文法的LL(1)分析表D-TLT-int|realL-idRR-,idR|,2020/4/30,luanj,19,3.10(续),先计算FIRST和FOLLOWFIRST(D)=FIRST(T)=int,realFIRST(L)=idFIRST(R)=,FOLLOW(D)=FOLLOW(L)=$FOLLOW(T)=idFOLLOW(R)=$,2020/4/30,luanj,20,3.10(续),2020/4/30,luanj,21,3.11,下面文法是否LL(1)文法？说明理由S-AB|PQxA-xyB-bcP-dP|Q-aQ|,2020/4/30,luanj,22,3.11(续),不是LL(1)文法LL(1)文法：对于产生式A-|,本题中，FIRST(AB)=x,FIRST(PQx)=d,a,x不满足条件(1),2020/4/30,luanj,23,3.15,(a)用3.1的文法构造(a,(a,a)的最右推导，说出每个右句型的句柄(b)给出对应(a)的最右推导的移进-归约分析器的步骤(c)对照(b)的移进-归约，给出自下而上构造分析树的步骤。,2020/4/30,luanj,24,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),2020/4/30,luanj,25,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),2020/4/30,luanj,26,3.15(续)(a)(b)续上表,S=(L)=(L,S)=(L,(L)=(L,(L,S)=(