《編譯原理》期末考試復(fù)習(xí)題.doc

《《編譯原理》期末考試復(fù)習(xí)題.doc》由會員分享，可在線閱讀，更多相關(guān)《《編譯原理》期末考試復(fù)習(xí)題.doc（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

4、符號，如果S x(其中x∈VT*),則稱x是文法的一個句子。 (2)設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)＝{x│S x,x∈VT*} 。 一、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃）（每個2分，共20分） 1．對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。() 2．甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。() √3．遞歸下降分析法是自頂向上分析方法。() 4．產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 () √5．LR 法是自頂向下語法分析方法。 () √6．在 SLR （ 1 ）

5、分析法的名稱中，S的含義是簡單的。() 7．綜合屬性是用于 “ 自上而下 ” 傳遞信息。() 8．符號表中的信息欄中登記了每個名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。 () 9．程序語言的語言處理程序是一種應(yīng)用軟件。 () 10．解釋程序適用于 COBOL 和 FORTRAN 語言。 () 三、填空題(每空1分，共10分) 1．一個句型中的最左簡單短語稱為該句型的___句柄__。 2．對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為 __語義規(guī)則___ 。 3．一個典型的編譯程序中，不僅包括__詞法分析___、__語法分析___、__中間代碼

6、生成___、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。 4． 從功能上說，程序語言的語句大體可分為__執(zhí)行性___語句和__說明性___語句兩大類。 5． 掃描器的任務(wù)是從__源程序___中識別出一個個___單詞符號__。 6． 產(chǎn)生式是用于定義__語法范疇___的一種書寫規(guī)則。 一、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃）（每個2分，共20分） 1．編譯程序是對高級語言程序的解釋執(zhí)行。() 2．一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。() √ 3．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 () 4．語法分析時必須先消除文法中的左遞歸 。

7、 () √5．LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。 () √6．逆波蘭表示法表示表達(dá)式時無須使用括號。 () 7．靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 () 8．進(jìn)行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。 () 9．兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。 () 10．一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。 () 三、填空題(每空1分，共10分) 1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：___ _和__ ___。 解釋_編譯 2．掃描器是__ ___，它接受輸入的__ __

8、_，對源程序進(jìn)行___ __并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。 詞法分析器 源程序 詞法分析 3．自上而下分析法采用___ _、歸約、錯誤處理、___ __等四種操作。 移進(jìn)_接受 4．一個LR分析器包括兩部分：一個總控程序和___ __。 一張分析表 5．后綴式abc-/所代表的表達(dá)式是____。 _a/(b-c) 6．局部優(yōu)化是在___范圍內(nèi)進(jìn)行的一種優(yōu)化。 _基本塊_ 一、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃）（每個2分，共20分） 1．設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。() 2．確定的自動機以及不確定的

9、自動機都能正確地識別正規(guī)集。(√) 3．詞法分析作為單獨的一遍來處理較好。 ( ) 4．構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。 (√) 5．規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。 ( ) 6．同心集的合并有可能產(chǎn)生新的“移進(jìn)”/“歸約”沖突。 ( ) 7．LR分析技術(shù)無法適用二義文法。 ( ) 8．樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。 () 9．程序中的表達(dá)式語句在語義翻譯時不需要回填技術(shù)。 (√) 10．對中間代碼的優(yōu)化依賴于具體的計算機。 ( ) 三、填空題(每空1分，共10分) 1．詞法分析基于__正則___文法進(jìn)行，即識別的單詞是該類文法的句

10、子。 2．語法分析基于__上下文無關(guān)___文法進(jìn)行，即識別的是該類文法的句子。語法分析的有效工具是__語法樹___。 3．分析句型時，應(yīng)用算符優(yōu)先分析技術(shù)時，每步被直接歸約的是__最左素短語___，而應(yīng)用LR分析技術(shù)時，每步被直接歸約的是___句柄__。 4．語義分析階段所生成的與源程序等價的中間表示形式可以有__逆波蘭___、___四無式表示__與___三元式表示__等。 一、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃）（每個2分，共20分） 1．一個 LL(l)文法一定是無二義的。 ( ) 7．LR 法是自頂向下語法分析方法。 ( ) 2．正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)

