编译部分：
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.\n”);
wait( );
printf(“My Child process,ID number %d exited.\n”);
exit( );
}
else printf(“It is child process,\n);
printf(“It is child or parent process.\n”);
}
(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分）