2014编译原理期末复习资料完整版

1、1.2.给出语言a n b n a mb m | n,m 0的一个上下文无关文法。 解：GS : S ABA aAb |B- aBb|给出语言1 n 0 m 1 m0 n| n,m 0的一个上下文无关文法。3.解： GS : S- 1S0 | AA 0A1 | P48第6题(5)、(6).画语法树6、已知文法G:表达式 := 项 I 表达式+项项:= 因子 I 项*因子因子 :=( 表达式)(5) i+(i+i)(6)解：(5)语法树：I ii+i*i(6)语法树:4.(6分)U表达式A龙因表达式P48第13题直接短语等一个上下文无关文法生成句子abbaa的推导树如下:13、b ba(3)求直

2、接短语解：直接短语有：a bP102例题6.1及其分析.(后加画语法树)例6.1设文法GS为：S aAcBeA bA AbB d对输入串abbcde#进行分析，检查该符号串是否是GS的句子。解：设一个先进后出的符号符，并把句子左括号“#”号放入栈底，其分析过程如下:步骤符号栈输入付号串动作(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)

3、#S#接受语法树如下:(b)计算分析题(60%)DFAf最简1、正规式7 NFAfP72 第 1 题(1 )、(4);第一题1、构造下列正规式相应的DFADFA.（1）1（0|1）*101 解：先构造NFA用子集法将NFA确定化01SAAAABABACABACAABZABZACAB除S, A外，重新命名其他状态，令 AB为B、AC为C、ABZ为D，因为D含有Z （NFA的终态），所以 D为终态，因此有：01SAAABBCBCADDCB得到DFA如下所示:0C b(ab)*|bb)*ab 解：先构造NFA1DP72 第 4 题（a）4、把下图确定化和最小化a解：确定化：用子集法将NFA确定化最小

4、化：初始分划得终态组A,B，非终态组Cn 0: A,B , C，对终态组进行审查，判断代替A,B、C，因此有：A和B是等价的，故这是最后的划分。重新命名，以abAACCA即DFA最小化如下:7、给文法GS: St aA|bQA t aA|bB|bBt bD|aQ Qt aQ|bD|bDt bB|aAEt aB|bFFt bD|aE|bDFA。NFA :构造相应的最小的 解：先构造abSAQAABZBZQDBQDQQDZDZABDAB将S、A、BZ、B、Q、DZ、D重新命名，分别用0、1、2、3、4、5、6表示。因为2、5中含有Z,所以它们为终态。因此有：ab014112246346445513

5、初始分划得：终态组2,5,非终态组 0,1,3,46n 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,60经过b到达 2, 3,6经过b到达 3,6,故得到新分划 0, 3,6,1,4 , 2,5 , 3,6,D分别代替0 , 1,4 , 2,5 , 3,6,其中A为始态，C为终态，可得到最小 DFAn 1: 2,5 , 1,4 , 0,3,6 对 0,3,6进行审查： n 3：得到最后划分0, 重新命名，以A, B, C, 如下：=(,i(E) =+, (T) =(,i(T)

6、=*, =(,i2、自顶向下方法(一)设文法G(E):E7 E + T | TT7 T*F|FF7 i | ( E )判断是否为LL(1)文法.构造文法的预测分析表.解：详见P93-96例题。(1)由于文法中含有左递归，所以必须先消除左递归，使文法变为:E7T EE 7 +TE| T7 FTT 7 *FT| 1 i 1( E)FIRST 集合如下:FIRSTFIRSTFIRSTFIRSTFOLLOW集合如下:FIRSTFOLLOVy E) =),#FOLLOVy E) =),#FOLLOy T) =+,),#FOLLOVy T) =+,),#SELECT集合如下： (EtTE ) =(,i (

7、Ef +TE) =+ (EJ| s ) =),# (TtFT) =(,i (Tt *FT ) =* (Tt| s ) = +,),# (Ft i ) =i (Ft ( E )=(FOLLOVy F) =+,*,),# 各产生式的SELECTSELECTSELECTSELECTSELECTSELECTSELECTi+*()#EtT EtT EEt +TET sT sTt FTt FTTT st *FTT sT sFt it ( E )SELECT由上可知有相同左部产生式的SELECT集合的交集为空，故文法是LL(1)文法。(2)构造文法的预测分析表如下：(二)P101 6.(4)改写下面文法为L

