编译原理陈意云课后答案.ppt
编译原理习题课编译原理习题课(2)栾 俊1/4/20231/4/202313.1考虑文法S-(L)|aL-L,S|S(a)建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树(b)为(a)的两个句子构造最左推导(c)为(a)的两个句子构造最右推导(d)这个文法产生的语言是什么1/4/202323.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 ,SSa(L )L ,SSaaS=(L)=(L,S)=(L,(L)=(L,(L,S)=(L,(L,a)=(L,(S,a)=(L,(a,a)=(S,(a,a)=(a,(a,a)1/4/202333.1(续续)-(a,(a,a),(a,a)S(L )L ,SSaS=(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(L )L ,SSaa(L )L ,SSaaSS=(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)1/4/202343.1(续续)描述的语言：括号匹配的串，串中的各项由”,”隔开，项可以是括号匹配的子串或a1/4/202353.2考虑文法S-aSbS|bSaS|(a)为句子abab构造两个不同的最左推导，以说明此文法二义(b)为abab构造对应的最右推导(c)为abab构造对应的分析树(d)这个文法产生的语言是什么1/4/202363.2(续续)(1)S=aSbS=abS=abaSbS=ababS=abab(2)S=aSbS=abSaSbS=abaSbS=ababS=ababS=aSbS=aSb=abSaSb=abSab=abab(2)Sa S b Sa S b SSa S b Sb S a S(1)(2)描述的语言是a,b数目相等的串1/4/202373.4文法R-R|R|RR|R*|(R)|a|b产生字母表(a,b)上所有不含的正规式该文法是二义的(a)证明该文法产生字母表a,b上的所有正规式(b)为该文法写一个等价的非二义文法。(c)按照上面的两个文法构造ab|b*a的分析树1/4/202383.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上的所有正规式1/4/202393.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*1/4/2023103.4(续续)-ab|b*a二义的 非二义的RR|RR RabR RaR *bRR RaR *R|RbR RbaEE|TT FTT FFabFF *ba1/4/2023113.5下面的条件语句文法stmt-if expr then stmt|matched_stmtmatched_stmt-if expr then matched_stmt else stmt|other试图消除悬空else的二义性。请证明此文法仍是二义的。1/4/2023123.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 stmt1/4/2023133.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 expr then matched_stmt else if expr then stmt else stmt=if expr then if expr then matched_stmt else if expr then matched_stmt else stmtif expr then if expr then matched_stmt else if expr then matched_stmt else stmt1/4/2023143.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 stmtif expr then if expr then matched_stmt else if expr then matched_stmt else stmt1/4/2023153.8(a)消除3.1的左递归1/4/2023163.8(a)(续续)S-(L)|aL-L,S|S只有直接左递归S-(L)|aL-SLL-,SL|1/4/2023173.10构造下面文法的LL(1)分析表D-TLT-int|realL-idRR-,idR|1/4/2023183.10(续续)先计算FIRST和FOLLOWFIRST(D)=FIRST(T)=int,realFIRST(L)=id FIRST(R)=,FOLLOW(D)=FOLLOW(L)=$FOLLOW(T)=idFOLLOW(R)=$1/4/2023193.10(续续)intrealid,$DD-TLD-TLTT-intT-realLL-idRRR-,idRR-1/4/2023203.11下面文法是否LL(1)文法？说明理由S-AB|PQxA-xyB-bcP-dP|Q-aQ|1/4/2023213.11(续续)不是LL(1)文法LL(1)文法：对于产生式A-|本题中，FIRST(AB)=x,FIRST(PQx)=d,a,x不满足条件(1)1/4/2023223.15(a)用3.1的文法构造(a,(a,a)的最右推导，说出每个右句型的句柄(b)给出对应(a)的最右推导的移进-归约分析器的步骤(c)对照(b)的移进-归约，给出自下而上构造分析树的步骤。1/4/2023233.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-a1/4/2023243.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,S1/4/2023253.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$接受1/4/2023263.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 )$SLS1/4/2023273.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 )$SLSLSLSL1/4/2023283.15(续续)(c)(a ,(a ,a )$SLSLSLSL栈输入动作$(L)$移进$(L)$归约:S-(L)$S$接受S1/4/202329谢谢！谢谢！1/4/202330
