計(jì)算機(jī)編譯原理小抄

1、編譯原理名詞解釋1.局部?jī)?yōu)化：局限于基本塊范圍的優(yōu)化稱。2.二義性文法：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義性文法。3.display表：過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動(dòng)記錄的起始地址。由于過程嵌套允許內(nèi)層過程引用外層過程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過程運(yùn)行時(shí)必須跟蹤它的所有外層過程的最新活動(dòng)記錄起始地址， display表就是用于登記每個(gè)外層過程的最新活動(dòng)記錄起始地址。5.最左推導(dǎo)：任何一步=都是對(duì)中的最右非終結(jié)符替換。6.語法：一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法：描述語言的語法結(jié)構(gòu)的形式規(guī)則。8.基本塊：指程序中一順序執(zhí)行的語句

2、序列，其中只有一個(gè)入口和一個(gè)出口，入口就是其中的第一個(gè)語句，出口就是其中的最后一個(gè)語句。9.語法制導(dǎo)翻譯：在語法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義子程序進(jìn)行翻譯的辦法叫做語法制導(dǎo)翻譯。10.短語：令g是一個(gè)文法，s劃文法的開始符號(hào)，假定是文法g的一個(gè)句型，如果有sa且a，則稱是句型相對(duì)非終結(jié)符a的短語。11.待用信息：如果在一個(gè)基本塊中，四元式i對(duì)a定值，四元式j(luò)要引用a值，而從i到j(luò)之間沒有a的其它定值，則稱j是四元式i的變量a的待用信息。12.規(guī)范句型：由規(guī)范推導(dǎo)所得到的句型。13.掃描器：執(zhí)行詞法分析的程序。14.超前搜索：在詞法分析過程中，有時(shí)為了確定詞性，需超前掃描若干個(gè)字符。1

3、5.句柄：一個(gè)句型的最左直接短語。16.語法制導(dǎo)翻譯：在語法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義程序進(jìn)行翻譯的方法 叫做語法制導(dǎo)翻譯。17.規(guī)范句型：由規(guī)范推導(dǎo)所得到的句型。18.素短語：素短語是指這樣一個(gè)短語，至少含有一個(gè)終結(jié)符，并且，除它自身外不再含任何更小的素短語。19.語法：是組規(guī)則，用它可形成和產(chǎn)生一個(gè)合式的程序。 20.語義：定義程序的意義的一組規(guī)則。21.優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化21詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具

