編譯原理期末考試復習題

1、編譯原理期末考試復習題一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）×1計算機高級語言翻譯成低級語言只有解釋一種方式。()×2在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。()3甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。 ()×4正則文法其產(chǎn)生式為 A->a ， A->Bb,  A,BVN ， a 、 bVT 。 ()5每個文法都能改寫為 LL(1) 文法。 ()6遞歸下降法允許任一非終極符是直接左遞歸的。 ()×7算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。

2、 ()×8自底而上語法分析方法的主要問題是候選式的選擇。 ()×9LR 法是自頂向下語法分析方法。 ()×10簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 ()三、填空題(每空1分，共10分)1編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成,代碼優(yōu)化等幾個基本階段,同時還會伴有_ _和 _ _。 表格管理 出錯處理_2若源程序是用高級語言編寫的,_ _是機器語言程序或匯編程序,則其翻譯程序稱為 _ _ 。_目標程序 _編譯程序3編譯方式與解釋方式的根本區(qū)別在于_ _。是否生成目標代碼_4對編譯程序而言,輸入數(shù)據(jù)是_ _, 輸出結果是_

3、_。_源程序 目標程序5產(chǎn)生式是用于定義_ _的一種書寫規(guī)則。 _語法成分6語法分析最常用的兩類方法是_ _和_ _分析法。 自上而下 _自下而上四、簡答題（20分）1. 什么是句子？ 什么是語言 ? 答：(1)設G是一個給定的文法，S是文法的開始符號，如果S x(其中xVT*),則稱x是文法的一個句子。 (2)設GS是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)xS x,xVT* 。參考答案：(每個2分，共4分)答：(1)設G是一個給定的文法，S是文法的開始符號，如果S x(其中xVT*),則稱x是文法的一個句子。 (2)設GS是給定文法，則由文法G所定義的語言L(G)可描述

4、為： L(G)xS x,xVT* 。 一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）×1對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。()×2甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。()3遞歸下降分析法是自頂向上分析方法。()×4產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 ()5LR 法是自頂向下語法分析方法。 ()6在 SLR （ 1 ）分析法的名稱中，S的含義是簡單的。()×7綜合屬性是用于 “ 自上而下 ” 傳遞信息。()×8符號表中的信息欄中登記了每

5、個名字的 屬性和特征等有關信息 ，如類型、種屬、所占單元大小、地址等等。 ()×9程序語言的語言處理程序是一種應用軟件。 ()×10解釋程序適用于 COBOL 和 FORTRAN 語言。 ()三、填空題(每空1分，共10分)1一個句型中的最左簡單短語稱為該句型的_句柄_。 2對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為 _語義規(guī)則_ 。3一個典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優(yōu)化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。4 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。5 掃描器的任務

6、是從_源程序_中識別出一個個_單詞符號_。 6 產(chǎn)生式是用于定義_語法范疇_的一種書寫規(guī)則。 一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）×1編譯程序是對高級語言程序的解釋執(zhí)行。()×2一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。() 3一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。 ()×4語法分析時必須先消除文法中的左遞歸 。 ()5LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。 ()6逆波蘭表示法表示表達式時無須使用括號。 ()×7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 ()×

7、8進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。 ()× 9兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。 ()×10一個語義子程序描述了一個文法所對應的翻譯工作。 ()三、填空題(每空1分，共10分)1計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：_ _和_ _。解釋_編譯2掃描器是_ _，它接受輸入的_ _，對源程序進行_ _并識別出一個個單詞符號，其輸出結果是單詞符號，供語法分析器使用。詞法分析器 源程序 詞法分析3自上而下分析法采用_ _、歸約、錯誤處理、_ _等四種操作。移進_接受4一個LR分析器包括兩部分：一個總控程序和_ _。一

