资源描述：
《编译原理复习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、......二、概念题1、设有文法：P→P+Q
2、QQ→Q*R
3、RR→(P)
4、i（1）证明Q*R+Q+Q是它的一个句型。（3分)（2）给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)（4）给出句子ｉ+ｉ*ｉ的最左推导。(4分)2、设有文法：E→E+T
5、TT→T*F
6、FF→(E)
7、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)
8、对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+)参考材料......三元式序列:OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)三、词法分析题给出下面语言的相应文法L1={anbnambm
9、n,m≥0}答案： S→AB
10、A
11、B
12、∑ A→ aAb
13、ab B→ aBb
14、ab给出下面语言的相应文法L2={anbnci
15、n≥1,i≥0}答案： S→ AB
16、B A→ a
17、aA B→ bBc
18、bc给出下面语言的相应文法L3={anbncm
19、m,n≥1，n为奇数，m为偶数}。答案：文法G(S):S→ACA→aaAbb/abC→ccCcc
20、/cc四、词法分析题参考材料......1、构造下面正规式相应的DFA((0
21、1)*
22、(11)*)*（要求：先将正规式转化为NFA，再将NFA确定化，最小化）2、构造下面正规式相应的DFA1(0
23、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} {
24、B,C,E} { B,C,D}3、构造一个DFA，它接受S={a，b}上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）答案：(一)相应的正规式为(a
25、b)*ab(a
26、b)*(二)①与此正规式对应的NFA为②状态转换矩阵为：参考材料......③最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}baa01b3ba④所以此等价的DFA为：开始状态为0，终态集为{3}，状态集为{0,1,3}，输入字母表是{a,b}状态转换图如上。4、构造与正规式b(a
27、b)*ba等价的DFA五、语法分析题1、对下面的文法G:
28、Expr→-ExprExpr→(Expr)
29、VarExprTailExprTail→-Expr
30、εVar→idVarTailVarTail→(Expr)
31、ε参考材料......（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—i
32、d((id))的分析过程。（8分）步骤符号栈输入串所用产生式0＃Exprid__id((id))＃1#ExprTailVarid__id((id))＃Expr→VarExprTail2#ExprTailVarTailidid__id((id))＃Var→idVarTail3#ExprTailVarTail__id((id))＃4#ExprTail__id((id))＃VarTail→ε5#Expr___id((id))＃ExprTail→_Expr6#Expr_id((id))＃7#Expr__id((id))＃Expr→_Expr8#Exprid((id))
33、＃参考材料......9#ExprTailVarid((id))＃Expr→VarExprTail10#ExprTailVarTailidid((id))＃Var→idVarTail11#ExprTailVarTail((id))＃12#ExprTail)Expr(((id))＃VarTail→(Expr)13#ExprTail)Expr(id))＃14#ExprTail))Expr((id))＃Expr→(Expr)15#ExprTail))Exprid))＃16#ExprTail))ExprTailVarid))＃Exp→VarExprTail17#Exp
34、rTail))ExprTailVarT