4、有獨(dú)立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。22ll(1)文法 若文法的任何兩個(gè)產(chǎn)生式a a | b都滿足下面兩個(gè)條件：（1）first(a ) first(b ) = f；（2）若b * e ，那么first(a ) follow( a ) = f。我們把滿足這兩個(gè)條件的文法叫做ll(1)文法，其中的第一個(gè)l代表從左向右掃描輸入，第二個(gè)l表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒有公共左因子外，ll(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。23語法樹句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。給

5、定文法g=(vn，vt，p，s)，對(duì)于g的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點(diǎn)的標(biāo)記是開始符號(hào)s。(2)每個(gè)節(jié)點(diǎn)的標(biāo)記都是v中的一個(gè)符號(hào)。(3)若一棵子樹的根節(jié)點(diǎn)為a，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)閍1a2ar，那么aa1a2ar一定是p中的一條產(chǎn)生式。(4)若一標(biāo)記為a的節(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則avn。(5)若樹的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法g的句型；若w中僅含終結(jié)符號(hào)，則w為文法g所產(chǎn)生的句子。24lr(0)分析器所謂lr(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸

6、約出的全部文法符號(hào)，并至多再向前查看0個(gè)輸入符號(hào)，就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作 (是移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等)。25語言和文法文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法g定義為四元組的形式：g=(vn，vt，p，s)其中：vn 是非空有窮集合，稱為非終結(jié)符號(hào)集合；vt 是非空有窮集合，稱為終結(jié)符號(hào)集合；p是產(chǎn)生式的集合(非空)；s是開始符號(hào)(或識(shí)別符號(hào))。這里，vnvt=，svn。v=vnvt，稱為文法g的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號(hào)的集合。文法g所描述的語言用l(g)表示，它由文法g所產(chǎn)

7、生的全部句子組成，即l(g)=x| s*x，其中s為文法開始符號(hào)，且 簡(jiǎn)單的說，文法描述的語言是該文法一切句子的集合。26詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。27ll(1)文法若文法的任何兩個(gè)產(chǎn)生式a a | b都滿足下面兩個(gè)條件：（1）first(a ) first(b ) = f；（2）若b * e ，那么first(a ) follow( a ) = f。我們把滿足這兩個(gè)條件的文法叫做ll(1)文法，其中的第一個(gè)l代表從左向右掃描輸入，第

8、二個(gè)l表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒有公共左因子外，ll(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。28語法樹句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。給定文法g=(vn，vt，p，s)，對(duì)于g的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點(diǎn)的標(biāo)記是開始符號(hào)s。(2)每個(gè)節(jié)點(diǎn)的標(biāo)記都是v中的一個(gè)符號(hào)。(3)若一棵子樹的根節(jié)點(diǎn)為a，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)閍1a2ar，那么aa1a2ar一定是p中的一條產(chǎn)生式。(4)若一標(biāo)記為a的節(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則avn。(5)若樹的所有葉

9、節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法g的句型；若w中僅含終結(jié)符號(hào)，則w為文法g所產(chǎn)生的句子。29lr(0)分析器所謂lr(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再向前查看0個(gè)輸入符號(hào)，就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作 (是移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等)。30語言和文法文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法g定義為四元組的形式：g=(vn，vt，p，s)其中：vn 是非空有窮集合，稱為非終結(jié)符號(hào)集合；vt 是非空有

10、窮集合，稱為終結(jié)符號(hào)集合；p是產(chǎn)生式的集合(非空)；s是開始符號(hào)(或識(shí)別符號(hào))。這里，vnvt=，svn。v=vnvt，稱為文法g的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號(hào)的集合。文法g所描述的語言用l(g)表示，它由文法g所產(chǎn)生的全部句子組成，即l(g)=x| s*x，其中s為文法開始符號(hào)，且 簡(jiǎn)單的說，文法描述的語言是該文法一切句子的集合。31.編譯過程的六個(gè)階段：詞法分析，語法分析，語義分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成32.解釋程序：把某種語言的源程序轉(zhuǎn)換成等價(jià)的另一種語言程序目標(biāo)語言程序，然后再執(zhí)行目標(biāo)程序。解釋方式是接受某高級(jí)語言的一個(gè)語句輸入，進(jìn)行解釋并控制計(jì)算機(jī)執(zhí)行，馬上

11、得到這句的執(zhí)行結(jié)果，然后再接受下一句。33.編譯程序：就是指這樣一種程序，通過它能夠?qū)⒂酶呒?jí)語言編寫的源程序轉(zhuǎn)換成與之在邏輯上等價(jià)的低級(jí)語言形式的目標(biāo)程序(機(jī)器語言程序或匯編語言程序)。34.解釋程序和編譯程序的根本區(qū)別：是否生成目標(biāo)代碼35.句子的二義性（這里的二義性是指語法結(jié)構(gòu)上的。）:文法gs的一個(gè)句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或者存在兩棵不同的語法樹，則稱這個(gè)句子是二義性的。36文法的二義性:一個(gè)文法如果包含二義性的句子，則這個(gè)文法是二義文法，否則是無二義文法。37.ll(1)的含義：(ll(1)文法是無二義的； ll(1)文法不含左遞歸)第1個(gè)l：從左到右掃描輸入串

12、。第2個(gè)l：生成的是最左推導(dǎo)。1 ：向右看1個(gè)輸入符號(hào)便可決定選擇哪個(gè)產(chǎn)生式38某些非ll(1)文法到ll(1)文法的等價(jià)變換: 1. 提取公因子 2. 消除左遞歸 39.文法符號(hào)的屬性:單詞的含義，即與文法符號(hào)相關(guān)的一些信息。如，類型、值、存儲(chǔ)地址等。40.一個(gè)屬性文法(attribute grammar)是一個(gè)三元組a=(g, v, f)g：上下文無關(guān)文法。v：屬性的有窮集。每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連。屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。f：關(guān)于屬性的斷言或謂詞(一組屬性的計(jì)算規(guī)則)的有窮集。斷言或語義規(guī)則與一個(gè)產(chǎn)生式相聯(lián)，只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性

13、。41.綜合屬性:若產(chǎn)生式左部的單非終結(jié)符a的屬性值由右部各非終結(jié)符的屬性值決定,則a的屬性稱為綜合屬。42.繼承屬性:若產(chǎn)生式右部符號(hào)b的屬性值是根據(jù)左部非終結(jié)符的屬性值或者右部其它符號(hào)的屬性值決定的,則b的屬性為繼承屬性。(1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號(hào)沒有繼承屬性。(2) 終結(jié)符只有綜合屬性，沒有繼承屬性，它們由詞法程序提供。在計(jì)算時(shí)： 綜合屬性沿屬性語法樹向上傳遞（即傳遞信息的方向是自下而上）；繼承屬性沿屬性語法樹向下傳遞（即傳遞信息的方向是自上而下）。 43.語法制導(dǎo)翻譯：是指在語法分析過程中，完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動(dòng)作。44.語法制導(dǎo)翻

14、譯實(shí)現(xiàn)：對(duì)單詞符號(hào)串進(jìn)行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語法樹并在語法樹的各結(jié)點(diǎn)處按語義規(guī)則進(jìn)行計(jì)算。45.中間代碼（中間語言）：1、是復(fù)雜性介于源程序語言和機(jī)器語言的一種表示形式。2、一般，快速編譯程序直接生成目標(biāo)代碼。3、為了使編譯程序結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，常采用中間代碼，這樣可以將與機(jī)器相關(guān)的某些實(shí)現(xiàn)細(xì)節(jié)置于代碼生成階段仔細(xì)處理，并且可以在中間代碼一級(jí)進(jìn)行優(yōu)化工作，使得代碼優(yōu)化比較容易實(shí)現(xiàn)。46.何謂中間代碼：源程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，易于代碼的機(jī)械生成。47.為何要轉(zhuǎn)換成中間代碼:(1)邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語言。(2)便

15、于移植，便于修改，便于進(jìn)行與機(jī)器無關(guān)的優(yōu)化。48.中間代碼的幾種形式：逆波蘭式（后綴式） ，三地址碼（三元式、四元式、間接三元式 ）49.符號(hào)表的一般形式：一張符號(hào)表的的組成包括兩項(xiàng)，即名字欄和信息欄。 信息欄包含許多子欄和標(biāo)志位，用來記錄相應(yīng)名字和種種不同屬性，名字欄也稱主欄。主欄的內(nèi)容稱為關(guān)鍵字（key word）。50.符號(hào)表的功能：（1）收集符號(hào)屬性 (2) 上下文語義的合法性檢查的依據(jù)： 檢查標(biāo)識(shí)符屬性在上下文中的一致性和合法性。(3)作為目標(biāo)代碼生成階段地址分配的依據(jù)51.符號(hào)的主要屬性及作用：1. 符號(hào)名 2. 符號(hào)的類型 （整型、實(shí)型、字符串型等）3. 符號(hào)的存儲(chǔ)類別（公共、私

16、有）4. 符號(hào)的作用域及可視性 （全局、局部） 5. 符號(hào)變量的存儲(chǔ)分配信息 （靜態(tài)存儲(chǔ)區(qū)、動(dòng)態(tài)存儲(chǔ)區(qū)）52.存儲(chǔ)分配方案策略：靜態(tài)存儲(chǔ)分配；動(dòng)態(tài)存儲(chǔ)分配：棧式、 堆式。 53.靜態(tài)存儲(chǔ)分配：1、基本策略：在編譯時(shí)就安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。2、適用的分配對(duì)象：子程序的目標(biāo)代碼段；全局?jǐn)?shù)據(jù)目標(biāo)（全局變量）3、靜態(tài)存儲(chǔ)分配的要求：不允許遞歸調(diào)用，不含有可變數(shù)組。fortran程序是段結(jié)構(gòu)，不允許遞歸，數(shù)據(jù)名大小、性質(zhì)固定。 是典型的靜態(tài)分配54.動(dòng)態(tài)存儲(chǔ)分配 ：1、如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、可變數(shù)組或允許用戶自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)

17、存儲(chǔ)管理技術(shù)。2、兩種動(dòng)態(tài)存儲(chǔ)分配方式：棧式，堆式棧式動(dòng)態(tài)存儲(chǔ)分配策略：將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧。【例】在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個(gè)過程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程工作結(jié)束時(shí)就釋放這部分空間。55.過程所需的數(shù)據(jù)空間包括兩部分：一部分是生存期在本過程這次活動(dòng)中的數(shù)據(jù)對(duì)象。如局部變量、參數(shù)單元、臨時(shí)變量等；另一部分則是用以管理過程活動(dòng)的記錄信息(連接數(shù)據(jù))。56.活動(dòng)記錄（ar）：一個(gè)過程的一次執(zhí)行所需要的信息使用一個(gè)連續(xù)的存儲(chǔ)區(qū)來管理，這個(gè)區(qū) (塊)叫做一個(gè)活動(dòng)記錄。構(gòu)成：1、臨時(shí)工作單元；2、局部變量；3、機(jī)器狀態(tài)信息；4、存取鏈；5、控制鏈；6、實(shí)參；7、

