编译原理复习习题答案

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|T TT*F|F F(E)|i（1）证明E+T*F是它的一个句型。（3分)答案：（2）给出E+T*F的所有短语，直接短语和句柄。(4分)短语: E+T*F, T*F,直接短语: T*F句柄: T*F（3）给出句子+*的最右推导。(4分)3、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+)

2、三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 三、词法分析题给出下面语言的相应文法L1=anbnambm|n,m0答案：  SAB|A|B| A aAb|ab B aBb|ab给出下面语言的相应文法L2=anbnci|n1,i0答案： S AB|B    A a|aA B bBc|bc给出下面语言的相应文法L3=anbncm| m,n1，n为奇数，m为偶数。答案：文法G(S):SAC

3、AaaAbb/ab CccCcc/cc 四、词法分析题1、构造下面正规式相应的DFA(0|1)*|(11)*)*（要求：先将正规式转化为NFA，再将NFA确定化，最小化）2、构造下面正规式相应的DFA1(0|1)*101答案：I        I0        I1 X         A,B,C  A,B,C    

4、0;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

5、,C,D,y   B,C,E      B,C,D3、构造一个DFA，它接受S=a，b上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）答案：(一)相应的正规式为(a|b)*ab(a|b)*(二) 与此正规式对应的NFA为状态转换矩阵为： 最小化：0，1，2 3，4，50， 2，1， 3，4，5baa01b3ba所以此等价的DFA为：开始状态为0 ，终态集为3 ，状态集为0,1,3 ，输入字母表是a,b 状态转换图如上。4、构造与正规式 b(a|b)*ba 等价的DFA五、

6、语法分析题1、对下面的文法G:Expr- ExprExpr(Expr)|Var ExprTailExprTail- Expr|Varid VarTail VarTail(Expr) |（1） 构造LL(1)分析表。（12分）答案：（1）FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(Var)=id FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) （2） 给出对句子idi

7、d(id)的分析过程。（8分）步骤 符号栈 输入串所用产生式0Expr id_ _id(id)1# ExprTail Var id_ _id(id)ExprVar ExprTail2# ExprTail VarTail idid_ _id(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)9# ExprTail Varid(id)ExprVar

8、 ExprTail10# ExprTail VarTail idid(id)Varid VarTail11# ExprTail VarTail(id) 12# ExprTail )Expr(id)VarTail(Expr)13# ExprTail )Expr(id)14# ExprTail ) )Expr(id)Expr(Expr)15# ExprTail ) )Exprid)16 # ExprTail ) )ExprTail Varid)ExpVar ExprTail17# ExprTail ) )ExprTail VarTail idid)Varid VarTail18# ExprTail

9、 ) )ExprTail VarTail )19# ExprTail ) )ExprTail)VarTail20# ExprTail ) )ExprTail21# ExprTail )22# ExprTail #ExprTail23# #分析成功2、对下面的文法G:ETEE+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')=*,FI

10、RST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E')=#,)FOLLOW(T)=+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F')=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#（2） 证明这个文法是LL(1)的。（6分）答案：考虑下列产生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E')=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T')=(,a,b,+,),#=FIRST(*F'

11、;)FIRST()=*=FIRST(*F')FOLLOW(F')=*(,a,b,+,),#=FIRST(E)FIRST(a) FIRST(b) FIRST()=所以,该文法式LL(1)文法.（3） 构造它的预测分析表。（6分）3、已知文法GS 为： S->a|(T)T->T,S|S 消除文法GS中的左递归，得文法G´S。 文法G´S是否为LL(1)的若是，给出它的预测分析表。4、对下面的文法G:S ® S Ú a T | a T | Ú a TT ® Ù a T | Ù a(1) 消除该

12、文法的左递归和提取左公因子；(2) 构造各非终结符的FIRST和FOLLOW集合；(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。答案：5、文法G(S)及其LR分析表如下，请给出串baba#的分析过程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案：步骤状态符号输入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6

13、024678#DbBba#70246#DbB#801#S#acc16六、语法分析题考虑文法:SAS|b ASA|a（1） 列出这个文法的所有LR(0) 项目。（5分）答案0.1.2.3.4.5.6.7.8.9.10.11.（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；移进归约

14、冲突消解所以不是SLR文法。七、证明题1、证明下面文法是LL(1)的但不是SLR(1)的。SAaAb|BbBaAB首先该文法无左递归存在,没有公共左因子。其次:对于SAaAb|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 I3= S I4= S A. I5= S B. I6= S I7= S I8= SAaAb. I9= SBbBa. 考察I0:FOLLOW(A

15、)=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：SA1：AAb2：AbBa3：BaAc4：Ba5：BaAb构造LR(0)项目集规范族：状态项目集转换函数0S·AA·AbA·bBaGO0，A1GO0，A1GO0，b21SA·AA·bACCEPTGO1，b32Ab·BaB·aAcB·aB·aAbGO2，B4GO2，a

16、5GO2，a5GO2，a53AAb·R14AbB·aGO4，a65Ba·AcBa·Ba·AbA·AbA·bBaGO5，A7R4GO5，A7GO5，A7GO5，b26AbBa·R27BaA·cBaA·bAA·bGO7，c8GO7，b9GO7，b98BaAc·R39BaAb·AAb·R5R1状态5存在“归约移进”冲突，状态9存在“归约归约”冲突，因此该文法不是LR(0)文法。状态5：FOLLOW(B)a，因此，FOLLOW(B)b状态9：FOLLOW(B)a，

17、FOLLOW(A)#，b，c，因此FOLLOW(B)FOLLOW(A)状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表如下：状态ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该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 (j>， C， 0， 106)105