一九九六年招收硕士学位研究生入学考试试题 试题名称:编译原理与操作系统 (5分) 画出一个DFA,它能接受∑={ 0, 1 }上能被3整除的二进制数. (5分) 下面的条件语句试图消除else的二义性.说明这个文法仍然是二义的. stmt ---> if expr then stmt | matched_stmt matched_stmt ---> if expr then matched_stmt else stmt | other (5分) 画出下面基本块的无环有向图. d := b*c e := a+b b := b*c a := e-d (15分) 构造下面文法的LL(1)分析表. S ---> aBS | bAS | ε B ---> aBB | b A ---> bAA | a 为上面文法写一个语法制导定义,它统计句子中a的个数和b的个数. (10分) 某些语言允许给出名字表的一个属性表,也允许声明嵌在另一个声明里面,下面文法抽象这个问题. D ---> attrlist namelist | attrlist (D) namelist ---> id, namelist | id attrlist ---> A attrlist | A A ---> decimal | fixed | float | real D ---> attrlist(D) 的含义是: 在括号中的声明提到的所有名字有attrlist中给出的属性,而不管声明嵌套多少层,.写一个翻译方案,它将一个名字的属性个数填入符号表. (10分) 下面是一个C语言程序及其运行结果.从运行结果看,函数func中四个局部变量i1,j1,f1,e1的地址间隔和它们类型的大小是一致的,而四个形式参数i,j,f,e的地址间隔和它们类型的大小不一致,试分析不一致的原因. #include <stdio.h> func(i,j,f,e) short i,j; float f,e; { short i1,j1; float f1,e1; i1= i; j1=j; f1=f; e1=e; printf("Addresses of i,j,f,e = %d, %d, %d, %d \n",&i,&j,&f,&e); printf("Addresses of i1,j1,f1,e1 = %d, %d, %d, %d \n",&i1,&j1,&f1,&e1); printf("Sizes of short, int, long, float, double=%d, %d, %d, %d, %d\n", sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double) ) } main() { short i,j; float f,e; i = j = 1; f = e = 1.0; func(I,j,f,e); } 运行结果 Addresses of i, j, f, e = -268438178, -268438174, -268438172, -268438164 Addresses of i1,j1,f1,e1 = -268438250, -268438252, -268438256, -268438260 Sizes of short, int, long, float, double = 2, 4, 4, 4, 8 (5分) 在存储管理中,覆盖和对换计数索要解决的是什么问题?各有什么特点? (5分) 假设有一台计算机只含有4各页框(页架或物理页),每一页的装入时间、访问位(R)和修改位(M)的值如下表所示.现在要淘汰其中的一页,问分别采用1) LRU算法; 2) NRU算法; 和 3) FIFO算法时,各淘汰那一页? 页 装入时间 最后访问时间 访问位(R) 修改位(M)  0 1026 2079 0 0  1 2030 2060 1 0  2 1020 2072 1 1  3 1060 2080 1 1  (10分) 在分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址的寻址空间为),会给页表的设计带来什么样的新问题?请给出一种解决方案,分析它的优点和缺陷. (10分) 在多用户系统中,请求I/O操作的进程可能会因为阻塞而被暂时换出内存,因而无法收到驱动程序返回的结果.采用那些方法可以解决这个问题?如何解决?各有什么特点? 十一. (10分) sleep 和 wakeup 是一对系统调用,其中sleep()的功能是阻塞调用者,被阻塞的进程一直处于睡眠状态,知道被其它的进程唤醒;而wakeup(process)的功能是唤醒阻塞(处于睡眠状态)的进程process.请用它们写出解决具有N个缓冲区的生产者与消费者问题的算法,并分析可能出现的情况. 十二. (10分) 在UNIX系统V中,当一个进程所访问的一页既不在内存又不在文件系统中时,该页可能在什么地方?存储管理模块是如何把它调入内存的?