23307235 编译原理试卷.docx
23307235编译原理一、判断题(共10题，20分)1、语法分析时必须先消除文法中的左递归。(2.0)错误2、在自下而上的语法分析中，语法树与分析树一定相同。(2.0)错误3、有穷自动机接受的语言是正则语言。(2.0)正确4、有穷自动机接受的语言是正则语言。(2.0)正确5、对一个右线性文法G,必存在一个左线性文法G',使得1.(G)=1.(G'),反之亦然。(2.0)正确6、一个有限状态自动机中，有且仅有一个惟一终态。(2.0)错误7、语法分析时必须先消除文法中的左递归。(2.0)错误8、确定的自动机以及不确定的自动机都能正确地识别正规集。(2.0)正确9、对任意一个右线性文法G,都存在一个NFAM,满足1.(G)=1.(M)。(2.0)正确10、在自下而上的语法分析中，语法树与分析树一定相同。(2.0)错误二、多选题(共5题，10分)11、符号表的每一项均包含(AC)。(2.0)A、名字栏B、类型栏C、信息栏D、值栏12、中间代码主要有(ACDE)。(2.0)A、四元式B、间接三元式C、三元式D、后缀式）有能力描述它。13、对正规文法描述的语言，以下（ABCDE（2.0）A、0型文法B、1型文法C、上下文无关文法D、右线性文法E、左线性文法14、下列优化中，属于循环优化的有（ABE）。（2.0）A、强度削弱B、合并已知量C、代码外提D、删除归纳变量15、对1.R分析表的构造，有可能存在（CE）动作冲突。(2.0)A、移进归约移进/归约归约/归约三、问答题(共3题，30分)16、写出算术表达式：A+B*(C-D)+E(CT)tN的:四元式序列；三元式序列；间接三元式序列(10.0)答案6.解答：表达式的四元式序列：(-,C,D,T)(2) (*,B,Ti,T2)(3) (+AKT3)(4) (-,CAT4)(5) (t,T4,N,T5)(6) (Z,E,T5,T6)(7) (+,T3,TT7)表达式的三兀式序列(1)(-,C,D)(2)(*,B,(1)(+A(2)(-,C,D)(t,(4),2(/EQ)(+X3),(6)间接三元式序列(CD)(2)(*,B,(1)(3)(+A(2)(t,(l),N)(5)(/,E,(4)(十,(6)17、按指定类型，给出语言的文法。1.=aibjj>il的上下文无关文法。(10.0)答案：1.解答：由1.=abIj>i21知，所求该语言对应的上下文无关文法首先应有SfaSb型产生式，以保证b的个数不少于a的个数；其次，还需有SfSb或SfbS型的产生式，用以保证b的个数多于a的个数；也即所求上下文无关文法GS为：GS:SaSbSbb18、分别写出语句a:=b*-c+b*-c的四元式、三元式和间接三元式的表示。(10.0)答案5.解答：三地址语句的四元式表示OPArglArg2Result(0)(1)(2)(3)(4)(5)uminus*uminus*+assigncbcbt2t5tlt3t4tlt2t3t4t5a三地址语句的三元式表示OPArglArg2(0)(1)(2)(3)(4)(5)minus*uminus*+assigncbcb(1)a(0)(2)(3)(4)三地址语句的间接三元式表示(O)(1)(2)(3)(4)(5)(14)(15)(16)(17)(18)(19)opArglArg2(14)(15)(16)(17)(18)(19)minus*uminus*+assigncbcb(15)a(14)(16)(17)(18)四、综合题(共2题，40分)19、将文法GV改造成为1.1.(I)的。GV:V-NNEEVV+ENi(20.0)答案：8.解答：对文法GV提取公共左因子后得到文法：G,V:VNAAEEVBB+EN>i求出文法GV中每一个非终结符号的FlRST集：FIRST(V)=iFIRST（八）=,FIRST(E)=iFIRST(B)=÷,FIRST(N)=i求出文法GIV中每一个非终结符号的FO1.1.oW集：FO1.1.oW(V)=#UFIRST(B)吩UFo1.1.oW(E)=#,+,FO1.1.OW（八）=FO1.1.OW(V)=+#FO1.1.OW(E)=FIRST()UFO1.1.OW(B)=FIRST()UF01.1.0W(E)=FO1.1.OW(B)=FO1.1.OW(E)=FO1.1.OW(N)=FIRST（八）UFO1.1.OW(V)=,+,#可以看到，对文法GTV的产生式AT钳印，有FIRST(E)FO1.1.OW（八）=+,=0对产生式BTe+E,有FIRST(+E)FO1.1.OW(B)=+=0而文法的其他产生式都只有一个不为£的右部，所以文法GV是1.1.(I)文法。20、请写出在=(a,b)上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状态最少的DFA。(20.0)答案：解答：根据题意，不以a开头就意味着以b开头，且以aa结尾的正规式为:b(ab)*aa根将图1所示的NFA确定化，如图2所示。从图2可知已为最简状态，由于开始状态0只能输入字符b而不能与状态1合并，而状态2和状态3面对输入符号的下一状态相同，但两者一为非终态、一为终态，故也不有合并，故图2所示的状态转换矩阵已是最简的DFA,如图3所示据正规式画出NFA,如图1所示。IkIbx(11,2(1,2)1,2,Y(1,2,Y)12Y图2状态转换矩阵重新命名IASaBIj1121231331a2ba图3最简DFA
