《2022年编译原理复习题答案.docx》由会员分享，可在线阅读，更多相关《2022年编译原理复习题答案.docx（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！二、概念题 1、设有文法： PP+Q|Q QQ*R|R RP|i （1）证明 Q*R+Q+Q是它的一个句型；（3 分 （2）给出 Q*R+Q+Q的全部短语,直接短语和句柄；4 分 （3）给出句子 +* 的最右推导； 4 分 （4）给出句子 +* 的最左推导； 4 分 2、设有文法： EE+T|T TT*F|F FE|i （1）证明 E+T*F是它的一个句型；（3 分 答案 ： E E T E T * F（2）给出 E+T*F的全部短语,直接短语和句柄；4 分 短语 : E+T*F, T*F, 直接短语 : T*F 句柄 :
2、T*F （3）给出句子 +* 的最右推导； 4 分 3、写出表达式 a+b*c-d 对应的逆波兰式和三元式序列；答案：逆波兰式： abcd-*+ 名师归纳总结 - - - - - - -第 1 页,共 16 页精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！三元式序列 : OP ARG1 ARG2 1 - c d 2 * b 1 3 + a 2 三、词法分析题给出下面语言的相应文法L1=anbnamb m|n,m 0 答案： SAB|A|B| AaAb|ab BaBb|ab 给出下面语言的相应文法L2=a nb nc i|n 1,i 0 答案：SAB|B Aa|aA Bb
3、Bc|bc 给出下面语言的相应文法L3= anbncm| m,n 1 ,n 为奇数, m为偶数 ；答案：文法 GS:S AC AaaAbb/ab CccCcc/cc 四、词法分析题名师归纳总结 - - - - - - -第 2 页,共 16 页精选学习资料 - - - - - - - - - 1、构造下面正规式相应的DFA 优秀资料欢迎下载！0|1*|11*（要求：先将正规式转化为NFA,再将 NFA确定化,最小化）2、构造下面正规式相应的 DFA 10|1 *101 答案：I I0 I1 X A,B,C B,C A,B,C B,C,D B,C B,C B,C,D B,C,D B,C,E B,
4、C,D B,C,E B,C B,C,D,y B,C,D,y B,C,E B,C,D 3、构造一个 DFA,它接受（要求：先将正规式转化为=a,b 上全部包含 ab 的字符串；NFA,再将 NFA确定化,最小化）答案： 一 相应的正规式为 a|b*aba|b* 二 与此正规式对应的 NFA为状态转换矩阵为：名师归纳总结 - - - - - - -第 3 页,共 16 页精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！ 最小化：0 ,1,2 3,4,5 0 , 2 ,1, 3 ,4,5 ba1aba03b所以此等价的 DFA为：开头状态为 0 ,终态集为 3 ,状态集为 0,
5、1,3 ,输入字母表是 a,b 状态转换图如上；4、构造与正规式 ba|b*ba 等价的 DFA 五、语法分析题1、对下面的文法 G: Expr- Expr ExprExpr|Var ExprTail ExprTail - Expr| Varid VarTail 名师归纳总结 VarTail Expr |第 4 页,共 16 页- - - - - - -精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！（1）构造 LL1 分析表；（12 分）答案：（1）FIRSTExpr=_ , , id FIRSTExprTail=_ FIRSTVarTail= , , FIRSTVar
6、=id FOLLOWExpr=# , FOLLOWExprTail =# , FOLLOWVar =_ , # , FOLLOWVarTail =_ , # , （2）给出对句子 id idid的分析过程；（8 分）名师归纳总结 步骤符号栈输入串所用产生式第 5 页,共 16 页0 Expr id_ _idid1 # ExprTail Var id_ _ididExprVar ExprTail 2 # ExprTail VarTail id id_ _ididVarid VarTail 3 # ExprTail VarTail _ _idid4 # ExprTail _ _ididVarTai
7、l 5 # Expr_ _ _idid ExprTail_ Expr 6 # Expr _idid7 # Expr_ _ididExpr_Expr 8 # Expr idid- - - - - - -精选学习资料 - - - - - - - - - 9 # ExprTail Var 优秀资料欢迎下载！ididExprVar ExprTail 10 # ExprTail VarTail id ididVarid VarTail Exp 11 # ExprTail VarTail id12 # ExprTail Expr idVarTail Expr 13 # ExprTail Expr id14
8、 # ExprTail Expr idExprExpr 15 # ExprTail Expr id 16# ExprTail ExprTail Var id Var ExprTail 17 # ExprTail Varid VarTail 18 ExprTail VarTail id id # ExprTail 19 ExprTail VarTail # ExprTail 20 ExprTail VarTail # ExprTail ExprTail 21 # ExprTail 22 # ExprTail # ExprTail 23 # # 分析胜利2、对下面的文法 G: ETE名师归纳总结
9、- - - - - - -第 6 页,共 16 页精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！E +E| TFTT T| FPFF *F | PE|a|b|（1）运算这个文法的每个非终结符的答案： FIRSTE=,a,b, FIRSTE=+, FIRSTT=,a,b, FIRSTT=,a,b, FIRSTF=,a,b, FIRSTF=*, FIRSTP=,a,b, FOLLOWE=#, FOLLOWE=#, FOLLOWT=+,# FOLLOWT=+,# FOLLOWF=,a,b,+,# FOLLOWF=,a,b,+,# FOLLOWP=*,a,b,+,# FIRST
10、和 FOLLOW；（8 分）名师归纳总结 - - - - - - -第 7 页,共 16 页精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！（2）证明这个文法是 LL1 的；（6 分）答案：考虑以下产生式 : EE|a bTT|F*F|PE|FIRST+EFIRST =+ =FIRST+EFOLLOWE=+#,= FIRSTT FIRST =,a,b, = FIRSTT FOLLOWT=,a,b,+,#= FIRST*F FIRST =* =FIRST*F FOLLOWF=* ,a,b,+,#= FIRSTE FIRSTa FIRSTb FIRST= 所以 , 该文法式
11、LL1 文法. （3）构造它的猜测分析表；（6 分）3、已知文法 GS 为：S-a|T T-T,S|S 名师归纳总结 - - - - - - -第 8 页,共 16 页精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！排除文法 GS中的左递归,得文法 G S ； 文法 G S 是否为 LL1 的？如是,给出它的猜测分析表；4、对下面的文法 G: S S a T | a T | a T T a T | a 1 排除该文法的左递归和提取左公因子；2 构造各非终结符的 FIRST和 FOLLOW集合；3 构造该文法的 LL1 分析表,并判定该文法是否是 LL1 的；答案：5、文法
12、 GS 及其 LR分析表如下,请给出串baba#的分析过程；名师归纳总结 - - - - - - -第 9 页,共 16 页精选学习资料 - - - - - - - - - 1 S DbB2 D d优秀资料欢迎下载！3 D 4 B a5 B Bba6 B D LR分析表GOTO ACTION b D a # S B 0 r3 s3 1 2 1 acc 6 2 s4 3 r2 S5 r6 4 r6 5 r4 r4 6 s7 r1 7 S8 8 r5 r5 答案：名师归纳总结 步骤状态符号输入串acc 第 10 页,共 16 页0 0 # baba# 1 02 #D baba# 2 024 #Db
13、 aba# 3 0245 #Dba ba# 4 0246 #DbB ba# 5 02467 #DbBb a# 6 024678 #DbBba # 7 0246 #DbB # 8 01 #S # - - - - - - -精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！六、语法分析题考虑文法 : SAS|b ASA|a （1）列出这个文法的全部 答案LR0 项目；（5 分）0. SS1. SS2. SAS 3. SaA S4. SAS 5. Sb6. Sb7. ASA8. AS A 9. ASA 10. Aa11. A（2）给出识别文法全部活前缀的DFA；（5 分）（3）求
14、全部非终结符的FOLLOW集；（5 分）（4）文法是 SLR文法吗？如是, 构造出它的 SLR分析表 , 否就说明理 由；（5 分）不是 SLR文法 状态 3,6,7 有移进归约冲突 状态 3：FOLLOWS =# 不包含 a,b 状态 6：FOLLOWS=#,a,b包含 a,b, ；移进归约冲突无法消解 状态 7：FOLLOWA=a,b包含 a,b ；移进归约冲突消解 所以不是 SLR文法；七、证明题名师归纳总结 - - - - - - -第 11 页,共 16 页精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！1、证明下面文法是 SAaAb|BbBa A BLL1 的
15、但不是 SLR1的；第一该文法无左递归存在 ,没有公共左因子；其次 :对于 SAaAb|BbBa FIRSTAaAb=a FIRSTBbBa=b FIRSTAaAbFIRSTBbBa= 所以该文法是 LL1 文法；2证明该文法不是 SLR 的；文法的 LR0 项目集规范族为 : 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. I6= S AaA.b I7= S BbB.a I8= S AaAb. I9= S BbBa. 考察 I0: FOLLOWA=a,b
16、FOLLOWB=a,b FOLLOWAFOLLOWB= a,b 产生规约 -规约冲突；所以该文法不是 SLR1 文法；2、证明下面文法是 SA AAb|bBa BaAc|a|aAb SLR1但不是 LR0 的；名师归纳总结 - - - - - - -第 12 页,共 16 页精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！解：文法 GS ：0：SA 1：AAb 2：AbBa 3：BaAc 4：Ba 5：BaAb构造 LR0 项目集规范族：名师归纳总结 状态项目集转换函数第 13 页,共 16 页0 S AGO0,A 1 1 AAbGO0,A 1 AbBa GO0,b 2
17、SAACCEPT 2 AAb GO1,b 3 AbBa GO2,B 4 3 BaAc GO2,a 5 Ba GO2,a 5 BaAb GO2,a 5 AAbR1 4 AbBa GO4,a 6 5 BaAc GO5,A 7 - - - - - - -精选学习资料 - - - - - - - - - 6 Ba优秀资料欢迎下载！R4 BaAb GO5,A 7 AAbGO5,A 7 AbBa GO5,b 2 AbBaR2 7 BaAc GO7,c 8 8 BaAb GO7,b 9 AAb GO7,b 9 BaAcR3 9 BaAbR5 AAbR1 状态 5 存在“ 归约移进” 冲突,状态 因此该文法不
18、是 LR0 文法；状态 5：9 存在“ 归约归约” 冲突,FOLLOWBa,因此, FOLLOWBb状态 9：FOLLOWBa,FOLLOWA#,b,c,因此 FOLLOWBFOLLOWA 状态 5 和状态 9 的冲突均可用 SLR1方法解决,构造 SLR1分析表 如下：名师归纳总结 状态a ACTION # A GOTO 第 14 页,共 16 页b c B - - - - - - -精选学习资料 - - - - - - - - - 0 S5 S2 优秀资料欢迎下载！1 4 ACCEPT 1 S3 2 3 S6 R1 R1 R1 7 4 S2 5 R4 6 R3 R2 R2 R2 7 S9
19、S8 8 9 R5 R1R1R1该 SLR1分析表无重定义,因此该文法是 文法；八、语义分析题SLR1文法,不是 LR01、将语句 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 名师归纳总结 - - - - - - -第 15 页,共 16 页精选学习资料 - - - - - - - - - 优秀资料 欢迎下载！109 2、写出下面语句经语法制导翻译后所生成的四元式代码序列；if xc do c:=c+1 else x:=x+5 答案：假设初始为100,就四元式代码序列为goto 102 100 if xc 103 goto 109 104 M:=C+1 105 C:=M 106 goto 102 107 N:=X+5 108 X:=N 109 名师归纳总结 - - - - - - -第 16 页,共 16 页