编译原理复习题答案_计算机-C++资料.pdf
优秀资料 欢迎下载！二、概念题 1、设有文法：PP+Q|Q QQ*R|R R(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 分)答案：EETETF *（2）给出 E+T*F的所有短语，直接短语和句柄。(4 分)短语:E+T*F,T*F,直接短语:T*F 句柄:T*F（3）给出句子+*的最右推导。(4 分)3、写出表达式 a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+)优秀资料 欢迎下载！三元式序列:OP ARG1 ARG2 (1)-c d (2)*b (1)(3)+a (2)三、词法分析题 给出下面语言的相应文法 L1=anbnambm|n,m 0 答案：SAB|A|B|A aAb|ab B aBb|ab 给出下面语言的相应文法 L2=anbnci|n 1,i 0 答案：S AB|B A a|aA B bBc|bc 给出下面语言的相应文法 L3=anbncm|m,n1，n 为奇数，m为偶数。答案：文法 G(S):SAC AaaAbb/ab CccCcc/cc 四、词法分析题 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！1、构造下面正规式相应的 DFA(0|1)*|(11)*)*（要求：先将正规式转化为 NFA，再将 NFA确定化，最小化）2、构造下面正规式相应的 DFA 1(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,D 3、构造一个 DFA，它接受=a，b上所有包含 ab 的字符串。（要求：先将正规式转化为 NFA，再将 NFA确定化，最小化）答案：(一)相应的正规式为(a|b)*ab(a|b)*(二)与此正规式对应的 NFA为 状态转换矩阵为：导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！最小化：0，1，2 3，4，5 0，2，1，3，4，5 所以此等价的 DFA为：开始状态为 0，终态集为3，状态集为0,1,3，输入字母表是a,b 状态转换图如上。4、构造与正规式 b(a|b)*ba 等价的 DFA 五、语法分析题 1、对下面的文法 G:Expr-Expr Expr(Expr)|Var ExprTail ExprTail-Expr|Varid VarTail VarTail(Expr)|b a a 0 1 b 3 b a 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！（1）构造 LL(1)分析表。（12 分）答案：（1）FIRST(Expr)=_,(,id FIRST(ExprTail)=_,FIRST(Var)=id FIRST(VarTail)=(,FOLLOW(Expr)=#,)FOLLOW(ExprTail)=#,)FOLLOW(Var)=_,#,)FOLLOW(VarTail)=_,#,)（2）给出对句子 id id(id)的分析过程。（8 分）步骤 符号栈 输入串 所用产生式 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)VarTail 5#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)Exp Var ExprTail 17#ExprTail)ExprTail VarTail id id)Varid VarTail 18#ExprTail)ExprTail VarTail )19#ExprTail)ExprTail )VarTail 20#ExprTail)ExprTail 21#ExprTail)22#ExprTail#ExprTail 23#分析成功 2、对下面的文法 G:ETE 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！E+E|TFT T T|FPF F *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)=(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！（2）证明这个文法是 LL(1)的。（6 分）答案：考虑下列产生式:EETTFFPEa b|*|()|FIRST(+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)文法.（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 T T a T|a(1)消除该文法的左递归和提取左公因子；(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分析表 ACTION GOTO b D a#S B D 0 r3 s3 1 2 1 acc 2 s4 3 r2 4 r6 S5 r6 6 5 r4 r4 6 s7 r1 7 S8 8 r5 r5 答案：步骤 状态 符号 输入串 0 0#baba#1 02#D baba#2 024#Db aba#3 0245#Dba ba#4 0246#DbB ba#5 02467#DbBb a#6 024678#DbBba#7 0246#DbB#8 01#S#acc 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！六、语法分析题 考虑文法:SAS|b ASA|a（1）列出这个文法的所有 LR(0)项目。（5 分）答案 0.SS 1.SS 2.SAS 3.SA S 4.SAS 5.Sb 6.Sb 7.ASA 8.AS A 9.ASA 10.Aa 11.Aa （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；移进归约冲突消解 所以不是 SLR文法。七、证明题 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！1、证明下面文法是 LL(1)的但不是 SLR(1)的。SAaAb|BbBa A B 首先该文法无左递归存在,没有公共左因子。其次:对于 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.I2=SA.aAb I3=SB.b Ba I4=SAa.Ab A.I5=SBb.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)的。SA AAb|bBa BaAc|a|aAb 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！解：文法 GS：0：SA 1：AAb 2：AbBa 3：BaAc 4：Ba 5：BaAb 构造 LR(0)项目集规范族：状态 项目集 转换函数 0 SA AAb AbBa GO0，A1 GO0，A1 GO0，b 2 1 SA AA b ACCEPT GO1，b 3 2 AbBa BaAc Ba BaAb GO2，B4 GO2，a 5 GO2，a 5 GO2，a 5 3 AAb R1 4 AbB a GO4，a 6 5 BaAc GO5，A7 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！Ba BaAb AAb AbBa R4 GO5，A7 GO5，A7 GO5，b 2 6 AbBa R2 7 BaA c BaA b AA b GO7，c 8 GO7，b 9 GO7，b 9 8 BaAc R3 9 BaAb AAb R5 R1 状态 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)分析表如下：状态 ACTION GOTO a b c#A B 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！0 S2 1 1 S3 ACCEPT 2 S5 4 3 R1 R1 R1 4 S6 5 R4 S2 7 6 R2 R2 R2 7 S9 S8 8 R3 9 R5 R1 R1 R1 该 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)导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个优秀资料 欢迎下载！109 2、写出下面语句经语法制导翻译后所生成的四元式代码序列。if xc do c:=c+1 else x:=x+5 答案：假设初始为 100，则四元式代码序列为 100 if xc goto 104 103 goto 109 104 M:=C+1 105 C:=M 106 goto 102 107 N:=X+5 108 X:=N 109 导分给出句子的最左推导分设有文法证明是它的一个句型分答案给出的所有短语直接短语和句柄分短语直接短语句柄给出句子的最右推导分写出表达式对应的逆波兰式和三元式序列答案逆波兰式优秀资料欢迎下载三元式序列三词法法四词法分析题优秀资料欢迎下载构造下面正规式相应的要求先将正规式转化为再将确定化最小化构造下面正规式相应的答案构造一个它接受上所有包含的字符串要求先将正规式转化为再将确定化最小化答案一相应的正规式为二与母表是状态转换图如上构造与正规式等价的五语法分析题对下面的文法优秀资料欢迎下载构造分析表分答案给出对句子的分析过程分步骤符号栈输入串所用产生式优秀资料欢迎下载分析成功对下面的文法优秀资料欢迎下载计算这个