8、L(1)文法，井对每个 LL(1)文法构造相应的预测分析表。Sfi|(E)EfE+S|ES|S解：首先为各非终结符构造集与FOWOW熱 但因为产生式-+Sl-SlJ存在左递归. 故第一步先消除之.写为：EtSE此时产生式已无左递归.可以开始写出EWW集与FOLLOW弟了.F/lS7XS)=(i.(=刚W7WfZmF)=+, -t e)FOLLOW(S)=+,- #F0Z3W( (由此可以写出预测分析表”rIC)+ -#sC)SEE FhJ-$F3、自底向上方法已知文法G(E):0 S t e1Et E + T23Tt T * F45Ft ( E )(1)证明该文法是SLR(1)文法Et tTt

9、 FFt i输入串出错的位置。(2)若已给出下面的SLR(1)分析表，试分析句子(i + ( * i )#状态ACTIONGOTOi+*()#ETF0S5S41231sacc2r 2S223r44r 444SS4823566r 666S5S4937S5S4108S6S1191Sr 111033r 331155r 553、解：(1):先分析LR(0)项目:la：EE-* E4-T Ei TTT*F Ti F Ff (E)Ff * iIll SJE- EfE +TJI扪 Tf F(TI4； F-*( E i E+T Ei TTf-T*FTfF Ff CE Fi+Ifii Ef E+ * TTi T

10、*FTi F(E)切 F-*CE Ef E +TIll； Ff CE I萨 EfE+丁- _Tf T *FI护 Tf T F */?! TfT* * F F+(E Ffi由上可见:IIS- E, Ef E.+T12E T# T-* T,+ F19L E+T, T-*K*FI 1 ,I 2 ,I 9 因为：对对对存在移进一归约冲突.分析FOLLOW 集:I1I2I9FOLLOW( S )= # n + =FOLLOW(E)= +, #, ) n * = FOLLOW(E)= +, #, ) n * =所以是SLR(1)文法。(2):STE PSX(i + ( * i ) #actio ngoto

11、10#(i + ( * i ) #S4204# (i + ( * i ) #S53045# (i+ ( * i ) #r 634043# (F+ ( * i ) #r425042# (T+ ( * i ) #r 286048# (E+ ( * i ) #S670486# (E+(* i ) #S4804864# (E+ (* i ) #errorthen while x*y3 do x:=x相应的三地址代码.-a*b else4、(一)给出语句 if a+b b+c*d while b+c*d10 do b:=b-(x*y+5)(1)t1=a+b(12)goto (6)(2)t2=c*d(13

12、)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)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 (14)(23)(二)Whilea 0 V b 0 then a：= a- 1else b：= b + 1End;翻译成四元式序列解：.(10 分)a,

13、0,(j ,(j，(j , a , 0,(j,(- , a, 1,(:= , T2 ,(j,(+ , b , 1,T3)(:= , T3 , , b)(j, , ,1)(15)5)3),5)15)T1),X)9)12)T2),a),1)5、（一）设有基本块（10分）T1：=2T2：=10/ T1T3：=S- RT4：=S+ RA:B:T5：=A=S+ RT6：B:(1)=T3 * T 5=16画出DAG图；假设基本块出口时只有A, B还被引用，请写出优化后的四元序列。5( 一)、解：(1)DAG:(3分)(2) 优化后的四元式T3：=S RT4：=S+ RA:=5*T4B:=T3+ T4(二)P255-257 DAG 图例试构造以下基本块 G的DAG(1)(8)(9)T0：= 3.14Ti：= 2* ToT2：A:B:T3：T4：T5：T6：=R+r=2* To=R+r=T3 * T 4=R-r=T5 *T6(1)解:B:if B=10 goto (1)画出DAG图；假设基本块出口时只有 A, B还被引用，请