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)对应的逆波兰式和三元式序列。答案：逆波兰式：
2、(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 三、词法分析题给出下面语言的相应文法L1=anbnambm|n,m0答案：SAB|A|B|AaAb|abBaBb|ab给出下面语言的相应文法L2=anbnci|n1,i0答案：SAB|BAa|aABbBc|bc给出下面语言的相应文法L3=anbncm| m,n1，n为奇数，m为偶数。答案：文法G(S):SAC AaaAbb/ab CccCcc/cc 四、词法分析题1、构造下面正规式相应的DFA(0|1)*|(11)*)*（要求：先将正规式转化为NFA，再将NFA确定化
3、，最小化）2、构造下面正规式相应的DFA1(0|1)*101答案：I I0 I1X A,B,CA,B,C B,CB,C,DB,C B,CB,C,DB,C,DB,C,E B,C,DB,C,EB,CB,C,D,yB,C,D,yB,C,EB,C,D3、构造一个DFA，它接受=a，b上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）答案：(一)相应的正规式为(a|b)*ab(a|b)*(二) 与此正规式对应的NFA为状态转换矩阵为： 最小化：0，1，2 3，4，50， 2，1， 3，4，5所以此等价的DFA为：开始状态为0 ，终态集为3 ，状态集为0,1,3 ，输入字母
4、表是a,b 状态转换图如上。4、构造与正规式 b(a|b)*ba 等价的DFA五、语法分析题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) =_ , # ,
5、) FOLLOW(VarTail) =_ , # , ) （2） 给出对句子idid(id)的分析过程。（8分）步骤 符号栈 输入串 所用产生式0 Expr id_ _id(id) 1 # ExprTail Var id_ _id(id) ExprVar ExprTail2 # ExprTail VarTail id id_ _id(id) Varid VarTail3 # ExprTail VarTail _ _id(id)4 # ExprTail _ _id(id) VarTail5 # Expr_ _ _id(id) ExprTail_ Expr6 # Expr _id(id)7 # E
6、xpr_ _id(id) Expr_Expr8 # Expr id(id)9 # ExprTail Var id(id) ExprVar ExprTail10 # ExprTail VarTail id id(id) Varid VarTail11 # 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 ) ) ExprTai
7、l Var id) ExpVar ExprTail17 # ExprTail ) )ExprTail VarTail id id) Varid VarTail18 # ExprTail ) )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、（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,+,),#（2） 证明这个文法是LL(1)的。（6分）答案：考虑下列产生式:FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E)=+#,)
9、=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)文法.（3） 构造它的预测分析表。（6分）3、已知文法GS 为： S-a|(T)T-T,S|S 消除文法GS中的左递归，得文法GS。文法GS是否为LL(1)的？若是，给出它的预测分析表。4、对下面的文法G:S S a T | a T | a TT a T | a(1) 消除该文法的左递归和提取左公
10、因子；(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答案：步骤 状态 符号 输入串0 0 # baba#1 02 #D baba#2 024 #Db aba#3 0245 #Dba ba#4 0246 #DbB ba#5 0
11、2467 #DbBb a#6 024678 #DbBba #7 0246 #DbB #8 01 #S # acc六、语法分析题考虑文法: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,；移进
12、归约冲突无法消解状态7：FOLLOW(A)=a,b包含a,b；移进归约冲突消解所以不是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= SA.aAb I3= SB.bBa I4= SAa.Ab A. I5= SB
13、b.Ba B. I6= SAaA.b I7= SBbB.a 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：SA1：AAb2：AbBa3：BaAc4：Ba5：BaAb构造LR(0)项目集规范族：状态项目集转换函数0SAAAbAbBaGO0，A1GO0，A1GO0，b21SAAAbACCEPTGO1，b32AbBaBaAcBaBaAb
14、GO2，B4GO2，a5GO2，a5GO2，a53AAbR14AbBaGO4，a65BaAcBaBaAbAAbAbBaGO5，A7R4GO5，A7GO5，A7GO5，b26AbBaR27BaAcBaAbAAbGO7，c8GO7，b9GO7，b98BaAcR39BaAbAAbR5R1状态5存在“归约移进”冲突，状态9存在“归约归约”冲突，因此该文法不是LR(0)文法。状态5：FOLLOW(B)a，因此，FOLLOW(B)b状态9：FOLLOW(B)a，FOLLOW(A)#，b，c，因此FOLLOW(B)FOLLOW(A)状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表如下：
15、状态ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该SLR(1)分析表无重定义，因此该文法是SLR(1)文法，不是LR(0)文法。八、语义分析题1、将语句if (A0) then while (C0) do C:=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:=N109