11、文法來描述。 ( ) 3．一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)，最多只有一個終態(tài)。 (√) 4．目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。 ( ) 5．逆波蘭法表示的表達(dá)式亦稱前綴式 。 (√ ) 6．如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。 (√ ) 8．?dāng)?shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。( ) 9．算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 () 10．對于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動態(tài)貯存分配策略。 () 三、填空題(每空1分，共10分) 1．語法分析是依據(jù)語言的__語法___規(guī)則進(jìn)行的，中間代

12、碼產(chǎn)生是依據(jù)語言的__語義___規(guī)進(jìn)行的。 2．語法分析器的輸入是__單詞符號串___，其輸出是__語法單位___。 3．一個名字的屬性包括__類型___和__作用域___。 4．產(chǎn)生式是用于定義___語法成分__的一種書寫規(guī)則。 5．逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為__(a+b+c)*d-e___ 。 6．語法分析最常用的兩類方法是__自上而下___和__自下而上___分析法。 二、填空題（每空2分，共22分） 1．已知文法G[S]：S→(A)|a ，A→AcS|S|b ；該文法的開始符號是 S，非終結(jié)符號集合為 {S,A}，終結(jié)符號集合為{a,b,c,

13、(,)}。 2．描述源程序中的單詞結(jié)構(gòu)有3種方法：有窮自動機，正規(guī)式和正規(guī)文法。 3．自上而下的語法分析方法有LL(1)和遞歸下降方法。 4．設(shè)有文法G[S]：S→Sa|a ，構(gòu)造它的拓廣文法，引入一個產(chǎn)生式：Sˊ→S ；則I。=Closure（{[Sˊ→S，＃]}）= {[Sˊ→S，＃], [S→Sa，＃/a], [S→a，＃/a]}。 5．在LR（0）項目集規(guī)范族中，若有項目：，其中，稱該項目為移進(jìn)項目。 6.LL(1)語法分析方法中應(yīng)解決的主要問題是消除回溯；LR語法分析方法中應(yīng)解決的主要問題是項目沖突。 三、判斷題（判斷下列各題的正錯，若正確，在括號中寫“正”；否則寫“錯”

14、。每題2分，共16分） 1．一個文法有二義性，則由它描述的語言一定具有二義性。（錯 ） 2．若一個語言有無窮多個句子，則定義該語言的文法一定是遞歸的。（正 ） 3．若有正規(guī)式a*b，則與之等價的文法應(yīng)該是G[A]：A→aA|b 。（ 正 ） 4．設(shè)有文法G[A]：A→aB ，B→bB|b，則該文法是LL(1)文法。（錯 ） 5．由文法法G的開始符號S推導(dǎo)出來的符號串，稱為文法G的句子。（ 錯 ） 6．最左素短語是句型最左邊的短語。（錯 ） 7．LR語法分析法是一種規(guī)范規(guī)約的分析方法。（正 ） 8．存在能夠被確定的有窮自動機DFA識別，卻不能用正規(guī)式表示的語言。（ 錯

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

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

17、b+/+ (8) 繼承屬性 (9) a+(i-1)*20+j-1 (10) 基本塊 一、 填空題（每空2分，共20分） 1目標(biāo)程序 （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 + *

18、( ) id 二、填空題（本大題共5小題，每小題2分，共10分） 1．編譯程序首先要識別出源程序中每個(單詞)，然后再分析每個(句子)并翻譯其意義。 2．編譯器常用的語法分析方法有(自底向上)和(自頂向下)兩種。 3．通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的(綜合)。 4．程序設(shè)計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動態(tài)存儲分配)方案。 5．對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目標(biāo)程序)。 三、名詞解釋題(共5

19、小題，每小題4分，共20分) 1．詞法分析 詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則 從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位， 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。 2．LL(1)文法 若文法的任何兩個產(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)生最左推導(dǎo)，1代表在

