编译原理习题课.ppt
习题课令文法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*FEE+TT*F一个上下文无关文法生成的句子abbaa的推导树如图。（1）给出该句子的相应的最左推导和最右推导（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有的短语、简单短语、句柄。SABSaBSaSBBS aBBS abBSabbSabbAaabbaa最左推导最右推导略产生式集合：SABSBSBBSAaSBbAa短语、句柄SABSaSBBAabba习题解答7给文法GS：SaA|bQAaA|bB|bBbD|aQQaQ|bD|bDbB|aAE EaB|bFaB|bFF FbD|aE|bbD|aE|bl构造相应的最小的DFA。l由于从S出发任何输入串都不能到达状态E和F，所以，状态E，F为多余的状态，不予考虑。aZSADQBbbbababbbaa简化产生式后生成的NFAIIa =-closure(MoveTo(I,a)Ib =-closure(MoveTo(I,b)1 1S2 2A3Q2 2A2 2A4B,Z3Q3Q5D,Z4B,Z3Q6D5D,Z2A7B6 6D2 2A7B7B3Q6Dl因为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四个状态.a62baa1babb4最小化的DFA124376abbaa5babababba8.给出下述文法所对应的正规式给出下述文法所对应的正规式lS0A|1BlA1S|1lB0S|0l将 A1S|1 和 B0S|0 分别代入 S0A|1B 得:nS=01S|01nS=10S|10l得产生式:S=01S|10S|01|10 化简得:lS=(01|10)S|(01|10)lS=(01|10)*(01|10)得正规式:l(01|10)*(01|10)9.9.将图将图4.184.18的的DFADFA最小化，并用正规式描述它所识别的语言：最小化，并用正规式描述它所识别的语言：a72bcbdb134c6aabbd5bl因为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)=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。abb13c6bd5a最小化后的DFA该DFA用正规式表示为：b*a(c|da)*bb*习题解答习题解答2对下面的文法G：ETEE+E|TFTTT|FPFF*F|P(E)|a|b|l计算这个文法的每个非终结符的FIRST集和FOLLOW集。l证明这个方法是LL(1)的。l构造它的预测分析表。1.S为文法开始符号，#一定是FOLLOW（S）元素2.设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*,(,a,b,+,),#P(,a,b,*,(,a,b,+,),#计算每个非终结符的FIRST集合lFIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;lFIRST(E)=+,lFIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;lFIRST(T)=FIRST(T)=(,a,b,;lFIRST(F)=FIRST(P)=(,a,b,;lFIRST(F)=FIRST(P)=*,;lFIRST(P)=(,a,b,;计算每个非终结符的FOLLOW集合lFOLLOW(E)=),#;lFOLLOW(E)=FOLLOW(E)=),#;lFOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;/不包含lFOLLOW(T)=FOLLOW(T)=FIRST(E)FOLLOW(E)=+,),#;lFOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;/不包含lFOLLOW(F)=FOLLOW(F)=FIRST(T)FOLLOW(T)=(,a,b,+,),#;lFOLLOW(P)=FIRST(F)FOLLOW(F)=*,(,a,b,+,),#;/不包含 l在求在求FOLLOWFOLLOW集合时集合时,要特别注意要特别注意P76P76页的定义页的定义:A A B B,FOLLOW(B),FOLLOW(B)包含包含 的的FIRSTFIRST元素元素,如果如果*,则则FOLLOW(A)FOLLOW(A)的元素就要加入到的元素就要加入到FOLLOW(B)FOLLOW(B)中。中。证明这个方法是LL(1)的 lSELECT(ETE/)=FIRST(T)=(,a,b,;lSELECT(E+E)=+;lSELECT(E)=FOLLOW(E/)=),#lSELECT(TFT)=FIRST(F)=(,a,b,;lSELECT(TT)=FIRST(T)=(,a,b,;lSELECT(T)=FOLLOW(T/)=+,),#;lSELECT(FPF)=FIRST(P)=(,a,b,;lSELECT(F*F)=*;lSELECT(F)=FOLLOW(F/)=(,a,b,+,),#;lSELECT(P(E)=(lSELECT(Pa)=alSELECT(Pb)=blSELECT(P)=预测分析表+*()a ab b#E ETETETETEE E+ET TFTFTFTFTT TTTTTF FPFPFPFPFF F*FP 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(+(i(的规范推导的规范推导最右推导最右推导S V ViT ViF Vi(Ti(T+Fi(T+(i(F+(i(+(i(指出句型指出句型F+Fi(F+Fi(的短语，句柄，素短语的短语，句柄，素短语短语：F+Fi(，F，F+F，(直接短语，(最左的直接短语为句柄(普通)素短语：(,F+F算符优先意义的句柄：(iF(TFT+FGSGS是否为是否为OPGOPG？l求所有非终结符的FIRSTVTl求所有非终结符的LASTVTl根据产生式求出所有优先关系：l相等关系l小于关系：终结符在前，非终结符在后，利用非终结符的FIRSTVT；l大于关系：非终结符在前，终结符在后，利用非终结符的LASTVT；FIRSTVT和和LASTVT FIRSTVT FIRSTVT 终结符在前，非终结符在后LASTVT LASTVT 非终结符在前，终结符在后S S i,+,),(i,+,),(S#S#i,+,*,(i,+,*,(S#S#V V i,+,),(i,+,),(F)V*i,+,*,(i,+,*,(F)V*T T+,),(+,),(VViT+,(,*+,(,*VViTF F),(,),(,TT+F*,(*,(TT+F算符优先关系算符优先关系 i i+*()#i i +*()#是算符优先文法是算符优先文法(+(i(+(i(的分析过程的分析过程 步骤步骤 栈栈 优先关系优先关系 当前符号当前符号 剩余输入剩余输入串串 移进或归移进或归约约 1 1#(#(+(i(#(+(i(#移进移进 2 2#(#(+(+(i(#(i(#归约归约 3 3#F#F#+#+(i(#(i(#移进移进 4 4#F+#F+(+(i(#i(#移进移进 5 5#F+(#F+(i(i i i(#(#归约归约 6 6#F+F#F+F+i+i i i(#(#归约归约 7 7#F#F#i#i i i(#(#移进移进 8 8#Fi#Fi i(i(#移进移进 9 9#Fi(#Fi(#(#归约归约 10 10#FiF#FiF i#i#归约归约 11 11#F#F#接受接受 证明下列文法不是LR（0）但是SLR（0）S AA Ab bBaB aAc a aAb习题 第7题1.首先拓展文法S AA AbA bBaB aAcB aB aAb2.分解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.构建NFAS AS AB aAcBaAcBaAcBaAcA AbA AbA AbB aB a A bBaAbBaAbBaAbBaB aAbBaAbBaAbBaAb123456789101112131415161718aAbaaAcAAbbBa19有穷自动机的确定化abcAB11,3,67,10,13,152,427,10,13,1511,14,16,3,6832,45411,14,16,3,674,19,175896577884,19,175,181299105,181112用LR（0）项目代替DFA状态图1:S AA AbA bBa6:A Ab7:AbBa2:AbBaB aAcB aB aAb10:A AbBaAb4:BaAcB a BaAbA AbA bBa9:AbBa11:BaAc5:AbBa3:S AA Ab8:A AbBaAcBaAbbAaBbbAaBbc状态ACTIONGOTOabc#AB1S232S453r1S6,r1r1r14r5S7,r5r5r585S96r2r2r2r2788S10S119r3r3r3r310r2,r6r2,r6r2,r6r2,r611r4r4r4r4ACTION元素有冲突,所以不是LR(0)文法.并且FOLLOW(A)与FOLLOW(B)无交集;并且,它们的后跟字符集中分别包含a,b,c,#，所以可以确定10号状态的操作。FOLLOW(S)与b也无交集.并且3和4项目集合中移进项目的符号是b，所以可以确定移进。是SLR(1)文法。1.S A2.A Ab3.A bBa4.B aAc5.B a6.B aAbFOLLOW(A)=#,b,cFOLLOW(B)=aFOLLOW(S)=#
