编译原理习题课.

习题课令文法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→SBBS→AaS→B→bA→a短语、句柄SABSaSBBAabba习题解答7．给文法G[S]：–SaA|bQ–AaA|bB|b–BbD|aQ–QaQ|bD|b–DbB|aA–EaB|bF–FbD|aE|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[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|1BA1S|1B0S|0将A1S|1和B0S|0分别代入S0A|1B得:S=01S|01S=10S|10得产生式:S=01S|10S|01|10化简得:S=(01|10)S|(01|10)S=(01|10)*(01|10)得正规式:(01|10)*(01|10)9.将图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等价，所以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|da)*bb*习题解答2．对下面的文法G：ETE’E’+E|εTFT’T’T|εFPF’F’*F’|εP(E)|a|b|^计算这个文法的每个非终结符的FIRST集和FOLLOW集。证明这个方法是LL(1)的。构造它的预测分析表。1.S为文法开始符号，#一定是FOLLOW（S）元素2.设AB是一个产生式，则First()的非空元素属于FOLLOW（B）如果*ε，则FOLLOW（A）的元素就要加入到FOLLOW（B）中，因为：•D1A1•A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集合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(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,^,+,),#};FOLLOW(P)=FIRST(F’)∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε在求FOLLOW集合时,要特别注意P76页的定义:AB,FOLLOW(B)包含的FIRST元素,如果*ε,则FOLLOW(A)的元素就要加入到FOLLOW(B)中。证明这个方法是LL(1)的SELECT(ETE/)=FIRST(T)={(,a,b,^};SELECT(E‘+E)={+};SELECT(E’ε)=FOLLOW(E/)={),#}SELECT(TFT‘)=FIRST(F)={(,a,b,^};SELECT(T‘T)=FIRST(T)={(,a,b,^};SELECT(T’ε)=FOLLOW(T/)={+,),#};SELECT(FPF’)=FIRST(P)={(,a,b,^};SELECT(F‘*F‘)={*};SELECT(F’ε)=FOLLOW(F/)={(,a,b,^,+,),#};SELECT(P(E))={(}SELECT(Pa)={a}SELECT(Pb)={b}SELECT(P^)={^}预测分析表+*()ab^#ETE‘TE’TE‘TE’E’+EεεTFT‘FT’FT‘FT’T‘εTεTTTεFPF‘PF’PF‘PF’F’ε*F‘εεεεεεP(E)ab^习题.第3题•有文法G[S]：S’#S#SVVT|ViTTF|T+FF)V*|(1.给出(+(i(的规范推导。2.指出句型F+Fi(的短语，句柄，素短语。3.G[S]是否为OPG？若是，给出(1)中句子的分析过程。给每个产生式加标号•SV［１］•VT［２］•VViT［３］•TF［４］•TT+F［５］•F)V*［６］•F(［７］给出(+(i(的规范推导——最右推导•SV［１］ViT［２］ViF［４］Vi(［７］T［２］i(T+F［５］i(T+(［７］i(F［４］+(i((［７］+(i(指出句型F+Fi(的短语，句柄，素短语•短语：F+Fi(，F，F+F，(•直接短语Ｆ，(•最左的直接短语为句柄(普通)Ｆ•素短语：(,F+F•算符优先意义的句柄：(ＳＶiＶF(TFT+FG[S]是否为OPG？求所有非终结符的FIRSTVT求所有非终结符的LASTVT根据产生式求出所有优先关系：相等关系小于关系：终结符在前，非终结符在后，利用非终结符的FIRSTVT；大于关系：非终结符在前，终结符在后，利用非终结符的LASTVT；FIRSTVT和LASTVTFIRSTVT终结符在前，非终结符在后LASTVT非终结符在前，终结符在后Si,+,),(S’#S#i,+,*,(S’#S#Vi,+,),(F)V*i,+,*,(F)V*T+,),(VViT+,(,*VViTF),(,TT+F*,(TT+F算符优先关系i+*()#i≯≮≯≮≮≯+≯≯≯≮≮≯*≯≯≯≯(≯≯≯≯)≮≮≡≮≮#≮≮≮≮≡是算符优先文法(+(i(的分析过程步骤栈优先关系当前符号剩余输入串移进或归约1##≮(((+(i(#移进2#((≯++(i(#归约3#F#≮++(i(#移进4#F++≮((i(#移进5#F+((≯ii(#归约6#F+F+≯ii(#归约7#F#≮ii(#移进8#Fii≮((#移进9#Fi((≯##归约10#FiFi≯##归约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→aAb2.分解LR（0）项目•S→·A；S→A·；•A→·Ab；A→A·b；A→Ab·；•A→·bBa；A→b·Ba；A→bB·a；A→bBa·；•B→·aAc；B→a·Ac；B→aA·c；B→aAc·；•B→·a；B→a·；•B→·aAb；B→a·Ab；B→aA·b；B→aAb·；3.构建NFAS→·AS→A·B→·aAcB→a·AcB→aA·cB→aAc·A→·AbA→A·bA→Ab·B→·aB→a·A→·bBaA→b·BaA→bB·aA→bBa·B→·aAbB→a·AbB→aA·bB→aAb·123456789101112131415161718aAbaaAcAAbbBaεεεεεεεεεεε19有穷自动机的确定化abcAB1{1,3,6}{7,10,13,15}{2,4}2{7,10,13,15}{11,14,16,3,6}{8}3{2,4}{5}4{11,14,16,3,6}{7}{4,19,17}5{8}{9}6{5}7{7}{8}8{4,19,17}{5,18}{12}9{9}10{5,18}11{12}用LR（0）项目代替DFA状态图1:S→·AA→·AbA→·bBa6:A→Ab·7:A→b·Ba2:A→b·BaB→·aAcB→·aB→·aAb10:A→Ab·B→aAb·4:B→a·AcB→a·B→a·AbA→·AbA→·bBa9:A→bBa·11:B→aAc·5:A→bB·a3:S→A·A→A·b8:A→A·bB→aA·cB→aA·bbAaBbbAaBbc状态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,c}FOLLOW(B)={a}FOLLOW(S)={#}