一、编译部分
1、请构造与正规式R=(a*/b*)b(ba)*等价的状态最少的DFA. (9分)
2、表达式-a+b*c+d+(e*f)/d*e,如果优先级由高到低依次为-.+.*./,且均为左结合，请写出其后缀式。（５分）
3、文法G及相应的翻译方案，如下
SbTc {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)文法G是不是算符优先文法，请予证实。（５分）
(5)文法Ｇ经消除左递归后得到的等价文法Ｇ'是不是文法？请予证实。（5分）
(6)文法G是不是LSR(1)文法，请予以证实。（7分）
(7)对于题材的输入符号串，该翻译方案的输出是什么？（5分）
4、数组var a:array[1..5,-3..6] of integer;按列存放，其首址100,每个整数占4个字节，内存按字节编址，则数组元素a[4,3]的地址是什么？ （5分）

二、操作系统部分
1.某数据库有一个写进程，N个读进程，它们之间读、写操作的互斥要求是：写进程正在写该数据库时，不能有其它进程读该数据库。读进程之间不互斥，可以同时读该数据库。如果有若干进程正在读该数据库，一个写进程正等待写，则后随欲读的进程也不能读该数据库，需等待写进程先写。请用信号量及 p,v操作描述这一组成进程的互斥及工作过程。（14分）
2、 请阅读下列程序：
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分）
3、 请为配置在32位机上的unix设计一个文件地址索引结构，其要求是：在使用该索引表将文件逻辑块号转换为物理块号时，不需要使用文件长度类型信息。发索引范围（逻辑块号的变化范围）为0-(10+128+128*128+128*128*128-1)。（12分）
4、在内存管理中，“内零头“和“外零头“各指的是什么？在固定式分区分配、可变式分区分配、页式虚拟存储系统、段式虚拟系统中，各会存在何种零头？为什么？（12分）