武汉大学1999年研究生入学考试 编译原理试题（共60分）

1. (5分)

计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？

2. (7分)

Chomsky将文法分成四类。指明这四类文法与自动机的对应关系。指出右线性文法、左
线性文法、正规文法之间的主要区别。

3. (8分)

何谓“语法制导翻译(SDTS)”?试给出用SDTS生成中间代码的要点，并用一简例予以说
明。

4. (10分)

设有L(G)={a2n+1b2ma2p+1| n≥0,p≥0,m≥1}。

① 给出描述该语言的正规表达式；

② 构造识别该语言的确定的有穷自动机(可直接用状态图形式给出)。

5. (10分)

区别下列概念：

① 原语与特权指令；

② 顺序进程与并发进程；

③ 死锁与饥饿；

④ 多用户OS与多道程序设计；

⑤ 存贮设备与存贮介质。

6. (5分)

从宏观结构上看，OS有哪几种结构设计方法？你认为哪种方法较好？为什么