清华大学计算机编译原理及操作系统试题

编译原理第1部分。(5%)给出NFA M的以下五重表示并确定它。

2 (5%)构造一个没有ε-转移的NFA M’，使得L(M’)= L(M)

3 (10%)证明文法G[A]是LR(1)文法。
G[a]:a-> ba |ε
b-> ab | b
4(5%)证明不冲突(shift

5。(5%)目标代码运行时的存储空采用基于进程活动记录的堆栈分配方案，并举例说明PASCAL
这样的语言如何访问非局部变量。

6(15%)文法G[R]:R-> R R | R | R * |(R)| A | B |ε
(1)证明文法G[R]生成字母表σ = {a，b}上的所有正则表达式(使用连接词
不省略)
(2)证明这个文法是二义性的
(3)根据三个运算符的优先和组合约定重构
一个等价的LL(1)()

7(5%)在下面的流程图中找出由后沿和后沿组成的回路。编译中的流程图做了什么？

操作系统部分

一、排名说明(10分)
多程序、多处理、进程、线程、虚拟内存
二、排名说明。画出NT操作系统的线程状态转换图(10分)
III。UNIX系统和Linux系统都提供了管道文件的功能，简单描述一下管道()的工作原理。(10分)
四。设周期性任务P1、P2和P3的周期T1、T2和T3分别为100、150和350；执行时间分别为
20、40和100。计算后的答案可以用频率单调调度算法调度吗？(10分)
五、如何实现I/O控制？各有什么优缺点？(10分)