18、返回地址57.什么是代碼優(yōu)化所謂優(yōu)化，就是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加快或占用存儲(chǔ)空間減少。58.優(yōu)化原則：等價(jià)原則：經(jīng)過優(yōu)化后不應(yīng)改變程序運(yùn)行的結(jié)果。 59.有效原則：使優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用的存儲(chǔ)空間較小。 60.合算原則：以盡可能低的代價(jià)取得較好的優(yōu)化效果。61.常見的優(yōu)化技術(shù)：(1) 刪除多余運(yùn)算(刪除公共子表達(dá)式) (2) 代碼外提 +刪除歸納變量+ (3)強(qiáng)度削弱; (4)變換循環(huán)控制條件 (5)合并已知量與復(fù)寫傳播 (6)刪除無用賦值62.基本塊：程序中只有一個(gè)入口和一個(gè)出口的一段順序執(zhí)行的語句序列，稱為程序

19、的一個(gè)基本塊。64. 遍：指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。65.無環(huán)路有向圖(dag):如果有向圖中任一通路都不是環(huán)路，則稱廬有向圖為無環(huán)路有向圖，簡(jiǎn)稱dag66.語法分析：按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過程。67.二義性文法：如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義性文法。68.后綴式：種把運(yùn)算量寫在前面，把算符寫在后面的表示表達(dá)式的方法。 69.直接推導(dǎo)和推導(dǎo)直接推導(dǎo)：令g=(vt,vn,s,p), 若ap, 且,(vtvn)*稱a直接推出,表示成a 同時(shí)也稱是a的直接推導(dǎo)，或稱 直接歸約到a。推導(dǎo)：如果存在一個(gè)直接推導(dǎo)序列：0

20、12 n（n0）表示成0+n，稱從0到n的長(zhǎng)度為n的推導(dǎo)。0*n,或者0=n或者0+n .70.語言：設(shè)文法g（vt，vn，s,p）。如果s*,則稱是一個(gè)句型。僅含終結(jié)符號(hào)的句型是一個(gè)句子。語言l(g）是由文法g產(chǎn)生的所有句子所組成的集合：l(g)|s*且vt*71.單詞符號(hào)：由詞法規(guī)則確定的，具有獨(dú)立意義的最基本的結(jié)構(gòu)。它一般包括：基本字，標(biāo)識(shí)符，常數(shù)，運(yùn)算符和界符。72. 上下文無關(guān)文法：它是這樣的一種文法，它所定義的語法范疇（或語法單位）完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境之外，不宜描述自然語言。73. ll（k）分析法：第一個(gè)l表示從左到右掃描輸入串，第二個(gè)l表示最左推導(dǎo)，k表示分析時(shí)每一

21、步需向前查看k個(gè)符號(hào)。74. lr（k）分析法：第一個(gè)l表示從左到右掃描輸入串，第二個(gè)r表示最左推導(dǎo)的逆過程（既最右歸約），分析時(shí)每一步需向前查看k個(gè)符號(hào)。75. 算符優(yōu)先分析：所謂算符優(yōu)先分析就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種優(yōu)先關(guān)系尋找“可歸約串”和進(jìn)行歸約。76.什么是屬性文法：它是在上下文無關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)配備若干相關(guān)的“值”（稱為屬性）。這些屬性代表與文法符號(hào)相關(guān)的信息。77.有哪些存儲(chǔ)分配策略？并敘述何時(shí)用何種存儲(chǔ)分配策略？靜態(tài)分配策略：在編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元，且在運(yùn)行時(shí)始終保持不變。棧式動(dòng)態(tài)分配策略：在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，每當(dāng)

22、調(diào)用一個(gè)過程，所需存儲(chǔ)空間就動(dòng)態(tài)地分配于棧頂，一旦退出，所占空間就予以釋放。堆式動(dòng)態(tài)分配策略：在運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，凡申請(qǐng)者從堆中分給一塊凡釋放者退回給堆。78.編譯過程中可進(jìn)行的優(yōu)化如何分類？最常用的代碼優(yōu)化技術(shù)有哪些？依據(jù)優(yōu)化所涉及的程序范圍，可分為局部?jī)?yōu)化，循環(huán)優(yōu)化和全局優(yōu)化三種類型。最常用的代碼優(yōu)化技術(shù)有刪除公共子表達(dá)式、復(fù)寫傳播、刪除無用代碼、代碼外提、強(qiáng)度消弱、刪除歸納變量等。79.一個(gè)編譯程序的代碼生成要著重考慮哪些問題？代碼生成器的設(shè)計(jì)要著重考慮目標(biāo)代碼的質(zhì)量問題，而衡量目標(biāo)代碼的質(zhì)量主要從占用空間和執(zhí)行效率兩個(gè)反面來綜合考慮。80. 詞法分析器的輸出結(jié)果是詞法分析程序

23、的功能是讀入源程序，輸出單詞符號(hào)。單詞符號(hào)是一個(gè)程序設(shè)計(jì)語言的基本語法符號(hào)。單詞符號(hào)一般分為下列五種：關(guān)鍵字 標(biāo)識(shí)符 常數(shù) 運(yùn)算符 界符81. lr項(xiàng)目集規(guī)范族的項(xiàng)目類型分為如下4種：移進(jìn)項(xiàng)目 歸約項(xiàng)目 待約項(xiàng)目 接受項(xiàng)目 82. lr項(xiàng)目集規(guī)范族的項(xiàng)目合并同心集后可能出現(xiàn)什么問題？(1)同心集合并后心仍相同，超前搜索為原全集（2）合并同心集后，轉(zhuǎn)換函數(shù)自動(dòng)合并（3）若g是lr(1)的文法，合并同心集后，不會(huì)有移進(jìn)，歸約沖突，可能會(huì)有歸約歸約沖突（4）合并同心集后，可能推遲發(fā)現(xiàn)錯(cuò)誤的時(shí)間，但錯(cuò)誤出現(xiàn)位置正確，錯(cuò)誤是歸約。83.字母表：符號(hào)的非空有窮集合。84.符號(hào)：語言中最基本的不可再分的單位

24、。85.符號(hào)串：字母表中符號(hào)組成的有窮序列。86.句子：字母表上符合某種規(guī)則構(gòu)成的串。87.語言：字母表上句子的集合。88.非終結(jié)符：出現(xiàn)在規(guī)則的左部，表示一定語法概念的詞。89.終結(jié)符：語言中不可再分割的字符串，是組成句子的基本單位。90.開始符號(hào)：表示所定義的語法范疇的非終結(jié)符，又稱為識(shí)別符號(hào)。91.元語言符號(hào)：用來說明文法符號(hào)之間關(guān)系的符號(hào)。92.產(chǎn)生式：是用來定義符號(hào)串之間關(guān)系的一組語法規(guī)則。93.推導(dǎo)：從開始符號(hào)開始，銅鼓使用產(chǎn)生式的右部取代左部，最終產(chǎn)生語言的一個(gè)句子的過程。94.規(guī)約：推導(dǎo)的逆過程。95.句型：從文法的開始符號(hào)開始，每步推導(dǎo)所得到的字符串。96.狀態(tài)轉(zhuǎn)換圖：使用狀

