編譯原理部分
1.(5%) 給出下述NFA M的五元組表示, 并將其確定化
2 (5%) 構(gòu)造一個不具有ε-轉(zhuǎn)移的NFA M’ , 使得L(M’)=L(M)
3 (10%) 證明文法G[A]是LR(1)文法.
G[A]: A->BA|ε
B->aB|b
4 (5%) 證明合并不存在沖突(移進(jìn)/歸約、歸約/歸約)的LR(1)項(xiàng)目集的同心集不會產(chǎn)生新的移進(jìn)/
歸約沖突.
5.(5%) 對目標(biāo)代碼運(yùn)行時的存儲空間采用基于過程活動記錄的棧式分配方案, 舉例說明象PASCAL
這樣的語言如何實(shí)現(xiàn)對非局部變量的訪問.
6(15%) 文法G[R]: R->R R | R·R | R*| (R) | a | b | ε
(1) 證明文法 G[R] 生成字母表 Σ={a, b} 上的所有正規(guī)表達(dá)式(用 代替”|”, 連接符·
沒有省略)
(2) 證明此文法是二義的
(3) 根據(jù)正規(guī)式的三個運(yùn)算符( ,·, *) (或, 連接, 閉包) 的優(yōu)先性和結(jié)合性約定重新構(gòu)
造一個等價的LL(1) 文法
7(5%) 找出下列流圖中的回邊和回邊組成的循環(huán).編譯中利用流圖完成什么工作?
操作系統(tǒng)部分
一、 名次解釋（10分）
多道程序、多重處理、進(jìn)程、線程、虛存
二、 畫出NT操作系統(tǒng)的線程狀態(tài)轉(zhuǎn)移圖（10分）
三、 UNIX系統(tǒng)與Linux系統(tǒng)等中都提供pipe文件功能，簡述pipe() 的工作原理。（10分）
四、 設(shè)周期性任務(wù)P1，P2，P3的周期T1，T2，T3分別為100，150，350；執(zhí)行時間分別為
20，40，100。試計(jì)算后回答是否可以用頻率單調(diào)調(diào)度算法進(jìn)行調(diào)度？（10分）
五、 I/O控制可用那幾種方式實(shí)現(xiàn)？各有何優(yōu)缺點(diǎn)？（10分）
1.(5%) 給出下述NFA M的五元組表示, 并將其確定化
2 (5%) 構(gòu)造一個不具有ε-轉(zhuǎn)移的NFA M’ , 使得L(M’)=L(M)
3 (10%) 證明文法G[A]是LR(1)文法.
G[A]: A->BA|ε
B->aB|b
4 (5%) 證明合并不存在沖突(移進(jìn)/歸約、歸約/歸約)的LR(1)項(xiàng)目集的同心集不會產(chǎn)生新的移進(jìn)/
歸約沖突.
5.(5%) 對目標(biāo)代碼運(yùn)行時的存儲空間采用基于過程活動記錄的棧式分配方案, 舉例說明象PASCAL
這樣的語言如何實(shí)現(xiàn)對非局部變量的訪問.
6(15%) 文法G[R]: R->R R | R·R | R*| (R) | a | b | ε
(1) 證明文法 G[R] 生成字母表 Σ={a, b} 上的所有正規(guī)表達(dá)式(用 代替”|”, 連接符·
沒有省略)
(2) 證明此文法是二義的
(3) 根據(jù)正規(guī)式的三個運(yùn)算符( ,·, *) (或, 連接, 閉包) 的優(yōu)先性和結(jié)合性約定重新構(gòu)
造一個等價的LL(1) 文法
7(5%) 找出下列流圖中的回邊和回邊組成的循環(huán).編譯中利用流圖完成什么工作?
操作系統(tǒng)部分
一、 名次解釋（10分）
多道程序、多重處理、進(jìn)程、線程、虛存
二、 畫出NT操作系統(tǒng)的線程狀態(tài)轉(zhuǎn)移圖（10分）
三、 UNIX系統(tǒng)與Linux系統(tǒng)等中都提供pipe文件功能，簡述pipe() 的工作原理。（10分）
四、 設(shè)周期性任務(wù)P1，P2，P3的周期T1，T2，T3分別為100，150，350；執(zhí)行時間分別為
20，40，100。試計(jì)算后回答是否可以用頻率單調(diào)調(diào)度算法進(jìn)行調(diào)度？（10分）
五、 I/O控制可用那幾種方式實(shí)現(xiàn)？各有何優(yōu)缺點(diǎn)？（10分）