20、決定分析器的每步 動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一 些明顯的性質(zhì)，它不是二義的，也不含左遞歸。 3．語法樹 句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。 給定文法G=(VN，VT，P，S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的 語法樹。這棵樹具有下列特征： (1)根節(jié)點的標(biāo)記是開始符號S。 (2)每個節(jié)點的標(biāo)記都是V中的一個符號。 (3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標(biāo)記從左向右的排列 次序為A1A2…AR，那么AA1A2…AR一定是P中的一條產(chǎn)生式。 (4)若一標(biāo)記為A的節(jié)點至少有一個除它以外的子孫，則AV

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

22、 G=(VN，VT，P，S) 其中：VN 是非空有窮集合，稱為非終結(jié)符號集合；VT 是非空有窮集合， 稱為終結(jié)符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。 這里，VN∩VT=，SVN。V=VN∪VT，稱為文法G的字母表，它是出現(xiàn) 文法產(chǎn)生式中的一切符號的集合。 文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即 L(G)={x| S*x，其中S為文法開始符號，且 } 簡單的說，文法描述的語言是該文法一切句子的集合。 四、簡答題(共4小題，每小題5分，共20分) 1．編譯程序和高級語言有什么區(qū)別? 用匯編語言或高級語言編寫

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

24、時 可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)? 級語言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進(jìn)行很快， 在過程中，不能進(jìn)行人機對話修改。FORTRAN語言就是編譯型高級語言。 2．編譯程序的工作分為那幾個階段? 詞法分析、語法分析和語義分析是對源程序進(jìn)行的分析(稱為編譯程序的前端)， 而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進(jìn)行綜合(稱為 編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價的目標(biāo)程序。 3．簡述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸

25、約到文法的 開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。 4．簡述代碼優(yōu)化的目的和意義。 代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進(jìn)行 一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目 標(biāo)程序運行時所需要的時間短，同時所占用的存儲空間少。 一、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃）（每個2分，共20分） 1．編譯程序是對高級語言程序的解釋執(zhí)行。( ) 2．一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。() 3．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 (√ ) 4．語法分析時必須先消除文法中的左遞歸

26、。 () 5．LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。 (√) 6．逆波蘭表示法表示表達(dá)式時無須使用括號。 (√ ) 7．靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 () 8．進(jìn)行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。 () 9．兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。 ( ) 10．一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。 () 三、填空題(每空1分，共10分) 1．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：___解釋__和__編譯___。 2．掃描器是__詞法分析器___，它接受輸入的__源程

27、序___，對源程序進(jìn)行___詞法分析__并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。 3．自上而下分析法采用___移進(jìn)__、歸約、錯誤處理、___接受__等四種操作。 4．一個LR分析器包括兩部分：一個總控程序和___一張分析表__。 5．后綴式abc-/所代表的表達(dá)式是___a/(b-c)__。 6．局部優(yōu)化是在__基本塊___范圍內(nèi)進(jìn)行的一種優(yōu)化。 一、是非題： 1.一個上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。 ( ) 2.一個句型的直接短語是唯一的。

28、 （ ） 3.已經(jīng)證明文法的二義性是可判定的。 （ ） 4.每個基本塊可用一個DAG表示。 （ ） 5.每個過程的活動記錄的體積在編譯時可靜態(tài)確定。 （ ） 6.2型文法一定是3型文法。

29、 （ ） 7.一個句型一定句子。 ( ) 8.算符優(yōu)先分析法每次都是對句柄進(jìn)行歸約。 X ( ) 9.采用三元式實現(xiàn)三地址代碼時，不利于對中間代碼進(jìn)行優(yōu)化。 （ ） 10.編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 (

30、 ) 11.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 X ( ) 12.目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。 ( ) 13.遞歸下降分析法是一種自下而上分析法。 ( ) 14.并不是每個文法都能改寫成LL(1)文法。 ( ) 15.每個基本塊只有一

31、個入口和一個出口。 ( ) 16.一個LL(1)文法一定是無二義的。 ( ) 17.逆波蘭法表示的表達(dá)試亦稱前綴式。 ( ) 18.目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。 ( ) 19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)

32、文法來描述。 ( ) 20.一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則文法是二義性的。 ( ) 答案：1. 2. 3. 4.√ 5.√ 6.

33、7. 8. 9.√ 10. 11. 12.√ 13. 14.√ 15.√ 16.√ 17. 18.√ 19.√ 20. 21.√ 22.√ 二、填空題： 2.編譯過程可分為 （ 詞法分析） ，（語法分析），（語義分析與中間代碼生成 ），（優(yōu)化）和（目標(biāo)代碼生成 ）五個階段。 3.如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是（ 二義性的 ）。 4.從功能上說，程序語言的語句大體可分為（ 執(zhí)行性 ）語句和（說明性 ）語句兩大類。 5.語法分析器的輸入是（ 單詞符號

34、 ），其輸出是（ 語法單位 ）。 6.掃描器的任務(wù)是從（ 源程序中 ）中識別出一個個（ 單詞符號 ）。 7.符號表中的信息欄中登記了每個名字的有關(guān)的性質(zhì)，如(類型、種屬、所占單元大小、地址）等等。 8.一個過程相應(yīng)的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)化），

35、（全局優(yōu)化）三個級別。 14.語法分析的方法大致可分為兩類，一類是（ 自上而下 ）分析法，另一類是（ 自下而上 ）分析法。 15.預(yù)測分析程序是使用一張（ 分析表 ）和一個（ 符號棧 ）進(jìn)行聯(lián)合控制的。 17.一張轉(zhuǎn)換圖只包含有限個狀態(tài),其中有一個被認(rèn)為是（初）態(tài);而且實際上至少要有一個（終 ）態(tài)。 19.語法分析是依據(jù)語言的（語法 ）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語言的（語義）規(guī)則進(jìn)行的。 21.一個文法G，若它的預(yù)測分析表M不含多重定義，則該文法是（LL(1) 文法）文法。 22.對于數(shù)據(jù)空間的存貯分配， FORTRAN采用( 靜態(tài)策略， PASC

36、AL采用( 動態(tài))策略。 24.最右推導(dǎo)亦稱為（規(guī)范推導(dǎo)），由此得到的句型稱為（規(guī)范）句型。 26.對于文法G，僅含終結(jié)符號的句型稱為 ( 句子 )。 27.所謂自上而下分析法是指(從開始符號出發(fā)，向下推導(dǎo)，推出句子） 29.局限于基本塊范圍的優(yōu)化稱（ 局部優(yōu)化 ）。 31.2型文法又稱為（上下文無關(guān)）文法；3型文法又稱為（正則 ）文法。 32.每條指令的執(zhí)行代價定義為(指令訪問主存次數(shù)加1） 33.算符優(yōu)先分析法每次都是對(最左素短語）進(jìn)行歸約。 三、名詞解釋題： 1.局部優(yōu)化-------局限于基本塊范圍的優(yōu)化稱。 2.二義性文法------如果一個文法存在某個句子對

37、應(yīng)兩棵不同的語法樹，則稱這個文法是二義性文法。 3.DISPLAY表----過程的嵌套層次顯示表，記錄該過程的各外層過程的最新活動記錄的起始地址。 5.最左推導(dǎo)------任何一步α=>β都是對α中的最右非終結(jié)符替換。 6.語法------一組規(guī)則，用它可形成和產(chǎn)生一組合式的程序。 7.文法------描述語言的語法結(jié)構(gòu)的形式規(guī)則。 8.基本塊------指程序中一順序執(zhí)行的語句序列，其中只有一個入口和一個出口，入口就是其中的第一個語句，出口就是其中的最后一個語句。 9.語法制導(dǎo)翻譯------在語法分析過程中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序進(jìn)行翻譯的辦法叫做語法制導(dǎo)翻譯。 1

38、0.短語------令G是一個文法，S劃文法的開始符號，假定αβδ是文法G的一個句型，如果有SαAδ且Aβ，則稱β是句型αβδ相對非終結(jié)符A的短語。 11.待用信息------如果在一個基本塊中，四元式i對A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。 12.規(guī)范句型------由規(guī)范推導(dǎo)所得到的句型。 13.掃描器------執(zhí)行詞法分析的程序。 14.超前搜索------在詞法分析過程中，有時為了確定詞性，需超前掃描若干個字符。 15.句柄------一個句型的最左直接短語。 16.語法制導(dǎo)翻譯------在語法分析過程中，根據(jù)

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

40、譯其意義。 2．編譯器常用的語法分析方法有(自底向上)和(自頂向下)兩種。 3．通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的(綜合)。 4．程序設(shè)計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動態(tài)存儲分配)方案。 5．對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目標(biāo)程序)。 三、名詞解釋題(共5小題，每小題4分，共20分) 1．詞法分析 詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則 從構(gòu)成源程序的字符串中識別出

41、一個個具有獨立意義的最小語法單位， 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。 2．LL(1)文法 若文法的任何兩個產(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)生最左推導(dǎo)，1代表在決定分析器的每步 動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一 些明顯的性質(zhì)，它不是二義的，也不含左遞歸。 3．

42、語法樹 句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。 給定文法G=(VN，VT，P，S)，對于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的 語法樹。這棵樹具有下列特征： (1)根節(jié)點的標(biāo)記是開始符號S。 (2)每個節(jié)點的標(biāo)記都是V中的一個符號。 (3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標(biāo)記從左向右的排列 次序為A1A2…AR，那么AA1A2…AR一定是P中的一條產(chǎn)生式。 (4)若一標(biāo)記為A的節(jié)點至少有一個除它以外的子孫，則AVN。 (5)若樹的所有葉節(jié)點上的標(biāo)記從左到右排列為字符串w，則w是文法G 的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。 4．L

43、R(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的 每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號，并至多再 向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否 已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動作 (是 移進(jìn)還是按某一產(chǎn)生式進(jìn)行歸約等)。 5．語言和文法 文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。 文法G定義為四元組的形式： G=(VN，VT，P，S) 其中：VN 是非空有窮集合，稱為非終結(jié)符號集合；VT 是非空有窮集合， 稱為終結(jié)符號集合；P是產(chǎn)生式的集合(非空)；S

44、是開始符號(或識別符號)。 這里，VN∩VT=，SVN。V=VN∪VT，稱為文法G的字母表，它是出現(xiàn) 文法產(chǎn)生式中的一切符號的集合。 文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即 L(G)={x| S*x，其中S為文法開始符號，且 } 簡單的說，文法描述的語言是該文法一切句子的集合。 四、簡答題(共4小題，每小題5分，共20分) 1．編譯程序和高級語言有什么區(qū)別? 用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器 語言表示的目標(biāo)程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程 的程序叫編譯程序。匯編程序是指沒有編譯過

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

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

47、譯階段。也就是要對程序代碼進(jìn)行 一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目 標(biāo)程序運行時所需要的時間短，同時所占用的存儲空間少。 3．對于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的語言相同），則稱文法G1和G2是等價的。 4．對于文法G[E]：E→T|E+T T→F|T*F F→P^F|P P→(E)|i，句型T+T*F+i的句柄是T ，最左素短語是 T*F。 5．最右推導(dǎo)的逆過程稱為規(guī)范歸約 ，也稱為 最左歸約。 6．規(guī)范規(guī)約中的可規(guī)約串是句柄 ，算符優(yōu)先分析中的可規(guī)約串是 最左素短語 7．（

48、A∨ B）∧（C∨ D∧ E） 的逆波蘭式是ＡＢ∨ＣＤＥ∧∨∧。 8．在屬性文法中文法符號的兩種屬性分別稱為繼承屬性 和綜合屬性（次序可換）。 9．符號表的每一項是由名字欄和 地址分配 兩個欄目組成。在目標(biāo)代碼生成階段，符號表是 地址分配 的依據(jù)。 10．一個過程的DISPLAY表的內(nèi)容是它的　直接外層 的DISPLAY表的內(nèi)容加上本過程的SP的地址 1．什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？ 解答： S-屬性文法是只含有綜合屬性的屬性文法。 （2分） L-屬性文法要求對于每個產(chǎn)生式AX1X2…Xn，其每個語義規(guī)

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

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

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

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

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

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

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

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

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

58、( 其中 x∈VT*), 則稱 x 是文 法的一個__句子___。 8．遞歸下降法不允許任一非終極符是直接__左___遞歸的。 9．自頂向下的語法分析方法的基本思想是：從文法的__開始符號____開始，根據(jù)給定的輸 入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行__直接推導(dǎo)____，試圖推導(dǎo)出文法的__句子 ____，使之與給定的輸入串___匹配___。 10．自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地 向上進(jìn)行___直接歸約__ ，力求歸約到文法的__開始符號___。 11常用的參數(shù)傳遞方式有___傳地址__，傳值和傳名。 12．在使用高級

59、語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部__語法___錯誤和語義的部分錯誤。 13．一個句型中的最左簡單短語稱為該句型的___句柄_。 14．對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為 __語義規(guī)則___ 。 15．一個典型的編譯程序中，不僅包括__詞法分析___、__語法分析___、__中間代碼生成___、 代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。 16． 從功能上說，程序語言的語句大體可分為__執(zhí)行性___語句和__說明性___語句兩大類。 17． 產(chǎn)生式是用于定義__語法范疇___的一種書寫規(guī)則。 18．語法分析是依據(jù)語言的

60、__語法___規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的__語義___規(guī) 進(jìn)行的。 19．語法分析器的輸入是__單詞符號串___，其輸出是__語法單位___。 20．產(chǎn)生式是用于定義___語法成分__的一種書寫規(guī)則。 21．逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為__(a+b+c)*d-e___ 。 22．語法分析最常用的兩類方法是__自上而下___和__自下而上___分析法。 23．計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：___解釋__和__編譯___。 24．掃描器是__詞法分析器___，它接受輸入的__源程序___，對源程序進(jìn)行___詞法分析__ 并識別出一個個

61、單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。 25．自上而下分析法采用___移進(jìn)__、歸約、錯誤處理、___接受__等四種操作。 26．一個 LR 分析器包括兩部分：一個總控程序和___一張分析表_。 27．后綴式 abc-/所代表的表達(dá)式是___a/(b-c)__。 28．局部優(yōu)化是在__基本塊___范圍內(nèi)進(jìn)行的一種優(yōu)化。 29．詞法分析基于__正則___文法進(jìn)行，即識別的單詞是該類文法的句子。 30．語法分析基于__上下文無關(guān)___文法進(jìn)行，即識別的是該類文法的句子。語法分析的有效 工具是__語法樹___。 31．分析句型時，應(yīng)用算符優(yōu)先分析技術(shù)時，每步被直

62、接歸約的是__最左素短語___，而應(yīng)用 LR 分析技術(shù)時，每步被直接歸約的是___句柄__。 32．語義分析階段所生成的與源程序等價的中間表示形式可以有__逆波蘭___、___三元式表示__與___四元式表示__等。 33．按 Chomsky 分類法，文法按照___規(guī)則定義的形式__進(jìn)行分類。 二、判斷題（對的打“√”，錯的打“”，每小題1分，共10分） 1、編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。 （ ） 2、含有優(yōu)化部分的編譯程序的執(zhí)行效率高。 （ ） 3、DFA和NFA都能正確地識別正規(guī)集。 （ ） 4、由文法的開始符號經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序

63、列是句子。 （ ） 5、算符優(yōu)先分析法是一種規(guī)范歸約的分析方法。 （ ） 6、采用自下而上分析，必須消除回溯。 （ ） 7、樹形表示和三元式不便于優(yōu)化，四元式和間接三元式則便于優(yōu)化。 （ ） 8、一個語義子程序描述了一個文法對應(yīng)的翻譯工作。 （ ） 9、若過程procm第K次被調(diào)用，則其DISPLAY表中就有K+1個元素。 （ ） 10、生成目標(biāo)代碼時應(yīng)該充分考慮提高寄存器的使用效率。 （ ） 二、判斷題（對的打“√”，錯的打“”，每小題1分，共10分） 1 2 3 4 5 6 7 8 9 10 √ √ √ √

64、 二、判斷題（對的打“√”，錯的打“”，每小題1分，共10分） 1、生成目標(biāo)代碼時應(yīng)該著重考慮如何使生成的目標(biāo)程序最短。 （ ） 2、含有優(yōu)化部分的編譯程序的執(zhí)行效率高。 （ ） 3、在編譯過程中，符號表的作用主要是輔助語法錯誤檢查。 （ ） 4、一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則。 （ ） 5、語法制導(dǎo)翻譯法是一種形式化分析方法。 （ ） 6、算符優(yōu)先分析法不是一種規(guī)范歸約的分析方法。 （ ） 7、一個LR(1)文法決不會是二義性文法。 （ ） 8、一個DFA只包含有限個狀態(tài)，其中只有一個初態(tài)，也只有一個終態(tài)。 （ ） 9、 若一個

65、語言是無窮集合，定義該語言的文法一定是遞歸的。 （ ） 10、一個句型中出現(xiàn)的某一產(chǎn)生式的右部即是該句型的句柄。 （ ） 二、判斷題（對的打“√”，錯的打“”，每小題1分，共10分） 1 2 3 4 5 6 7 8 9 10 √ √ √ √ √ 二、填空題（本大題共5小題，每小題2分，共10分） 1．編譯程序首先要識別出源程序中每個(單詞)，然后再分析每個(句子)并翻譯其意義。 2．編譯器常用的語法分析方法有(自底向上)和(自頂向下)兩種。 3．通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對

66、源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的(綜合)。 4．程序設(shè)計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動態(tài)存儲分配)方案。 5．對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目標(biāo)程序)。 三、名詞解釋題(共5小題，每小題4分，共20分) 1．詞法分析 詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則 從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位， 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。 2．LL(1)文法 若文法的任何兩個產(chǎn)生式A a | b都滿足下面兩個條件： （1）FIRST(a ) FIRST(b ) = f； （2）若b * e ，那么FIRST(