《编译原理》期末复习资料要点

1、1. 给出语言a b a b |n,m 0的一个上下文无关文法。（6分）解：GS : S ABA aAb| £B aBb| £2 .给出语言1 n 0mlm0n |n,m 0的一个上下文无关文法。解： GS : S- 1S0|AA- 0A1 | e3 .P48第6题（5）、（6）.画语法树6、已知文法G:表达式 := 项| 表达式+ 项项:= 因子|项*因子因子 :=（表达式）I i（5 ） i+（i+i）（ 6） i+i*i解：（5）语法树：（6）语法树：表达式）ZbxN表达式二 十 项表达式;表达式,+ 项abbaa的推导树如下:4.P48第13题直接短语等13、 一个

2、上下文无关文法生成句子b ba（3）求直接短语解：直接短语有：a £ bP102例题6.1及其分析.(后加画语法树)例6.1设文法GS为：(1)S >aAcBe(2)A >b(3)A >Ab(4)B >d对输入串abbcde#进行分析，检查该符号串是否是GS的句子。解：设一个先进后出的符号符，并把句子左括号“#”号放入栈底，其分析过程如下:步骤符号栈输入符号串动作(1)#abbcde#移进(2)#abbcde#移进(3)#abbcde#归约(A >b)(4)#aAbcde#移进(5)#aAbcde#归约(A >Ab)(6)#aAcde#移进#aAc

3、de#移进(8)#aAcde#归约(B >d)(9)#aAcBe#移进(10)#aAcBe#归约(S >aAcBe)(11)#S#接受语法树如下:AA4/a babb(4)(6)(a)(b)一、计算分析题(60%)1、正规式 一 NFA一 DFA一 最简 P72 第 1 题(1)、(4);第一题1、构造卜列正规式相应的a b beda b b c d e(9)(11)(c)(d)DFADFA.(1) 1(0|1)*101解：先构造NFA用子集法将NFA确定化01SAAAABABACABACAABZABZACAB除S, A外，重新命名其他状态，令 AB为B、AC为C、ABZ为D,因为

4、D含有Z （NFA的终态），所以D为终态，因此有:01SAAABBCBCADDCB得到DFA如下所示:(4) b(ab)*|bb)*ab解：先构造NFA得到DFA如下所示:P72 第 4 题（a）4、把下图确定化和最小化解：确定化:用子集法将NFA确定化ab00110101110重新命名，以A、B、C代替 0、01、1,其中A为初态，A, B为终态，因此有:abABCBBCCA最小化:初始分划得终态组A,B,非终态组CA和B是等价的，故这是最后的划分。重新命名，以A、Cno： A,B , C,对终态组进行审查，判断代替A,B、C,因此有:abAACCA即DFA最小化如下:第7题7、给文法GS:

5、 S-aA|bQ AfaA|bB|bBfbD|aQQfaQ|bD|bDfbB|aAE-aB|bF FfbD|aE|b构造相应的最小的 DFA。 解：先构造NFA:用子集法将NFA确定化:abSAQAABZBZQDBQDQQDZDZABDAB将S、A、BZ、B、Q、DZ、D重新命名，分别用0、1、2、3、4、5、6表示。因为2、5中含有Z,所以它们为终态。因此有：ab014112246346445513初始分划得：终态组 2,5,非终态组 0,1,3,46no： 2,5 , 0,1,3,4,61,4对0,1,3,4,6进行审查：1,4输入b到达 2,5,而0,3,6输入b到达 3,4,6,故得到

6、新分划 0,3,6m： 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,6DFA重新命名，以A, B, C, D分别代替0 , 1,4 , 2,5 , 3,6,其中A为始态，C为终态，可得到最小 如下：2、自顶向下方法(一)设文法G(E):E + T | TT- T * F| FF - i | ( E )(1)判断是否为LL(1)文法.(2)构造文法的预测分析表.解：详见P93-96例题。(1)由于文法中含有左递归，所以必须先消除左递归，使文法变为:T E&#

7、39;E'f+TE'| £Tf FT'T'一*FT'| £F - i I ( E )FIRST 集合如下：FIRST (E) =(,iFIRST (E') =+, s FIRST (T) =(,iFIRST (T') =*, s FIRST (F) =(,iFOLLOW合如下：FOLLOW E) =),#FOLLOW E') =),#FOLLOW T) =+,),#FOLLOW T') =+,),#FOLLOW F) =+,*,),#各产生式的SELECT集合如下：SELECT (E一TE')

8、=(,iSELECT (E'f+TE') =+SELECT (E'f e ) = ),# SELECT (TFT') =(,iSELECT (T'一*FT' ) =*SELECT (T'f e ) = +,),# SELECT ( F- i ) =i SELECT ( F- ( E ) = (由上可知有相同左部产生式的SELECT集合的交集为空，故文法是LL(1)文法。(2)构造文法的预测分析表如下:i+*()#E一 T E'一T E'E'一+TE'££T一 FT'一 FT

9、9;T'£一*FT'££F一 i一 (E )(二)P101 6.(4)改写下面文法为LL(1)文法，井对每个 LL(1)文法构造相应的预测分析表。ST(E)EfE+S|E-S|S解：首先为各非终结符构造制的集与尸。军。印集，但因为产生式存在左递归, 故第一步先消除之，写为工(£)Et眼£t+S 用-SEIe此时产生式已无左递归，可以开始写卅F依5T集与F0口QW集了 FlRSNS=(i" (AFIRS71F)FUtSTEM，e)FOLLOW(S)=+r -FOLLOWiEHFOLLOWCE由此可以写出预测分析表，预浦分

10、析豪() + -#ST5- £)£ETE*ESE1Ef3、自底向上方法已知文法G(E): S' 一 E1E + T2E- T3T- T * F4T- F5 F -( E )6F - i(1)证明该文法是 SLR(1)文法.(2)若已给出下面的SLR(1)分析表，试分析句子(i + ( * i )#输入串出错的位置。状 态ACTIONGOTOi+*()#ETF0S5S41231Sacc22S7223r44r 444S5S4823566r 666S5S4937S5S4108S6S1191Sr 111033r 331155r 553、解：(1):先分析LR (0)项目:由

11、上可见:11 炉 T T * F *11rEtE +TIo： 2 *EE-* * E+T Ef , T Tf -T*FJFFf F * iS'f E, Ef E指19E- E+T,T-+T. + FIi ,I 2,I 9存在移进一归约冲突.分析FOLLOW 集:因为： 对 11 FOLLOW( S' )= # n + =6对 12FOLLOW(E尸 +, #, ) n * = 6对 19FOLLOW(E尸 +, #, ) n * = 6所以是SLR(1)文法。(2):4、(一)给出语句 if a+b > b+c*d while b+c*d>10 do b:=b-(x

12、*y+5)then while x*y>3 do x:=x相应的三地址代码-a*b elseSTEPSX(i + ( * i ) #actiongoto10#(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 ) #error(1)t1=a+b(12)goto (6)(2)t2=c*d(13) 1goto (23)t3

13、=b+t2(14)t7=c*d(4)if t1>t3 goto (6)(15)t8=b+t7goto (14)(16) 1if t8>10 goto (18)(6)t4=x*y(17)goto (23)(7)if t4>3 goto (9)(18)t9=x*y(8)goto (13)(19)1t10=t9+5(9)t5=a*b(20)t11=b-t10(10)t6二x-t5(21)b=t11(11)1x=t6(22)1goto (14)(23)(二)Whilea>0 V b<0 doBeginX： = X+ 1;if a >0 then a： = a 1el

14、se b： = 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：

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