南信大编译原理期中试卷(软件工程)

编译原理期中试卷(软件工程)1简答题（每题5分，共计15分）(1) 简述编译程序与解释程序的区别。解释程序不生成目标代码，而编译程序生成目标代码(2) 什么是句柄？令GS是一个文法，如果有S=*A且A=*则称是一个关于非终结符号A的，句型的短语。其次如果有S=A且A=则称是直接短语。一个句型的最左直接短语称为该句型的句柄。(3) 自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么？自顶向下的语法分析解决的核心问题是：（1） 消除左递归 (2) 避免回溯自底向上的语法分析解决的核心问题是： 寻找句柄2文法GS: S=ab(T) T=T,SS给出句型(a,(b,S)的短语与直接短语(简单短语)、句柄和最左素短语。（10分）短语：(a,(b,S)，a,(b,S)，a，(b,S)，b,S，b直接短语(简单短语)：a，b句柄：a最左素短语：a3按指定类型给出下列语言的文法,并指出语言的类型。（每个5分，共10分）(1) L1= anbm| n0,m0 S:= aS|bS|b(2) L2= 0n1nbmcm| n0，m 0 S:=AB A:=0A1|01 B:=bBc|4构造正则式ba*|(ab)*b对应的DFA并最小化。（要求步骤清楚，15分） b 1 0 a 6 2 a 3 b 4 b 5 IaIb0,2,431,5,632,41,5,61,65,62,435,61,61,65,6 b a a b b5. 请在划线处填空。（5分）BEGIN /* Start Algorithms */ (1) PUSH(#),PUSH(S);把第一个输入符号读进b; FLAG = TRUE；WHILE FLAG DOBEGIN 把栈顶符号上托出去并放在X中； IF X Vt THEN IF X=b THEN 把下一个输入符号读进a ELSE ERRORELSE IF X=# THEN FLAG = FALSE ELSE ERRORELSE IF MX,b=X X1X2XK THEN (2) 将XkXk-1X1入栈 ELSEERROREND /* End Of While */END /* End of Algorithms */6为文法GP：P=begin S end S=AC A=V:=E C=if E then SE:=VE E:=+VE | V=i 构造递归下降识别程序（15分）构造程序（略，注意判断预测的符号）7请给出文法的First和Follow集合，给出分析表（15分）E=TE E=+E T=FT T= /T F=PF F= *FP=(E)ab 根据下列分析表，分析句子i+i*i。 （10分）将分析过程填入如下的表格中。步骤栈输入串规则（动作）1#Ei+i*i#E:=TE2#ETi+i*i#T:=FT3#ETFi+i*i#F:=i4#ETii+i*i#弹栈5#ET+i*i#T:= 6#E+i*i#E:=+TE7#ET+i*i#弹栈8#ETi*i#T:=FT9#ETFi*i#F:=i10#ETii*i#弹栈11#ET*i#T:=*FT12#ETF*i#弹栈13#ETFi#F:=i14#ETii#弹栈15#ET#T:= 16#E#E:= 17#Acc8文法GE： (1) EKFc (2) KaK (3) Kd (4) Fb，对应的LR(0)分析表如图，ACTIONGOTO状态abcd#EFK0S3S4121acc2S653S3S474r3r3r3r3r35S86r4r4r4r4r47r2r2r2r2r28r1r1r1r1r1 依据右边的表格格式，写出分析adbc的过程。（10分）答题格式如下：步骤符号栈状态栈输入串动作1#0adbc#Shift S32#a03dbc#Shift S43#ad034bc#Reduce R34#aK037bc#Reduce R25#K02bc#Shift S66#Kb026c#Reduce R47#KF025c#Shift S88#KFc0258#Reduce R