编译原理习题课.ppt

《编译原理习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、习题课令文法G[E]为:E→TE+TE-TT→FT*FT/FF→(E)i证明E+T*F是它的句型,指出这个句型的所有短语、直接短语和句柄EE+TE+T*F短语：E+T*F和T*F直接短语：T*F句柄：T*FEE+TT*F一个上下文无关文法生成的句子abbaa的推导树如图。（1）给出该句子的相应的最左推导和最右推导（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有的短语、简单短语、句柄。SABSaBSaSBBSaBBSabBSabbSabbAaabbaa最左推导最右推导略产生式集合：S→ABSB→SBB

2、S→AaS→B→bA→a短语、句柄SABSaSBBAabba习题解答7．给文法G[S]：SaA

3、bQAaA

4、bB

5、bBbD

6、aQQaQ

7、bD

8、bDbB

9、aAEaB

10、bFFbD

11、aE

12、b构造相应的最小的DFA。由于从S出发任何输入串都不能到达状态E和F，所以，状态E，F为多余的状态，不予考虑。aZSADQBbbbababbbaa简化产生式后生成的NFAIIa=ε-closure(MoveTo(I,a))Ib=ε-closure(MoveTo(I,b))1[S]2[A]3[Q]2[A]2[A]4[B,Z]3[Q]3[Q]5[D,Z]4[B,Z]3[

13、Q]6[D]5[D,Z]2[A]7[B]6[D]2[A]7[B]7[B]3[Q]6[D]因为4,5状态包含Z,所以都是终态,1,2,3,6,7都是非终态;1态输入b后为3,是非终态;2和3输入b后为4和5是终态,所以1和2,3是不同的状态;2和3是相同等价状态;4和5是等价状态;6何是等价状态;所以,最后剩下:1,2,4,6四个状态.a62baa1babb4最小化的DFA124376abbaa5babababba8.给出下述文法所对应的正规式S0A

14、1BA1S

15、1B0S

16、0将A1S

17、1和B0S

18、0分别代入S0A

19、1B得:S=01S

20、01S=10S

21、1

22、0得产生式:S=01S

23、10S

24、01

25、10化简得:S=(01

26、10)S

27、(01

28、10)S=(01

29、10)*(01

30、10)得正规式:(01

31、10)*(01

32、10)将图4.18的DFA最小化，并用正规式描述它所识别的语言：a72bcbdb134c6aabbd5b因为6，7是DFA的终态，其他是非终态，可将状态集分成两个子集：P1={1，2，3，4，5}，P2={6，7}。由于F(6,b)=F(7,b)=6,而6，7又没有其他输入，所以6，7等价。由于F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,而6，7等价，所以

33、3,4等价。由于F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而3，4等价，所以1,2等价。由于状态5没有输入字符b,所以与1，2，3，4都不等价。综上所述，上图DFA的状态可最细分解为：P={{1，2}，{3，4}，{5}，{6，7}}。abb13c6bd5a最小化后的DFA该DFA用正规式表示为：b*a(c

34、da)*bb*习题解答2．对下面的文法G：ETE’E’+E

35、εTFT’T’T

36、εFPF’F’*F’

37、εP(E)

38、a

39、b

40、^计算这个文法的每个非终结符的FIRST集和FOLLOW集。证明这个方法是LL(1)的。构造它的预

41、测分析表。S为文法开始符号，#一定是FOLLOW（S）元素设AB是一个产生式，则First()的非空元素属于FOLLOW（B）如果*ε，则FOLLOW（A）的元素就要加入到FOLLOW（B）中，因为：D1A1AB两个产生式，在推导过程中，可能会出现这样的句型S*…1A1…*…1B1…*…1B1…计算每个非终结符的FIRST和FOLLOW集合非终结符FIRST集合FOLLOW集合E(,a,b,^),#E’+,ε),#T(,a,b,^+,),#T‘(,a,b,^,ε+,),#F(,a,b,^(,a,b,^,+,),#F

42、’*,ε(,a,b,^,+,),#P(,a,b,^*,(,a,b,^,+,),#计算每个非终结符的FIRST集合FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(E’)={+,ε}FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(T‘)=FIRST(T)∪{ε}={(,a,b,^,ε};FIRST(F)=FIRST(P)={(,a,b,^};FIRST(F’)=FIRST(P)={*,ε};FIRST(P)={(,a,b,^};计算每个非终结符的FOLLOW集合FOLLOW

43、(E)={),#};FO