上海交通大学一九九八年硕士研究生入学考试试题试题名称：编译原理及操作系统操作系统部分（共50分）一、进程p1,p2,.pn都含有对同一共享数据进行存取的临界区（c.s）,请用锁（lock）和信号量（semaphore）各说明或设计一种临界区互斥机制，除实现互斥执行外，它们还能使欲进入临界区的进程不会无限期等待。（12分）二、1、进程用户态图象（映象）通常由哪些段组成？它们的作用和区别是什么？（6分）2、在C语言程序中，如果没有对外部变量，静态局部变量和动态局部变量赋初值，则它们的初值是什么，请说明其原因。（7分）三、1请说明页式虚拟存储器的地址变换过程，并指出哪些操作是由操作系统完成的。（5分）2在上述地址变换过程中，进程状态有无可能发生变化？如可能，则请指出在哪些点上可能发生变化。（5分）四、1.在unix文件系统中，文件的连接（link）是如何实现的？（6分）2. 请说明一种为文件改名（换名，rename）的基本方法。（4分）3. 使用link后，unix中某个文件可能有若干个路径名（pathname）,有人认为使用其不同的路径名就可以使同一用户具有对该文件的不同存取权，你的意见如何，并说明理由。（3分）编译原理部分（共50分）一、生成语言l=a该文法是不是算符优先文法，请构造算符优先关系表证实之。（5分）一、生成语言l=a该文法是不是算符优先文法，请构造算符优先关系表证实之。（5分）输入串为bcccaadadb时，该翻译方案的输出是什么？（4分）三维数组a2:5,-2:2,5:7首址为100,每个数组元素占4个存储单元，求数组元素a（3,1,6）的地址。（5分）下列程序段若以E表示循环体，A表示初始化，1表示增量，T表示测试。1：=1；WhileI=0,m=1,n=2的文法是什么？它是chomsky那一型文法?（5分）二、文法G1：PaPQRabRRQQRBQbbbRbccRcc它是chomsky哪一型文法？请证aaabbbccc是G1的一个句子。（5分）三、文法G2：PaPbQQbQcbScSSaa1、请构造它的SLR分析表，以说明它是不是SLR文法。（7分）2、在消除左递归、提取公共因子后可得等价文法G2,它是不是ll（1）文法。（6分）四、求与正规R=（ab）*a（ab）*a（ba）*等价的minDFA（8分）五、文法G3及相应翻译方案为Sun:=sun+aI;pbQbprint:”1”QcRprint:”2”Qaprint:”3”RQabprint:”4”I:=I+1End（$分）请用正规表达式表示这个程序段可能的执行序列。