编译原理习题解答

《编译原理习题解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.从下列文法中消除左递归，提取左公因子S→Aa

2、Ab

3、cA→Ad

4、Se

5、f先消除直接的左递归A→SeA’

6、fA’A’→dA’

7、ε再消除间接左递归：S→SeA’a

8、SeA’b

9、fA’a

10、fA’b

11、cS→fA’aS’

12、fA’bS’

13、cS’S’→eA’aS’

14、eA’bS’

15、εS→fA’aS’

16、fA’bS’

17、cS’S’→eA’aS’

18、eA’bS’

19、εA’→dA’

20、ε提取左公因子：S→fA’B

21、cS’B→aS’

22、bS’S’→eA’C

23、εC→aS’

24、bS’A’→dA’

25、εP811.S→a

26、^

27、(T)T→T,S

28、S消除左递归：S→a

29、^

30、(T)T→ST’T’→，ST’

31、εProcedureTBe

32、ginS;T’EndProcedureSIfsym=‘(‘thenBeginAdvance;TIfsym=‘)’thenadvanceElseerrorEndElseifsym=‘^’thenadvanceElseifsym=‘a’thenadvanceElseerrorProcedureT’Ifsym=‘,’thenBeginAdvance;S;T’End(2)判断是否为LL(1)First(T’)={‘,’，ε}First(T)=First(S)={a，^,(}Follow(S)={#，’,’，）}Follow(T)={）}Follow(T’)={）}T’有两个候选，但first

33、(T’)∩follow(T’)=φ文法是LL(1)的构造预测分析表：a^(),#SS→aS→^S→(T)TT→ST’T→ST’T→ST’T’T’→εT’→,ST’2.E→TE’E’→+E

34、εT→FT’T’→T

35、εF→PF’F’→*F’

36、εP→(E)

37、a

38、b

39、^+*()^abε#E→TE’E’→+E

40、εT→FT’T’→T

41、εF→PF’F’→*F’

42、εP→(E)

43、a

44、b

45、^FIRST(E)={(,^,a,b};FIRST(E’)={+,ε};FIRST(T)={(,^,a,b

46、};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,#};因为：E’→+E

47、εFIRST(+E)FOLLOW(E’)={+}{),#}=Φ;T’→T

48、εFIRST(T)FOLLOW(T

49、’)={(,^,a,b}{+,),#}=Φ;F’→*F’

50、εFIRST(*F)FOLLOW(F’)={*}{+,(,),a,b,^,#}=Φ;P→(E)

51、a

52、b

53、^FIRST(“(E)”)FIRST(a)FIRST(b)FIRST(^)=Φ;所以是LL(1)文法。构造预测分析表：+*()ab^#EE→TE’E→TE’E→TE’E→TE’E’E’→+EE’→εE’→εTT→FT’T→FT’T→FT’T→FT’T’T’→εT’→TT’→εT’→TT’→TT’→TT’→εFF→PF’F→PF’F→PF’F→PF’F’F’→ε*F’F’→εF’→εF’→εF’→εF’→εF’→ε

54、PP→(E)P→aP→bP→^4.E→-EE→(E)

55、VTT→-E

56、εV→idFF→(E)

57、ε-()idε#EVTF-()id#EE→-EE→(E)E→VTVV→idFTT→-ET→εT→εFF→εF→(E)F→εF→εFIRST(E)={-,(,id};FIRST(V)={id};FIRST(T)={-,ε};FIRST(F)={(,ε};FOLLOW(E)={),#};FOLLOW(V)={-,),#};FOLLOW(T)={),#};FOLLOW(F)={-,),#};分析栈输入串输出#E#TV#TFid#TF#T#E-#E#E-#E#TV#

58、TFid#TFid--id((id))#id--id((id))#id--id((id))#--id((id))#--id((id))#--id((id))#-id((id))#-id((id))#id((id))#id((id))#id((id))#((id))#EVTVidFFεT-EE-EEVTVidFF(E)分析栈输入串输出#T)E(#T)E#T))E(#T))E#T))TV#T))TFid#T))TF#T))T#T))#T)#T#