资源描述:
《编译原理-样卷-答案》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、浙江工业大学之江学院2012/2013(2)编译原理A卷(答案)一、选择题(10*2=20)DBBACCABDA二、填空题(10*2=20)1.是否生成冃标代码2.词法分析、语法分析3.汇编指令、「『重定位4.句型5.终结符集、非终结符集、开始符号和一组产生式6.a/(b-c)7.逆波兰表达式、四元式表示、三元式表示和树型表示8.语法规则9.继承属性10・LR分析表三、解答题1.答:不是。1分将B-*aB
2、c替换A-*Bc
3、a屮的B,有A-*aBc
4、cc
5、a4分可见有左公共因子a,所以G不是LL(l)文法。2.答:对于文法G定义的句子i+i*i,有两棵不同的语法树:~2分<1
6、S+Si••11所以该文法是二义文法。一3分3・答:wab+cdel0-/+8+*+5分4.答:⑴构造该正规式对应的NFAN;5分0J(2)将NFAN确定化,得到DFAM(用DFA图表示),使得L(M)=L(N);01{X}{A,B,Y}{A,B,Y}{B,Y}{B,Y}{B,Y}{B,Y}{B,Y}0,1⑶将DFAM最小化(用DFA图表示)。5分5.消除所给文法的左递归,得GIS(L)
7、aSL1—,SU
8、e5分实现预测分析器的不含递归调用的一种有效方法是使用一张分析农和一个栈进行联合控制,面构造预测分析农:根据文法&有:First(S)={(,a)First(L)={(,a
9、)First(L*)={,}Follow(S)={),,,#}Follow(L)={)}Follow(U)={)}按以上结果,构造预测分析表M如下:日肉结符^()1a#S2(L)S8LL^SL'L^SL'L'L'XL'T,SL文法&是LL(1)的,因为它的1丄(1)分析表不含多重定义入口。5分预测分析器对输入符号串(a,(a,a))做出的分析动作如下:步骤栈剩余输入串输出1#S(a,(a,a))##2#)L(a,(a,a))#S->(L)3#)La,(a,a))#4#)USa,(a,a))#L->Sf5#)Uaa,(a,a))#S—a6#)U,(a,a))#7#)US,,(a
10、,a))#LJ,SU8#)L*S(a,a))#9#)LJL((a,a))#S->(L)10#)U)La,a))#11#)L')L*Sa,a))#L->SL*12#儿兀aa,a))#S—>a13#)LJU用))#14杓LJL/S,用))#LJ,SU15#)LJUSa))#16#)L,)L,aa))#S—>a17#儿兀))#18#)U)))#LJw19#)1/)#20#))#L*—>£21##(1)拓广文法G':(O)S'fS(l)S—A(2)A~BA(3)Af£(4)B~aB(5)B~b:FIRST(A)={£a,b};FIRST(B)={a,b}构造的DFA如F:项目集规范族
11、看出,不存在冲突动作。.••该文法是LR(1)文法。LR(1)分析表如下:状态ActionGotoaBSAB0S4S5r31231acc9rl3S4S5r3634S4S575r5r5r56r2一rdrird(3)输入串abab的分析过程为:步骤状态栈符号栈当询字符剩余字符串动作(1)0abab»移进(2)04bab«移进(3)045saba归约B-»b⑷047saBab»归约B->aB(5)03ab«移进(6)031b移进(7)0315^Babn归约B9b(8)0317=BaB归约B->aB(9)033^BB归约A今e(10)0336n归约A->BA(11)036#BA#归约
12、ATBA(12)02#A#归约S->A(13)01#Sacc