8、張分析表5后綴式abc-/所代表的表達式是_。 _a/(b-c)6局部優(yōu)化是在_范圍內(nèi)進行的一種優(yōu)化。_基本塊_一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）1設r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。(×)2確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。()3詞法分析作為單獨的一遍來處理較好。 (× )4構造LR分析器的任務就是產(chǎn)生LR分析表。 ()5規(guī)范歸約和規(guī)范推導是互逆的兩個過程。 (× )6同心集的合并有可能產(chǎn)生新的“移進”/“歸約”沖突。 (× )7LR分析技術無法適用二義文法。 (

9、15; )8樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。 (×)9程序中的表達式語句在語義翻譯時不需要回填技術。 ()10對中間代碼的優(yōu)化依賴于具體的計算機。 (× )三、填空題(每空1分，共10分)1詞法分析基于_正則_文法進行，即識別的單詞是該類文法的句子。 2語法分析基于_上下文無關_文法進行，即識別的是該類文法的句子。語法分析的有效工具是_語法樹_。3分析句型時，應用算符優(yōu)先分析技術時，每步被直接歸約的是_最左素短語_，而應用LR分析技術時，每步被直接歸約的是_句柄_。4語義分析階段所生成的與源程序等價的中間表示形式可以有_逆波蘭_、_四無式表示_與

10、_三元式表示_等。一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）1一個 LL(l)文法一定是無二義的。 (× ) 7LR 法是自頂向下語法分析方法。 (× )2正規(guī)文法產(chǎn)生的語言都可以用上下文無關文法來描述。 (× )3一張轉換圖只包含有限個狀態(tài)，其中有一個被認為是初態(tài)，最多只有一個終態(tài)。 ()4目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 (× )5逆波蘭法表示的表達式亦稱前綴式 。 ( )6如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。 ( )8數(shù)組元素的地址計算與數(shù)組的存儲方式有關。

11、(× )9算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。 (×)10對于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動態(tài)貯存分配策略。 (×)三、填空題(每空1分，共10分)1語法分析是依據(jù)語言的_語法_規(guī)則進行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī)進行的。2語法分析器的輸入是_單詞符號串_，其輸出是_語法單位_。3一個名字的屬性包括_類型_和_作用域_。4產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。5逆波蘭式 ab+c+ d*e- 所表達的表達式為_(a+b+c)*d-e_ 。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 二、填空題（每空2分，共22

12、分）1已知文法GS：S(A)|a ，AAcS|S|b ；該文法的開始符號是 S，非終結符號集合為 S,A，終結符號集合為a,b,c,(,)。2描述源程序中的單詞結構有3種方法：有窮自動機，正規(guī)式和正規(guī)文法。3自上而下的語法分析方法有LL(1)和遞歸下降方法。4設有文法GS：SSa|a ，構造它的拓廣文法，引入一個產(chǎn)生式：SS ；則I。=Closure（S·S，）= S·S，, S·Sa，/a, S·a，/a。5在LR（0）項目集規(guī)范族中，若有項目：，其中，稱該項目為移進項目。6.LL(1)語法分析方法中應解決的主要問題是消除回溯；LR語法分析方法中應解決

13、的主要問題是項目沖突。三、判斷題（判斷下列各題的正錯，若正確，在括號中寫“正”；否則寫“錯”。每題2分，共16分）1一個文法有二義性，則由它描述的語言一定具有二義性。（錯 ）2若一個語言有無窮多個句子，則定義該語言的文法一定是遞歸的。（正 ）3若有正規(guī)式a*b，則與之等價的文法應該是GA：AaA|b 。（ 正 ）4設有文法GA：AaB ，BbB|b，則該文法是LL(1)文法。（錯 ）5由文法法G的開始符號S推導出來的符號串，稱為文法G的句子。（ 錯 ）6最左素短語是句型最左邊的短語。（錯 ）7LR語法分析法是一種規(guī)范規(guī)約的分析方法。（正 ）8存在能夠被確定的有窮自動機DFA識別，卻不能用正規(guī)式

14、表示的語言。（ 錯 ）1. 文法G的一個句子對應于多個推導，則G是二義性的。（× ）2. 動態(tài)的存儲分配是指在運行階段為源程序中的數(shù)據(jù)對象分配存儲單元。（ ）3. 算符優(yōu)先文法采用“移進規(guī)約”技術，其規(guī)約過程是規(guī)范的。（ × ）4. 刪除歸納變量是在強度削弱以后進行。（ ）5. 在目標代碼生成階段，符號表用于目標代碼生成。（ × ）一 填空題（每空2分，共20分）1. 不同的編譯程序關于數(shù)據(jù)空間的存儲分配策略可能不同，但大部分編譯中采用的方案有兩種：靜態(tài)存儲分配方案和動態(tài)存儲分配方案，而后者又分為（1） 和 （2） 。2. 規(guī)范規(guī)約是最（3）規(guī)約。3. 編譯程序的

