上海交通大学一九九九年硕士生编译原理及操作系统试题

　　上海交通大学一九九九年硕士生入学考试试题

　　试题序号20

　　试题名称：编译原理及操作系统。

　　编译原理部分(共50分)

　　一、 请写出在å={a,b}上，不是a开头的，以aa结尾的字符串集合的正规表达式，并构造与之等价的状态最少的的DFA。(9分)

　　二、 给出方法G1：

　　S aSb P

　　P bPc bQC

　　Q Qa a

　　1、 它是Chomsky哪一型方法?

　　2、 它生成的语言是什么?

　　3、 它是不是算符优先文法，请构造算符优先关系表证实之。

　　4、 请证实所有(a)左递归文法(b)有公共左因子的文法均不是ll(1)文法。

　　5、 文法G1消除左递归，提取公共左因子后是不是ll(1)文法?请证实。 (共15分)

　　三、给出文法G2:S SaS SbS cSd eS f

　　1、 请证实这是一个二义文法;

　　2、 给出什么的约束条件，可构造出无冲突的LR分析表?请证实你的论点。(8分)。

　　四、给出下列代码序列：

　　(1) a:=b-c

　　(2) d:=a+4

　　(3) e:=a-b

　　(4) f:=c+e

　　(5) b:=b+c

　　(6) c:=b-f

　　(7) if b

　　(8) b:=b-c

　　(9) f:=b+f

　　(10) a:=a-f

　　(11) if a=c goto (3)

　　(12) halt

　　1、 请划分基本块，并构造流图。

　　2、 假定各基本块出口之后的活跃变量均为a.c.f,循环中可用作固定分配的寄存器为R0和R1,固定分配给循环中哪二个变量，可使执行代价省得最多? (10分)

　　五、下列基本块内代码：

　　t1:=3*a

　　t2:=2*c

　　t3:=t1+t2

　　t4:=t3+5

　　t5:=2*c

　　t6:=3*a

　　t7:=t6+t5

　　t8:=t7-1

　　t9:=t4-t8

　　1、 请问dag进行局部优化。

　　2、 基本块出口时t9衡为6，是否有进一步优化的方法，可获得此结果?

　　(共8分)

　　操作系统原理部分

　　1、 你认为下列哪几种指令应该在核心状态下执行：(10分)

　　(1) 屏蔽所有中断;

　　(2) 读时钟周期;

　　(3) 设置时钟日期;

　　(4) 改变存储映像图;

　　(5) 存取某地址单元的内容;

　　(6) 停机。

　　2、 请用信号量实现对某数据库的读者_写者(reader—writer)互斥，(10分)其要求是：

　　.读者与写者之间，写者与写者之间互斥;

　　.读者之间不互斥。

　　3、 一台计算机有8台磁带机，它们由n个进程竞争使用，每个进程可能需要3台磁带机，请问n为多少时，系统没有死锁危险，请说明其原因。 (6分)

　　4、 当前磁盘读写位于柱面号20，此时有多个磁盘请求以下柱面号顺序送至磁盘驱动器：10，22，20，2，40，6，38。寻道(track)时，移动一个柱面需6MS，按下列三种算法计算所需寻道时间(柱面移动顺序及所需时间，总寻道时间;忽略最近指定柱面后所需寻道时间)

　　(1) 先到先服务

　　(2) 下一个最邻近柱面

　　(3) 电梯算法(当前状态：向上)(10分)

　　5、 一台计算机有4个页推，装入时间，上次引用时间和它们的R(读)和M(修改)位如下所示(时间单位：滴答)，请问NRU、FIFO、LRO和第二次机会算法将替换哪一页? (10分)

　　页 装入时间 上次引用时间 R M

　　0 126 279 0 0

　　1 230 260 1 0

　　2 120 272 1 1

　　3 160 280 1 1

　　6、在unix系统中，如果当前上当是/usr/wang,那么相对路径为../last/´´´,文件的绝对路径是什么? (4分)