一九九五年招收硕士学位研究生入学考试试题 试题名称:编译原理与操作系统 (8分) Pascal语言无符号数的正规定义如下: num(digit( . digit) ? ( E ( + | - ) ? digit) ? 其中digit表示数字.用状态转换图表示接受无符号数的确定的有限自动机. (10分) 给出接受文法 S ---> (L) | a L ---> L , S | S 的活前缀的一个确定的有限自动机. (15分) 为语言 { | n > m ≥ 0 } 写三个文法,它们分别是二义文法,LR(1)文法和非LR(1)且非二义的文法.不必证明你写的文法的正确性.但每个文法的产生式不能超过4个. (10分) 下面的文法产生含加号的算术表达式.两个整型数相加时,结果是整型数,否则是实型数.注意,当一个整型数和一个实型数相加时,应先将此整型数转换成实型数. E ----> E + T | T T ----> num . num | num 给出语法制导的定义(或叫做加上动作子程序),它产生相应的后缀表达式,该后缀表达式已插入了适当的整型数转换成实型数的操作. (7分) 用数的最优化代码生成算法为表达式 ( a ± b ) * ( c – d ) – ( e + f ) / ( g – h ) 产生目标代码.假定所有的变量都是静态的,并假定只有两个寄存器可用. 简答题(每小题4分) 什么是系统调用?它们与普通的过程调用有什么不同? 确定作业调度算法时通常要考虑那些因素,如何衡量一个调度算法的性能? 解决死锁问题有那几种策略?它们处理死锁的基本思想分别是什么? 什么是虚拟存储器?虚拟存储器的容量如何确定? 在UNIX中,进程映象中的数据段是由那几部分组成的?其主要内容是什么? (8分) 在Madnick给出的文件系统层次模型中,从用户程序发出一条“读”文件命令到系统启动I/O设备开始读,要经过那些主要步骤,各属于什么模块? (8分) 在UNIX系统中,假设有二个用户进程A和B在同时运行,它们开始执行时要打开若干文件,其操作如下: A进程: … fda1=open("/usr/tmp/SharedData",O_RDONLY (只读) ); fda2=open("local",O_WRONLY (只写) ); fda3=open("/usr/tmp/SharedData",O_RDWR (读写) ); … B进程: … fdb1=open("/usr/tmp/SharedData", O_RDONLY); fdb2=open("private",O_RDONLY); … 假设这些操作都能成功完成,试给出(或画出)完成这些文件打开操作之后,进程A和进程B的用户打开文件表,系统打开文件表和相应被打开文件的活动i-节点(inode)表的内容(如文件访问计数等).并用图形表示这些数据结构之间相互关系.