编译原理期末试题及答案

1、试为表达式w+(a+b)*(c+d/(e-10)+8)写出相应的逆波兰表示。2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。4、已知文法G(S)及相应翻译方案S→aAb{print“1”}S→a{print“2”}A→AS{print“3”}A→c{print“4”}输入acab,输出是什么？5、已知文法G(S)S→bAaA→(B|aB→Aa)写出句子b(aa)b的规范归约过程。6、已知文法G[S]S→S*aF|aF|*aFF→+aF|+a消除文法左递归。1、设文法G(S):S→^|a|(T)T→T,S|S⑴消除左递归；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表2.语句ifEthenS(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。4.设某语言的for语句的形式为fori:＝E(1)toE(2)doS其语义解释为i:＝E(1)LIMIT:＝E(2)again:ifi＜＝LIMITthenBeginS;i:＝i＋1gotoagainEnd;（1）写出适合语法制导翻译的产生式；（2）写出每个产生式对应的语义动作。7.已知文法G(S)S→a|^|(T)T→T,S|S(1)给出句子(a,(a,a))的最左推导；(2)给出句型((T,S),a)的短语,直接短语，句柄。8.对于C语言doSwhileE语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。9.已知文法G(S)S→aAcBeA→Ab|bB→d(1)给出句子abbcde的最左推导及画出语法树；(2)给出句型aAbcde的短语、素短语。10.设文法G(S):S→(T)|aS|aT→T,S|S⑴消除左递归和提公共左因子；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表。12.已知文法G(S)E→E+T|TT→T*F|FF→(E)|i(1)给出句型(i+i)*i+i的最左推导及画出语法树；(2)给出句型(E+T)*i+F的短语，素短语和最左素短语。答案：(1)消除左递，文法变为G’[S]：S→^|a|(T)'T→ST’|ST’→,ST’|ε此文法无左公共左因子。(2)构造相应的FIRST和FOLLOW集合：FIRST(S)={a,^,(}，FOLLOW(S)={#,,,)}FIRST(T)={a,^,(}，FOLLOW(T)={}}FIRST(T’)={,,ε}，FOLLOW(F)={)}(3)构造预测分析表：a^(),#SS→aS→^S→(T)'TT→ST’T→ST’T→ST’T’T’→εT’→,ST’2.(1)C→ifEthenS→CS(1)(2)C→ifEthen{BACK(E.TC,NXQ);C.chain:=E.FC}S→CS(1){S.chain:=MERG(C.Chain,S(1).Chain)}4.(1)F→fori:=E(1)toE(2)doS→FS(1)(2)F→fori:=E(1)toE(2)do{GEN(:=,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)}S→FS(1){BACKPATCH(S(1).chain,NXQ);GEN(+,F.place,1,F.place);GEN(j,_,_,F.QUAD);S.chain:=F.chain}7.最左推导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,Sa直接短语T,Sa句柄T,S9.(1)S=aAcBe=AAbcBe=abbcBe=abbcde(2)短语:aAbcde,Ab,d素短语:Ab,d10.(1)S→(L)|aS’S’→S|εL→SL’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→aS’S’S’→SS’→εS’→SS’→εS’→εLL→SL’L→SL’L’→,SL’L’L’→ε12.(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如下：startbb0ab7、消除左递归后的文法：B1BB0B|1B|相应的翻译方案如下：B1{B.i:=1}B{B.val:=B.val}B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}|{B.val:=B.i}《编译原理》期末试题（三）2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。答：逆波兰式：abc*bd*+:=3、对于文法G(S):）MaLa|(LMbMbS答：1）bMabLbbbMbS)((2）短语:Ma)，(Ma)，b(Ma)b直接短语:Ma)句柄:Ma)三、设有字母表{a，b}上的正规式R=(ab|a)*。解：（1）（2）将（1）所得的非确定有限自动机确定化εab-01131221+3（3）对（2）得到的DFA化简，合并状态0和2为状态2：ab-+013123+12312313+13123012aaba-+++0123baaεε-+SbM(TMabL)（4）令状态1和2分别对应非终结符B和AG:A→aB|a|ε；B→aB|bA|a|b|ε；可化简为：G:A→aB|ε；B→aB|bA|ε四、设将文法G改写成等价的LL(1)文法，并构造预测分析表。G：S→S*aT|aT|*aT；T→+aT|+a解：消除左递归后的文法G’:S→aTS’|*aTS’S’→*aTS’|εT→+aT|+a提取左公因子得文法G’’:S→aTS’|*aTS’S’→*aTS’|εT→+aT’T’→T|εSelect(S→aTS’)={a}Select(S→*aTS’)={*}Select(S→aTS’)∩Select(S→*aTS’)=ФSelect(S’→*aTS’)={*}Select(S’→ε)=Follow(s’)={#}Select(S’→*aTS’)∩Select(S’→ε)=ФSelect(T→+aT’)={+}Select(T’→T)=First(T)={+}Select(T’→ε)=Follow(T’)={*,#}Select(T’→T)∩Select(T’→ε)=Ф所以该文法是LL(1)文法。预测分析表：*+a#S→*aTS’→aTS’S’→*aTS’→εT→+aT’T’→ε→T→ε6设文法G为：S→A；A→BA|ε；B→aB|b解：（1）拓广文法G’：(0)S’→S(1)S→A(2)A→BA(3)A→ε(4)B→aB(5)B→b；FIRST(A)={ε,a,b}；FIRST(B)={a,b}构造的DFA如下:12aab-++项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。（2）LR(1)分析表如下：(3)输入串abab的分析过程为：五、对文法G(S)：S→a|^|(T)；T→T，S|S答：(1))},^,,{,)()},^,{)((},^,,{,)((},^,{)(aTLASTVTaSLASTVTaTFIRSTVTaSFIRSTVT(2)是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。（2分）(3)给出输入串(a,a)#的算符优先分析过程。步骤栈当前输入字符剩余输入串动作1#(a,a##(移进2#(a,a)#(a移进3#(a,a)#a,归约a^(),#a^(=),#=4#(N,a)#(,移进5#(N,a)#,a移进6#(N,a)#a)归约7#(N,N）#,)归约8#(N)#(=)移进9#(N)#)#归约10#N#接受五、设有文法G[A]：A→BCc|gDBB→bCDE|εC→DaB|caD→dD|εE→gAf|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）文法。2．对于文法G[S]：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄？句型baSb的语法树如图五(2)所示。解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。3．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，，{A}，{C})，其中：(A，0)={C}(A，1)={A，B}(B，1)={C}(C，1)={C}。请画出状态转换距阵和状态转换图。解：状态转换距阵为：01ACA，BBCCC状态转换图为ASBbBSabAB1C1111七已知文法G为:（0）S′→S（1）S→aAd（2）S→bAc（3）S→aec（4）S→bed（5）A→e试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。【】【答案：】构造LR(1)分析表如下：二、设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。(8分)答：构造相应的正规式：(0|1)*1(0|1)(3分)NFA:(2分)11100确定化：(3分)ecAdI0:S′→·S,#S→·aAd,#S→·bAc,#S→·aec,#S→·bed,#I2：S→a·Ad,#S→a·ec,#A→·e,daI1：S′→S·,#SI3:S→b·Ac,#S→b·ed,#A→·e,cbI6:S→bA·c,#AI7：S→be·d,#A→e·,cI11：S→bed·,#dI10：S→bAc·,#I4：S→aA·d,#I5：S→ae·c,#A→e·,deI8：S→aAd·,#I9：S→aec·,#cr411S106r210r39r18S11r57r5S95S846S734S52acc1A#S3bedc1SgotoaS2action0状态01234I0I1I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3}{1,2,4}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2,3,4}0101000111四、对于文法G(E):(8分)ET|E+TTF|T*FF(E)|i1.写出句型(T*F+i)的最右推导并画出语法树。2.写出上述句型的短语，直接短语、句柄和素短语。答：1.(4