编译原理复习题答案

1、二、概念题1、设有文法：P-P+QIQQ Q*R|RR-(P)|i(1) 证明Q*R+Q+Q 是它的一个句型。(3分)(2) 给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)(3) 给出句子i + i * i的最右推导。(4分)(4) 给出句子i + i * i的最左推导。(4分)2、 设有文法： E+T|TT-T*F|FF-(E)|i(1) 证明E+T*F是它的一个句型。(3分)答案：E E T E T*F(2) 给出E+T*F的所有短语，直接短语和句柄。(4分)短语：E+T*F, T*F,直接短语：T*F句柄:T*F(3) 给出句子i + i * i的最右推导。(4分)3、写出表达式

2、a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+)三元式序列：OPARG1ARG2(1)-cd*b(1)+a(2)三、词法分析题给出下面语言的相应文法L1=anbnambm|n,m >0答案：S-AB|A|B|刀A aAb|abB aBb|ab给出下面语言的相应文法L2=anbnci|n >1,i»答案：S AB|BA a|aAB bBc|bc给出下面语言的相应文法L3=anbncm| m,n> n,为奇数，m 为偶数答案：文法G(S):SACAaaAbb/abC ccCcc/cc四、词法分析题专业word可编辑1、构造下面正规式相应的

3、DFA(011)*1(11)*)*(要求：先将正规式转化为NFA,再将NFA确定化，最小化)2、构造下面正规式相应的 DFA1(0|1)*101答案：II011XA,B,CA,B,C B,C B,C,DB,C B,C B,C,DB,C,D B,C,E B,C,DB,C,E B,C B,C,D,yB,C,D,y B,C,E B,C,D3、构造一个DFA,它接受二a , b上所有包含ab的字符串。(要求：先将正规式转化为NFA,再将NFA确定化，最小化)答案：(一)相应的正规式为(a|b)*ab(a|b)*(二) M此正规式对应的NFA为状态转换矩阵为:IJO.1,2)11,2.3(lr21<

4、;1,2,3乙丸6占(1,211.2.3JU,乙6罰|l2r3f5f>U,2.51(1,2,3,5,61<lr2,5,6>最小化:0,1, 23, 4, 50,2, 1 ,3, 4, 5所以此等价的DFA为：开始状态为0 ,终态集为3,状态集为0,1,3, 输入字母表是a,b状态转换图如上。4、构造与正规式 b(a|b)*ba 等价的DFA五、语法分析题1、对下面的文法G:Expr * ExprExpr i(Expr)|Var ExprTailExprTaif Expr| eVarid VarTailVarTaiR(Expr) | e(1)构造LL(1)分析表(12 分)答案

5、:(1 ) FIRST(Expr)二匕,(,id FIRST(ExprTail)=_ ,& FIRST(Var)二idFIRST(VarTiil)= ( ,0FOLLOW(Expr)二# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) 步骤符号栈输入串所用产生式id()EzcrEiiCirVarEizpxTai 1EmrfEsprTailExprTail-. EjrEqprTiil-*EzprT'ailVarVar予idVarTailVarTailVarai 1£

6、;Vai'Tai 1 VrTailt(2)给出对句子id id(id)的分析过程。(8分)# Expr# ExprTail Varid_ _id(id) #idid(id) # Expr f Var ExprTail# ExprTail VarTail id id_d(id) # Varf id VarTail# ExprTail VarTail_ _id(id)# ExprTail_ _id(id) #VarTaif£# Expr_ _id(id) #ExprTailf _ Expr# Expr# Expr_id(id) #Expr f _Expr_id(id) # Exp

7、rid(id) #ExpVar ExprTail# ExprTail VarTail id id(id) #VarTid VarTail# ExprTail VarTail(id) # ExprTail )Expr(id) #VarTaiT(Expr)# ExprTail )Expr(id) # ExprTail ) )Expr(id) #ExprT (Expr)# ExprTail ) )Exprid) # ExprTail )ExprTail Varid) #ExprTail# ExprTail )# ExprTail Varid(id) #ExprTail VarTail id id)

8、# ExprTail )ExprTail VarTail )# ExprTail )ExprTail )# ExprTail ) )# ExprTail )# ExprTailExp t VarVarT id VarTailVarTaiT£ExprTailg#ExprTail#分析成功F面的文法G:910111213141516171819202122232、对E'E| £T FT'T'丹F PF'F' *F'| &P(E)|a|b|A(1) 计算这个文法的每个非终结符的 FIRST和 FOLLOW°( 8分

9、)答案：FIRST(E)=(,a,b,AFIRST(E')二+, jFIRST(T)二(,a,b"FIRST(T')=(,a,b,A, jFIRST(F)=(,a,b,AFIRST(F')二*, jFIRST(P)=(,a,b,AFOLLOW(E)二#,)FOLLOW(E')二#,)FOLLOW(T)二+,),#FOLLOW(T')二+,),#FOLLOW(F)二(,a,b,"+,),#FOLLOW(F')二(,a,b,"+,),#FOLLOW(P)=*,(,a,b,A,+,),#(2) 证明这个文法是LL(1)的。

10、(6分)答案：考虑下列产生式：E E|T T|F *F |P (E)F|a|bFIRST(+E)Q FIRST(沪+ A 护 ©FIRST(+E)Q FOLLOW(E')二+ A#,)= ©FIRST(T)A FIRST(沪(,a,bf A 护 ©FIRST(T)A FOLLOW(T')=(,a,b,A A +,),#= ©FIRST(*F')A FIRST(沪* A = ©FIRST(*F')A FOLLOW(F')二* A (,a,b,A,+,),#= © FIRST(E)AFIRST(a)

11、 AFIRST(b) AFIRST(A)= © 所以该文法式LL(1)文法.(3) 构造它的预测分析表。(6分)2a期班pE fTE'农EtTZ*£ ->7ZrEJ+E*E' f耳*Ef THTVT fFTTrFT丁 FT*T'ppa卩T八F T*p &F*apF FFpF PFFf呼FPFf口Fr T &FfF T貝FTF* TFf ->Fr+pF f 2FfbaPS3、已知文法GS为:S->a|(T)T->T,S|S 消除文法GS中的左递归，得文法G'S。 文法GfS是否为LL(1)的？若是，给出它

12、的预测分析表4、对下面的文法G:S S a T | a T | a TT a T | a(1) 消除该文法的左递归和提取左公因子；构造各非终结符的FIRST和FOLLOW集合； 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的答案: 构适该文注的LL(1)分析表答：(1)(消除左递归2分)St aTS, aTS*SJ yaTS | sT t Ft AdT I a a井判斷该文注是奁是LL的。(提魅左公因子2分)Ft aTS1 | v a TSf S J aTSt | £Tt auF厂 t T I £(4分) FIRST(S)af v； FTRATF尸卜£

13、; FIRST(T) FIRSTS)=a * £ FOLLOW(S)= FOLLOWfS*)FOLLOW(T)f 祁 FOLLOW(T)=,时5、文法G(S)及其LR分析表如下，请给出串baba#的分析过程(1)s J DbB(2)D J d(3)D J e(4)B J a(5)B J Bba (6) B J eLR®»00765432oa£a>£&bACTIONs3Ds00s5aaa>a c c4kS6B2D00765432koosososs4sofl： sfl:D bfl: Dfl:苹ujnfl:fl:fl:a fl：留

14、 fl:fl:a b a fl：>>4W word£!>>acc专业word可编辑六、语法分析题考虑文法：SAS|bASA|a（1）列出这个文法的所有LR（0）项目。（5分）答案0.SS1.SS2.SAS 3. S A S4.SAS5.Sb6.Sb7. A SA8. AS A9.ASA10.A a11. A a（2）给出识别文法所有活前缀的 DFA°（ 5分）（3）求所有非终结符的FOLLOW集。（5分）（4）文法是SLR文法吗？若是，构造出它的SLR分析表，否则说明理 由。（5分） 不是SLR文法状态3, 6，7有移进归约冲突状态3：FOLLOW(

15、S ')=不包含 a,b状态6：FOLLOW（S）=#,a,b包含a,b,；移进归约冲突无法消解状态7：FOLLOW（A）=a,b包含a,b ；移进归约冲突消解所以不是SLR文法七、证明题1、证明下面文法是LL(1)的但不是SLR(1)的。St AaAb|BbBaASBt£首先该文法无左递归存在，没有公共左因子。其次对于 St AaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=bFIRST(AaAb) n FIRST(BbBa)= 所以该文法是LL(1)文法。(2)证明该文法不是 SLR的。文法的LR(0)项目集规范族为：I0=S' t .s S

16、 t .AaAb S t .BbBa A t . b t .I1= S't s. I2= StA.aAb I3= StB.bBa I4= StAa.Ab At. I5= StBb.Ba Bt. I6= StAaA.b I7= StBbB.a I8= StAaAb. I9= StBbBa. 考察I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A)n FOLLOW(B)= a,b.专业word可编辑产生规约-规约冲突。所以该文法不是SLR(1)文法。2、证明下面文法是SLR(1但不是LR(0)的S AAAb|bBaB aAc|a|aAb解:文法GS:0:SA1

17、:A Ab2 :A bBa3:BaAc4:Ba5 :B aAb构造LR(0)项目集规范族：状态项目集转换函数0SAGO0 , A = 1A AbGO0 , A = 1A bBaGO0 , b = 21S A ACCEPTA AbGO1 , b = 32At b BaGO2 , B =4B aAcGO2 , a =5B aGO2 , a =5B aAbGO2 , a =53A Ab R14A bB aGO4 , a =65B aAcGO5 , A = 7B a R4B aAbGO5 , A = 7A AbGO5 , A = 7A bBaGO5 , b = 26A bBa R27B aAcGO7

18、, c = 8B aAbGO7 , b = 9A A bGO7 , b = 98B aAc R39B aAb R5A Ab R1状态5存在 归约-移进”中突，状态9存在 归约-归约”冲突，因此该文法不是LR(O)文法。状态5 :FOLLOW(B) = a,因此，FOLLOW(B) A b =O状态9 :FOLLOW(B) = a, FOLLOW(A) = #, b, c,因此FOLLOW(B) A FOLLOW(A) =O状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表如下：状态ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0) 文法。八、语义分析题1、将语句if (A<0)(B>0) the n while (C>0) do C:=C-D翻译成四元式答案：100 (j<，A，0，104)101 (j， 102)102 (j>，B，0，1