《编译原理》期末复习资料(完整版)

1.给出语言{anbnambm|n,m≥0}的一个上下文无关文法。(6分)解：G[S]：S—ABA—aAb|εB—aBb|ε2.给出语言{1n0m1m0n|n,m≥0}的一个上下文无关文法。解：G[S]：S—1S0|AA—0A1|ε3.P48第6题（5）、（6）.画语法树6、已知文法G：表达式::=项｜表达式＋项项::=因子｜项*因子因子::=（表达式）｜i（５）i+(i+i)（６）i+i*i解：(5)语法树：（6）语法树：4.P48第13题直接短语等13、一个上下文无关文法生成句子abbaa的推导树如下：(3)求直接短语解：直接短语有：aεbP102例题6.1及其分析.(后加画语法树)例6.1设文法G[S]为：(1)S—aAcBe(2)A—b(3)A—Ab(4)B—d对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。解：设一个先进后出的符号符，并把句子左括号“#”号放入栈底，其分析过程如下：步骤符号栈输入符号串动作（1）#abbcde#移进（2）#abbcde#移进（3）#abbcde#归约（A—b）（4）#aAbcde#移进（5）#aAbcde#归约（A—Ab）（6）#aAcde#移进（7）#aAcde#移进（8）#aAcde#归约（B—d）（9）#aAcBe#移进（10）#aAcBe#归约（S—aAcBe）（11）#S#接受语法树如下：一、计算分析题（60%）1、正规式→NFA→DFA→最简DFAP72第1题（1）、（4）；第一题1、构造下列正规式相应的DFA.（1）1(0|1)*101解：先构造NFA用子集法将NFA确定化01SAAAABABACABACAABZABZACAB除S，A外，重新命名其他状态，令AB为B、AC为C、ABZ为D，因为D含有Z（NFA的终态），所以D为终态,因此有：01SAAABBCBCADDCB得到DFA如下所示：(4)b((ab)*|bb)*ab解：先构造NFA得到DFA如下所示：P72第4题（a）4、把下图确定化和最小化解：确定化：用子集法将NFA确定化ab00110101110重新命名，以Ａ、Ｂ、Ｃ代替{0}、{01}、{1}，其中A为初态，A，B为终态，因此有：abABCBBCCA最小化：：初始分划得终态组{A,B}，非终态组{C}Π0：{A,B}，{C}，对终态组进行审查，判断A和B是等价的，故这是最后的划分。重新命名，以A、C代替{A,B}、{C}，因此有：abAACCA即DFA最小化如下：第7题7、给文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b构造相应的最小的DFA。解：先构造NFA：用子集法将NFA确定化：abSAQAABZBZQDBQDQQDZDZABDAB将S、A、BZ、B、Q、DZ、D重新命名，分别用0、1、2、3、4、5、6表示。因为2、5中含有Z，所以它们为终态。因此有：ab014112246346445513613初始分划得：终态组｛2,5｝，非终态组｛0,1,3,46｝Π0：｛2,5｝,｛0,1,3,4,6｝对｛0,1,3,4,6｝进行审查：{1,4}输入b到达｛2,5｝，而{0,3,6}输入b到达｛3,4,6｝，故得到新分划｛1,4｝,｛0,3,6｝Π1：｛2,5｝,｛1,4｝,｛0,3,6｝对｛0,3,6｝进行审查：{0}经过b到达｛2｝，{3,6}经过b到达｛3,6｝，故得到新分划｛0｝，｛3,6｝Π3：得到最后划分{0}，{1,4}，{2,5}，{3,6}重新命名，以A，B，C，D分别代替{0}，{1,4}，{2,5}，{3,6},其中A为始态，C为终态，可得到最小DFA如下：2、自顶向下方法(一)设文法G(E)：E→E+T|TT→T*F|FF→i|(E)(1)判断是否为LL(1)文法.(2)构造文法的预测分析表.解：详见P93-96例题。(1)由于文法中含有左递归，所以必须先消除左递归，使文法变为：E→TE`E`→+TE`|εT→FT`T`→*FT`|εF→i|(E)FIRST集合如下：FIRST（E）={(,i}FIRST（E`）={+,ε}FIRST（T）={(,i}FIRST（T`）={*,ε}FIRST（F）={(,i}FOLLOW集合如下：FOLLOW（E）={),#}FOLLOW（E`）={),#}FOLLOW（T）={+,),#}FOLLOW（T`）={+,),#}FOLLOW（F）={+,*,),#}各产生式的SELECT集合如下：SELECT（E→TE`）={(,i}SELECT（E`→+TE`）={+}SELECT（E`→|ε）={),#}SELECT（T→FT`）={(,i}SELECT（T`→*FT`）={*}SELECT（T`→|ε）={+,),#}SELECT（F→i）={i}SELECT（F→(E)）={(}由上可知有相同左部产生式的SELECT集合的交集为空，故文法是LL(1)文法。（2）构造文法的预测分析表如下：i+*()#E→TE`→TE`E`→+TE`→ε→εT→FT`→FT`T`→ε→*FT`→ε→εF→i→(E)(二)P1016.(4)改写下面文法为LL(1)文法，井对每个LL(1)文法构造相应的预测分析表。解：3、自底向上方法已知文法G(E):[0]S'→E[1]E→E+T[2]E→T[3]T→T*F[4]T→F[5]F→(E)[6]F→i(1)证明该文法是SLR(1)文法.(2)若已给出下面的SLR(1)分析表，试分析句子(i+(*i))#输入串出错的位置。状态ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r53、解：（1）：先分析LR（0）项目：由上可见：I1,I2,I9存在移进—归约冲突.分析FOLLOW集：因为：对I1FOLLOW(S’)={#}∩{+}=ф对I2FOLLOW(E)={+,#,)}∩{*}=ф对I9FOLLOW(E)={+,#,)}∩{*}=ф所以是SLR(1)文法。（2）：STEPSX(i+(*i)#actiongoto10#(i+(*i)#S4204#(i+(*i)#S53045#(i+(*i)#r634043#(F+(*i)#r425042#(T+(*i)#r286048#(E+(*i)#S670486#(E+(*i)#S4804864#(E+(*i)#error4、(一)给出语句ifa+bb+c*dthenwhilex*y3dox:=x-a*belsewhileb+c*d10dob:=b-(x*y+5)相应的三地址代码.(1)t1=a+b(12)goto(6)(2)t2=c*d(13)goto(23)(3)t3=b+t2(14)t7=c*d(4)ift1t3goto(6)(15)t8=b+t7(5)goto(14)(16)ift810goto(18)(6)t4=x*y(17)goto(23)(7)ift43goto(9)(18)t9=x*y(8)goto(13)(19)t10=t9+5(9)t5=a*b(20)t11=b-t10(10)t6=x-t5(21)b=t11(11)x=t6(22)goto(14)(23)(二)Whilea＞0∨b＜0doBeginX：＝X＋1；ifa＞0thena：＝a－1elseb：＝b＋1End；翻译成四元式序列.(10分)解：(1)(j＞，a，0，5)(2)(j，＿，＿，3)(3)(j＜，b，0，5）(4)(j，＿，＿，15)(5)(＋，x，1，T1)(6)(:=，T1，＿，x)(7)(j＞，a，0，9)(8)(j，＿，＿，12)(9)(－，a，1，T2)(10)(:=，T2，＿，a)(11)(j，＿，＿，1)(12)(＋，b，1，T3)(13)(:=，T3，＿，b)(14)(j，＿，＿，1)(15)5、(一)设有基本块(10分)T1：＝2T2：＝10∕T1T3：＝S－RT4：＝S＋RA：＝T2*T4B：＝AT5：＝S＋RT6：＝T3*T5B：＝T6(1)画出DAG图；(2)假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。5(一)、解：(1)DAG：(3分)(2)优化后的四元式T3：＝S－RT4：＝S＋RA：＝5*T4B：＝T3＋T4(二)P255-257DAG图例试构造以下基本块G的DAG(1)T0：＝3.14(2)T1：＝2*T0(3)T2：＝R+r(4)A：＝T1*T2(5)B：＝A(6)T3：＝2*T0(7)T4：＝R+r(8)T5：＝T3*T4(9)T6：＝R-r(10)B：＝T5*T6(11)ifB=10goto(1)(1)画出DAG图；(2)假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。解：（1）DAG图如下：（2）四元序列如下：○1T2：＝R+r○2T6：＝R-r○3A：＝6.28*T2○4B：＝A*T6四、1.1先给出NFA图：画状态转换表:I01ABC'D'E'ABBCBDCBEBBDBBDBBCBCBCEBC得DFA如下图：1.4画状态转换表:I01ABCDE01245132424151315由NFA，得DFA如图：P72第4题（a）画状态转换表:IIaIbABC00110101011得DFA如下图：第7题.解：画状态转换表（设G为终态）:IabSAAAQBG用划分法化简DFA如下：得最简DFA如下图：QBGDGDBEFQQAAQBEDGDBBDFDG