编译原理复习题答案

1、二、概念题1、设有文法：PQ P+Q|QCH Q*R|RRH (P)|i(1)证明Q*R+Q+O它的一个句型。(3分)(2)给出Q*R+Q+Q所有短语，直接短语和句柄。(4分)(3)给出句子i + i * i的最右推导。(4分)(4)给出句子i + i * i的最左推导。(4分)2、设有文法： E+T|T T -T*F|F F -(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

2、分)3、写出表达式a+b*(c-d) 对应的逆波兰式和三元式序列。答案：逆波兰式： (abcd-*+)三元式序列：OP ARG1 ARG2(1) -cd(2) *b(1)(3) +a(2)三、词法分析题给出下面语言的相应文法L1=anbnambm|n,m >0答案：S-AB|A|B| E2 aAb|abB aBb|ab给出下面语言的相应文法L2=anbnci|n >1,i >0答案：S- AB|B2 a|aAB bBc|bc给出下面语言的相应文法L3= anbncm| m,n Ll , n 为奇数,m为偶数答案：文法G(S):S -ACA-> aaAbb/abCf cc

3、Ccc/cc四、词法分析题1、构造下面正规式相应的DFA(0|1) .1(11) .)*(要求：先将正规式转化为 NFA再将NFA1定化，最小化)2、构造下面正规式相应的DFA1(0|1) *101答案：II0I1XA,B,CA,B,C B,C B,C,DB,C B,C B,C,DB,C,D B,C,EB,C,DB,C,E B,CB,C,D,yB,C,D,yB,C,E B,C,D3、构造一个DFA它接受=a, b上所有包含ab的字符串(要求：先将正规式转化为 NFA再将NFA1定化，最小化)答案：(一)相应的正规式为(a|b)*ab(a|b)*(二)与此正规式对应的NFA为状态转换矩阵为:精选

4、IJO.1,2)U.2J口，之，同*当 6(1,2141,2.3L,2，3,5,6111.2,3,5,>1asim,5,旬£1,2,3,5,61叫最小化：0,1, 2 3 , 4, 50, 2 , 1, 3 , 4, 5baaboV b,状态集为0,1,3,所以此等价的DFA为：开始状态为0 ,终态集为3输入字母表是a,b状态转换图如上。4、构造与正规式 b(a|b)*ba 等价的DFA五、语法分析题1、对下面的文法G:Expr ExprExpr(Expr)|Var ExprTailExprTail Expr| &Varid VarTailVarTail (Expr)

5、|(1)构造LL(1)分析表。(12分)答案:(1) FIRST(Expr尸_ , ( , id FIRST(ExprTail)=_ , & FIRST(Var尸idFIRST(VarTail)= ( ,£ FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) 步骤 符号栈输入串所用产生式0# Expr1 # ExprTail Var2 # ExprTail VarTailid3 # ExprTailVarTailid_ _id(id)#idid(id)#ExprVar ExprTailidid(id) #Varid VarTail_ _id(

6、id)#4# ExprTail_id(id)#VarTail 一 eFOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) id()EzcrEq： f VarEizpxTai 1Emrf(Emr)EsprTailExprTail-. E乐r，距rTail-* EEzprT,ailVarVar idVarTailVarTailWar%” 一Vai'Tai 1 一VrTailt(2)给出对句子idid(id)的分析过程。(8分)5# Expr_6# Expr_id(id)#id(id) # ExprTail Expr7# Expr_id(id)#

7、ExprExpr8# Exprid(id) #9# ExprTail Varid(id) ExprVar ExprTail10# ExprTail VarTail idid(id) Varid VarTail11#ExprTailVarTail12#ExprTail )Expr(13#ExprTail )Expr(id) (id) # VarTail (Expr)(id) 14# ExprTail ) )Expr(id) Expr(Expr)15# ExprTail ) )Exprid) 16# ExprTail ) )Var ExprTail17# ExprTail ) )ExprTail

8、Var id) Exp ExprTail VarTail id id) Varid VarTail18# ExprTail ) )ExprTail VarTail ) 19# ExprTail ) )ExprTail ) VarTail 一 e20#ExprTail) )21#ExprTail)22#ExprTail23#)#ExprTail &)#ExprTail &分析成功2、对下面的文G:E'f+E| eTfFT'T'f T| eFPF'F' 7*F'| £F(E)|a|b| A(1)计算这个文法的每个非终结符的

9、FIRST和F0LL0W(8分)答案：FIRST(E尸(abjFIRST(E)=+, & FIRST"尸(abjFIRST(T')=(,a,b,A,& FIRST(F 尸(ab,FIRST(F)=*, £ FIRST(P 尸(abjFOLLOW(E 尸#,)FOLLOW(E')=#,)FOLLOW"尸+,),#FOLLOW(T')=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F)=(,a,b,A+,),#FOLLOW(P)=*,(,a,b,A,+,),#(2)证明这个文法是LL(1)的。(6分)答案

10、：考虑下列产生式：E E|T T|F *F |P (E)1A|a|bFIRST(+E) A FIRST( e)=+ A e = 0FIRST(+E) A FOLLOW(E')=+n #,)= 0FIRST(T) A FIRST(£ )=(,a,b,A n e = 0FIRST(T) A FOLLOW(T')=(,a,b,A A +,),#= 0FIRST(*F') A FIRST( & )=* A e = 0FIRST(*F') A FOLLOW(F')=* A (,a,b,A,+,),#=0FIRST(E) AFIRST(a) A F

11、IRST(b) A FIRST)= ©所以，该文法式LL(1)文法.(3)构造它的预测分析表。(6分)口十不1柞卬副3E/E fTE'EtTZ*£ 一龙,£ ->7ZrE”EtEEr f 1炉Ef T6中T tFT卡TfFTFt 口'TtFF妙T,ppTf 7+T aF fT.FfT,p f 1力pF t PF，pF 一 PF,FfWFt*q戌口Fr T已尸r f斗尸F' -> 日F T心Fr T紧户TFf -y GF，pPf(E)P f wq产T入PfZ3、已知文法GS为:S->a|(T)T->T,S|S消除文法G

12、S中的左递归，得文法G'S 文法G'S是否为LL(1)的？若是，给出它的预测分析表。4、对下面的文法G:S S a T | a T |a TT a T | a(1)消除该文法的左递归和提取左公因子；(2)构造各非终结符的FIRST和FOLLO储合；(3)构造该文法的LL(1)分析表，并判断该文法是否是 LL(1)的答案：并判断该文法是否是LL(D的. (提取左公因子2分) St aTS1 v a TSf S t 7 仃 TS' I £ 丁一 。丁' 7，T I £(3)构造该文法的IX分析表, 答：(1)(消除在递归？分)St aTSf “h

13、TS'S- yaTS' | ET > T > 八口 T | a(4分)FIRST(S)af v；FIRST(S)=, £ FIRST(T)F1RST(T)=a f £ FOLLOWS) =FOLLOWS*)=FOLLOW(T)f 用FOLLOWfT), #)5、文法G(S)及其LR分析表如下，请给出串baba#的分析过程(1) S DbB B a (5) B Bba (6) B eLR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案:步骤状态符号输入用00#baba

