武汉大学1997年研究生入学考试编译原理试题（共55分）
1. (4分)
设有语言L(G)={adaR | aÎ(a,b)*, aR 为a之逆}，试构造产生此语言的上下文无
关文法G。
2. (10分)
设有语言L(G)={a2nb2n+1a2n | n30}
① 给出描述语言的正则表达式R；
② 直接画出识别该语言的状态转换图。
3. (8分)
LR分析器与优先分析器在识别句柄时的主要异同是什么？
4. (6分)
什么是规范句型的活前缀？引进它的意义何在？
5. (9分)
(简答下列问题)
① 批处理、分时和实时操作系统各有什么特点？
② 文件有那几种逻辑结构？有哪几种物理结构？
③ 产生死锁的必要条件是什么？
6. (9分)
某系统的进程状态图如下所示：
图1 进程状态图
① 说明一个进程发生变迁3、4、6的原因；
② 下述因果变迁是否会发生？若会，在什么情况下发生？
(a) 3®5; (b) 6®4; (c) 6®7;
③ 根据此进程状态图，说明该系统的 CPU调度策略和调度效果。
7. (9分)
某一系统采用请求分页式虚存管理，页面淘汰算法为LRU(最近最少使用)法。每个作业
占15页主存，其中一页用来存放程序，每一页存放200个整型变量。考虑下列程序：
var A,B:array[1..20,1..100] of integer;
i,j:integer;
begin
for i:=1 to 20 do
for j:=1 to 100 do
A[i,j]:=0;
for i:=1 to 20 do
for j:=1 to 100 do
B[i,j]=A[i,j];
end;
设数组A,B均按行存储，程序页已调入主存，变量i,j存放在程序页中。问此程序会产
生多少次缺页中断？运行结束后，留在内存中有哪些页？