编译原理试题与解析-北京工业大学-01

第1页共5页北京工业大学2003-04-2学期010700-11班级《编译原理》试卷学号_______________姓名________________成绩___________题号一二三四五六分数一.（10分）改写以下文法，使其满足采用自顶向下分析方法的要求。SaXcY|YdXXaY|cYbYcX|b解:(1)消除XXaY|c的左递归XcX’X’aYX’|ε(2)提取YbYcX|b的左因子YbY’Y’YcX|ε整理后，原文法变为SaXcY|YdXcX’X’aYX’|εYbZZYcX|ε二.(15分)考虑文法G[S]：SxSNy|NxNzN|εε1.求出该文法的每个非终结符的FOLLOW集；2.构造该文法的预测分析表。解:1、FIRST(S)={x,z}FIRST(N)={z,ε}FOLLOW(S)={#,y,z}FOLLOW(N)={x,y}第2页共5页2、预测分析表三.(20分)符号串xxyyyx是如下文法G[S]的句子，SxB|yAAxS|yAA|xByS|xBB|y(1)构造该句子的分析树；(2)写出生成该句子的最左推导；(3)写出生成该句子的规范归约过程；指出每步归约中的句柄。解:(1)语法分析树（6分）(2)SxBxxBBxxyBxxyySxxyyyAxxyyyx(5分)(3)规范归约（9分）xxyyyxxxByyx句柄为yxxByyxxxByyA句柄为xxxByyAxxByS句柄为yAxxBySxxBB句柄为ySxxBBxB句柄为xBBxBS句柄为xBxyz#SNSxSNySNxSNxSxBxBByySyAxNεNεNzN第3页共5页四.（20分）考虑简单赋值语句的文法G[S]：Sid:=EEE+EEE*EEid（1）试构造识别该文法所有规范句型活前缀的有限自动机。（2）判断该文法是否为LR(0)文法（必须说明理由）。解:(1)I0:S’.SS.id=EI1:S’S.I2:Sid.=EI3:Sid=.EE.E+EE.E*EE.idI4:Sid=E.EE.+EEE.*EI5:Eid.I6:EE+.E（2）由于I4、I8、I9均有移进—归约冲突，E.E+EE.E*E故该文法不是LR(0)文法。E.idI7:EE*EE.E+EE.E*EE.idI8:EE+EEE.+EEE.*EI9:EE*E.EE.+EEE.*EI0I1I2I3I4I7I6I8I9I7I5SidididE+id=E+E*+第4页共5页五.（15分）考虑以下语法制导定义产生式语义规则SL1.L2Print(L1.val+L2.val*2-L2.num)LL1BL.val=2*L1.val+B.valL.num=L1.num+1LBL.val=B.valL.num=1B0B.val=0B1B.val=1（1）写出句子11.01的带注释分析树、或属性计算过程。（2）给出处理该句子的结果（Print输出结果）。解：（1）句子11.01的带注释分析树：（2）处理该句子的结果（Print输出结果）为3.25SLL.LBBLB10B11print(3+1*2-2)L.val=2*L.val+B.val=3L.num=L.num+1=2L.val=B.val=1L.num=1B.val=1B.val=1L.val=B.val=0L.num=1L.val=2*L.val+B.val=1L.num=L.num+1=2B.val=0B.val=1第5页共5页六.（20分）设语言L是“能被5整除的十进制正整数”组成的集合，（1）试写出描述语言L的正规表达式；（2）画出识别语言L的状态转移图。解：（1）语言L的正规表达式为：(1|2|……|9)(0|1|……|9)*(0|5)|5（2）识别语言L的状态转移图为：012250/51-4，6-91-4，6-90/51-4，6-9