上海交通大学1997年硕士研究生入学考试编译原理及操作系统

上海交通大学1997年硕士研究生入学考试编译原理及操作系统 编译部分： 1、 请构造与正规式R=(a*/b*)b(ba)*等价的状态最少的DFA. (9分) 2、 表达式-a+b*c+d+(e*f)/d*e,如果优先级由高到低依次为-.+.*./,且均为左结合，3、 请写出其后缀式。（５分） 4、 文法G及相应的翻

上海交通大学1997年硕士研究生入学考试编译原理及操作系统

编译部分：

1、 请构造与正规式R=(a*/b*)b(ba)*等价的状态最少的DFA. (9分)

2、 表达式-a+b*c+d+(e*f)/d*e,如果优先级由高到低依次为-.+.*./,且均为左结合，3、 请写出其后缀式。（５分）

4、 文法G及相应的翻译方案，5、 如下

Ｓ bTc {print:”1”}

Sa {print:”2”}

TR {print:”3”}

RR/S {print:”4”}

RS {print:”5”}

1． 文法G属于chomsky哪一型文法？（１分兵

2． 符号串bR/bTc/bSc/ac是不3． 是该文法的一个句型，4． 请证实。（２分）

5． 若是句型，6． 写出该句型的所有短语、素短语，7． 以及句柄。（６分档

8． 文法G是不9． 是算符优先文法，10． 请予证实。（５分）

11． 文法Ｇ经消除左递归后得到的等价文法Ｇ＇是不12． 是ll(1)文法，13． 请予证实。（5分）

14． 文法G是不15． 是LSR(1)文法，16． 请予以证实。（7分）

17． 对于题材的输入符号串，18． 该翻译方案的输出是什么？（5分）

6、 数组var a:array[1..5,-3..6] of integer;按列存放，7、 其首址100,每个整数占4个字节，8、 内存按字节编址，9、 则数组元素a[4,3]的地址是什么？ （5分）

操作系统部分

10、 某数据库有一个写进程，11? N个读进程，12、 它们之间读、写操作的互斥要求是：

1． 写进程正在写该数据库时，2． 不3． 能有其它进程读该数据库。

4． 读进程之间不5． 互斥，6． 可以同7． 时读该数据库。

8． 如果有若干进程正在读该数据库，9． 一个写进程正等待写，10． 则后随欲读的进程也不11． 能读该数据库，12． 需等待写进程先写。

请用信号量及 p,v操作描述这一组成进程的互斥及工作过程。（14分）

13、 请阅读下列程序：

main( )

{

int I ;

while ((I=fork())== -1);

if (I);

{

printf(“It is patent process.”);

wait( );

printf(“My Child process,ID number %d exited.”);

exit( );

}

else printf(“It is child process,);

printf(“It is child or parent process.”);

}

(1) 说明运行该程序时可能产生的各种输出。

(2) 说明执行本程序的两个进程，(3) 在执行哪些语句时会发生由SRUN状态转变为SSLEEP,或SZOMB状态，(4) 发生这些状变化的可能原因是什么？（12分）

14、 请为配置在32位机上的unix设计一个文件地址索引结构，15、 其要求是：（1）在使用该索引表将文件逻辑块号转换为物理块号时，16、 不17、 需要使用文件长度类型信息。发（2）索引范围（逻辑块号的变化范围）为0-(10+128+128*128+128*128*128-1)。（12分）

18、 在内存管理中，19、 “内零头“和“外零头“各指20、 的是什么？在固定式分区分配、可变式分区分配、页式虚拟存储系统、段式虚拟系统中，21、 各会存在何种零头？为什么？（12分）