编译原理习题课.ppt

《编译原理习题课.ppt》由会员分享，可在线阅读，更多相关《编译原理习题课.ppt（29页珍藏版）》请在三一文库上搜索。

1、 令文法GE为: ETE+TE-T TFT*FT/F F(E)i 证明E+T*F是它的句型,指出这个句型的所有短语、直接短语 和句柄 EE+TE+T*F 短语： E+T*F和T*F 直接短语： T*F 句柄： T*F E E+T T*F 一个上下文无关文法生成的句子abbaa的推导树如图。 （1）给出该句子的相应的最左推导和最右推导 （2）该文法的产生式集合P可能有哪些元素？ （3）找出该句子的所有的短语、简单短语、句柄。 SABSaBSaSBBS aBBS abBSabbSabbAaabbaa 最左推导 最右推导略 产生式集合： SABS BSBB SAa S Bb Aa 短语、句柄 S A

2、B S aSBBAa bba 习题解答 7给文法GS： SaA|bQ AaA|bB|b BbD|aQ QaQ|bD|b DbB|aA EaB|bF FbD|aE|b l 构造相应的最小的DFA。 l 由于从S出发任何输入串都 不能到达状态E和F，所以 ，状态E，F为多余的状态 ，不予考虑。 a Z SAD Q B b b b a b a b b b a a 简化产生式后生成的NFA IIa = - closure(MoveTo(I,a) Ib = -closure(MoveTo(I,b) 1S2A3Q 2A2A4B,Z 3Q3Q5D,Z 4B,Z3Q6D 5D,Z2A7B 6D2A7B 7B3

3、Q6D l因为4,5状态包含Z,所以都是终态,1,2,3,6,7都是非终态; l1态输入b后为3,是非终态;2和3输入b后为4和5是终态,所以1和2,3是不同的状态; l2和3是相同等价状态;4和5是等价状态;6何是等价状态; l所以,最后剩下:1,2,4,6四个状态. a 6 2 b a a 1 b a b b 4 最小化的DFA 124 3 7 6 a b b a a 5 b a b a b a b b a 8.给出下述文法所对应的正规式 l S0A|1B l A1S|1 l B0S|0 l 将 A1S|1 和 B0S|0 分别代入 S0A|1B 得: nS=01S|01 nS=10S|1

4、0 l得产生式:S=01S|10S|01|10 化简得: lS=(01|10) S | (01|10) lS=(01|10)*(01|10) 得正规式: l(01|10)*(01|10) 9.将图4.18的DFA最小化，并用正规式描述它所识别的语言： a 72 b c b d b 13 4 c 6 a a b b d 5 b l因为6，7是DFA的终态，其他是非终态，可将状态集分成两个子集 ：P1=1，2，3，4，5，P2=6，7。 l由于F(6,b)=F(7,b)=6,而6，7又没有其他输入，所以6，7等价。 l由于F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)

5、=6,F(4,b)=7,而6 ，7等价，所以3,4等价。 l由于F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而3，4等价，所以1,2 等价。 l由于状态5没有输入字符b,所以与1，2，3，4都不等价。 l综上所述，上图DFA的状态可最细分解为：P=1，2，3，4， 5，6，7。 a b b 13 c 6 b d 5 a 最小化后的DFA 该DFA用正规式表示为： b*a(c|da)*bb* 习题解答 2对下面的文法G： ETE E+E| TFT TT| FPF F*F| P(E)|a|b| l 计算这个文法的每个非终结符的FIRST集和FOLLOW 集。 l 证明这个方

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

7、(,a,b,+,),# P (,a,b, *,(,a,b,+,),# 计算每个非终结符的FIRST集合 l FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; l FIRST(E)=+, l FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,; l FIRST(T)=FIRST(T)=(,a,b,; l FIRST(F)=FIRST(P)=(,a,b,; l FIRST(F)=FIRST(P)=*,; l FIRST(P)=(,a,b,; 计算每个非终结符的FOLLOW集合 l FOLLOW(E)=),#; l FOLLOW(E)=FOLLO

8、W(E)=),#; l FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含 l FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#; l FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包 含 l FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+, ),#; l FOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不 包含 l 在求FOLLOW集合时,要特别注意P76页的定义: A B,FOLLOW(B)包含的FIRST元

9、素,如果*,则 FOLLOW(A)的元素就要加入到FOLLOW(B)中。 证明这个方法是LL(1)的 l SELECT(ETE/)=FIRST(T)=(,a,b,; l SELECT(E+E)=+; l SELECT(E)=FOLLOW(E/)=),# l SELECT(TFT)=FIRST(F)=(,a,b,; l SELECT(TT)=FIRST(T)=(,a,b,; l SELECT(T)=FOLLOW(T/)=+,),#; l SELECT(FPF)=FIRST(P)=(,a,b,; l SELECT(F*F)=*; l SELECT(F)=FOLLOW(F/)=(,a,b,+,),#

