《编译原理总结复习题包括答案.doc》由会员分享，可在线阅读，更多相关《编译原理总结复习题包括答案.doc（17页珍藏版）》请在三一文库上搜索。
1、.二、概念题1、设有文法 ：PP+Q|QQQ*R|RR(P)|i（ 1）证明 Q*R+Q+Q 是它的一个句型 。（ 3 分)（ 2）给出 Q*R+Q+Q 的所有短语 ，直接短语和句柄 。(4 分)（ 3）给出句子 + *的最右推导 。(4 分)（ 4）给出句子 + *的最左推导 。(4 分)2、设有文法 ：EE+T|TTT*F|FF(E)|i（1）证明 E+T*F 是它的一个句型 。（ 3 分 )答案： EETET * F（2）给出 E+T*F 的所有短语 ，直接短语和句柄 。(4 分)短语 :E+T*F, T*F,直接短语 : T*F句柄 : T*F（3）给出句子 + *的最右推导 。(4
2、分)3、写出表达式 a+b*(c-d) 对应的逆波兰式和三元式序列。答案：逆波兰式 ：(abcd-*+).专业 word 可编辑.三元式序列 :OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)三、词法分析题给出下面语言的相应文法nnmmL1=a b a b |n,m0答案： S AB|A|B|A aAb|abB aBb|ab给出下面语言的相应文法L2=a nb nci |n1,i0答案： S AB|BA a|aAB bBc|bc给出下面语言的相应文法L3= anbncm| m,n 1n，为奇数，m 为偶数 。答案：文法 G(S):SACAaaAbb/abCccCcc/cc四、词
3、法分析题.专业 word 可编辑.1、构造下面正规式相应的DFA(0|1)* |(11)*)*（要求：先将正规式转化为NFA，再将 NFA 确定化，最小化）2、构造下面正规式相应的DFA1(0|1)* 101答案：II0I1XA,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,yB,C,E B,C,D3、构造一个 DFA，它接受=a ，b上所有包含 ab 的字符串 。（要求：先将正规式转化为NFA，再将 NFA 确定化，最小化）答案：(一)相应的正规式为 (a|b)*ab(a|b)*(二)与此正规式对
4、应的NFA 为状态转换矩阵为 ：.专业 word 可编辑. 最小化：0， 1，23，4，50， 2，1， 3，4，5baaab013b所以此等价的 DFA 为：开始状态为 0 ，终态集为 3 ，状态集为 0,1,3 ，输入字母表是 a,b 状态转换图如上 。4、构造与正规式b(a|b)*ba等价的 DFA五、语法分析题1、对下面的文法 G:Expr- ExprExpr(Expr)|Var ExprTailExprTail- Expr| Varid VarTailVarTail(Expr) |.专业 word 可编辑.（ 1）构造 LL(1)分析表 。（ 12 分）答案：（ 1 ） FIRST(
5、Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(Var)=id FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) （2）给出对句子 id id(id) 的分析过程 。（ 8 分）步骤符号栈输入串所用产生式0 Exprid_ _id(id) 1# ExprTail Varid_ _id(id) Expr Var ExprTail2# ExprTail VarTail id id_ _i
6、d(id) Varid VarTail3# ExprTail VarTail_ _id(id) 4# ExprTail_ _id(id) VarTail5# Expr_ _id(id) ExprTail_ Expr6# Expr_id(id) 7# Expr_id(id) Expr_Expr8# Exprid(id) .专业 word 可编辑.9# ExprTail Varid(id) ExprVar ExprTail10# ExprTail VarTail id id(id)Varid VarTail11# ExprTail VarTail(id) 12# ExprTail )Expr(id
7、)VarTail(Expr)13# ExprTail )Expr(id) 14# ExprTail ) )Expr(id) Expr(Expr)15# ExprTail ) )Exprid) 16# ExprTail ) )ExprTail Varid)ExpVarExprTail17# ExprTail ) )ExprTail VarTail idid) Varid VarTail18# ExprTail ) )ExprTail VarTail)19# ExprTail ) )ExprTail)VarTail20# ExprTail ) )ExprTail21# ExprTail )22#
8、ExprTail#ExprTail23#分析成功2、对下面的文法 G:ETE.专业 word 可编辑.E+E|TFTTT|FPFF*F|P(E)|a|b|（1）计算这个文法的每个非终结符的FIRST和 FOLLOW。（ 8 分）答案：FIRST(E)=(,a,b,FIRST(E)=+,FIRST(T)=(,a,b,FIRST(T)=(,a,b, FIRST(F)=(,a,b,FIRST(F)=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F
9、)=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#.专业 word 可编辑.（2）证明这个文法是 LL(1)的。（ 6 分）答案：考虑下列产生式 :EE|TT|F* F |P(E )| a|bFIRST(+E)FIRST()=+ = FIRST(+E)FOLLOW(E)=+ #,)= FIRST(T)FIRST()=(,a,b, = FIRST(T)FOLLOW(T)=(,a,b, +,),#= FIRST(*F)FIRST()=* = FIRST(*F)FOLLOW(F)=* (,a,b,+,),#= FIRST(E)FIRST(a) FIRST(b) FIRST()=
10、 所以 ,该文法式 LL(1)文法 .（3）构造它的预测分析表 。（ 6 分）3、已知文法 GS 为：S-a|(T)T-T,S|S.专业 word 可编辑.消除文法 GS中的左递归 ，得文法 GS。 文法 GS是否为 LL(1)的？若是，给出它的预测分析表 。4、对下面的文法 G:SSa T |a T|a TTa T|a(1) 消除该文法的左递归和提取左公因子 ；(2) 构造各非终结符的 FIRST和 FOLLOW 集合；(3) 构造该文法的 LL(1)分析表，并判断该文法是否是 LL(1)的。答案：5、文法 G(S)及其 LR 分析表如下 ，请给出串 baba# 的分析过程 。.专业 wor
11、d 可编辑.(1) S DbB (2) D d (3) D(4) B a (5) B Bba (6) BLR 分析表ACTIONGOTObDa#SBD0r3s3121acc2 s43 r24r6S5r665r4r46s7r17S88r5r5答案：步骤状态符号输入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678 #DbBba#70246#DbB#801#S#acc.专业 word 可编辑.六、语法分析题考虑文法 :SAS|bASA|a（ 1）列出这个文法的所有 LR(0) 项目 。（5 分）答案0
12、. SS1. SS2. SAS 3. SA S4. SAS5. Sb6. Sb7. ASA8. A S A 9. A SA 10. A a11. A a（ 2）给出识别文法所有活前缀的 DFA。（ 5 分）（ 3）求所有非终结符的 FOLLOW 集。（ 5 分）（ 4）文法是 SLR文法吗？若是，构造出它的 SLR分析表 ,否则说明理由。（ 5 分）不是 SLR文法状态 3，6，7 有移进归约冲突状态 3： FOLLOW(S )=#不包含 a,b状态 6：FOLLOW(S)=#,a,b 包含 a,b,；移进归约冲突无法消解状态 7：FOLLOW(A)=a,b 包含 a,b；移进归约冲突消解所以
13、不是 SLR文法 。七、证明题.专业 word 可编辑.1、证明下面文法是LL(1)的但不是 SLR(1)的。SAaAb|BbBaAB首先该文法无左递归存在,没有公共左因子。其次 :对于 S AaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=bFIRST(AaAb) FIRST(BbBa)=所以该文法是LL(1)文法 。(2)证明该文法不是SLR 的 。文法的 LR(0)项目集规范族为:I0=S .S S .AaAb S .BbBa A . B .I1= S S. I2= S A.aAb I3= S B.bBa I4= S Aa.Ab A . I5= S Bb.Ba B
14、. I6= S AaA.b I7= S BbB.a I8= S AaAb. I9= S BbBa. 考察 I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A) FOLLOW(B)= a,b.专业 word 可编辑.产生规约 - 规约冲突 。所以该文法不是SLR(1)文法 。2、证明下面文法是SLR(1)但不是 LR(0)的。SAAAb|bBaBaAc|a|aAb解：文法 GS ：0：SA1： A Ab2： A bBa3： BaAc4： Ba5： B aAb构造 LR(0) 项目集规范族 ：状态项目集转换函数0SAGO0 ，A 1A AbGO0 ，A 1AbBaGO0
15、 ，b 21S AACCEPT.专业 word 可编辑.A AbGO1 ，b 32A b BaGO2 ，B 4BaAcGO2 ，a 5BaGO2 ，a 5BaAbGO2 ，a 53A Ab R14A bB aGO4 ，a 65B aAcGO5 ，A 7B a R4B aAbGO5 ，A 7A AbGO5 ，A 7AbBaGO5 ，b 26A bBa R27B aA cGO7 ，c8B aA bGO7 ，b 9A AbGO7 ，b 98B aAc R39B aAb R5A Ab R1状态 5 存在 “归约移进 ”冲突 ，状态 9 存在 “归约归约 ”冲突 ，因此该文法不是 LR(0) 文法 。状
16、态 5：.专业 word 可编辑.FOLLOW(B) a，因此，FOLLOW(B) b 状态 9：FOLLOW(B) a， FOLLOW(A) # ，b，c，因此FOLLOW(B) FOLLOW(A) 状态 5 和状态 9 的冲突均可用SLR(1)方法解决 ，构造 SLR(1) 分析表如下：状态ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该 SLR(1) 分析表无重定义 ，因此该文法是 SLR(1)文法，不是 LR(0)文法。八、语义分析题.专业 word 可编辑.1、将语句if(A0)the
17、nwhile(C0)doC:=C-D翻译成四元式答案：100 (j ， B， 0， 104)103(j ， -， -， 109)104(j ， C， 0， 106)105(j ， -， -， 109)106(- ， C， D， T1)107(:= ， T1， - ， C)108(j ， -， -， 104)1092、写出下面语句经语法制导翻译后所生成的四元式代码序列。if xc do c:=c+1 else x:=x+5答案：假设初始为 100，则四元式代码序列为100ifxcgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N.专业 word 可编辑.109.专业 word 可编辑.