《编译原理复习题答案》由会员分享，可在线阅读，更多相关《编译原理复习题答案（23页珍藏版）》请在金锄头文库上搜索。
1、二、概念题1、设有文法：P-P+QIQQ Q*R|RR-(P)|i(1) 证明Q*R+Q+Q 是它的一个句型。(3分)(2) 给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)(3) 给出句子i + i * i的最右推导。(4分)(4) 给出句子i + i * i的最左推导。(4分)2、 设有文法： E+T|TT-T*F|FF-(E)|i(1) 证明E+T*F是它的一个句型。(3分)答案：E E T E T*F(2) 给出E+T*F的所有短语，直接短语和句柄。(4分)短语：E+T*F, T*F,直接短语：T*F句柄:T*F(3) 给出句子i + i * i的最右推导。(4分)3、写出表达式
2、a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+)三元式序列：OPARG1ARG2(1)-cd*b(1)+a(2)三、词法分析题给出下面语言的相应文法L1=anbnambm|n,m 0答案：S-AB|A|B|刀A aAb|abB aBb|ab给出下面语言的相应文法L2=anbnci|n 1,i答案：S AB|BA a|aAB bBc|bc给出下面语言的相应文法L3=anbncm| m,n n,为奇数，m 为偶数答案：文法G(S):SACAaaAbb/abC ccCcc/cc四、词法分析题专业word可编辑1、构造下面正规式相应的DFA(011)*1(11)*)*(
3、要求：先将正规式转化为NFA,再将NFA确定化，最小化)2、构造下面正规式相应的 DFA1(0|1)*101答案：II011XA,B,CA,B,C B,C B,C,DB,C B,C B,C,DB,C,D B,C,E B,C,DB,C,E B,C B,C,D,yB,C,D,y B,C,E B,C,D3、构造一个DFA,它接受二a , b上所有包含ab的字符串。(要求：先将正规式转化为NFA,再将NFA确定化，最小化)答案：(一)相应的正规式为(a|b)*ab(a|b)*(二) M此正规式对应的NFA为状态转换矩阵为:IJO.1,2)11,2.3(lr21U,2.51(1,2,3,5,61最小化:
4、0,1, 23, 4, 50,2, 1 ,3, 4, 5所以此等价的DFA为：开始状态为0 ,终态集为3,状态集为0,1,3, 输入字母表是a,b状态转换图如上。4、构造与正规式 b(a|b)*ba 等价的DFA五、语法分析题1、对下面的文法G:Expr * ExprExpr i(Expr)|Var ExprTailExprTaif Expr| eVarid VarTailVarTaiR(Expr) | e(1)构造LL(1)分析表(12 分)答案:(1 ) FIRST(Expr)二匕,(,id FIRST(ExprTail)=_ ,& FIRST(Var)二idFIRST(VarTiil)=
5、 ( ,0FOLLOW(Expr)二# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) 步骤符号栈输入串所用产生式id()EzcrEiiCirVarEizpxTai 1EmrfEsprTailExprTail-. EjrEqprTiil-*EzprTailVarVar予idVarTailVarTailVarai 1VaiTai 1 VrTailt(2)给出对句子id id(id)的分析过程。(8分)# Expr# ExprTail Varid_ _id(id) #idid(id) # E
6、xpr f Var ExprTail# ExprTail VarTail id id_d(id) # Varf id VarTail# ExprTail VarTail_ _id(id)# ExprTail_ _id(id) #VarTaif# Expr_ _id(id) #ExprTailf _ Expr# Expr# Expr_id(id) #Expr f _Expr_id(id) # Exprid(id) #ExpVar ExprTail# ExprTail VarTail id id(id) #VarTid VarTail# ExprTail VarTail(id) # ExprTai
7、l )Expr(id) #VarTaiT(Expr)# ExprTail )Expr(id) # ExprTail ) )Expr(id) #ExprT (Expr)# ExprTail ) )Exprid) # ExprTail )ExprTail Varid) #ExprTail# ExprTail )# ExprTail Varid(id) #ExprTail VarTail id id) # ExprTail )ExprTail VarTail )# ExprTail )ExprTail )# ExprTail ) )# ExprTail )# ExprTailExp t VarVar
8、T id VarTailVarTaiTExprTailg#ExprTail#分析成功F面的文法G:910111213141516171819202122232、对EE| T FTT丹F PFF *F| &P(E)|a|b|A(1) 计算这个文法的每个非终结符的 FIRST和 FOLLOW( 8分)答案：FIRST(E)=(,a,b,AFIRST(E)二+, jFIRST(T)二(,a,bFIRST(T)=(,a,b,A, jFIRST(F)=(,a,b,AFIRST(F)二*, jFIRST(P)=(,a,b,AFOLLOW(E)二#,)FOLLOW(E)二#,)FOLLOW(T)二+,),#
9、FOLLOW(T)二+,),#FOLLOW(F)二(,a,b,+,),#FOLLOW(F)二(,a,b,+,),#FOLLOW(P)=*,(,a,b,A,+,),#(2) 证明这个文法是LL(1)的。(6分)答案：考虑下列产生式：E E|T T|F *F |P (E)F|a|bFIRST(+E)Q FIRST(沪+ A 护 FIRST(+E)Q FOLLOW(E)二+ A#,)= FIRST(T)A FIRST(沪(,a,bf A 护 FIRST(T)A FOLLOW(T)=(,a,b,A A +,),#= FIRST(*F)A FIRST(沪* A = FIRST(*F)A FOLLOW(F
10、)二* A (,a,b,A,+,),#= FIRST(E)AFIRST(a) AFIRST(b) AFIRST(A)= 所以该文法式LL(1)文法.(3) 构造它的预测分析表。(6分)2a期班pE fTE农EtTZ* -7ZrEJ+E*E f耳*Ef THTVT fFTTrFT丁 FT*Tppa卩T八F T*p &F*apF FFpF PFFf呼FPFf口Fr T &FfF T貝FTF* TFf -Fr+pF f 2FfbaPS3、已知文法GS为:S-a|(T)T-T,S|S 消除文法GS中的左递归，得文法GS。 文法GfS是否为LL(1)的？若是，给出它的预测分析表4、对下面的文法G:S S
11、 a T | a T | a TT a T | a(1) 消除该文法的左递归和提取左公因子；构造各非终结符的FIRST和FOLLOW集合； 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的答案: 构适该文注的LL(1)分析表答：(1)(消除左递归2分)St aTS, aTS*SJ yaTS | sT t Ft AdT I a a井判斷该文注是奁是LL的。(提魅左公因子2分)Ft aTS1 | v a TSf S J aTSt | Tt auF厂 t T I (4分) FIRST(S)af v； FTRATF尸卜 FIRST(T) FIRSTS)=a * FOLLOW(S)= FOLLOWfS*)FOLLOW(T)f 祁 FOLLOW(T)=,时5、文法G(S)及其LR分析表如下，请给出串baba#的分析过程(1)s J DbB(2)D J d(3)D J e(4)B J a(5)B J Bba (6) B J eLR00765432oaa&bACTIONs3Ds00s5aaaa c c4kS6B2D0076543
