资源描述:
《编译原理习题课.ppt》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、习题课令文法G[E]为:E→TE+TE-TT→FT*FT/FF→(E)i证明E+T*F是它的句型,指出这个句型的所有短语、直接短语和句柄EE+TE+T*F短语:E+T*F和T*F直接短语:T*F句柄:T*FEE+TT*F一个上下文无关文法生成的句子abbaa的推导树如图。(1)给出该句子的相应的最左推导和最右推导(2)该文法的产生式集合P可能有哪些元素?(3)找出该句子的所有的短语、简单短语、句柄。SABSaBSaSBBSaBBSabBSabbSabbAaabbaa最左推导最右推导略产生式集合:S→ABSB→SBB
2、S→AaS→B→bA→a短语、句柄SABSaSBBAabba习题解答7.给文法G[S]:SaA
3、bQAaA
4、bB
5、bBbD
6、aQQaQ
7、bD
8、bDbB
9、aAEaB
10、bFFbD
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.给出下述文法所对应的正规式S0A
14、1BA1S
15、1B0S
16、0将A1S
17、1和B0S
18、0分别代入S0A
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:ETE’E’+E
35、εTFT’T’T
36、εFPF’F’*F’
37、εP(E)
38、a
39、b
40、^计算这个文法的每个非终结符的FIRST集和FOLLOW集。证明这个方法是LL(1)的。构造它的预
41、测分析表。S为文法开始符号,#一定是FOLLOW(S)元素设AB是一个产生式,则First()的非空元素属于FOLLOW(B)如果*ε,则FOLLOW(A)的元素就要加入到FOLLOW(B)中,因为:D1A1AB两个产生式,在推导过程中,可能会出现这样的句型S*…1A1…*…1B1…*…1B1…计算每个非终结符的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