25、態(tài)轉(zhuǎn)換圖是設(shè)計(jì)詞法分析程序的一種好途徑，狀態(tài)轉(zhuǎn)換圖是一張有限方向圖。在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài)，用圓圈表示。一個(gè)狀態(tài)轉(zhuǎn)換圖可用于識(shí)別（或接受）一定的字符串。97. 五元式：有限狀態(tài)集合、有窮字母表、轉(zhuǎn)換函數(shù)、唯一的初始狀態(tài)、終止?fàn)顟B(tài)集合。98.確定的有限自動(dòng)機(jī)（dfa）：一個(gè)確定有限自動(dòng)機(jī)（dfa） m是一個(gè)五元式：m (s,s0 ,f) ，其中s是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)，是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符，是一個(gè)從s至s的單值部分映射。 (s,a)=s意味著：當(dāng)現(xiàn)行狀態(tài)為、輸入字符為a時(shí)，將轉(zhuǎn)換到下一狀態(tài)s。我們稱s為s的一個(gè)后繼狀s0s是唯一的初態(tài)f 是一個(gè)終態(tài)

26、集（可空）。99.非確定有限自動(dòng)機(jī)（nfa）：一個(gè)非確定有限自動(dòng)機(jī)（nfa） m是一個(gè)五元式：m (s,s0 ,f) ，其中s是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)，是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符，是一個(gè)從s*至s的子集的映射，即： s* 2s，s0s是唯一的初態(tài)，f是一個(gè)終態(tài)集（可空）。簡(jiǎn)答題：1.簡(jiǎn)要說明語義分析的基本功能。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2.目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。應(yīng)著重考慮的問題：(1)如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如

27、何充分利用指令系統(tǒng)的特點(diǎn)。3.簡(jiǎn)述編譯程序的工作過程。編譯程序的工作過程，是指從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過程，是非常復(fù)雜的，就其過程而言，一般可以劃分為五個(gè)工作階段：詞法分析，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞；語法分析，根據(jù)語言的語法規(guī)則，把單詞符號(hào)串分解成各類語法單位；語義分析與中間代碼產(chǎn)生，即對(duì)各類語法單位，分析其漢一并進(jìn)行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更高效的代碼；目標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級(jí)語言指令形式。4編譯程序和高級(jí)語言有什么區(qū)別?用匯編語言或高級(jí)語言編寫的程序，必須先送入計(jì)算機(jī)，經(jīng)過轉(zhuǎn)換成用機(jī)器語言表示的目標(biāo)程序（這個(gè)過程即編譯

28、），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機(jī)器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對(duì)應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語言表示的程序。解釋型編譯程序?qū)⒏呒?jí)語言程序的一個(gè)語句，先解釋成為一組機(jī)器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)行人和計(jì)算機(jī)的對(duì)話，隨時(shí)可以修改高級(jí)語言的程序。basic語言就是解釋型高級(jí)語言。編譯型編譯程序?qū)⒓?jí)語言編寫的程序，一次就會(huì)部翻譯成機(jī)器語言表

