编译原理与技术期末考试试卷答案 软件学院

1、参考答案及评分标准一、填空（15分，每空1分）1高级，低级2源程序，单词3自顶向下4综合，继承5结构，名称6非局部名字访问，参数传递7上下文有关，上下文无关，正规8abcd+*+二、（15分）答：正规表达式（4）代表了这个程序段所有可能走过的全部步序列（5分）把A,T,B,I分别代表相应的基本块，E表示程序段的出口，则程序段可以表示为如下的流（程）图：（5分） A T B I E转换为等价的确定状态自动机如下： T 0 1 2 3 4 A T B I由上述确定状态自动机可以得到等价的正规表达式为：AT(BIT)*（5分）如果没有画流程图而直接给出自动机可以给分。既没有画流程图，也没有画自动机，

2、可以根据描述的理由是否能说明清楚酌情给分。三、（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分析符号串baabbb是否为该文法的句子的过程如下表所示：（7分）步骤栈输入串输出1$Sbaabbb$2$BAbbaabbb$S bAB3$BAaabbb$4$BbAaaabbb$A aAb5$BbAabbb$6$BbbAaabbb$A aAb7$BbbAbbb$8$Bbbbbbb$A b9$Bbbbb

3、$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,$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,a

4、B c,b2文法的LR(1)分析表如下：（10分）状态actiongotoabcd$SAB0S5S41231acc2S63S74S10895r5r66r17r38S119S1210r6r511r212r4从分析表中可知没有多重表项，因此该文法是LR(1)文法3由识别所有活前缀的确定有限状态自动机（DFA）可知，存在同心集I5和I10，合并后的LR(1)项目集为：A c,a/b B c,a/b，可见在该项目集中存在归约-归约冲突，因此该文法不是LALR(1)文法。（5分）五、（10分，每小题5分）答：1A：array(1.100, record(x×integer)×(y&#

5、215;char)2func：integer×(integerpointer(integer)record(i×integer)×(c×char)六、（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$aaA