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

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

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

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

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

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

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

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

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

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

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

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

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

12、碼產(chǎn)生是依據(jù)語言的__語義___規(guī)進(jìn)行的。 2．語法分析器的輸入是__單詞符號串___，其輸出是__語法單位___。 3．一個(gè)名字的屬性包括__類型___和__作用域___。 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種方法：有窮自動(dòng)機(jī)，正規(guī)式和正規(guī)文法。 3．自上而下的語法分析方法有LL(1)和遞歸下降方法。 4．設(shè)有文法G[S]：S→Sa|a ，構(gòu)造它的拓廣文法，引入一個(gè)產(chǎn)生式：Sˊ→S ；則I。=Closure（{[Sˊ→S，＃]}）= {[Sˊ→S，＃], [S→Sa，＃/a], [S→a，＃/a]}。 5．在LR（0）項(xiàng)目集規(guī)范族中，若有項(xiàng)目：，其中，稱該項(xiàng)目為移進(jìn)項(xiàng)目。 6.LL(1)語法分析方法中應(yīng)解決的主要問題是消除回溯；LR語法分析方法中應(yīng)解決的主要問題是項(xiàng)目沖突。 三、判斷題（判斷下列各題的正錯(cuò)，若正確，在括號中寫“正”；否則寫“錯(cuò)”

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

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

16、3. 編譯程序的工作過程一般劃分為5個(gè)階段：詞法分析、（4） 、語義分析與中間代碼生成，代碼優(yōu)化及（5） 。另外還有（6）和出錯(cuò)處理。 4．表達(dá)式x+y*z/(a+b)的后綴式為 （7） 。 5．文法符號的屬性有綜合屬性和 （8）。 6．假設(shè)二位數(shù)組按行存放，而且每個(gè)元素占用一個(gè)存儲單元，則數(shù)組a[1..15,1..20]某個(gè)元素a[i，j]的地址計(jì)算公式為（9）。 7．局部優(yōu)化是局限于一個(gè)（10）范圍內(nèi)的一種優(yōu)化。 答案：： (1) 棧式動(dòng)態(tài)存儲分配 (2) 堆式動(dòng)態(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．編譯程序首先要識別出源程序中每個(gè)(單詞)，然后再分析每個(gè)(句子)并翻譯其意義。 2．編譯器常用的語法分析方法有(自底向上)和(自頂向下)兩種。 3．通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對源程序的(綜合)。 4．程序設(shè)計(jì)語言的發(fā)展帶來了日漸多變的運(yùn)行時(shí)存儲管理方案，主要分為兩大類，即(靜態(tài)存儲分配)方案和(動(dòng)態(tài)存儲分配)方案。 5．對編譯程序而言，輸入數(shù)據(jù)是(源程序)，輸出結(jié)果是(目標(biāo)程序)。 三、名詞解釋題(共5

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

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

21、N。 (5)若樹的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法G 的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。 4．LR(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的 每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號，并至多再 向前查看0個(gè)輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否 已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dò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ì)算機(jī)，經(jīng)過轉(zhuǎn)換成用機(jī)器 語言表示的目標(biāo)程序（這個(gè)過程即編譯），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程 的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn) 換過的叫目標(biāo)程序，也就是機(jī)器語言。 編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來 將匯編語言編寫的程序，按照一一對應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語言表示的程序。 解釋型編譯程序?qū)⒏呒壵Z言程序的一個(gè)語句，先解釋成為一組機(jī)器語言的指令， 然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序 止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)行人和計(jì)算機(jī)的"對話"，隨

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

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

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

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

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

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

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

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

32、文法來描述。 ( ) 20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一個(gè)文法存在某個(gè)句子對應(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)代碼生成 ）五個(gè)階段。 3.如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是（ 二義性的 ）。 4.從功能上說，程序語言的語句大體可分為（ 執(zhí)行性 ）語句和（說明性 ）語句兩大類。 5.語法分析器的輸入是（ 單詞符號

