试题编号20
操作系统部分（共50分）
一 1、 进程p1,p2,…..pn都含有对同2、 一共享数据进行存取的临界区（c.s），3、
请用锁（lock）和信号量（semaphore）各说明或设计一种临界区互斥机制，4、 除实现互斥执行外，5、
它们还能使欲进入临界区的进程不6、 会无限期等待。（12分）
二 1、进程用户态图象（映象）通常由哪些段组成？它们的作用和区别是什么？（6分）
2、在C语言程序中，如果没有对外 部变量，静态局部变量和动态局部变量赋初值，则它们的初值是什么，请说明其原因。（7分）
三、1．请说明页式虚拟存储器的地址变换过程，并指出哪些操作是由操作系统完成的。（5分）
2． 在上述地址变换过程中，3． 进程状态有无可能发生变化？如可能，4． 则请指5． 出在哪些点上可能发生变化。（5分）
四、1．在unix文件系统中，文件的连接（link）是如何实现的？（6分）
2．请说明一种为文件改名（换名，rename）的基本方法。（4分）
3．使用link后，unix中某个文件可能有若干个路径名（pathname）,有人认为使用其不同的路径名就可以使同一用户具有对该文件的不同存取权，你的意见如何，并说明理由。（3分）
编译原理部分（共50分）
1、 生成语言l={albmclanbn l>=0,m>=1,n>=2 }的文法是什么？它是chomsky那一型文法？ （5分）
2、 文法G1：P aPQR abR
RQ QR
BQ bb
bR bc
cR cc
它是chomsky哪一型文法？请证aaabbbccc是G1的一个句子。（5分）
3、 文法G2:PaPbQ
QbQcbSc
SSaa
1、 请构造它的SLR分析表，2、 以说明它是不3、 是SLR文法。（７分）
２、在消除左递归、提取公共因子后可得等价文法Ｇ２，它是不是ll(1)文法。（６分）
四、求与正规R=(ab)*a(ab)*a(ba)*等价的minＤＦＡ （８分）
五、文法Ｇ3及相应翻译方案为
pbQb {print:”1”}
QcR {print:”2”}
Qa {print:”3”}
RQab {print:”4”}
1、 该文法是不2、 是算符优先文法，3、 请构造算符优先关系表证实之。（５分）
4、 输入串为bcccaadadb时，5、 该翻译方案的输出是什么？（４分）
1、 三维数组a[2:5,-2:2,5:7]首址为100,每个数组元素占４个存储单元，2、 求数组元素a(3,1,6)的地址。 （５分）
3、 下列程序段若以Ｂ表示循环体，4、 Ａ表示初始化，5、 Ｉ表示增量，6、 Ｔ表示测试。
I:=1;
While I<=n do
Begin
Sun:=sun+a[I];
I:=I+1
End
请用正规表达式表示这个程序段可能的执行序列。 （５分）