《编译原理》试卷B(2009-2010-1).doc

中南财经政法大学2009 2010学年第一学期期末考试试卷课程名称：编译原理（B）卷 课程代号：_09281020_ 考试形式：闭卷笔试使用对象：计算机科学与技术0701班-_题号12345678910总分总分人分值101010151010101015100得分_得分评阅人 1名词解释：（每题2分,，共 10分 ）句柄LR（1）文法无环路有向图(DAG)语法制导翻译局部优化院（系）： 专业： 年级： 学生姓名： 学号： 课堂号：_ - 密 - 封 - 线 -得分评阅人2（ 10分）某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。得分评阅人3（ 10分）下面两个文法中哪一个不是LR（1）文法？对非LR（1）的那个文法。给出那个有移进归约冲突的规范的LR（1）项目集。S aAc S aAc A bbA | b A bAb | b 第 1 页(共 4 页)得分评阅人4（ 15 分）程序的文法如下：P DD D ; D | id : T | proc id ; D ; S（1）写一个语法制导定义，打印该程序一共声明了多少个id。（2）写一个翻译方案，打印该程序每个变量id的嵌套深度。 - 密 - 封 - 线 -得分评阅人5（ 10分）在PASCAL语言中，简单类型的变量的声明例举如下：m, n : integerp, q, r : real 为这样的声明写一个LR（1）文法（为简单起见，变量标识符都用id表示），并根据你的文法写一个语法制导定义（或叫做为你的文法加上语义动作），它将变量的类型填入符号表。 第 2 页(共 4 页)得分评阅人6（ 10分）下面程序在SUN工作站上运行时陷入死循环，试说明原因。如果将第8行的long *p改成short *p，并且将第23行long k 改成short k后，loop中的循环体执行一次便停止了。试说明原因。main()addr();loop();long *p;loop()long i,j;j=0;for(i=0;i10;i+)(*p)-;j+;addr()long k;k=0;p=&k; - 密 - 封 - 线 -得分评阅人7（ 10分）一个C语言函数如下：main()int i,j,k;i=5;j=1;while(j100)k=i+1;j=j+k;经优化编译后，生成的代码如下：.file“optimize.c” gcc2_compiled.:_gnu_compiled_c:.text.align 2.globl _func.type_func,function _func:pushl %ebpmovl %esp,%ebpmovl $1,%eaxmovl $6,%edx.align 2,0x90L4:addl %edx,%eaxcmpl $99,%eaxjle L4leaveretLfe1:.size_func,Lfe1-_func试说明编译器对这个程序作了哪些种类的优化（只需要说复写传播、删除公共子表达式等，不需要说怎样完成这些优化的）。 第 3 页(共 4 页)得分评阅人8（ 10分）为下面文法添加语义规则（或叫动作子程序），输出S产生的二进制数的值，如输入是101时，输出5。 S SS S B | BB 0 |