29、示的程序，而且過程進(jìn)行很快，在過程中，不能進(jìn)行人機(jī)對(duì)話修改。fortran語言就是編譯型高級(jí)語言。5編譯程序的工作分為那幾個(gè)階段?詞法分析、語法分析和語義分析是對(duì)源程序進(jìn)行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱為對(duì)源程序進(jìn)行綜合(稱為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。6簡(jiǎn)述自下而上的分析方法。所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點(diǎn)。7簡(jiǎn)述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對(duì)程序代碼進(jìn)行一種

30、等價(jià)變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短，同時(shí)所占用的存儲(chǔ)空間少。8什么是s-屬性文法？什么是l-屬性文法？它們之間有什么關(guān)系？解答：s-屬性文法是只含有綜合屬性的屬性文法。 l-屬性文法要求對(duì)于每個(gè)產(chǎn)生式ax1x2xn，其每個(gè)語義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是xj的一個(gè)繼承屬性，且該屬性僅依賴于：(1)產(chǎn)生式xj的左邊符號(hào)x1,x2xj-1的屬性；(2)a的繼承屬性。 (3)s-屬性文法是l-屬性文法的特例。 9什么是句柄？什么是素短語？一個(gè)句型的最左直接短語稱為該句型的句柄。素短語是這樣的一個(gè)短語，它至少包含一個(gè)終結(jié)符并且不包含更小的素短

31、語。10劃分程序的基本塊時(shí)，確定基本塊的入口語句的條件是什么？解答：（1）程序第一個(gè)語句，或（2）能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或（3）緊跟在條件轉(zhuǎn)移語句后面的語句。11運(yùn)行時(shí)的display表的內(nèi)容是什么？它的作用是什么？答：display表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進(jìn)入的過程層次為i，則它的diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、直至最外層(主程序，0層)等每層過程的最新活動(dòng)記錄的起始地址。通過display表可以訪問其外層過程的變量。12. 目標(biāo)代碼有

32、哪幾種形式？生成目標(biāo)代碼時(shí)通常應(yīng)考慮哪幾個(gè)問題？目標(biāo)代碼通常采用三種形式：機(jī)器語言，匯編語言，待裝配機(jī)器語言模塊。應(yīng)著重考慮的問題： (1)如何使生成的目標(biāo)代碼較短；(2)如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；(3)如何充分利用指令系統(tǒng)的特點(diǎn)。13.簡(jiǎn)述規(guī)范歸約的基本思想。用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的候選式時(shí)，即把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符號(hào)。14.闡述編譯程序各個(gè)組成部分主要完成的工作。(1)詞法分析的任務(wù):輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞。2）語法分析：在詞法分析的基礎(chǔ)上，根據(jù)語言

33、的語法規(guī)則，把單詞符號(hào)串分解成各類語法單位。（3）語義分析與中間代碼產(chǎn)生：對(duì)語法分析所識(shí)別出的各類語法范疇，分析其含義，并進(jìn)行初步翻譯。（4）優(yōu)化：在于對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效的目標(biāo)代碼。（5）目標(biāo)代碼生成：把中間代碼變換成特定機(jī)器上的低級(jí)語言代碼。15.什么是編譯器的前端和后端，這樣劃分有何意義？ 編譯器粗略分為：詞法分析，語法分析，類型檢查，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成，目標(biāo)代碼優(yōu)化。把中間代碼生成及之前階段劃分問編譯器的前端，那么后端與前端是獨(dú)立的。后端只需要一種中間代碼表示，可以是三地址代碼或四元式等，而這些都與前端生成的方式無關(guān)。也就是

34、不論你前端是用fortran還是c/c+,只要生成了中間代碼表示就可以了，后端是不管你是用哪種語言生成的。16.喬姆斯基把文法分為哪幾種類型？對(duì)這幾種類型文法作簡(jiǎn)要說明。把文法分成四種類型：0，1，2，3型。與上下文無關(guān)文法一樣，它們都由四部分組成，但對(duì)產(chǎn)生式的限制有所不同。0型(短語文法，圖靈機(jī))：產(chǎn)生式形如： a b 其中：a (vt vn)*且至少含有一個(gè)非終結(jié)符；b (vt vn)*。1型(上下文有關(guān)文法，線性界限自動(dòng)機(jī))：產(chǎn)生式形如： a b 其中：|a| |b|。僅 se 例外，但此時(shí)s不得出現(xiàn)在任何產(chǎn)生式的右部。2型(上下文無關(guān)文法，非確定下推自動(dòng)機(jī))：產(chǎn)生式形如： a b 其中

35、：a vn；b (vt vn)*。3型(正規(guī)文法，有限自動(dòng)機(jī))：產(chǎn)生式形如： a ab 或 a a其中： a vt e；a，bvn產(chǎn)生式形如： a ba 或 a a 其中： a vt e；a，bvn。17.簡(jiǎn)述編譯過程中遍的概念以及遍數(shù)的多少對(duì)編譯器設(shè)計(jì)的影響。遍的概念：對(duì)源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。遍可以和階段相應(yīng)，也可無關(guān)。遍中通常含有若干個(gè)階段。實(shí)際上，根據(jù)語言的不同，編譯器可以是一遍（onepass）所有的階段由一遍完成，其結(jié)果是編譯得很好，但（通常）代碼卻不太有效。pascal語言和c語言均允許單遍編譯。（modula-2

36、語言的結(jié)構(gòu)則要求編譯器至少有兩遍）。大多數(shù)帶有優(yōu)化的編譯器都需要超過一遍：典型的安排是將一遍用于掃描和分析，將另一遍用于語義分析和源代碼層優(yōu)化，第3遍用于代碼生成和目標(biāo)層的優(yōu)化。更深層的優(yōu)化則可能需要更多的遍：5遍、6遍、甚至8遍都是可能的。18.編譯程序與解釋程序有何區(qū)別？答：二者的工作方法不同，后者是邊解釋邊執(zhí)行，解釋所得的代碼并不保存；前者是先將高級(jí)語言翻譯感情上標(biāo)代碼，將其保存到指定的空間中，待需要時(shí)再執(zhí)行之，甚至可以在案一個(gè)機(jī)器上編譯，而在另一臺(tái)機(jī)器上執(zhí)行。19.何謂素短語？答：素短語是滿足下述條件的短語：（1）它至少含有一個(gè)終結(jié)符號(hào)（2）滿足條件（1）的“最小”短語20.過程調(diào)用時(shí)

37、，主調(diào)程序與被調(diào)程序之間的信息傳遞有哪些方式？答：形式參數(shù)與實(shí)在參數(shù)結(jié)合方式傳遞（簡(jiǎn)稱參數(shù)傳遞）、返回值傳遞、共享數(shù)據(jù)區(qū)傳遞。21.何謂語法制導(dǎo)翻譯？答：語法制導(dǎo)翻譯是對(duì)前后文無關(guān)文法的擴(kuò)充，即對(duì)文法中的每個(gè)產(chǎn)生式都附加一個(gè)語義動(dòng)作或語義子程序，且在語法分析過程中，每當(dāng)需要使用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，語法分析程序除執(zhí)行相應(yīng)的語法分析動(dòng)作外，還要執(zhí)行相應(yīng)的語義動(dòng)作或調(diào)用相應(yīng)的語義子程序，完成相應(yīng)的語義分析和翻譯工作。22.何謂算符文法？答：當(dāng)一個(gè)文法的所有產(chǎn)生式的右部均不出現(xiàn)兩個(gè)非終結(jié)符號(hào)相鄰的情況時(shí)，該就被稱為算符文法。23.什么是句子？ 什么是語言 ?答：(1)設(shè)g是一個(gè)給定的文法，s是

38、文法的開始符號(hào)，如果s x(其中xvt*),則稱x是文法的一個(gè)句子。 (2)設(shè)gs是給定文法，則由文法g所定義的語言l(g)可描述為： l(g)xs x,xvt* 。24.寫一文法，使其語言是偶正整數(shù)的集合,要求： (1)允許0打頭；(2) 不允許1打頭。解：(1)gs=(s,p,d,n,0,1,2,9,p,s) p: s-pd|d p-np|n d-0|2|4|6|8 n-0|1|2|3|4|5|6|7|8|9 (2)gs=(s,p,r,d,n,q ,0,1,2,9,p,s) p: s-pd|p0|d p-nr|n r-qr|q d-2|4|6|8 n-1|2|3|4|5|6|7|8|9 q

39、-0|1|2|3|4|5|6|7|8|925.算符優(yōu)先分析法和lr（1）分析法每次歸約的分別是什么。算法優(yōu)先分析法每次規(guī)約的都是當(dāng)前句型的最左素短語，lr分析法每次規(guī)約的都是句柄26.lr分析器由哪些部分組成？它是怎樣工作的？由三部分構(gòu)成：（1）總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的lr分析器總控程序都是相同的。（2）分析表或分析函數(shù)。不同的文法分析表將不同，同一個(gè)文法采用的lr分析器不同時(shí)，分析表也不同，分析表又可分為動(dòng)作（action）表和狀態(tài)轉(zhuǎn)換（goto）表兩個(gè)部分，它們都由二維數(shù)組表示。（3）分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧。它們均是先進(jìn)后出棧。27.語法分析方法分為哪兩類？基本

40、思想是什么？遇到的基本問題是什么？目前語法分析常用的方法有自頂向下分析和自底向上分析兩大類。自頂向下分析法也稱面向目標(biāo)的分析方法，也就是從文法的開始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯(cuò)。自頂向下的確定分析方法需要對(duì)文法有一定的限制，但是由于實(shí)現(xiàn)方法簡(jiǎn)單，直觀，便于手工構(gòu)造或自動(dòng)生成語法分析器，因而仍是目前常用的方法之一。而自頂向下的不確定分析方法是帶回溯的分析方法，這種方法實(shí)際上是一種窮舉得試探方法，因此效率低，代價(jià)高，因而極少使用。28.常用的三種循環(huán)優(yōu)化技術(shù)是?代碼外提，刪除歸納變量，強(qiáng)度削弱。29.ll（1）文法的條件：1文

41、法不含左遞歸2）first() first() = 3）對(duì)文法中的每個(gè)非終結(jié)符a，若它存在某個(gè)候選首符集包含，則 first（a） follow（a）=。 29.簡(jiǎn)述lr分析法:1）lr（k）文法是從左到右分析，每次向貌似句柄的符號(hào)串后看k個(gè)輸入符號(hào)的一種編譯方法30.寫出lr(0)分析表的構(gòu)造步驟:確定g的lr(0)項(xiàng)目以lr(0)項(xiàng)目為狀態(tài),構(gòu)造一個(gè)能識(shí)別文法g的所有活前綴的nfa利用子集法,將nfa確定化,成為以項(xiàng)目集合為狀態(tài)的dfa根據(jù)利用上述dfa可直接構(gòu)造出lr分析表。 31. 比較lr(0)、slr（1）、lr（1）、lalr（1）分析表的優(yōu)缺點(diǎn):這4種分析表都能識(shí)別對(duì)應(yīng)文法的全

42、部句子，其共同特征就是用規(guī)范規(guī)約的方法尋找句柄進(jìn)行規(guī)約。在這4種方法中，lr（0）分析表對(duì)文法的要求較高，其構(gòu)造方法是其它表構(gòu)造方法的基礎(chǔ)；slr（1）分析表對(duì)文法的要求有所降低，容易實(shí)現(xiàn)，因而很有實(shí)用價(jià)值；lr（1）分析表對(duì)文法的要求最低，適用于一大類文法，故其分析能力最強(qiáng)，但其實(shí)現(xiàn)代價(jià)過高；lalr（1）分析表的分析能力介于slr（1）和lr（1）之間，實(shí)現(xiàn)代價(jià)比lr（1）低。 32.寫出產(chǎn)生式、語義規(guī)則和語義子程序之間的關(guān)系。產(chǎn)生式:一個(gè)產(chǎn)生式描述了一個(gè)語法單位,但它只說明了該語法單位能產(chǎn)生的符號(hào)串,并未指明所產(chǎn)生的符號(hào)串有什么實(shí)際意義,即該符號(hào)串究竟要做什么。語義規(guī)則:一個(gè)產(chǎn)生式的語義

43、規(guī)則描述了該產(chǎn)生式的具體的動(dòng)作意義,即該產(chǎn)生式產(chǎn)生的符號(hào)串要做什么。語義子程序:按照產(chǎn)生式的語義規(guī)則生成某種中間代碼,實(shí)現(xiàn)相應(yīng)的動(dòng)作。33為了獲得更優(yōu)化的程序，可以從哪些層次上對(duì)程序進(jìn)行優(yōu)化？為了獲得更優(yōu)化的程序，可以從各個(gè)環(huán)節(jié)著手：在源代碼級(jí)，可以選擇適當(dāng)?shù)乃惴ê桶才胚m當(dāng)?shù)膶?shí)現(xiàn)語句來提高程序的效率。在語義動(dòng)作的設(shè)計(jì)上，考慮產(chǎn)生更高效的中間代碼，并為優(yōu)化階段做準(zhǔn)備。在中間代碼級(jí)，安排專門的優(yōu)化階段，進(jìn)行各種等價(jià)變換，以改進(jìn)代碼的效率。在目標(biāo)代碼級(jí)，考慮如何有效地利用寄存器，如何選擇指令，以及進(jìn)行窺孔優(yōu)化等。 34.常用的優(yōu)化方法局部?jī)?yōu)化: 刪除公共子表達(dá)式、復(fù)寫傳播、刪除無用代碼。循環(huán)優(yōu)化：代