15、工作過程一般劃分為5個階段：詞法分析、（4） 、語義分析與中間代碼生成，代碼優(yōu)化及（5） 。另外還有（6）和出錯處理。4表達式x+y*z/(a+b)的后綴式為 （7） 。5文法符號的屬性有綜合屬性和 （8）。6假設二位數(shù)組按行存放，而且每個元素占用一個存儲單元，則數(shù)組a1.15,1.20某個元素ai，j的地址計算公式為（9）。7局部優(yōu)化是局限于一個（10）范圍內(nèi)的一種優(yōu)化。答案：(1) 棧式動態(tài)存儲分配(2) 堆式動態(tài)存儲分配(3) 左(4) 語法分析(5) 目標代碼生成(6) 表格管理(7) xyz*ab+/+(8) 繼承屬性(9) a+(i-1)*20+j-1(10) 基本塊一、 填空題（

16、每空2分，共20分）1目標程序 （target code） 語法分析（syntax analyzer） 代碼優(yōu)化器（code optimizer） 代碼產(chǎn)生器（code generator） 符號表管理（symbol table manager）2 繼承屬性（inherited attribute）3 局部優(yōu)化（local optimization）4 四元式（quatriple）5 E + * ( ) id二、填空題（本大題共5小題，每小題2分，共10分）1編譯程序首先要識別出源程序中每個(單詞)，然后再分析每個(句子)并翻譯其意義。 2編譯器常用的語法分析方法有(自底向上)和(自頂向下)兩

17、種。3通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的(綜合)。4程序設計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動態(tài)存儲分配)方案。5對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結果是(目標程序)。三、名詞解釋題(共5小題，每小題4分，共20分)1詞法分析詞法分析的主要任務是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。2LL(1)文法 若文法

18、的任何兩個產(chǎn)生式A ® a | b都滿足下面兩個條件：（1）FIRST(a ) Ç FIRST(b ) = f；（2）若b Þ* e ，那么FIRST(a ) Ç FOLLOW( A ) = f。 我們把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個L代表從左向右掃描輸入，第二個L表示產(chǎn)生最左推導，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語法樹 句子的樹結構表示法稱為語法樹(語法分析樹或語法推導樹)。給定文法G=(VN，VT，P，S)，對于G的任何句型都

