中国科学技术大学 一九九二年招收硕士学位研究生入学考试试题 试题名称:编译原理和操作系统 编译原理部分: (25分) 下面是一个FORTRAN77的程序,按语言的语义,该程序的结果是什么?在静态存储分配的情况下,实际的运行结果是什么?扼要说明理由. CALL SUB CALL SUB END SUBROUTINE SUB DATA I/10/ WRITE(*,*)I I=100 END 把下面自动机化简.  画出表达式(a+b)*c+d-(a+b)*c的树形表示和无环有向图(dag)表示. 画出下面程序第3次进入函数factor时的活动记录栈和静态链(访问链). program fact(input,output); var f, n: integer; function factor(n: integer): integer; begin if n=0 then factor:=1 else factor:=n*factor(n-1) end; begin readln(n); f:=factor(n); writeln(f) end. 一语言的文法如下 (10分) S ( aSb | Sb | b 描述该语言. 该文法是LR(1)文法吗?给出理由.若不是LR(1)的,给出这个语言的一个LR(1)文法. (10分) 考虑文法 S ( (L) | a L ( L,S | S 给出语法制导翻译(或语法制导定义),它打印出括号嵌套的最大深度. 写一个语法制导翻译(或翻译方案),它打引出每个a在句中是第几个字符.如,当句子为 (a,(a,(a,a),(a))) 时,两小题的结果分别是3和 2 5 8 10 14 . (5分) 给出下面语言的一个上下文无关文法 “形式为xy且xy的a和b的串” (说得更明白一些,若串长为偶数时,分成的等长的前后两部分不相同.) 操作系统部分: 填空(10分): 文件的物理组织有四种类型________、_______、_______和_______. 进程的基本特征是_______、_______、_______和_______. 引起进程调度的原因有(任举三种)_________、________和________. 产生死锁的四个必要条件是________、_______、_______和_______. 在非多道程序系统中,常用的作业调度算法有:__________、_________和___________. 通过_____________技术把原为独享设备改造成能为若干个用户共享的设备,以提高设备的利用率. 判断题(4分,每题1分,正确打“”,错误打“”) ( ) 进程是一段可执行的程序. ( ) 原语是用以完成特定功能的不可中断的一段程序. ( ) 引入SPOOLing系统是为了解决联机作业控制. ( ) 地址空间仅仅是指程序用来访问信息所用的一系列地址的集合. 用类 ALGOL语言描述(10分): 进程创建原语 利用信号量实现两并行进程的互斥 进程调度算法 设备管理中Release过程 回答问题(10分): 何谓临界资源?何谓临界区? 何谓死锁?如何预防? 作业调度程序的功能是什么? 建立一个文件的主要步骤有哪些? 说明在段页式存贮管理系统中动态地址翻译过程.(8分) 试分析UNIX系统中软中断信号的处理过程,必要时,可辅以流程图或图表说明.(8分)