44、碼外提、強(qiáng)度削弱、刪除歸納變量35.簡(jiǎn)述基本塊的入口、基本塊的劃分、流圖？答：入口就是其中的第一個(gè)語句1.求出四元式程序中的各個(gè)基本塊中的入口地1)程序的第一個(gè)語句2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句3)緊跟在條件轉(zhuǎn)移語句后面的語句。2. 對(duì)以上求出的每一入口語句，構(gòu)造其所屬的基本塊。它是由該人口語句（開始）到一轉(zhuǎn)移語句(包括該轉(zhuǎn)移語句)，或到一停語句(包括該停語句)之間的語句序列組成的。3. 刪除無用代碼。凡未被納入某一基本塊中的語句，都是程序中控制流程無法到達(dá)的語句，從而也是不會(huì)被執(zhí)行到的語句，我們可把它們從程序中刪除。操作系統(tǒng)1解釋進(jìn)程的順序性和并發(fā)性答：目前使用的計(jì)算機(jī)基本

45、上是馮諾依曼式結(jié)構(gòu)，其基本特點(diǎn)是處理器順序執(zhí)行指令。進(jìn)程在順序的處理器上的執(zhí)行是嚴(yán)格按順序進(jìn)行的，這就是進(jìn)程的順序性，。當(dāng)一個(gè)進(jìn)程獨(dú)占處理器順序執(zhí)行的時(shí)，具有兩個(gè)特點(diǎn)：（1）封閉性，進(jìn)程執(zhí)行的結(jié)果只取決于進(jìn)程本身，不受外界影響（2）可再現(xiàn)性，當(dāng)進(jìn)程再次重復(fù)執(zhí)行時(shí)，必定獲得相同的結(jié)果。進(jìn)程具有并發(fā)性。也就是說在一個(gè)進(jìn)程的工作沒有全部完成之前，另一個(gè)進(jìn)程就可以開始工作。并發(fā)進(jìn)程相互之間可能是無關(guān)的，也可能是有交互的。這些有交互的進(jìn)程共享某些資源。2.對(duì)相關(guān)臨界區(qū)的管理有哪些要求？答：為了使并發(fā)進(jìn)程能正確執(zhí)行，對(duì)若干進(jìn)程共享某一資源的相關(guān)臨界區(qū)的管理應(yīng)滿足以下三個(gè)要求：（1）一次最多讓一個(gè)進(jìn)程在臨界

46、區(qū)中執(zhí)行，當(dāng)有進(jìn)程在臨界區(qū)中時(shí)。其他想進(jìn)入臨界區(qū)執(zhí)行的進(jìn)程必須等待（2）任何一個(gè)進(jìn)入臨界區(qū)執(zhí)行的進(jìn)程必須在有限的時(shí)間內(nèi)退出臨界區(qū)，即任何一個(gè)進(jìn)程都不應(yīng)該無限的逗留在自己的臨界區(qū)中（3）不能強(qiáng)迫一個(gè)進(jìn)程無限的等待進(jìn)如它的臨界區(qū)即有進(jìn)程退出了臨界區(qū)時(shí)應(yīng)讓下一個(gè)等待進(jìn)入臨界區(qū)的進(jìn)程進(jìn)入他的臨界區(qū)執(zhí)行。3什么是線程？多線程技術(shù)具有哪些優(yōu)越性？答：線程是進(jìn)程中可獨(dú)立執(zhí)行的子任務(wù)，一個(gè)進(jìn)程可以有一個(gè)或者多個(gè)線程，每個(gè)線程都有一個(gè)唯一的標(biāo)識(shí)符。線程與進(jìn)程有許多相似之處，往往把線程又稱為“輕型進(jìn)程”。線程與進(jìn)程的根本區(qū)別是把進(jìn)程作為資源分配單位，而線程是調(diào)度和執(zhí)行單位。優(yōu)越性：（1）創(chuàng)建速度快，系統(tǒng)開銷小，創(chuàng)