19、能構造與之關聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點的標記是開始符號S。(2)每個節(jié)點的標記都是V中的一個符號。(3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標記從左向右的排列次序為A1A2AR，那么A®A1A2AR一定是P中的一條產(chǎn)生式。(4)若一標記為A的節(jié)點至少有一個除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點上的標記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結符號，則w為文法G所產(chǎn)生的句子。4LR(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個

20、輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作 (是移進還是按某一產(chǎn)生式進行歸約等)。5語言和文法文法就是語言結構的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式: G=(VN，VT，P，S)其中：VN 是非空有窮集合，稱為非終結符號集合；VT 是非空有窮集合，稱為終結符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。這里，VNVT=Æ，SVN。V=VNVT，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)

21、=x| SÞ*x，其中S為文法開始符號，且 簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題(共4小題，每小題5分，共20分)1編譯程序和高級語言有什么區(qū)別? 用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉換過的叫目標程序，也就是機器語言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應的關系，轉換成用機器語言表示的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句，先解

22、釋成為一組機器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的"對話"，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快，在過程中，不能進行人機對話修改。FORTRAN語言就是編譯型高級語言。2編譯程序的工作分為那幾個階段? 詞法分析、語法分析和語義分析是對源程序進行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合(稱為編譯程序的后端)，它

23、們從源程序的中間表示建立起和源程序等價的目標程序。3簡述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。4簡述代碼優(yōu)化的目的和意義。 代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結果相同的前提下，盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間少。一、是非題（請在括號內(nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）1編譯程序是對高級語言程序的解釋執(zhí)行。(× )2一個有限狀態(tài)自動機中，有且僅有一個唯一的終

24、態(tài)。(×)3一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應。 ( )4語法分析時必須先消除文法中的左遞歸 。 (×)5LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。 ()6逆波蘭表示法表示表達式時無須使用括號。 ( )7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 (×)8進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。 (×)9兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。 (× )10一個語義子程序描述了一個文法所對應的翻譯工作。 (×)三、填空題(每空1分，共10分)1計算機執(zhí)行用

25、高級語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析器_，它接受輸入的_源程序_，對源程序進行_詞法分析_并識別出一個個單詞符號，其輸出結果是單詞符號，供語法分析器使用。3自上而下分析法采用_移進_、歸約、錯誤處理、_接受_等四種操作。4一個LR分析器包括兩部分：一個總控程序和_一張分析表_。5后綴式abc-/所代表的表達式是_a/(b-c)_。 6局部優(yōu)化是在_基本塊_范圍內(nèi)進行的一種優(yōu)化。一、是非題：1.一個上下文無關文法的開始符，可以是終結符或非終結符。 ( )2.一個句型的直接短語是唯一的。 （ ）3.已經(jīng)證明文法的二義性是可判定的。 （ ）4.每個基本塊可用一

26、個DAG表示。 （ ）5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。 （ ）6.2型文法一定是3型文法。 （ ）7.一個句型一定句子。 ( )8.算符優(yōu)先分析法每次都是對句柄進行歸約。 X ( )9.采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進行優(yōu)化。 （ ）10.編譯過程中，語法分析器的任務是分析單詞是怎樣構成的。 ( )11.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。 X ( )12.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( )13.遞歸下降分析法是一種自下而上分析法。 ( )14.并不是每個文法都能改寫成LL(1)文法。 ( )15.每個基本塊只有一個入口和一個出口。 (

27、 )16.一個LL(1)文法一定是無二義的。 ( )17.逆波蘭法表示的表達試亦稱前綴式。 ( )18.目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( )19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關文法來描述。 ( )20.一個優(yōu)先表一定存在相應的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22.如果一個文法存在某個句子對應兩棵不同的語法樹，則文法是二義性的。 ( )答案：1.× 2.× 3.× 4. 5. 6.× 7.× 8.× 9. 10.× 11.×12. 13.× 14.

28、15. 16. 17.× 18. 19. 20.× 21. 22.二、填空題：2.編譯過程可分為 （ 詞法分析） ，（語法分析），（語義分析與中間代碼生成 ），（優(yōu)化）和（目標代碼生成 ）五個階段。3.如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是（ 二義性的 ）。 4.從功能上說，程序語言的語句大體可分為（ 執(zhí)行性 ）語句和（說明性 ）語句兩大類。5.語法分析器的輸入是（ 單詞符號 ），其輸出是（ 語法單位 ）。6.掃描器的任務是從（ 源程序中 ）中識別出一個個（ 單詞符號 ）。7.符號表中的信息欄中登記了每個名字的有關的性質(zhì)，如(類型、種屬、所占單元大小、

29、地址）等等。8.一個過程相應的DISPLAY表的內(nèi)容為(現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址)10.常用的兩種動態(tài)存貯分配辦法是（棧式）動態(tài)分配和（堆式）動態(tài)分配。11.一個名字的屬性包括( 類型)和(作用域 )。12.常用的參數(shù)傳遞方式有(傳地址），（傳值），（傳名）13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為(局部優(yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個級別。14.語法分析的方法大致可分為兩類，一類是（ 自上而下 ）分析法，另一類是（ 自下而上 ）分析法。15.預測分析程序是使用一張（ 分析表 ）和一個（ 符號棧 ）進行聯(lián)合控制的。17.一張轉換圖只包含有限個狀態(tài),其中有一個被認為

30、是（初）態(tài);而且實際上至少要有一個（終 ）態(tài)。19.語法分析是依據(jù)語言的（語法 ）規(guī)則進行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進行的。21.一個文法G，若它的預測分析表M不含多重定義，則該文法是（LL(1) 文法）文法。22.對于數(shù)據(jù)空間的存貯分配， FORTRAN采用( 靜態(tài)策略， PASCAL采用( 動態(tài))策略。24.最右推導亦稱為（規(guī)范推導），由此得到的句型稱為（規(guī)范）句型。26.對于文法G，僅含終結符號的句型稱為 ( 句子 )。27.所謂自上而下分析法是指(從開始符號出發(fā)，向下推導，推出句子）29.局限于基本塊范圍的優(yōu)化稱（ 局部優(yōu)化 ）。31.2型文法又稱為（上下文無關）文法；3型

31、文法又稱為（正則 ）文法。32.每條指令的執(zhí)行代價定義為(指令訪問主存次數(shù)加1）33.算符優(yōu)先分析法每次都是對(最左素短語）進行歸約。三、名詞解釋題：1.局部優(yōu)化-局限于基本塊范圍的優(yōu)化稱。2.二義性文法-如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義性文法。3.DISPLAY表-過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。5.最左推導-任何一步=>都是對中的最右非終結符替換。6.語法-一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。7.文法-描述語言的語法結構的形式規(guī)則。8.基本塊-指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是

32、其中的第一個語句，出口就是其中的最后一個語句。9.語法制導翻譯-在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義子程序進行翻譯的辦法叫做語法制導翻譯。10.短語-令G是一個文法，S劃文法的開始符號，假定是文法G的一個句型，如果有SA且A，則稱是句型相對非終結符A的短語。11.待用信息-如果在一個基本塊中，四元式i對A定值，四元式j要引用A值，而從i到j之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。12.規(guī)范句型-由規(guī)范推導所得到的句型。13.掃描器-執(zhí)行詞法分析的程序。14.超前搜索-在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。15.句柄-一個句型的最左直接短語。16.語

33、法制導翻譯-在語法分析過程中，根據(jù)每個產(chǎn)生式所對應的語義程序進行翻譯的方法 叫做語法制導翻譯。17.規(guī)范句型-由規(guī)范推導所得到的句型。18.素短語-素短語是指這樣一個短語，至少含有一個終結符，并且，除它自身外不再含任何更小的素短語。19.語法-是組規(guī)則，用它可形成和產(chǎn)生一個合式的程序。 20.待用信息-如果在一個基本塊中，四元式i對A定值，四元式j要引用A值，而從i到j之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。21.語義-定義程序的意義的一組規(guī)則。 1編譯程序首先要識別出源程序中每個(單詞)，然后再分析每個(句子)并翻譯其意義。 2編譯器常用的語法分析方法有(自底向上)和(自頂

34、向下)兩種。3通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的(綜合)。4程序設計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動態(tài)存儲分配)方案。5對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結果是(目標程序)。三、名詞解釋題(共5小題，每小題4分，共20分)1詞法分析詞法分析的主要任務是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。2LL(1)文法

35、 若文法的任何兩個產(chǎn)生式A ® a | b都滿足下面兩個條件：（1）FIRST(a ) Ç FIRST(b ) = f；（2）若b Þ* e ，那么FIRST(a ) Ç FOLLOW( A ) = f。 我們把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個L代表從左向右掃描輸入，第二個L表示產(chǎn)生最左推導，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語法樹 句子的樹結構表示法稱為語法樹(語法分析樹或語法推導樹)。給定文法G=(VN，VT，P，S)，對于G的任

36、何句型都能構造與之關聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點的標記是開始符號S。(2)每個節(jié)點的標記都是V中的一個符號。(3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標記從左向右的排列次序為A1A2AR，那么A®A1A2AR一定是P中的一條產(chǎn)生式。(4)若一標記為A的節(jié)點至少有一個除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點上的標記從左到右排列為字符串w，則w是文法G的句型；若w中僅含終結符號，則w為文法G所產(chǎn)生的句子。4LR(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再向前

37、查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作 (是移進還是按某一產(chǎn)生式進行歸約等)。5語言和文法文法就是語言結構的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：G=(VN，VT，P，S)其中：VN 是非空有窮集合，稱為非終結符號集合；VT 是非空有窮集合，稱為終結符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。這里，VNVT=Æ，SVN。V=VNVT，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L

38、(G)=x| SÞ*x，其中S為文法開始符號，且 簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題(共4小題，每小題5分，共20分)1編譯程序和高級語言有什么區(qū)別? 用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉換過的叫目標程序，也就是機器語言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應的關系，轉換成用機器語言表示的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句

39、，先解釋成為一組機器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的"對話"，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快，在過程中，不能進行人機對話修改。FORTRAN語言就是編譯型高級語言。2編譯程序的工作分為那幾個階段? 詞法分析、語法分析和語義分析是對源程序進行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合(稱為編譯程序的后端

40、)，它們從源程序的中間表示建立起和源程序等價的目標程序。3簡述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。4簡述代碼優(yōu)化的目的和意義。 代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結果相同的前提下，盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間少。3對于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的語言相同），則稱文法G1和G2是等價的。4對于文法GE：ET|E+T TF|T*F FPF|P P(E)

41、|i，句型T+T*F+i的句柄是T ，最左素短語是 T*F。 5最右推導的逆過程稱為規(guī)范歸約 ，也稱為 最左歸約。6規(guī)范規(guī)約中的可規(guī)約串是句柄 ，算符優(yōu)先分析中的可規(guī)約串是 最左素短語7（A B）（C ¬D E） 的逆波蘭式是¬。8在屬性文法中文法符號的兩種屬性分別稱為繼承屬性 和綜合屬性（次序可換）。9符號表的每一項是由名字欄和 地址分配 兩個欄目組成。在目標代碼生成階段，符號表是 地址分配 的依據(jù)。 10一個過程的DISPLAY表的內(nèi)容是它的直接外層 的DISPLAY表的內(nèi)容加上本過程的SP的地址1什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關系？解答：S-屬

42、性文法是只含有綜合屬性的屬性文法。 （2分）L-屬性文法要求對于每個產(chǎn)生式AàX1X2Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj的一個繼承屬性，且該屬性僅依賴于：（1） 產(chǎn)生式Xj的左邊符號X1,X2Xj-1的屬性；（2） A的繼承屬性。 （2分）S-屬性文法是L-屬性文法的特例。 （2分）2什么是句柄？什么是素短語？一個句型的最左直接短語稱為該句型的句柄。（3分）素短語是這樣的一個短語，它至少包含一個終結符并且不包含更小的素短語。（3分）3劃分程序的基本塊時，確定基本塊的入口語句的條件是什么？解答：（1）程序第一個語句，或（2）能由條件轉移語句或無條件轉移語句轉移到

43、的語句，或（3）緊跟在條件轉移語句后面的語句。4(6分)運行時的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當進入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表diaplay.假定現(xiàn)在進入的過程層次為i，則它的diaplay表含有i+1個單元，自頂向下每個單元依次存放著現(xiàn)行層、直接外層、直至最外層(主程序，0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。二、判斷1計算機高級語言翻譯成低級語言只有解釋一種方式。(×) 2在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。(×)3甲

44、機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系 統(tǒng)功能完全相同。 ( )4正則文法其產(chǎn)生式為 A->a ， A->Bb, A,BVN ， a 、 bVT 。 (×)5每個文法都能改寫為 LL(1) 文法。 () 6遞歸下降法不允許任一非終極符是直接左遞歸的。 () 7算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。 (×) 8自底而上語法分析方法的主要問題是候選式的選擇。 (×)9LR 法是自頂向下語法分析方法。 (×)10簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 (×) 11“ 用高級語言書寫的源程序都必須通過編譯,

45、 產(chǎn)生目標代碼后才能投入運行 ”這種說法。( × )12若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。( × )13一個句型的句柄一定是文法某產(chǎn)生式的右部。 ( )14在程序中標識符的出現(xiàn)僅為使用性的。 ( × )15僅考慮一個基本塊，不能確定一個賦值是否真是無用的。 ( )16削減運算強度破壞了臨時變量在一基本塊內(nèi)僅被定義一次的特性。 ( )17在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達式外提和削減運算強度。 ( × )18數(shù)組元素的地址計算與數(shù)組的存儲方式有關。 ( × )19編譯程序與具體的機器有關,與具體的語言無關。 (

46、 × ) 20遞歸下降分析法是自頂向上分析方法。( )21產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 ( × )22LR 法是自頂向下語法分析方法。 (×)23在 SLR （ 1 ）分析法的名稱中，S 的含義是簡單的。( ) 24綜合屬性是用于 “ 自上而下 ” 傳遞信息。( × )25符號表中的信息欄中登記了每個名字的 屬性和特征等有關信息 ，如類型、種屬、所占 單元大小、地址等等。 ( × )26程序語言的語言處理程序是一種應用軟件。 ( × ) 27一個 LL(l)文法一定是無二義的。 ( × ) 28正規(guī)文法產(chǎn)生的語

47、言都可以用上下文無關文法來描述。 ( × )29一張轉換圖只包含有限個狀態(tài)，其中有一個被認為是初態(tài)，最多只有一個終態(tài)。 ( ) 30目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 ( × )31逆波蘭法表示的表達式亦稱后綴式 。 ( )32如果一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的。 ( )33數(shù)組元素的地址計算與數(shù)組的存儲方式有關。( × )34對于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動態(tài)貯存分配策略。 ( × )35編譯程序是對高級語言程序的解釋執(zhí)行。( × ) 36一個有限狀態(tài)自動機中，有且僅有一個

48、唯一的終態(tài)。( × ) 37語法分析時必須先消除文法中的左遞歸 。 ( × )38LR 分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準確地指出出錯地點。 ( ) 39逆波蘭表示法表示表達式時無須使用括號。 ( ) 40靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 ( × ) 41進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。( × ) 42兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。( × ) 43一個語義子程序描述了一個文法所對應的翻譯工作。 ( × )44r 和 s 分別是正規(guī)式，則有 L(r|s)=

49、L(r)L(s)。( × ) 45確定的的自動機以及不確定的自動機都能正確地識別正集()46分析作為單獨的一遍來處理較好。 ( × )47 LR 分析器的任務就是產(chǎn)生 LR 分析表。 ( ) 48歸約和規(guī)范推導是互逆的兩個過程。 ( )49同心集的合并有可能產(chǎn)生新的“移進”/ “歸約” 沖突 (×)50.lR 分析技術無法適用二義文法。 ( × )51樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。 ( × )52序中的表達式語句在語義翻譯時不需要回填技術。 ( ) 三、填空1編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義

50、分析,中間代碼 生成,代碼優(yōu)化等幾個基本階段,同時還會伴有_表格處理_和 _出錯處理_。 2若源程序是用高級語言編寫的,_目標程序_是機器語言程序或匯編程序, 則其翻譯程序稱為 _編譯程序_ 。 3編譯方式與解釋方式的根本區(qū)別在于_是否生成目標代碼_。 4對編譯程序而言,輸入數(shù)據(jù)是_源程序_, 輸出結果是_目標程序_。 5產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法7設 G 是一個給定的文法，S 是文法的開始符號，如果 S->x( 其中 xVT*), 則稱 x 是文 法的一個_句子_。8遞歸下降法不允許任一非終極符是直接_左_

51、遞歸的。 9自頂向下的語法分析方法的基本思想是：從文法的_開始符號_開始，根據(jù)給定的輸 入串并按照文法的產(chǎn)生式一步一步的向下進行_直接推導_，試圖推導出文法的_句子_，使之與給定的輸入串_匹配_。 10自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地 向上進行_直接歸約_ ，力求歸約到文法的_開始符號_。 11常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。 12在使用高級語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部_語法_錯誤和語義的部分錯誤。13一個句型中的最左簡單短語稱為該句型的_句柄_。14對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為 _語義規(guī)則_ 。

52、 15一個典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、 代碼優(yōu)化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。16 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。 17 產(chǎn)生式是用于定義_語法范疇_的一種書寫規(guī)則。18語法分析是依據(jù)語言的_語法_規(guī)則進行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī) 進行的。19語法分析器的輸入是_單詞符號串_，其輸出是_語法單位_。20產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。21逆波蘭式 ab+c+ d*e- 所表達的表達式為_(a+b+c)*d-e_ 。 22語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。23計算機執(zhí)行用高級語言編