《编译原理习题课.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最左推导最右推导略产生式集合：SABSBSBBSAaSBbAa短语、句柄,S,A,B,S,a,S,B,B,A,
2、a,b,b,a,习题解答,7给文法GS：SaA|bQAaA|bB|bBbD|aQQaQ|bD|bDbB|aAEaB|bFFbD|aE|b构造相应的最小的DFA。,由于从S出发任何输入串都不能到达状态E和F，所以，状态E，F为多余的状态，不予考虑。,简化产生式后生成的NFA,因为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四个状态.,最小化的DFA,1,2,4,3,7,6,a,b,b,a,a,5,b,a,b,
3、a,b,a,b,b,a,8.给出下述文法所对应的正规式,S0A|1BA1S|1B0S|0将 A1S|1 和 B0S|0 分别代入 S0A|1B 得:S=01S|01S=10S|10得产生式:S=01S|10S|01|10 化简得:S=(01|10)S|(01|10)S=(01|10)*(01|10)得正规式:(01|10)*(01|10),将图4.18的DFA最小化，并用正规式描述它所识别的语言：,因为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)=
4、F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,而6，7等价，所以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。,最小化后的DFA,该DFA用正规式表示为：b*a(c|da)*bb*,习题解答,2对下面的文法G：ETEE+E|TFTTT|FPFF*F|P(E)|a|b|计算这个文法的每个非终结符的FIRST集和FOLLOW集。证明这个方法是LL(1)的。构造它的预
5、测分析表。,S为文法开始符号，#一定是FOLLOW（S）元素设A B是一个产生式，则First()的非空元素属于FOLLOW（B）如果*，则FOLLOW（A）的元素就要加入到FOLLOW（B）中，因为：D 1A1A B两个产生式，在推导过程中，可能会出现这样的句型S*1A1*1B1*1B1,计算每个非终结符的FIRST和FOLLOW集合,计算每个非终结符的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,;
6、FIRST(F)=FIRST(P)=(,a,b,;FIRST(F)=FIRST(P)=*,;FIRST(P)=(,a,b,;,计算每个非终结符的FOLLOW集合,FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含FOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包含FOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;FOLLO
7、W(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 在求FOLLOW集合时,要特别注意P76页的定义:A B,FOLLOW(B)包含的FIRST元素,如果*,则FOLLOW(A)的元素就要加入到FOLLOW(B)中。,证明这个方法是LL(1)的,SELECT(ETE/)=FIRST(T)=(,a,b,;SELECT(E+E)=+;SELECT(E)=FOLLOW(E/)=),#SELECT(TFT)=FIRST(F)=(,a,b,;SELECT(TT)=FIRST(T)=(,a,b,;SELECT(T)=FOLLOW(T/)=+,),#;SELECT(FPF)=
8、FIRST(P)=(,a,b,;SELECT(F*F)=*;SELECT(F)=FOLLOW(F/)=(,a,b,+,),#;SELECT(P(E)=(SELECT(Pa)=aSELECT(Pb)=bSELECT(P)=,预测分析表,习题.第3题,有文法GS：S#S#SV VT|ViT TF|T+F F)V*|(给出(+(i(的规范推导。指出句型F+Fi(的短语，句柄，素短语。GS是否为OPG？若是，给出(1)中句子的分析过程。,给每个产生式加标号,SV VT V ViT TF T T+F F)V*F(,给出(+(i(的规范推导最右推导,S V ViT ViF Vi(Ti(T+Fi(T+(i(
9、F+(i(+(i(,指出句型F+Fi(的短语，句柄，素短语,短语：F+Fi(，F，F+F，(直接短语，(最左的直接短语为句柄(普通)素短语：(,F+F算符优先意义的句柄：(,GS是否为OPG？,求所有非终结符的FIRSTVT求所有非终结符的LASTVT根据产生式求出所有优先关系：相等关系小于关系：终结符在前，非终结符在后，利用非终结符的FIRSTVT；大于关系：非终结符在前，终结符在后，利用非终结符的LASTVT；,FIRSTVT和LASTVT,算符优先关系,是算符优先文法,(+(i(的分析过程,证明下列文法不是LR（0）但是SLR（0）,S AA Ab bBaB aAc a aAb,习题 第
10、7题,1.首先拓展文法,S AA AbA bBaB aAcB aB 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；B aAb；BaAb；BaAb；BaAb；,3.构建NFA,S A,S A,B aAc,BaAc,BaAc,BaAc,A Ab,A Ab,A Ab,B a,B a,A bBa,AbBa,AbBa,AbBa,B aAb,BaAb,BaAb,BaAb,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,a,A,b,a,
11、a,A,c,A,A,b,b,B,a,19,有穷自动机的确定化,用LR（0）项目代替DFA状态图,1:S AA AbA bBa,6:A Ab,7:AbBa,2:AbBaB aAcB aB aAb,10:A AbBaAb,4:BaAcB a BaAbA AbA bBa,9:AbBa,11:BaAc,5:AbBa,3:S AA Ab,8:A AbBaAcBaAb,b,A,a,B,b,b,A,a,B,b,c,ACTION元素有冲突,所以不是LR(0)文法.并且FOLLOW(A)与FOLLOW(B)无交集;并且,它们的后跟字符集中分别包含a,b,c,#，所以可以确定10号状态的操作。FOLLOW(S)与b也无交集.并且3和4项目集合中移进项目的符号是b，所以可以确定移进。是SLR(1)文法。,S AA AbA bBaB aAcB aB aAb,FOLLOW(A)=#,b,c,FOLLOW(B)=a,FOLLOW(S)=#,
