《《编译原理与技术》期末考试试卷答案 05(软件学院).doc》由会员分享,可在线阅读,更多相关《《编译原理与技术》期末考试试卷答案 05(软件学院).doc(22页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date编译原理与技术期末考试试卷答案 05(软件学院)参考答案参考答案及评分标准一、填空(15分,每空1分)1高级,低级2源程序,单词3自顶向下4综合,继承5结构,名称6非局部名字访问,参数传递7上下文有关,上下文无关,正规8abcd+*+二、(15分)答:正规表达式(4)代表了这个程序段所有可能走过的全部步序列(5分)把A,T,B,I分别代表相应的基本块,E表示程序段的出
2、口,则程序段可以表示为如下的流(程)图:(5分) A T B I E转换为等价的确定状态自动机如下: T 0 1 2 3 4 A T B I由上述确定状态自动机可以得到等价的正规表达式为:AT(BIT)*(5分)如果没有画流程图而直接给出自动机可以给分。既没有画流程图,也没有画自动机,可以根据描述的理由是否能说明清楚酌情给分。三、(20分)答:1FIRST(S)=a,bFOLLOW(S)=$FIRST(A)=a,bFOLLOW(A)=b,$FIRST(B)=b,FOLLOW(B)=c,$(6分,每个1分)。2LL(1)分析表如下:(7分)abc$SaBcbABAaAbbBb3分析符号串baab
3、bb是否为该文法的句子的过程如下表所示:(7分)步骤栈输入串输出1$Sbaabbb$2$BAbbaabbb$S bAB3$BAaabbb$4$BbAaaabbb$A aAb5$BbAabbb$6$BbbAaabbb$A aAb7$BbbAbbb$8$Bbbbbbb$A b9$Bbbbb$10$Bbb$11$B$12$B 四、(25分)答:1文法G的拓广文法G如下:(10分)SSS AadAbBbdBaA cB c 构造识别所有活前缀的确定有限状态自动机(DFA)如下:SS, $ I1 I2 I6 S Aa,$S Aa,$ a S Bb,$S Bb,$SS,$S Aa,$S dAb,$S Bb,
4、$S dBa,$A c,aB c,b I0 S A I3 I7 B b S dAb,$S dAb,$S dAb,$S dBa,$A c,bB c,a I4 I8 I11 d A b I9 I12 S dBa,$S dBa,$ B a cA c,bB c,a I5 c I10 A c,aB c,b2文法的LR(1)分析表如下:(10分)状态actiongotoabcd$SAB0S5S41231acc2S63S74S10895r5r66r17r38S119S1210r6r511r212r4从分析表中可知没有多重表项,因此该文法是LR(1)文法3由识别所有活前缀的确定有限状态自动机(DFA)可知,存
5、在同心集I5和I10,合并后的LR(1)项目集为:A c,a/b B c,a/b,可见在该项目集中存在归约-归约冲突,因此该文法不是LALR(1)文法。(5分)五、(10分,每小题5分)答:1A:array(1.100, record(xinteger)(ychar)2func:integer(integerpointer(integer)record(iinteger)(cchar)六、(15分)答:当分析器的输入为aacbb时翻译结果是:12020(5分)方法一:aacbb的分析树如下: A a B A b a B A b c由于分析器采用移进-归约的方式进行,归约时使用产生式的顺序为:A c,B Ab,A aB,B Ab,A aB,因此打印结果为:12020。方法二:句子aacbb的最右推倒为:A=aB=aAb=aaBb=aaAbb=aacbb。归约过程是最右推导的逆,从右向左考察推导过程中使用的产生式即为归约过程采用的顺序,因此打印结果为:12020。方法三:移进-归约的分析步骤如下:栈输入串动作输出$aacbb$移进$aacbb$移进$aacbb$移进$aacbb$归约,A c1$aaAbb$移进$aaAbb$归约,B Ab2$aaBb$归约,A aB0$aAb$移进$aAb$归约,B Ab2$aB$归约,A aB0$A$完成因此输出结果为:12020。-
限制150内