《《编译原理》期末复习资料(完整版)(共14页).doc》由会员分享，可在线阅读，更多相关《《编译原理》期末复习资料(完整版)(共14页).doc（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上1. 给出语言a n b n a mb m | n,m 0的一个上下文无关文法。(6分)解：GS：SAB AaAb | BaBb |2. 给出语言1 n 0 m 1 m0 n | n,m 0的一个上下文无关文法。解：GS：S1S0 | AA0A1 |3. P48 第6题（5）、（6）.画语法树6、已知文法G：:=:=*:=（）i（）i+(i+i)（）i+i*i解：(5)语法树： （6）语法树： 4. P48第13题直接短语等13、 一个上下文无关文法生成句子abbaa的推导树如下：(3)求直接短语解：直接短语有：abP102例题6.1及其分析.( 后加画语法树) 例6
2、.1 设文法GS为：(1)SaAcBe (2)Ab (3)AAb (4)Bd对输入串abbcde#进行分析，检查该符号串是否是GS的句子。解：设一个先进后出的符号符，并把句子左括号“#”号放入栈底，其分析过程如下：步骤符号栈输入符号串动作（1）#abbcde#移进（2）#abbcde#移进（3）#abbcde#归约（Ab）（4）#aAbcde#移进（5）#aAbcde#归约（AAb）（6）#aAcde#移进（7）#aAcde#移进（8）#aAcde#归约（Bd）（9）#aAcBe#移进（10）#aAcBe#归约（SaAcBe）（11）#S#接受语法树如下： 一、 计算分析题（60%）1、正规式
3、 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为初态，
4、A，B为终态，因此有：abABCBBCCA最小化：初始分划得终态组A,B，非终态组C0：A,B，C，对终态组进行审查，判断A和B是等价的，故这是最后的划分。重新命名，以A、C代替A,B、C，因此有：abAACCA即DFA最小化如下：第7题 7、给文法GS：SaA|bQAaA|bB|bBbD|aQQaQ|bD|bDbB|aAEaB|bFFbD|aE|b构造相应的最小的DFA。解：先构造NFA：用子集法将NFA确定化：abSAQAABZBZQDBQDQQDZDZABDAB将S、A、BZ、B、Q、DZ、D重新命名，分别用0、1、2、3、4、5、6表示。因为2、5中含有Z，所以它们为终态。因此有：ab
5、014112246346445513613初始分划得：终态组2,5，非终态组0,1,3,460：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,61：2,5,1,4,0,3,6对0,3,6进行审查：0经过b到达2，3,6经过b到达3,6，故得到新分划0，3,63：得到最后划分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 |T T T * F |F F i |
6、 ( E )(1) 判断是否为LL(1)文法.(2) 构造文法的预测分析表.解：详见P93-96例题。(1) 由于文法中含有左递归，所以必须先消除左递归，使文法变为：ETEE+TE|TFTT*FT|F i | ( E ) FIRST集合如下：FIRST（E）=(,iFIRST（E）=+,FIRST（T）=(,iFIRST（T）=*,FIRST（F）=(,i FOLLOW集合如下：FOLLOW（E）=),#FOLLOW（E）=),#FOLLOW（T）=+,),#FOLLOW（T）=+,),#FOLLOW（F）=+,*,),# 各产生式的SELECT集合如下：SELECT（ETE）=(,iSELE
7、CT（E+TE）=+SELECT（E|）=),#SELECT（TFT）=(,iSELECT（T*FT）=*SELECT（T|）=+,),#SELECT（F i）=i SELECT（F ( E )）=(由上可知有相同左部产生式的SELECT集合的交集为空，故文法是LL(1)文法。（2）构造文法的预测分析表如下：i+*()#ETETEE+TETFTFTT*FTF i ( E )(二) P101 6.(4) 改写下面文法为LL(1)文法，井对每个LL(1)文法构造相应的预测分析表。解：3、自底向上方法已知文法G(E): 0 S E1 E E + T2 E T3 T T * F4 T F5 F ( E
8、 ) 6 F i (1) 证明该文法是SLR(1)文法.(2) 若已给出下面的SLR(1)分析表，试分析句子(i + ( * i )#输入串出错的位置。状态ACTIONGOTOi+*()#ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r53、解：（1）：先分析LR（0）项目：由上可见：I1 ,I2 ,I9 存在移进归约冲突. 分析FOLLOW集：因为：对I1 FOLLOW(S)= # + =对I2FOLLOW(E)= +, #, ) * =对I
9、9FOLLOW(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、(一) 给出语句 if a+b b+c*d then while x*y3 do x:=x-a*b else
10、 while b+c*d10 do b:=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)if t1t3 goto (6)(15)t8=b+t7(5)goto (14)(16)if t810 goto (18)(6)t4=x*y(17)goto (23)(7)if t43 goto (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
11、(14)(23)(二) Whilea0 b0do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻译成四元式序列. (10分)l 解： (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
12、：10T1T3：SRT4：SRA：T2 * T4B：AT5：SRT6：T3 * T5B：T6(1) 画出DAG图；(2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。5(一)、解：(1)DAG：(3分) (2) 优化后的四元式 T3：SR T4：SR A：5*T4 B：T3T4(二) P255-257 DAG图例 试构造以下基本块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)if
13、B=10 goto (1)(1) 画出DAG图；(2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。解：（1）DAG图如下：（2） 四元序列如下： T2：R+r T6：R-r A：6.28* T2 B：A*T6 四、l 1.1 先给出NFA图：画状态转换表:I01ABCDEABBCBDCBEBBDBBDBBCBCBCEBC得DFA如下图：1.4画状态转换表:I01ABCDE01245132424151315由NFA，得DFA如图：l P72第4题（a） 画状态转换表:IIaIbABC00110101011得DFA如下图： 第7题.解：画状态转换表（设G为终态）:IabSAQBGDGDBEFAAQQAAQBEQBGDGDBBDFDG用划分法化简DFA如下：得最简DFA如下图：专心-专注-专业