10、; l SELECT(P(E)=( l SELECT(Pa)=a l SELECT(Pb)=b l SELECT(P)= 预测分析表 +*()ab# ETETETETE E+E TFTFTFTFT TTTTT FPFPFPFPF F*F P(E)ab 习题.第3题 有文法GS： S #S# SV VT | ViT TF | T+F F)V* | ( 1. 给出(+(i(的规范推导。 2. 指出句型F+Fi(的短语，句柄，素短语。 3. GS是否为OPG？若是，给出(1)中句子的分析过程 。 给每个产生式加标号 SV VT V ViT TF T T+F F)V* F ( 给出(+(i(的规范推导

11、最右推导 S V ViT ViF Vi( Ti( T+Fi( T+( i( F+( i( ( +( i ( 指出句型F+Fi(的短语，句柄，素短语 短语： F+Fi(， F，F+F，( 直接短语 ，( 最左的直接短语为句柄(普通) 素短语： (, F+F 算符优先意义的句柄： ( i F ( T FT+ F GS是否为OPG？ l求所有非终结符的FIRSTVT l求所有非终结符的LASTVT l根据产生式求出所有优先关系： l相等关系 l小于关系：终结符在前，非终结符在后，利用 非终结符的FIRSTVT ； l大于关系：非终结符在前，终结符在后，利用 非终结符的LASTVT ； FIRSTVT

12、和LASTVT FIRSTVT 终结符在前， 非终结符在后 LASTVT 非终结符在前， 终结符在后 S i,+,),( S #S#i,+,*,( S #S# V i,+,),( F)V*i,+,*,( F)V* T +,),( VViT+,(,* VViT F ),(, TT+F*,( TT+F 算符优先关系 i + * ( ) # i + * ( ) # 是算符优先文法 (+(i(的分析过程 步骤 栈 优先关系 当前符号 剩余输入 串 移进或归 约 1 # #( ( (+(i(# 移进 2 #( (+ + (i(# 归约 3 #F #+ + (i(# 移进 4 #F+ +( ( i(# 移

13、进 5 #F+( (i i (# 归约 6 #F+F +i i (# 归约 7 #F #i i (# 移进 8 #Fi i( ( # 移进 9 #Fi( (# # 归约 10 #FiF i# # 归约 11 #F # # 接受 证明下列文法不是LR（0）但是SLR（0） S A A Ab bBa B aAc a aAb 习题 第7题 1.首先拓展文法 S A A Ab A bBa B aAc B a B aAb 2.分解LR（0）项目 S A；S A； A Ab；A Ab；A Ab ； A bBa；AbBa；AbBa；AbBa； B aAc；BaAc；BaAc；BaAc ； B a； B a

14、； B aAb；BaAb；BaAb；BaAb ； 3.构建NFA S AS A B aAcBaAcBaAcBaAc A AbA AbA Ab B aB a A bBaAbBaAbBaAbBa B aAbBaAbBaAbBaAb 1 2 3 45 6 789 10 1112 1314 15 161718 a Ab a aAc A Ab bBa 19 有穷自动机的确定化 abcAB 11,3,67,10,13,152,4 27,10,13,1511,14,16,3, 6 8 32,45 411,14,16,3,6 74,19,17 589 65 778 84,19,175,1812 99 105,

15、18 1112 用LR（0）项目代替DFA状态图 1: S A A Ab A bBa 6: A Ab 7: AbBa 2: AbBa B aAc B a B aAb 10: A Ab BaAb 4: BaAc B a BaAb A Ab A bBa 9: AbBa 11: BaAc 5: AbBa 3: S A A Ab 8: A Ab BaAc BaAb b A a B b b A a Bb c 状态ACTIONGOTO abc#AB 1S23 2S45 3r1S6, r1r1r1 4r5S7, r5r5r58 5S9 6r2r2r2r2 78 8S10S11 9r3r3r3r3 10r2, r6r2, r6r2, r6r2, r6 11r4r4r4r4 ACTION元素有冲突,所以不是LR(0)文法.并且FOLLOW(A)与FOLLOW(B)无交集; 并且,它们的后跟字符集中分别包含a,b,c,#，所以可以确定10号状态的操作。FOLLOW(S)与 b也无交集.并且3和4项目集合中移进项目的符号是b，所以可以确定移进。是SLR(1)文法。 1.S A 2.A Ab 3.A bBa 4.B aAc 5.B a 6.B aAb FOLLOW(A)=#,b,c FOLLOW(B)=a FOLLOW(S)=#