编译原理陈意云课后答案.ppt

编译原理习题课(2)栾俊[e-mail]4/21/20202020/4/[e-mail]23.1•考虑文法S-(L)|aL-L,S|S(a)建立句子(a,(a,a))和(a,((a,a),(a,a)))的分析树(b)为(a)的两个句子构造最左推导(c)为(a)的两个句子构造最右推导(d)这个文法产生的语言是什么2020/4/[e-mail]33.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))2020/4/[e-mail]43.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)))2020/4/[e-mail]53.1(续)•描述的语言：括号匹配的串，串中的各项由”,”隔开，项可以是括号匹配的子串或a2020/4/[e-mail]63.2•考虑文法S-aSbS|bSaS|ε(a)为句子abab构造两个不同的最左推导，以说明此文法二义(b)为abab构造对应的最右推导(c)为abab构造对应的分析树(d)这个文法产生的语言是什么2020/4/[e-mail]73.2(续)•(1)S=aSbS=abS=abaSbS=ababS=abab(2)S=aSbS=abSaSbS=abaSbS=ababS=abab•S=aSbS=aSb=abSaSb=abSab=abab(2)SaSbSεaSbSεεSaSbSbSaSεεε(1)(2)描述的语言是a,b数目相等的串2020/4/[e-mail]83.4•文法R-R’|’R|RR|R*|(R)|a|b产生字母表(a,b)上所有不含ε的正规式该文法是二义的(a)证明该文法产生字母表{a,b}上的所有正规式(b)为该文法写一个等价的非二义文法。(c)按照上面的两个文法构造ab|b*a的分析树2020/4/[e-mail]93.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/[e-mail]103.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*2020/4/[e-mail]113.4(续)-ab|b*a•二义的非二义的RR|RRRabRRaR*bRRRaR*R|RbRRba…EE|TTFTTFFabFF*ba2020/4/[e-mail]123.5•下面的条件语句文法stmt-ifexprthenstmt|matched_stmtmatched_stmt-ifexprthenmatched_stmtelsestmt|other试图消除悬空else的二义性。请证明此文法仍是二义的。2020/4/[e-mail]133.5(续)•由于matched_stmt不能保证then和else的配对，因而存在二义性•句型ifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmt存在两个不同的最左推导期望的是：ifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmt2020/4/[e-mail]143.5(续)•一种推导，和期望的不一样stmt=matched_stmt=ifexprthenmatched_stmtelsestmt=ifexprthenifexprthenmatched_stmtelsestmtelsestmt=ifexprthenifexprthenmatched_stmtelseifexprthenstmtelsestmt=ifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmtifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmt2020/4/[e-mail]153.5(续)•另一种推导stmt=ifexprthenstmt=ifexprthenmatched_stmt=ifexprthenifexprthenmatched_stmtelsestmt=ifexprthenifexprthenmatched_stmtelsematched_stmt=ifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmtifexprthenifexprthenmatched_stmtelseifexprthenmatched_stmtelsestmt2020/4/[e-mail]163.8(a)•消除3.1的左递归2020/4/[e-mail]173.8(a)(续)•S-(L)|aL-L,S|S•只有直接左递归S-(L)|aL-SL’L’-,SL’|ε2020/4/[e-mail]183.10•构造下面文法的LL(1)分析表D-TLT-int|realL-idRR-,idR|ε2020/4/[e-mail]193.10(续)•先计算FIRST和FOLLOWFIRST(D)=FIRST(T)={int,real}FIRST(L)={id}FIRST(R)={,,ε}FOLLOW(D)=FOLLOW(L)={$}FOLLOW(T)={id}FOLLOW(R)={$}2020/4/[e-mail]203.10(续)intrealid,$DD-TLD-TLTT-intT-realLL-idRRR-,idRR-ε2020/4/[e-mail]213.11•下面文法是否LL(1)文法？说明理由S-AB|PQxA-xyB-bcP-dP|εQ-aQ|ε2020/4/[e-mail]223.11(续)•不是LL(1)文法•LL(1)文法：对于产生式A-α|β*(1)()()(2)()()FIRSTFIRSTFIRSTFOLLOW若，那么•本题中，FIRST(AB)={x},FIRST(PQx)={d,a,x}不满足条件(1)2020/4/[e-mail]233.15•(a)用3.1的文法构造(a,(a,a))的最右推导，说出每个右句型的句柄•(b)给出对应(a)的最右推导的移进-归约分析器的步骤•(c)对照(b)的移进-归约，给出自下而上构造分析树的步骤。2020/4/[e-mail]243.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-a2020/4/[e-mail]253.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,S2020/4/[e-mail]263.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$接受2020/4/[e-mail]273.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))$SLS2020/4/21lua