上海交通大学编译原理与操作系统九八

上海交通大学一九九八年硕士讨论生入学考试试题 试题名称：编译原理及操作系统 操作系统部分（共 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={albmclanbn l>=0,m>=1,n>=2 }的文法是什么？它是 chomsky 那一型文法？ （5 分）二、文法 G1：P aPQR abR RQ QR BQ bb bR bc cR cc它是 chomsky 哪一型文法？请证 aaabbbccc 是 G1的一个句子。（5 分）三、文法 G2:PaPbQ QbQcbSc SSaa1、请构造它的 SLR 分析表，以说明它是不是 SLR 文法。（７分） ２、在消除左递归、提取公共因子后可得等价文法Ｇ２，它是不是 ll(1)文法。（６分）四、求与正规 R=(ab)*a(ab)*a(ba)*等价的 min ＤＦＡ （８分）五、文法Ｇ 3及相应翻译方案为pbQb {print:”1”}QcR {print:”2”}Qa {print:”3”}RQab {print:”4”}1、该文法是不是算符优先文法，请构造算符优先关系表证实之。（５分）2、输入串为 bcccaadadb 时，该翻译方案的输出是什么？（４分）一、三维数组 a[2:5,-2:2,5:7]首址为 100,每个数组元素占４个存储单元，求数组元素a(3,1,6)的地址。 （５分）二、下列程序段若以Ｂ表示循环体，Ａ表示初始化，Ｉ表示增量，Ｔ表示测试。 I:=1; While I<=n do Begin Sun:=sun+a[I]; I:=I+1 End 请用正规表达式表示这个程序段可能的执行序列。 （５分）