中国科学技术大学 一九九七年招收硕士学位研究生入学考试试题 试题名称:编译原利于操作系统 编译原理部分 (8分) 为正规式 ( a | b )a ( a | b ) 构造一个确定的有限自动机. (5分) 在Pascal语言中, begin , var 和 type 是保留字,而 integer, true 和 sin等是标准标识符.保留字有固定含义,而标准标识符可由用户进行重定义,编译器在处理这两类符号时有何区别? (10分) 为下列文法构造LR(1)项目集规范族,然后通过合并同心集构造LALR(1) 项目集规范族,最后确定该文法是否是LALR(1)文法. S ---> A B ---> ε C --->ε A ---> BCA A ---> a (7分)简要说明为什么C语言可以允许一函数的返回值类型是函数类型(即函数指针类型),而Pascal语言不允许? (10分)就下面的文法 S ---> ( L ) |ａ　 Ｌ　--->　L, S | S 给出一个翻译方案，它输出每个ａ的嵌套深度．如句子( a, ( a, a) ) 的输出是1 2 2 (10分)简要说明为什么下面程序的运行不终止. main() { addr(); loop(); } long *p; loop() { long i, j; j=0; for( i=0; i < 10; i ++) { printf(“*p=%ld\n,j=%ld\n”,*p, j ); (*p) – – ; j ++; } } addr() { long x; x=0; p=&x; } 操作系统部分 (6分) 在操作系统中,虚拟技术主要表现在那些地方? (6分) 某操作系统只支持单级文件目录,如果它允许在该目录下有任意多的文件和任意长的文件名,可否用它来模拟多级目录?若可以,请给出你的方法. (8分) 解决死锁问题的方法通常有哪几种?各有什么特点? (10分) 请用send / receive 原语和伪Pascal语言(或C语言) 写出一个解决具有N个缓冲区的“生产者---消费者”问题的算法. (10分) 在UNIX系统V中,请求调页管理采用了哪几种主要的数据结构?其功能各是什么?如果一个进程当前访问的虚地址为1996K,相应的物理页号为1997,其拷贝在对换设备1上,对应的块号为2000,引用计数为1.请以该情况为例,给出上述主要数据结构之间的关系描述. (10分) 在分页存储管理中,如果虚地址的长度为64位,页的大小为4K,那么一个作业的页表有多大?会给系统的实现带来什么样的新问题?请给出两种可能的解决方案.