编译原理期末试题及答案(共13页).doc

精选优质文档-倾情为你奉上1、 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。2、写出表达式ab*(c-d)/e的逆波兰式和三元序列。3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。4、已知文法G(S)及相应翻译方案SaAb print “1”Sa print “2”AAS print “3”Ac print “4”输入acab, 输出是什么？5、 已知文法G(S)SbAaA(B | aBAa)写出句子b(aa)b的规范归约过程。6、已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左递归。专心-专注-专业1、设文法G(S): S | a | (T) TT,S | S 消除左递归； 构造相应的FIRST和FOLLOW集合； 构造预测分析表 2.语句 if E then S(1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 4.设某语言的for语句的形式为for i:E(1) to E(2) do S其语义解释为i:E(1)LIMIT:E(2)again: if iLIMIT thenBeginS;i:i1goto againEnd;（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。7.已知文法G(S)Sa | | (T)TT,S | S(1) 给出句子(a,(a,a)的最左推导；(2) 给出句型(T,S),a)的短语, 直接短语，句柄。8.对于 C 语言do S while E语句 (1)改写文法，使之适合语法制导翻译； (2)写出改写后产生式的语义动作。9.已知文法G(S) SaAcBe AAb| b Bd(1)给出句子abbcde的最左推导及画出语法树；(2)给出句型aAbcde的短语、素短语。 10.设文法G(S): S(T) | aS | a TT,S | S 消除左递归和提公共左因子； 构造相应的FIRST和FOLLOW集合； 构造预测分析表。12.已知文法G(S) EE+T | T TT*F| F F(E)| i (1) 给出句型 (i+i)*i+i的最左推导及画出语法树； (2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。 答案：(1)消除左递，文法变为GS：S | a | (T)'TST | ST,ST |此文法无左公共左因子。(2)构造相应的FIRST和FOLLOW集合： FIRST(S)=a, , (， FOLLOW(S)=#, , )FIRST(T)=a, , ( ，FOLLOW(T)=FIRST(T)=, ，FOLLOW(F)=)(3)构造预测分析表：a(),#SSaSS(T)'TTSTTSTTSTTTT,ST2. (1)Cif E thenSCS(1) (2) Cif E then BACK(E.TC, NXQ); C.chain:=E.FC SCS(1) S.chain:=MERG(C.Chain, S(1). Chain)4. (1) Ffor i:=E(1) to E(2) do SFS(1)(2) Ffor i:=E(1) to E(2) doGEN(:=, E(1).place, _, entry(i);F.place:=entry(i);LIMIT:=Newtemp;GEN(:=, E(2).place, _, LIMIT);Q:=NXQ;F.QUAD:=q;GEN(j, entry(i), LIMIT, q+2)F.chain:=NXQ;GEN(j, _, _, 0)SFS(1)BACKPATCH(S(1).chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain7. 最左推导S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T)=>(a,(T,S)=>(a,(S,S)=>(a,(a,S)=>(a,(a,a)短语 (T,S),a) (T,S),a (T,S) T,S a直接短语 T,S a句柄 T,S9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde(2) 短语: aAbcde, Ab, d 素短语: Ab, d10.(1) S (L) | aS SS | LSL L,SL |(2) FIRST(S)=a, ( FIRST(S)=a, (, FIRST(L)=a, ( FIRST(L)=, FOLLOW(S)=, ), # FOLLOW(S)=, ), #FOLLOW(L)= ) FOLLOW(L)= )(3) ( ) a , # SS (L)S aSSSSSSSSSLLSLLSLL,SL LL12.(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T =>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T =>(i+i)*i+F=>(i+i)*i+i (2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短语 i, E+T最左素短语 E+T编译原理期末试题（二）对于函数f2，由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。6、正规式b*a(bb*a) *b*体现的特点是，每个a的左边都有若干b，除非a是第一个字母。该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：start2abb10ab7、消除左递归后的文法：B ® 1 B¢B¢ ® 0 B¢ | 1 B¢ | e相应的翻译方案如下：B ® 1 B¢.i := 1 B¢B.val := B¢.valB¢ ® 0 B¢1.i := B¢.i ´ 2 B¢1 B¢.val := B¢1.val| 1 B¢1.i := B¢.i ´ 2 +1 B¢1 B¢.val := B¢1.val| e B¢.val := B¢.i编译原理期末试题（三）2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:= 3、对于文法G(S): SbM(TMabL)答：1） 2） 短语: Ma)， (Ma)， b(Ma)b直接短语: Ma) 句柄: Ma)三、 设有字母表a，b上的正规式R=(ab|a)*。 解：（1）0123baa-+（2）将（1）所得的非确定有限自动机确定化ab-01131221+3ab-+013123+12312313+13123012aaba-+（3）对（2）得到的DFA化简，合并状态0和2 为状态2：12aab-+（4）令状态1和2分别对应非终结符B和AG: AaB|a|； BaB|bA|a|b|；可化简为：G: AaB|；BaB|bA|四、 设将文法G改写成等价的LL(1)文法，并构造预测分析表。 G：SS*aT|aT|*aT； T+aT|+a 解：消除左递归后的文法G: SaTS|*aTSS*aTS|T+aT|+a 提取左公因子得文法G:SaTS|*aTSS*aTS|T+aTTT| Select(SaTS)=aSelect(S*aTS)=*Select(SaTS)Select(S*aTS)=Select(S*aTS)=*Select(S)=Follow(s)=#Select(S*aTS)Select(S)= Select(T+aT)=+Select(TT)=First(T) =+Select(T )=Follow(T)=*,#Select(TT)Select(T)= 所以该文法是LL(1)文法。预测分析表： *+a#S*aTSaTSS*aTST+aTT T 6设文法G 为： SA；ABA|；BaB|b解：（1）拓广文法G：(0) SS (1) SA (2) ABA(3) A(4) BaB (5) Bb ； FIRST(A) = , a, b；FIRST(B) = a, b构造的DFA 如下:项目集规范族看出，不存在冲突动作。该文法是LR(1)文法。（2） LR(1)分析表如下： (3)输入串abab 的分析过程为：五、 对文法G(S)：S a | | (T)；T T，S | S 答：(1) a(),#a>>>>>>(<<<=<)>>>,<<<>>#<<<=(2) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。（2分）(3) 给出输入串(a,a)#的算符优先分析过程。步骤 栈当前输入字符剩余输入串动作1#(a,a#<( 移进2#(a,a)#(<a 移进3#(a,a)#a>, 归约4#(N,a)#(<, 移进5#(N,a)#,<a 移进6#(N,a)#a>) 归约7#(N,N）#,>) 归约8#(N)#(=) 移进9#(N)# )># 归约10#N#接受五、设有文法GA：ABCc | gDBBbCDE |CDaB | caDdD |EgAf | c(1) 计算该文法的每一个非终结符的FIRST集和FOLLOW集；(2) 试判断该文法是否为LL（1）文法。（15）FIRSTFOLLOWABCDEA,b,c,d,gbA,c,dDC,gA,c,dC,d,gA,b,c,g是LL（1）文法。ASBbBSab2对于文法GS：S®AB，A®Aa|bB，B®a|Sb求句型baSb的全部短语、直接短语和句柄？句型baSb的语法树如图五(2)所示。解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。3设有非确定的有自限动机NFA M=(A，B，C，0，1，d，A，C)，其中：d (A，0)=C d (A，1)=A，B d (B，1)=C d (C，1)=C。请画出状态转换距阵和状态转换图。解：状态转换距阵为：d01ACA，BBÆCCÆC状态转换图为11011七 已知文法G为:（0） S S（1） S aAd（2） S bAc（3） S aec（4） S bed（5） A eecAdI0:S· S , # S· aAd , # S · bAc , # S ·aec , #S · bed , #I2： Sa · Ad , #Sa · ec , # A· e , d aI1：SS · , #SI3: Sb · Ac , # Sb · ed , # A· e , cbI6: SbA·c,# AI7：Sbe · d , #Ae · , cI11：Sbed · , #dI10：SbAc · , # I4：SaA· d , #I5：Sae· c , # Ae · , deI8：SaAd · , #I9：Saec · , #c 试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。【】【答案：】构造LR(1)分析表 如下： r4 11S10 6r2 10 r3 9 r1 8S11r5 7r5S9 5S8 4 6S7 3 4S5 2acc 1A#S3bedc1S gotoaS2 action 0状态二、设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)答：构造相应的正规式：(0|1)*1(0|1) (3分)NFA: (2分) 1 110432 e e e e 1 0 0确定化：(3分)I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 1四、对于文法G(E): (8分)E®T|E+TT®F|T*FF®(E)|iETF(E)E+TFiTT*F1. 写出句型(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄和素短语。答：1. (4分)EÞTÞFÞ(E) Þ(E+T) Þ(E+F) Þ(E+i) Þ(T+i) Þ(T*F+i) 2. (4分)短语：(T*F+i), T*F+i, T*F, i直接短语：T*F, i句柄：T*F素短语：T*F, i九、(9分) 设已构造出文法G(S)：(1) S ® BB(2) B ® aB(3) B® b的LR分析表如下ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。答：步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#acc1. 设有如下文法G（S），试消除其左递归。G（S）：S>Ac|c A>Bb|b B>Sa|a解：SabcS|bcS|cS, SabcS|2. 试构造与下面G（S）等价的无左递归的文法。G（S）：S>Sa|Nb|c N>Sd|Ne|f解：SfNbS|cS, SaS|dNbS|, NeN|3. 设有文法G（S）：S>aBc|bABA>aAb|bB>b| 求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。 构造LL(1)分析表，并分析符号串baabbb是否是。解：（1）FIRST(aBc)=a, FIRST(bAB)=b FIRST(aAb)=a, Ab: FIRST(Ab)=b, Bb: FIRST(b) = b, FIRST()= FOLLOW(A)=b, #, FOOLOW(B)=c, #SELECT(SaBc)=a, SELECT(SbAB) =b, SELECT(AaAb)=a, SELECT(Ab)=b, SELECT(Bb)=b, SELECT(B)=c, #因此，所得的LL(1)分析表如表A-4所示。表A-4 LL(1)分析表输入VN输入符号abc#SSaBcSbABAAaAbAbBBbBB（2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。图A-16 识别串baabbb的过程4. 已知文法G(S)：S>a|(T)T>T,S|S给出句子(a,a),a)的最左推导并画出语法树；给出句型(T,a,(T)所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。解：（1）最左推导：S(T)(T,S)(S,S) (a,S)(a,(T)(a,(T,S)(a,(S,S)(a,(a, S)(a,(a,a)语法树：如图A-16所示。图A-16 (a,(a,a)的语法树（2）句型(T, a, (T)的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。短语：a | T,a | (T) | T , a , (T) | (T , a , (T)直接短语：a | (T)素短语：a | (T)最左素短语：a句柄：a活前缀： | ( | (T | (T , | (T , a 图A-17 (T,a,(T)的语法树项目集族和DFA1、w a b + c d e 10 - / + 8 + * +2、abcd-*e/+3、abc+e*bc+f/+:=4、42315、句子b(aa)b的规范归约过程：步骤符号栈输入串动作0#b(aa)b#预备1#b(aa)b#移进2#b(aa)b#移进3 #b(a a)b# 移进4#b(Aa)b#归约5 #b(Ma)b#移进6#b(Ma)b#移进7#b(B b# 归约8#bAb#归约9#bAb#移进10#S#接受6、消除左递归SaFS | *aFSS*aFS | F+aF | +a