14、#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678#DbBba#70246#DbB#801#S#acc六、语法分析题 考虑文法 :S AS|b A SA|a（ 1） 列 出这个文法的所有LR（0） 项目。 （ 5 分）答案0. S S 1. S S 2. s as 3. s a s4. S AS 5. S b 6. S b 7. A SA8. a s a 9. a sa 10. a a 11. a a（ 2）给出识别文法所有活前缀的DFA。 （ 5 分）（3）求所有非终结符的FOLLOW。（5分）（4）文法是SL

15、R文法吗？若是，构造出它的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)的S AaAb|BbBaAtB- £首先该文法无左递归存在，没有公共左因子。其次:对于 S- AaAb|BbBa FIRST(AaAb尸a FIRST(BbBa尸bFIRST(AaAb)n FIRST(Bb

16、Ba尸所以该文法是LL(1)文法。(2)证明该文法不是 SLR的。文法的LR(0)项目集规范族为：I0=S' 一.S SfAaAb SfBbBa Af B 一.I1= S '- S. I2= S f A.aAb I3= S f B.bBa I4= S f Aa.Ab Af I5= S 一Bb.Ba Bf I6= S f AaA.b I7= S BbB.a I8= S -AaAb. I9= S f BbBa. 考察I0:FOLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A) FOLLOW(B尸a,b 产生规约-规约冲突。所以该文法不是SLR(1)文法。2、证明

17、下面文法是SLR(1)但不是LR(0)的S A2 Ab|bBaB aAc|a|aAb解：文法GS:0: SA1:卜Ab2: 2bBa3: B aAc4: Ba5: B aAb构造LR(0)项目集规范族:状态项目集转换函数0S7 AGO0, A = 1K AbGO0, A = 12 bBaGO0, b =21S AACCEPTK AbGO1, b =322 b BaGO2, B=4腔 aAcGO2, a =5B7 aGO2, a =5B aAbGO2, a =53K Ab-R142bB- aGO4, a = 65腔 a AcGO5, A = 7B a R4B a AbGO5, A = 7K Ab

18、GO5, A = 72 bBaGO5, b = 262 bBa-R27腔aAcGO7, c = 8B aA bGO7, b =9K AbGO7, b =98- aAc R39B aAb-R5K Ab-R1状态5存在“归约移进”冲突，状态 9存在“归约归约”冲突，因此该文法不是LR(0)文法。状态5:FOLLOW(男a,因止匕 FOLLOW(B) b:状态9:FOLLOW(男a, FOLLOW(A> #, b,c,因止匕 FOLLOW(B) FOLLOW(A) =状态5和状态9的冲突均可用SLR(1)方法解决，构造SLR(1)分析表 如下：状态ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1该SLR(1)分析表无重定义，因此该文法是 SLR(1)文法，不是LR(0) 文法。八、语义分析题1、将语句if (A<0)(B>0) then while (C>0) do C:=C-D翻译成四元式答案：100 (j< , A, 0, 104)101 (j , - , - , 102)102 (j> , B, 0, 104)103 (j , - , - , 109)104 (j> , C