中科院软件所2000之后博士考试题

页码112356本页介绍03编译及答案03软基（附末题答案）05编译另外的就请到/openpic.php?user=jw-ok&pid=734296958&_dir=%2F28530707下载图片吧，以前还考离散，现在不考了，我就没上传。中科院编译原理2003年试题公布 感谢中科大陈意云老师在网上公布此份试题及部分解答。 1（10分）叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。 ( 1 | 01 )* 0* 2（10分）某语言有两种语句： S 过程调用语句 | 下标变量赋值语句 过程调用语句的形式是：id(id, id, , id)，即过程名加置于圆括号中的变量表。 下标变量赋值语句的形式是：id(id, id, , id) := id(id, id, , id)，赋值号两边都是数组名加置于圆括号中的变量表。 (a) 请你完成过程调用语句和下标变量赋值语句的文法设计，得到一个以语句S为开始符号的LR(1)文法。不得超过6个产生式，不需要给出你的文法是LR(1)文法的证明。 (b) 如果想在LR分析的同时完成语义分析和中间代码生成，基于你的文法有什么困难？ 3（10分） (a) 为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。 E E *E | +E | E | unsigned_integer (b) 为上面的表达式产生栈机器代码。代码执行后，表达式的值留在栈上。你自己设计所需的栈机器指令，并写清楚指令的含义。 4（10分）在C语言的教材上，称&为地址运算符，&a为变量a的地址。但是教材上没有说明表达式&a的类型是什么。另外，教材上说，数组名代表数组的首地址，但是也没有说明这个值的类型。它们所带来的一个问题是，如果a是一个数组名，那么表达式a和&a的值都是数组a的首地址，但是它们的使用是有区别的，初学时很难掌握。 下面我们给出4个C文件，请你根据编译报错信息和程序运行结果，写出表达式a和&a的类型表达式。若你能掌握它们的类型，那么它们的区别就清楚了，你也就会正确使用它们了。 （1）文件1： typedef int A1020; A a; A *fun() return(a); 该函数在Linux上用gcc编译时，报告的类型错误如下： 第6行：warning: return from incompatible pointer type （2）文件2： typedef int A1020; A a; A *fun() return(&a); 该函数在Linux上用gcc编译时，没有类型方面的错误。 （3）文件3： typedef int A1020; typedef int B20; A a; B *fun() return(a); 该函数在Linux上用gcc编译时，没有类型方面的错误。 （4）文件4： typedef int A1020; A a; fun() printf(“%d,%d,%dn”, a, a+1, &a+1); main() fun(); 该程序的运行结果是： 134518112, 134518192, 134518912 编译原理部分答案1该正规式描述的语言是，所有不含子串001的0和1的串。 2 (a) S Call | Assign Call id(id_list) Assign id(id_list) := id(id_list) id_list id_list, id | id (b) 由于过程参数和下标表达式的中间代码是不一样的，在id和id_list, id向id_list归约时，不知按哪种方式处理。 3 (a) E E1 *E2if E1.sign= E2.sign then E.sign := POS else E.sign := NEG E +E1 E.sign := E1.sign E E1 if E1.sign= POS then E.sign := NEG else E.sign := POS E unsigned_integer E.sign := POS (b) 指令的解释如下： PUSH值： 将值压栈 NEG： 将栈顶值取出，计算其相反数，把结果压入栈 MUL： 将栈顶和次栈顶的值取出，将它们相乘，把结果压栈 产生代码的翻译方案如下： E E1 *E2 emit(MUL) E +E1 E E1 emit(NEG) E unsigned_integeremit(PUSH unsigned_integer.lexval) 4对一个t类型的数组a i1 i2 in 来说，表达式a的类型是： pointer(array(0. i2 1, array(0. in 1, t) 而表达式&a的类型是： pointer(array(0. i1 1, array(0. in 1, t) 中科院 计算所-软件所 2003年考研试题第一部分 编译（40）一、（1/01）*0*说明是什么语言 画出DFA（10） 二、 S过程调用语句/数组的赋值语句（10） 过程调用语句为：id(id,id,id) 赋值语句: id(id,id):=id(id,id) (a)写一个LR（1）方法（产生式不大于6个） (b)若在LR分析同时完成语义分析，中间代码生成，基于你的文法有什么困 难？ 三、EE*E/+E/-E/unsigned-integer (10) 为上面表达式产生栈机器代码，代码执行后，表达式值留在栈上，自己设计所需栈机器指令，并写清指令含义。 四、C语言中，a表示数组首址，而&a也表示数组首址，然而使用时有时并不相同，请根据下面写出a与&a类型表达式 （10） (1)文件1: tgpedef int A1020 A a; A * func ( ) return(a); 在linux上用gcc编译 报告:第6行warning: return from incompatible pointer type (2)typedef int A1020 A a; A *func( ) return(&a); 无类型方面错误 (3)typedef int A1020 typedef int B20 A a; B *func( ) return(a); 无类型方面错误 (4) typedef int A1020 A a; func( ) Printf(“%d,%d,%d/n,a,a+1,&a+1); main( ) func( ); 结果：134518112，134518192，134518912 第二部分 操作系统（40）五. 1、操作系统内核有强内核和微内核，unix是前者，windowsNT是后者，简介微内核比强内核的优点。（4） 2、若只有进程控制，其独立性表现在？引入线程后，独立性有何改变（4） 3、请求调页存储系统确定页面大小的标准（4） 六、 1.死锁的证明 在m个同类资源，n个进程共享它，每次进程只能获得或释放至多一个资源，问会不会发生死锁，若： (1)、设每个进程所需资源数为ri 1=ri=m (6) 2、windows NT页面大小为4KB，采用两级页表机构，为提高 设了32K或64K的Cache，试叙述windows NT地址变换过程的页面调度策略。（10） 3、假设有一种新磁盘技术，两者即磁盘与内存访问时间在同一数量级上，作下面哪些修改以采用更快的磁盘访问速度。 （12） （1） 进程调度（4） （2）内存管理（4） （3）磁盘驱动程序（4） 第三部分 数据结构（70分） 七. 选择（52） 八.简答（102） 说明:七和八题都很简单,多是考察有关树方面的小问题,第八题和填空题差不多,非常简单,故没抄下来. 九、（55分） 1、广义表，设H表示Get head ，T表示Get Tail 从下表中分解出原子a,请给出H、T操作序列。 L=( ),(b,c), (b,(c,a),(c,d),(e),d) H(T(H(T(H(H(T(T(L)2、串序列T=“abcabcabca”模式串w=“abca”用kmp算法，求next1:10 3、一无向图，边非负权值，问用Dijkstra最短路径算法能否给出一棵生成树？该树是否一定是最小生成树？说明理由。 4、判断向一无环图增加一边是否会使图中产生环的问题时，应选用什么样的数据结构？（一名话简单回答）在使用这种数据结构时该判断所需时间。 5、设向一棵空平衡二叉树（AVL）中插入关键字序列为45，24，12，62，70，50，10，38画出每插入一关键字后该树状态示意图，若在此基础上删除关键字62，给出删除后的状态图。 十、（15分）有n张扑克牌，存在由记录组成的数组A（1：n）中，每个记录有三个域，其中，N0为每张扑克初始序号，一旦给定不改变,Cor表示每张扑克花色，梅花方块红桃next=NULL;/for(i=1;i=n;i+)switch(A.Cor)/case 梅花:Insert(first0,Ai);break;case 方块:Insert(first1,Ai);break;case 红桃:Insert(first2,Ai);break;case 黑桃:Insert(first3,Ai);break;default:exit(ERROR);/switch/forfor(i=0,j=1;inext;while(p)Aj+=p-card;p=p-next;/Sort void Insert(CardLink &f,CardType c)/CardNode p,q;if(!(p=(CardLink)malloc(sizeof(CardNode)exit(OVERFLOW);p-card=c; q=f;r=f-next;while(r&c.Val=r-card.Val)q=r;r=r-next;/whilep-next=r;q-next=p;/Insert2005编译原理部分1（5分）下面是用正规式表示的变量声明：( int | float ) id (, id )* ;请改用上下文无关文法表示，也就是写一个上下文无关文法，它和该正规式等价。2（10分）在C语言中，3+和( id + id )+这样的表达式被编译时，编译器都会报告如下的错误：invalid lvalue in increment现有如下简化的C语言表达式文法：E E + E | ( E ) | E + | id | num请你写一个语法制导定义或翻译方案，它检查+的运算对象是否合法。3（10分）下面是一个C语言程序： long f1(i)long i;return(i*10);long f2(long i)return(i*10);main()printf(“f1 = %d, f2 = %dn”, f1(10.0), f2(10.0) );其中函数f1和f2仅形式参数的描述方式不一样。该程序在X86/Linux机器上的运行结果如下：f1 = 0, f2 = 100请解释为什么用同样的实在参数调用这两个函数的结果不一样。4（5分）优化编译器对下面程序的局部变量i和j不分配空间，为什么？main()long i, j;i = 5;j = i * 2;printf(“%dn”, i+j);编译原理部分答案1D T L ; T int | floatL L, id | id2给非终结符E一个综合属性v，其值可取lvalue或rvalue，分别表示E是左值表达式和右值表达式，那么语法制导定义如下（无输出则表示无错）：E EE E1 + E2E.v := rvalueE ( E1 )E.v := E1.vE E1 +if E1.v = rvalue then printf(“invalid lvalue in increment”); E.v := rvalueE idE.v := lvalueE numE.v := rvalue3历史上，C语言中有参函数定义的一般形式是：类型标识符 函数名（形式参数列表）形式参数声明对于这种形式的声明，C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的。如本题中函数f1的声明是这种形式。现在，ANSI新标准允许使用另一种方法声明形式参数，即在函数名后的括号中列出形式参数的同时，声明形式参数的类型。本题中函数f2的声明是这种形式。C语言编译器对于这种形式的函数声明是要进行实在参数和形式参数的个数和类型是否一致的检查的。因此，在编译函数调用f2(10.0