北京工业大学2003-04-2学期010700-H班级《编译原理》
试卷
云南省高中会考试卷哪里下载南京英语小升初试卷下载电路下试卷下载上海试卷下载口算试卷下载
题号一-四五六分数学号.成绩一.(10分)改写以下文法，使其满足采用自顶向下分析方法的要求。aXcYiYdXaYicbYcXi解:XXX，YYY'整理后,sXX，z(1)消除(2)提取XaYlc的左递归cX，aYX'丨£bYcXIb的左因子bY，YcXi£原文法变为aXcYIYdcX，aYX*I£bZYcXi£二.(15分)考虑文法G[S]：SxSNyINxNzN|e求出该文法的每个非终结符的FOLLOW集;构造该文法的预测分析表。解:X,Z,FIRST(S)={X,zJFIRST(N)={z,e}FOLLOW(S)={#,y,z}FOLLOW(N)={X,y}（20分）符号审xxyyyx是如下文法G[S]的句子,xBIyAxSIyAAXySIxBBIy2、预测分析表Xyz#sSTxSNyStNxStNxNNT8NTeNtzNSAB构造该句子的分析树；写出生成该句子的最左推导；写出生成该句子的规范归约过程；指出每步归约中的句柄。解：(1)语法分析树(6分)SXX（2）SxBxxBBxxyBxxyySxxyyyAxxyyyx（5分）(3)规范归约(9分)xxyyyxxxByyx句柄为yxxByyxxxByyA句柄为XxxByyAxxByS句柄为yAxxBySxxBB句柄为ySxxBBxB句柄为xBBxBS句柄为xB0四.(20分)考虑简单赋值语句的文法G[S]：SEEE(1)(2)id:=EE+EE*Eid试构造识别该文法所有规范句型活前缀的有限自动机。判断该文法是否为LR(O)文法(必须说明理由)。解:⑴S，SII：s，L:SIs：SEEEII：SEEEEEEEEEEEEEEEEEIo：I5：le：I：：Is：I9：.S.id=ES.id.=Eid=.E+.E*.idid=E.+E.*id.E+.E.E+E.E*E.idE*E.E+E.E*E.idE+EE.+EE.*EE*E.E.+EE.*E.EEEE.EE(2)III于L,、Is.I9均有移进一归约冲突,故该文法不是LR(O)文法。五.(15分)考虑以下语法制导定义产生式语义规则sLi•L：Print(—L*'.num.Li.val+Lz.val*2")LLiBL.val2*Li.val+B.valL・numLi.num+1LBL.valB.valL・num1B0B.val0B1B.val1写出句子11.01的带注释分析树、或属性计算过程。给出处理该句子的结果(Print输出结果)。解:(1)句子11.01的带注释分析树:Lnum=L.num+l=2L.val=2*L.val+B.val=3Lval=2*L.val+B,val=lPrint{3+l*2'-)Lval=B.val=OLjium=iLLjium=Ljium+1=2L.num=lL.val=B.val=lbB.val=lBLB.val=lB・val=lB.val=O(2)处理该句子的结果(Print输出结果)为3.25六.(20分)设语言L是“能被5整除的十进制正整数”组成的集合，试写出描述语言L的正规表达式；画出识别语言L的状态转移图。语言L的正规表达式为：|9)(01……|9)*(0|5)|5解:(1)(1|2|(2)识别语言L的状态转移图为:0/5
浙公网安备 33021202002483