34、 ），其輸出是（ 語法單位 ）。 6.掃描器的任務(wù)是從（ 源程序中 ）中識別出一個(gè)個(gè)（ 單詞符號 ）。 7.符號表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如(類型、種屬、所占單元大小、地址）等等。 8.一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為(現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址) 10.常用的兩種動(dòng)態(tài)存貯分配辦法是（棧式）動(dòng)態(tài)分配和（堆式）動(dòng)態(tài)分配。 11.一個(gè)名字的屬性包括( 類型)和(作用域 )。 12.常用的參數(shù)傳遞方式有(傳地址），（傳值），（傳名） 13.根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為(局部優(yōu)化），（循環(huán)優(yōu)化），

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

36、AL采用( 動(dòng)態(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í)行代價(jià)定義為(指令訪問主存次數(shù)加1） 33.算符優(yōu)先分析法每次都是對(最左素短語）進(jìn)行歸約。 三、名詞解釋題： 1.局部優(yōu)化-------局限于基本塊范圍的優(yōu)化稱。 2.二義性文法------如果一個(gè)文法存在某個(gè)句子對

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

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

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

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

41、一個(gè)個(gè)具有獨(dú)立意義的最小語法單位， 并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。 2．LL(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è)輸入符號。除了沒有公共左因子外，LL(1)文法還有一 些明顯的性質(zhì)，它不是二義的，也不含左遞歸。 3．

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

43、R(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的 每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號，并至多再 向前查看0個(gè)輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否 已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dò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ì)算機(jī)，經(jīng)過轉(zhuǎn)換成用機(jī)器 語言表示的目標(biāo)程序（這個(gè)過程即編譯），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程 的程序叫編譯程序。匯編程序是指沒有編譯過

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

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

47、譯階段。也就是要對程序代碼進(jìn)行 一種等價(jià)變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目 標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短，同時(shí)所占用的存儲空間少。 3．對于文法G1和G2，若有L(G1)=L(G2) （或 G1和G2的語言相同），則稱文法G1和G2是等價(jià)的。 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．符號表的每一項(xiàng)是由名字欄和 地址分配 兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號表是 地址分配 的依據(jù)。 10．一個(gè)過程的DISPLAY表的內(nèi)容是它的　直接外層 的DISPLAY表的內(nèi)容加上本過程的SP的地址 1．什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？ 解答： S-屬性文法是只含有綜合屬性的屬性文法。 （2分） L-屬性文法要求對于每個(gè)產(chǎn)生式AX1X2…Xn，其每個(gè)語義規(guī)

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

50、轉(zhuǎn)移到的語句，或 （3）緊跟在條件轉(zhuǎn)移語句后面的語句。 4．(6分)運(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表可以訪問其外層過程的變量。 二、判斷 1．計(jì)算機(jī)高級語言翻譯成低級語言只有解釋一種方式。() 2．在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)

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

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

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

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

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

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

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

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

59、語言編程時(shí),首先可通過編譯程序發(fā)現(xiàn)源程序的全部__語法___錯(cuò)誤和語義的部分錯(cuò)誤。 13．一個(gè)句型中的最左簡單短語稱為該句型的___句柄_。 14．對于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為 __語義規(guī)則___ 。 15．一個(gè)典型的編譯程序中，不僅包括__詞法分析___、__語法分析___、__中間代碼生成___、 代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。 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．計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：___解釋__和__編譯___。 24．掃描器是__詞法分析器___，它接受輸入的__源程序___，對源程序進(jìn)行___詞法分析__ 并識別出一個(gè)個(gè)

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

62、接歸約的是__最左素短語___，而應(yīng)用 LR 分析技術(shù)時(shí)，每步被直接歸約的是___句柄__。 32．語義分析階段所生成的與源程序等價(jià)的中間表示形式可以有__逆波蘭___、___三元式表示__與___四元式表示__等。 33．按 Chomsky 分類法，文法按照___規(guī)則定義的形式__進(jìn)行分類。 二、判斷題（對的打“√”，錯(cuò)的打“”，每小題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、一個(gè)語義子程序描述了一個(gè)文法對應(yīng)的翻譯工作。 （ ） 9、若過程procm第K次被調(diào)用，則其DISPLAY表中就有K+1個(gè)元素。 （ ） 10、生成目標(biāo)代碼時(shí)應(yīng)該充分考慮提高寄存器的使用效率。 （ ） 二、判斷題（對的打“√”，錯(cuò)的打“”，每小題1分，共10分） 1 2 3 4 5 6 7 8 9 10 √ √ √ √

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

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

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