47、建線程不需要另行分配資源（2）通信簡(jiǎn)潔，信息傳送速度快，線程間的通信在同一地址空間進(jìn)行，不需要額外的通信機(jī)制（3）并行性高，線程能獨(dú)立執(zhí)行，能充分利用和發(fā)揮處理器與外圍設(shè)備并行工作的能力。多線程機(jī)制是操作系統(tǒng)的發(fā)展趨勢(shì)，他能提高計(jì)算機(jī)系統(tǒng)的性能。4簡(jiǎn)述unix系統(tǒng)中管道機(jī)制pipe和fifo的區(qū)別答：pipe文件是一種在兩個(gè)進(jìn)程間傳送信息的臨時(shí)文件，一旦寫入pipe文件中的信息被讀取后，這個(gè)pipe文件就沒有必要保存了，它占用的存儲(chǔ)空間就可被收回。命名管道fifo適用于不同的用戶的進(jìn)程間的通信。所謂命名管道，實(shí)際上是一個(gè)冠有文件名的管道文件。命名管道的使用方式與無名管道的使用方式不同。對(duì)命名管

48、道的使用就像對(duì)普通文件的使用一樣，要通過文件操作來使用，首先必須建立文件，讀寫之前先打開文件，通信結(jié)束后要關(guān)閉文件。命名管道屬于該文件的建立者所有。在建立有名管道文件時(shí)可設(shè)置訪問權(quán)限。只有被授權(quán)的用戶才可按訪問權(quán)限使用有名管道文件。利用有名管道文件通信時(shí)，通信的發(fā)送者用只寫方式打開，通信的接受著用只讀的方式打開。對(duì)被打開的有名管道文件，進(jìn)程可按打開的方式對(duì)該文件讀或?qū)?。在讀寫的過程中管道機(jī)制要對(duì)讀寫操作進(jìn)行同步控制，以保證信息傳輸?shù)恼_性。通信結(jié)束后要關(guān)閉該文件，以后需要時(shí)可再次打開。5簡(jiǎn)述信號(hào)量s的物理含義答：s0時(shí)，s表示可使用的資源數(shù)，或表示可使用的資源的進(jìn)程數(shù)。s0時(shí)，表示無資源可供使

49、用或表示不允許進(jìn)程在進(jìn)入臨界區(qū)。s0時(shí)，|s|表示等待使用資源的進(jìn)程個(gè)數(shù)或表示等待進(jìn)入臨界區(qū)的進(jìn)程個(gè)數(shù)。當(dāng)s0時(shí)，使用p（s）的進(jìn)程不會(huì)等待，調(diào)用v（s）后使可用資源數(shù)加1或是可用資源的進(jìn)程數(shù)加1.當(dāng)s0時(shí)，調(diào)用p（s）的進(jìn)程必須等待，調(diào)用v（s）后將釋放一個(gè)等待使用資源者或釋放一個(gè)等待進(jìn)入臨界區(qū)者6如果一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者他們共享的緩沖區(qū)（b）容量為可以存放n件物品，如何使用pv操作來實(shí)現(xiàn)他們正確的同步？答：設(shè)信息量empty（表示緩沖區(qū)中可存放多少件物品）的初值為n，信號(hào)量full（表示緩沖區(qū)中存有幾件物品）的初值為0.但是當(dāng)緩沖區(qū)已經(jīng)有n件物品時(shí)，生產(chǎn)者想在存入一件物品將被拒絕，每存一

50、件物品后，由于調(diào)用v（full），故empty的值表示緩沖區(qū)中可用的物品數(shù)，只要full0，消費(fèi)者調(diào)用p（full）后總可去取物品。每取走一件物品后，由于調(diào)用v（empty），便增加了一個(gè)可用來存放物品的位置。用指針k和t分別表示生產(chǎn)者往緩沖區(qū)村物品和消費(fèi)者從緩沖區(qū)物品的相對(duì)位置，他們的初值為0.那么，一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者共有容量為n的緩沖區(qū)時(shí)，可進(jìn)行如下同步工作：設(shè)信號(hào)量empty,full，初值為empty=n,full=0，整型變量k,t，初值為k=t=0生產(chǎn)者進(jìn)程：begin l1:produce a product;p（empty）;bk:=product;k:=（k+1）mod

51、n;v（full）;go to l1;end;消費(fèi)者進(jìn)程：begin l2:p（full）take a product from bt; t:=（t+1）mod n; v（empty）;consume;go to l2;end;7進(jìn)程通信方式有兩種，即直接通信和間接通信，給出各自使用的原語形式答：（1）直接通信：這種通信方式是固定在一對(duì)進(jìn)程之間進(jìn)行。例如，進(jìn)程a把新建只發(fā)送給進(jìn)程b，而進(jìn)程b也只接收進(jìn)程a的信件。那么，“send”和“receive”兩條原語的形式如下：send （b,m）把信件m發(fā)送給進(jìn)程b，receive（a,x）接收來自進(jìn)程a的信件且存入x中，進(jìn)程a和進(jìn)程b通過“send

52、”和“receive”操作而自動(dòng)建立了一種聯(lián)結(jié)（2）間接通信：這種通信方式是以信箱為媒體來實(shí)現(xiàn)通信的，只要接收進(jìn)程的設(shè)立一個(gè)信箱，那么，若干個(gè)進(jìn)程都可向同一個(gè)進(jìn)程發(fā)送信件。利用信箱通信時(shí)，“send”和“receive”原語中應(yīng)給出信箱名，send （n,m）把信件m發(fā)送給信件n中，receive（n,x）從信件n中取出一封信存入x中8unix中，消息緩沖機(jī)制的作用是什么？答：unix中消息緩沖機(jī)制是利用緩沖區(qū)來傳輸消息的。有系統(tǒng)統(tǒng)一管理一組緩沖區(qū)，其中每一個(gè)緩沖區(qū)都可用來放一個(gè)消息。當(dāng)一個(gè)進(jìn)程要發(fā)送消息時(shí)，首先向系統(tǒng)申請(qǐng)一個(gè)緩沖區(qū)；然后再把組織好的消息存入緩沖區(qū)；接著把村有消息的緩沖區(qū)鏈接到

