编译原理复习习题--有答案版

1、1、 给出下面语言的相应文法 。 L1=anbnci|n1,i0答案： S AB|B A a|aA B bBc|bc 2给出下面语言的相应文法L1=anbncmdm| m,n1，n为奇数，m为偶数。答案：文法G(S):SAC AaaAbb/ab CccCcc/cc3、构造一个DFA，它接受S=a，b上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）(一) 相应的正规式为(a|b)*ab(a|b)*(二) 与此正规式对应的NFA为答案；在自己写的纸上4、对下面的文法G:ETE E+E| TFT TT|FPF F *F| P(E)|a|b|（1） 证明这个文法是LL

2、(1)的。考虑下列产生式:E ->E|T ->T|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()= 所以,该文法式LL(1)文法.计算这个文法的每个非终结符的F

3、IRST和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')=(,a,b,+,),# FOLLOW(P)=*,(,a,b,+,),# （3）构造它的预测分析表。（6分）答案；

4、在手机上写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 给出下面语言的相应文法L1=anbnambm|n,m0给出下面语言的相应文法答案： SAB|A|B| A aAb|ab B aBb|abL2=anbnci|n1,i0给出下面语言的相应文法答案： S AB|B A a|aA B bBc|bc 17、对下面的文法G:S ® S Ú a T | a T | Ú a TT ® Ù a T | &#

5、217; a(1) 消除该文法的左递归和提取左公因子；(2) 构造各非终结符的FIRST和FOLLOW集合；(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。18、文法G(S)及其LR分析表如下，请给出串baba#的分析过程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案： 步骤 状态 符号 输入串 0 0 # baba# 1 02 #D baba# 2 024 #Db aba# 3 0245 #Db

6、a ba# 4 0246 #DbB ba# 5 02467 #DbBb a# 6 024678 #DbBba # 7 0246 #DbB # 8 01 #S # acc 七、证明题1、证明下面文法是LL(1)的但不是SLR(1)的。SAaAb|BbBaAB首先该文法无左递归存在,没有公共左因子。 其次:对于SAaAb|BbBa FIRST(AaAb)=a FIRST(BbBa)=b FIRST(AaAb)FIRST(BbBa)= 所以该文法是LL(1)文法。(2)证明该文法不是SLR的。 文法的LR(0)项目集规范族为: I0=S.S S.AaAb S.BbBa A. B. I1= S S.

7、I2= S I3= S I4= S A. I5= S B. I6= S I7= S I8= SAaAb. I9= SBbBa. 考察I0: FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A)FOLLOW(B)= a,b 产生规约-规约冲突。 所以该文法不是SLR(1)文法。2、证明下面文法是SLR(1)但不是LR(0)的。SAAAb|bBaBaAc|a|aAb解：文法GS： 0：SA 1：AAb 2：AbBa 3：BaAc 4：Ba 5：BaAb状态5存在“归约移进”冲突，状态9存在“归约归约”冲突，因此该文法不是LR(0)文法。 状态5： FOLLOW(B)a，因此，

8、FOLLOW(B)b 状态9： FOLLOW(B)a，FOLLOW(A)#，b，c，因此FOLLOW(B)FOLLOW(A) 状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。八、语义分析题1、将语句if (A<0) Ú (B>0) then while (C>0) do C:=C-D翻译成四元式答案：100 (j<， A， 0， 104)101 (j， -， -， 102)102 (j>， B， 0， 104)103 (j， -， -， 109)104

9、(j>， C， 0， 106)105 (j， -， -， 109)106 (-， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)1092、写出下面语句经语法制导翻译后所生成的四元式代码序列。 if x<y then while e>c do c:=c+1 else x:=x+5答案：假设初始为100，则四元式代码序列为 100ifx<ygoto102101goto107102ife>cgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1097、设有文法：

10、EE+T|TTT*F|FF(E)|i（1） 证明E+T*F是它的一个句型。（3分)： +Þ+*（2） 给出E+T*F的所有短语，直接短语和句柄。(4分)短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F（3） 给出句子+*的最右推导。(4分)没有 答案10、11、构造下面正规式相应的DFA1(0|1)*101答案： I I0 I1 X A,B,C A,B,C B,C B,C,D B,C B,C B,C,D B,C,D B,C,E B,C,D B,C,E B,C B,C,D,y B,C,D,y B,C,E B,C,D14、对下面的文法G:Expr- ExprExpr(E

11、xpr)|Var ExprTailExprTail- Expr|Varid VarTail VarTail(Expr) |（1）构造LL(1)分析表。（12分）（2）给出对句子idid(id)的分析过程。（8分）答案： （1）FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(Var)=id FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) （2） 给出对句子idid(id)

12、的分析过程。（步骤 符号栈 输入串 所用产生式 0 Expr id_ _id(id) 1 # ExprTail Var id_ _id(id) ExprVar ExprTail 2 # ExprTail VarTail id id_ _id(id) Varid VarTail 3 # ExprTail VarTail _ _id(id) 4 # ExprTail _ _id(id) VarTail5 # Expr_ _ _id(id) ExprTail_ Expr 6 # Expr _id(id) 7 # Expr_ _id(id) Expr_Expr 8 # Expr id(id)9 # ExprTail Var id(id) ExprVar ExprTail 10 # ExprTail VarTail id id(id) Varid VarTail 11 # ExprTail VarTail (id) 12 # ExprTail )Expr( (id) VarTail(Expr) 13 # ExprTail )Expr (id) 14 # ExprTail ) )Expr( (id) Expr(Expr) 15 # ExprTail ) )Expr id) 16 # ExprTail ) ) ExprTail Var id) ExpVarExprTai 17 # ExprTa