编译原理精华总结--计算题.ppt

《编译原理精华总结--计算题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1练习：给出i+i*i的规范推导，并画出语法树。iＥ＋iＥ＊iＥＥＥ最左推导过程：E=>E+E=>i+E=>i+E*E=>i+i*E=>i+i*i文法G[E]如下：E→E+EE→E*EE→(E)E→i课堂练习2（1）转换函数；（3）状态转换图DFA三种表示的转换（2）状态转换矩阵；DFAM=({0,1,2,3},{a,b},f,0,{3})f(0,a)=1f(0,b)=2f(1,a)=3f(1,b)=2f(2,a)=2f(2,b)=3f(3,a)=2f(3,b)=1ab0120132022303211a10

2、32aabbbba3课堂练习4f35621iaaaabbbbstartNFA转变为DFA4等价的DFAaCDBAEFSbaaaaabbbbbabFstartNFA转变为DFA5DFA最小化课堂练习：把下图最小化6（1）将所有状态分成两个子集：终态集｛0｝和非终态集｛1,2,3,4,5｝；（2）当输入a时可判断｛1,2,3,4,5｝可再拆分，拆分后：｛4｝｛1,2,3,5｝；（3）当输入b时可判断｛1,2,3,5｝可再拆分，拆分后：｛1,5｝｛2,3｝；（4）当输入a时可判断｛2,3｝可再拆分，拆分后：

3、｛2｝｛3｝；｛1,5｝在输入a或b时指向相同，不可再拆。得：最小DNF为：DFA最小化课堂练习构造a(b*c

4、c*b)的NFAa(b*c

5、c*b)SZSAZab*c

6、c*bSAZac*bb*cBSAZabbcCεεc正规式构造NFA课堂练习43521aaaabbbb求以下NFA的正规式第一步64aaz3521saabbbb6NFA构造正规式第二步第三步第四步zs(a

7、b)*(aa

8、bb)(a

9、b)*aa

10、bbz52s（a

11、b）*（a

12、b）*aaz521sa

13、ba

14、bbb6NFA构造正规式

15、例:给出如图NFA等价的正规文法GABCDaaabbbbG=（{A，B，C，D}，{a，b}，P，A）其中P：A→aBA→bDB→bCC→aAC→bDC→εD→aBD→bDD→εNFA构造正规文法课堂练习求G[S]:S→aS

16、bS

17、aA

18、bBA→aC

19、a,B→bC

20、bC→aC

21、bC的等价的NFABASaaaabbbbC正规文法构造NFA12课堂练习文法G[E]：E→E+T

22、E-T

23、TT→T*F

24、T/F

25、FF→(E)

26、I消除方法左递归E→TE'E'→+TE‘

27、-TE'

28、T→FT'T'→*FT'

29、/FT'

30、F

31、→(E)

32、i消除左递归13【例】文法：（1）S→Qc

33、c（2）Q→Rb

34、b（3）R→Sa

35、a该文法的每个非终结符为间接左递归，消除方法：非终结符排序为：S、Q、R把（1）右部代入（3）得：（4）R→Qca

36、ca

37、a再将（2）的右部代入（4）得：（5）R’→Rbca

38、bca

39、ca

40、a对（5）消除直接左递归得：R→(bca

41、ca

42、a)R’R’→bcaR’

43、εS→Qc

44、cQ→Rb

45、bR→(bca

46、ca

47、a)R’R’→bcaR’

48、ε最终文法变为：消除左递归14FIRST(F)={(,i}FIRST(T’)={*,ε}

49、FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}判断方法是否是LL(1)方法【例】判断文法G[E]是否为LL(1)文法。E→TE’E'→+TE'｜εT→FT‘T'→*FT'｜εF→(E)｜i【解】文法不含左递归E’–>+TE’

50、FIRST(+TE’)={+}，FOLLOW(E’)={),＃}FIRST(+TE’)∩FOLLOW(E’)=φT’–>*FT’

51、FIRST(*FT’)={*},FOLLOW(T’)={+,),＃}FIRST(*FT’)∩FOLLOW(T’)=

52、φF–>(E)

53、iFIRST((E))=｛(｝,FIRST(i)=｛i｝FIRST((E))∩FIRST(i)=φ所以G[E]是LL(1)文法。15【例】文法G：E→TE'E'→+TE'

54、T→FT'T'→*FT'

55、F→(E)

56、i构造文法G的分析表i+*()#EE→TE'E→TE’E’E'→+TE'E’→εE’→εTT→FT’T→FT’T’T’→T’→*FT’T’→εT’→εFF→iF→(E)构造方法分析表16例:文法G[E]:E::=E+T

57、TT::=T*F

58、FF::=(E)

59、i求句型T+T+i的短语、

60、简单短语、句柄、素短语、最左素短语短语：T+T+i,T+T,T,i简单短语：T,I句柄：T素短语：T+T和i最左素短语：T+T短语、简单短语、句柄、素短语、最左素短语TE+TFiEE+T17【例】试构造FIRSTVT集和LASTVT集E'→#E#E→E+TE→TT→T*FT→FF→(E)F→i方法一：根据定义FIRSTVT(E')={#}FIRSTVT(E)={+,*,i,(}FIRSTVT(T)=