53、消息隊(duì)列中。所有這些工作可通過調(diào)用消息存入緩沖區(qū)；接著把村有消息的緩沖區(qū)鏈接到消息隊(duì)列中。所有這些工作可通過調(diào)用消息緩沖機(jī)制所提供的系統(tǒng)調(diào)用來完成。接受消息的進(jìn)程也可通過系統(tǒng)調(diào)用從消息隊(duì)列中取用消息，從緩沖機(jī)制取出消息后，就應(yīng)釋放該緩沖區(qū)。unix的消息緩沖機(jī)制設(shè)置了多個(gè)消息隊(duì)列。對(duì)不同的類型的消息分別設(shè)置不同的消息隊(duì)列。進(jìn)程間傳送的每一個(gè)消息都有一個(gè)指定的類型。消息緩沖機(jī)制根據(jù)發(fā)送進(jìn)程給定的消息類型，從與該類型相關(guān)聯(lián)的消息隊(duì)列中讀出一個(gè)消息。于是發(fā)送進(jìn)程和接收進(jìn)程既可以使用同一消息隊(duì)列中讀出一個(gè)消息。于是發(fā)送進(jìn)程和接收進(jìn)程既可以使用同一消息隊(duì)列進(jìn)行通信。9為什么并發(fā)進(jìn)程執(zhí)行時(shí)可能會(huì)產(chǎn)生與時(shí)間

54、相關(guān)的錯(cuò)誤？如何避免？答：有交互的并發(fā)進(jìn)程可能會(huì)同時(shí)使用共享資源，如果對(duì)這種情況不加控制，由于進(jìn)程占用處理器的時(shí)間，執(zhí)行的速度和外界的影響等。就會(huì)引起與時(shí)間有關(guān)的錯(cuò)誤。只要使若干并發(fā)進(jìn)程的相關(guān)臨界區(qū)互斥執(zhí)行，就可避免造成這類錯(cuò)誤。10簡(jiǎn)述文件的組織結(jié)構(gòu) 文件的組織結(jié)構(gòu)是指文件的構(gòu)造方式。用戶和文件系統(tǒng)信信從不同的角度對(duì)待同一個(gè)文件。（1）文件的邏輯結(jié)構(gòu)：用戶按自己對(duì)信息的處理要求確定文件的邏輯結(jié)構(gòu)。我們把用戶組織的文件稱為邏輯文件。邏輯文件有如下兩種形式。流式文件：指用戶對(duì)文件中的信息不再劃分可獨(dú)立的單位，整個(gè)文件由依次的一串停止組成；記錄式文件：指用戶對(duì)文件中的信息按邏輯上獨(dú)立的含義現(xiàn)劃分信

55、息單位。每個(gè)信息單位稱為一個(gè)邏輯記錄。簡(jiǎn)稱為記錄（2）文件的存儲(chǔ)結(jié)構(gòu)：文件系統(tǒng)根據(jù)存儲(chǔ)設(shè)備的類型、用戶采用的存儲(chǔ)方式?jīng)Q定文件在存儲(chǔ)介質(zhì)上的組織方式。目前常用的存儲(chǔ)設(shè)備有磁盤機(jī)和磁帶機(jī)，他們的組織文件如下：磁帶文件的組織：磁帶機(jī)是一種順序存取的設(shè)備，組織在磁帶上的文件都采用順序結(jié)構(gòu)的；磁盤文件的組織：文件在磁盤上有多種組織方式。常用的有順序結(jié)構(gòu)、鏈接結(jié)構(gòu)和索引結(jié)構(gòu)11文件系統(tǒng)能允許用戶去關(guān)閉一個(gè)不是自己打開或建立的文件嗎？ 關(guān)閉文件操作只有文件的建立者或打開者才有權(quán)關(guān)閉文件。因此文件文件系統(tǒng)一般不能允許用戶去關(guān)閉一個(gè)不是自己打開或建立的文件。12敘述下列術(shù)語;存儲(chǔ)介質(zhì)、卷、塊、文件和記錄。 存儲(chǔ)

56、介質(zhì)：可用來記錄信息的磁帶、硬磁盤組、軟磁盤片、光盤、卡片等稱為存儲(chǔ)介質(zhì)。目前常用的存儲(chǔ)介質(zhì)是磁帶機(jī)和磁盤機(jī)。卷：把存儲(chǔ)介質(zhì)的物理單位定義為“卷.一盤磁帶、一張軟磁片、一個(gè)硬盤組都可以稱為一個(gè)卷。塊：把存儲(chǔ)介質(zhì)上連續(xù)信息所組成的一個(gè)區(qū)域稱為“塊”。塊是存儲(chǔ)設(shè)備與主存儲(chǔ)器之間進(jìn)行信息交換的物理單位。每次問題把一塊或幾塊信息讀入主存儲(chǔ)器，或是把主存儲(chǔ)器上的信息寫到一塊或幾塊中。文件：是指邏輯上具有完整意義的信息集合。記錄：是指文件內(nèi)信息按邏輯上獨(dú)立的含義劃分的信息單位，每個(gè)單位稱為一個(gè)邏輯單位，簡(jiǎn)稱為記錄。13文件系統(tǒng)應(yīng)由哪些部分組成？ 文件系統(tǒng)由以下一些部分組成：（1）文件目錄：是實(shí)現(xiàn)按名存取的

57、一種手段。目錄結(jié)構(gòu)應(yīng)既能方便文件的檢索，又能保證文件系統(tǒng)的安全。（2）文件的組織：用戶按信息的使用和處理方式來組織文件。文件系統(tǒng)要從系統(tǒng)效率和方便檢索的角度來考慮如何保存文件。通常文件在存儲(chǔ)介質(zhì)上可以有多種組織形式。（3）文件存儲(chǔ)空間的管理：對(duì)文件的存儲(chǔ)空間的分配和空閑情況進(jìn)行登記和管理。（4）文件操作：是文件系統(tǒng)提供給用戶使用文件的一組接口。用戶調(diào)用文件操作提出對(duì)文件的使用要求。（5）文件的安全措施：文件共享既能節(jié)省存儲(chǔ)空間又可減少傳送文件的時(shí)間，但文件需要適當(dāng)?shù)陌踩Ｗo(hù)措施，既要防止有意或無意地破壞文件，又要避免隨意的剽竊文件，實(shí)現(xiàn)文件的保護(hù)和保密。14文件是如何進(jìn)行分類的？ 文件可以按各種分類方法進(jìn)行分類，主要有以下幾種：（1）按用途分類：可把文件分為系統(tǒng)文件、庫(kù)文件和用戶文件。（2）按保護(hù)級(jí)別分類：可以把文件分成執(zhí)行文件、只讀文件和讀寫文件等。（3）按信息流向分類：一般可以分為輸入文件、輸出文件和輸入/輸出文件。（4）按存放時(shí)限分類，可以分成臨時(shí)文件