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

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

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

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

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

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

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

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

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

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

10、_三元式表示_等。一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃，錯(cuò)誤的劃×）（每個(gè)2分，共20分）1一個(gè) LL(l)文法一定是無二義的。 (× ) 7LR 法是自頂向下語法分析方法。 (× )2正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 (× )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è)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。 ( )8數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。

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

12、分）1已知文法GS：S(A)|a ，AAcS|S|b ；該文法的開始符號(hào)是 S，非終結(jié)符號(hào)集合為 S,A，終結(jié)符號(hào)集合為a,b,c,(,)。2描述源程序中的單詞結(jié)構(gòu)有3種方法：有窮自動(dòng)機(jī)，正規(guī)式和正規(guī)文法。3自上而下的語法分析方法有LL(1)和遞歸下降方法。4設(shè)有文法GS：SSa|a ，構(gòu)造它的拓廣文法，引入一個(gè)產(chǎn)生式：SS ；則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)解決

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

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

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

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

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

18、的任何兩個(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ì)，它不是二義的，也不含左遞歸。3語法樹 句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。給定文法G=(VN，VT，P，S)，對(duì)于G的任何句型都

19、能構(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，那么A®A1A2AR一定是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)生的句子。4LR(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再向前查看0個(gè)

20、輸入符號(hào)，就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(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é)符號(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)生的全部句子組成，即L(G)

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

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

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

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

25、高級(jí)語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。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è)句型的直接短語是唯一的。 （ ）3.已經(jīng)證明文法的二義性是可判定的。 （ ）4.每個(gè)基本塊可用一

26、個(gè)DAG表示。 （ ）5.每個(gè)過程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。 （ ）6.2型文法一定是3型文法。 （ ）7.一個(gè)句型一定句子。 ( )8.算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。 X ( )9.采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)行優(yōu)化。 （ ）10.編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 ( )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è)基本塊只有一個(gè)入口和一個(gè)出口。 (

27、 )16.一個(gè)LL(1)文法一定是無二義的。 ( )17.逆波蘭法表示的表達(dá)試亦稱前綴式。 ( )18.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 ( )19.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 ( )20.一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 ( )21.3型文法一定是2型文法。 ( )22.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則文法是二義性的。 ( )答案：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)化）和（目標(biāo)代碼生成 ）五個(gè)階段。3.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是（ 二義性的 ）。 4.從功能上說，程序語言的語句大體可分為（ 執(zhí)行性 ）語句和（說明性 ）語句兩大類。5.語法分析器的輸入是（ 單詞符號(hào) ），其輸出是（ 語法單位 ）。6.掃描器的任務(wù)是從（ 源程序中 ）中識(shí)別出一個(gè)個(gè)（ 單詞符號(hào) ）。7.符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如(類型、種屬、所占單元大小、

29、地址）等等。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)化），（全局優(yōu)化）三個(gè)級(jí)別。14.語法分析的方法大致可分為兩類，一類是（ 自上而下 ）分析法，另一類是（ 自下而上 ）分析法。15.預(yù)測(cè)分析程序是使用一張（ 分析表 ）和一個(gè)（ 符號(hào)棧 ）進(jìn)行聯(lián)合控制的。17.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài),其中有一個(gè)被認(rèn)為

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

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

32、其中的第一個(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è)字符。15.句柄-一個(gè)句型的最左直接短語。16.語

33、法制導(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.待用信息-如果在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。21.語義-定義程序的意義的一組規(guī)則。 1編譯程序首先要識(shí)別出源程序中每個(gè)(單詞)，然后再分析每個(gè)(句子)并翻譯其意義。 2編譯器常用的語法分析方法有(自底向上)和(自頂

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

35、 若文法的任何兩個(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ì)，它不是二義的，也不含左遞歸。3語法樹 句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。給定文法G=(VN，VT，P，S)，對(duì)于G的任

36、何句型都能構(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，那么A®A1A2AR一定是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)生的句子。4LR(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號(hào)，并至多再向前

37、查看0個(gè)輸入符號(hào)，就能確定相對(duì)于某一產(chǎn)生式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(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é)符號(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)生的全部句子組成，即L

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

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

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

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

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

43、的語句，或（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ī)高級(jí)語言翻譯成低級(jí)語言只有解釋一種方式。(×) 2在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。(×)3甲

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

45、 產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種說法。( × )12若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。( × )13一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 ( )14在程序中標(biāo)識(shí)符的出現(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數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。 ( × )19編譯程序與具體的機(jī)器有關(guān),與具體的語言無關(guān)。 (

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

47、言都可以用上下文無關(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è)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。 ( )33數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。( × )34對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動(dòng)態(tài)貯存分配策略。 ( × )35編譯程序是對(duì)高級(jí)語言程序的解釋執(zhí)行。( × ) 36一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)

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

49、L(r)L(s)。( × ) 45確定的的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正集()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編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義

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

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

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