清華大學2001年考研專業課試卷編譯原理及操作系統

編譯原理部分

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%) 證明合并不存在沖突(移進/歸約、歸約/歸約)的LR(1)項目集的同心集不會產生新的移進/歸約沖突.

5.(5%) 對目標代碼運行時的存儲空間采用基于過程活動記錄的棧式分配方案, 舉例說明象PASCAL這樣的語言如何實現對非局部變量的訪問.

6(15%) 文法G[R]: R->R+R | R·R | R*| (R) | a | b | ε

(1)    證明文法 G[R] 生成字母表 Σ={a, b} 上的所有正規表達式(用+代替”|”, 連接符·沒有省略)

(2)    證明此文法是二義的

(3)    根據正規式的三個運算符(+,·, *) (或, 連接, 閉包) 的優先性和結合性約定重新構造一個等價的LL(1) 文法

7(5%) 找出下列流圖中的回邊和回邊組成的循環.編譯中利用流圖完成什么工作?
 
 
  
 
 
操作系統部分

一、名次解釋（10分）

多道程序、

多重處理、

進程、

線程、

虛存

二、畫出NT操作系統的線程狀態轉移圖（10分）

三、UNIX系統與Linux系統等中都提供pipe文件功能，簡述pipe() 的工作原理。（10分）

四、設周期性任務P1，P2，P3的周期T1，T2，T3分別為100，150，350；執行時間分別為20，40，100。試計算后回答是否可以用頻率單調調度算法進行調度？（10分）

五、I/O控制可用那幾種方式實現？各有何優缺點？（10分）