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

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

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

3、子？什么是語(yǔ)言?答：（1）設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果Sx（其中xCVT*）,則稱x是文法的一個(gè)句子。（2）設(shè)GS是給定文法，則由文法G所定義白語(yǔ)言L（G）可描述為：L（G）=xSx,xCVT*。一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃M錯(cuò)誤的劃X）（每個(gè)2分，共20分）M.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRA咪用動(dòng)態(tài)貯存分配策略。（）X2.甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。（）3.遞歸下降分析法是自頂向上分析方法。（）M.產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。（）然.LR法是自頂向下語(yǔ)法分析方法。（）達(dá).在SLR（1）分析法的名稱中

4、，S的含義是簡(jiǎn)單的。（）X7.綜合屬性是用于“自上而下”傳遞信息。（）刈.符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。（）>9.程序語(yǔ)言的語(yǔ)言處理程序是一種應(yīng)用軟件。（）M0.解釋程序適用于COBOL和FORTRAN語(yǔ)言。（）三、填空題（每空1分，共10分）1一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的_句柄_。2對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為_語(yǔ)義規(guī)則_。3 一個(gè)典型的編譯程序中，不僅包括_詞法分析_、_語(yǔ)法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。4 從功能上說，程序語(yǔ)言的語(yǔ)

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

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

7、優(yōu)化是在_范圍內(nèi)進(jìn)行的一種優(yōu)化。_基本塊_一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃M錯(cuò)誤的劃X）（每個(gè)2分，共20分）1 .設(shè)r和s分別是正規(guī)式，則有L（r|s尸L（r）L（s）。（X）2 .確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。（守3 .詞法分析作為單獨(dú)的一遍來處理較好。（x）4 .構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。（V）5 .規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（X）6 .同心集的合并有可能產(chǎn)生新的移進(jìn)”/歸約”沖突。（x）7 .LR分析技術(shù)無法適用二義文法。（X）8 .樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。（X）9 .程序中的表達(dá)式語(yǔ)句在語(yǔ)義翻譯時(shí)不需要

8、回填技術(shù)。（v）10 .對(duì)中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。（X）三、填空題（每空1分，共10分）1 詞法分析基于_正則_文法進(jìn)行，即識(shí)別的單詞是該類文法的句子。2 語(yǔ)法分析基于_上下文無關(guān)_文法進(jìn)行，即識(shí)別的是該類文法的句子。語(yǔ)法分析的有效工具是_語(yǔ)法樹_。3 .分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是最左素短語(yǔ)，而應(yīng)用LR分析技術(shù)時(shí)，每步被直接歸約的是_句柄_。4 語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有_逆波蘭_、_四無式表示_與_三元式表示_等。一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃V,錯(cuò)誤的劃X）（每個(gè)2分，共20分）1 .一個(gè)LL（l）文法一定是無二義的。（X）

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

10、言的_語(yǔ)法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的_語(yǔ)義_規(guī)進(jìn)行的。2語(yǔ)法分析器的輸入是_單詞符號(hào)串_，其輸出是_語(yǔ)法單位_。3一個(gè)名字的屬性包括_類型_和_作用域_。4產(chǎn)生式是用于定義_語(yǔ)法成分_的一種書寫規(guī)則。5逆波蘭式ab+c+d*e-所表達(dá)的表達(dá)式為_（a+b+c）*d-e_。6語(yǔ)法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。二、填空題（每空2分，共22分）1.已知文法GS:S-（A）|a,A->AcS|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自上而下的語(yǔ)

11、法分析方法有LL（1）和遞歸下降方法。4.設(shè)有文法GS: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)目：AA?bB，其中bVT，稱該項(xiàng)目為移進(jìn)項(xiàng)目。6 .LL（1）語(yǔ)法分析方法中應(yīng)解決的主要問題是消除回溯；LR語(yǔ)法分析方法中應(yīng)解決的主要問題是項(xiàng)目沖突。三、判斷題（判斷下列各題的正錯(cuò)，若正確，在括號(hào)中寫“正”；否則寫“錯(cuò)”。每題2分，共16分）1一個(gè)文法有二義性，則由它描述的語(yǔ)言一定具有二義性。（錯(cuò)）2若一個(gè)語(yǔ)言有無窮多個(gè)句子，則定義該語(yǔ)言的文法一定是

12、遞歸的。（正）7 .若有正規(guī)式a*b,則與之等價(jià)的文法應(yīng)該是GA:ZaA|b。（正）8 .設(shè)有文法GA:A-aB,B-bB|b,則該文法是LL（1）文法。（錯(cuò)）9 .由文法法G的開始符號(hào)S推導(dǎo)出來的符號(hào)申，稱為文法G的句子。（錯(cuò)）6最左素短語(yǔ)是句型最左邊的短語(yǔ)。（錯(cuò)）7 .LR語(yǔ)法分析法是一種規(guī)范規(guī)約的分析方法。（正）8 .存在能夠被確定的有窮自動(dòng)機(jī)DFA識(shí)別，卻不能用正規(guī)式表示的語(yǔ)言。(錯(cuò))1 .文法G的一個(gè)句子對(duì)應(yīng)于多個(gè)推導(dǎo)，則G是二義性的。(X)2 .動(dòng)態(tài)的存儲(chǔ)分配是指在運(yùn)行階段為源程序中的數(shù)據(jù)對(duì)象分配存儲(chǔ)單元。(，)3 .算符優(yōu)先文法采用“移進(jìn)-規(guī)約”技術(shù)，其規(guī)約過程是規(guī)范的。(X)4

13、 .刪除歸納變量是在強(qiáng)度削弱以后進(jìn)行。(V)5 .在目標(biāo)代碼生成階段，符號(hào)表用于目標(biāo)代碼生成。(X)一.填空題(每空2分，共20分)11.不同的編譯程序關(guān)于數(shù)據(jù)空間的存儲(chǔ)分配策略可能不同，但大部分編譯中采用的方案有兩種：靜態(tài)存儲(chǔ)分配方案和動(dòng)態(tài)存儲(chǔ)分配方案，而后者又分為(1)和。2 .規(guī)范規(guī)約是最(3)規(guī)約。3 .編譯程序的工作過程一般劃分為5個(gè)階段：詞法分析、(4)、語(yǔ)義分析與中間代碼生成，代碼優(yōu)化及(5)。另外還有(6)和出錯(cuò)處理。4 .表達(dá)式x+y*z/(a+b)的后綴式為。5 .文法符號(hào)的屬性有綜合屬性和工8L6 .假設(shè)二位數(shù)組按行存放，而且每個(gè)元素占用一個(gè)存儲(chǔ)單元，則數(shù)組a1.15,1

14、.20某個(gè)元素ai,j的地址計(jì)算公式為(9!。7 .局部?jī)?yōu)化是局限于一個(gè)(10)范圍內(nèi)的一種優(yōu)化。答案：(1)棧式動(dòng)態(tài)存儲(chǔ)分配(2)堆式動(dòng)態(tài)存儲(chǔ)分配左(4)語(yǔ)法分析(5)目標(biāo)代碼生成(6)表格管理(7)xyz*ab+/+(8)繼承屬性(9)a+(i-1)*20+j-1(10) 基本塊一、填空題（每空2分，共20分）1 目標(biāo)程序（targetcode）語(yǔ)法分析（syntaxanalyzer）代碼優(yōu)化器（codeoptimizer）代碼產(chǎn)生器（codegenerator）符號(hào)表管理（symboltablemanager）2 繼承屬性（inheritedattribute）3 局部?jī)?yōu)化（localo

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

16、序）。三、名詞解釋題（共5小題，每小題4分，共20分）1 詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示（token），送給語(yǔ)法分析程序。2 LL（1）文法若文法的任何兩個(gè)產(chǎn)生式A|都滿足下面兩個(gè)條件：（ 1） FIRST（）FIRST（）=；（2）若*，那么FIRST（）FOLLOW（A）=。我們把滿足這兩個(gè)條件的文法叫做LL（1）文法，其中的第一個(gè)L代表從左向右掃描輸入，第二個(gè)L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒有公共左因子外，LL（1）文法還

17、有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語(yǔ)法樹句子的樹結(jié)構(gòu)表示法稱為語(yǔ)法樹（語(yǔ)法分析樹或語(yǔ)法推導(dǎo)樹）。給定文法G=（VN，VT，P，S），對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹。這棵樹具有下列特征：(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)锳iA醍,那么AAAA一定是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)分析

18、器所謂LR(0)分析，是指從左至右掃描和自底向上的語(yǔ)法分析，且在分析的每一步，只須根據(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)行歸約等)。5語(yǔ)言和文法文法就是語(yǔ)言結(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))。這里，VnAVt=,SVnoV=VNUVt,稱為

19、文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號(hào)的集合。文法G所描述的語(yǔ)言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G尸x|S*x，其中S為文法開始符號(hào)，且xVT簡(jiǎn)單的說，文法描述的語(yǔ)言是該文法一切句子的集合。四、簡(jiǎn)答題(共4小題，每小題5分，共20分)1 編譯程序和高級(jí)語(yǔ)言有什么區(qū)別?用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫的程序，必須先送入計(jì)算機(jī)，經(jīng)過轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的目標(biāo)程序(這個(gè)過程即編譯)，才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語(yǔ)言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機(jī)器語(yǔ)言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用

20、來將匯編語(yǔ)言編寫的程序，按照一一對(duì)應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的程序。解釋型編譯程序?qū)⒏呒?jí)語(yǔ)言程序的一個(gè)語(yǔ)句，先解釋成為一組機(jī)器語(yǔ)言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語(yǔ)句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進(jìn)行人和計(jì)算機(jī)的"對(duì)話"，隨時(shí)可以修改高級(jí)語(yǔ)言的程序。BASIC語(yǔ)言就是解釋型高級(jí)語(yǔ)言。編譯型編譯程序?qū)⒓?jí)語(yǔ)言編寫的程序，一次就會(huì)部翻譯成機(jī)器語(yǔ)言表示的程序，而且過程進(jìn)行很快，在過程中，不能進(jìn)行人機(jī)對(duì)話修改。FORTRA語(yǔ)言就是編譯型高級(jí)語(yǔ)言。2 編譯程序的工作分為那幾個(gè)階段?詞法分析、語(yǔ)法分析和語(yǔ)義分析是對(duì)源程序進(jìn)行的分析

21、（稱為編譯程序的前端），而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱為對(duì)源程序進(jìn)行綜合（稱為編譯程序的后端），它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。3簡(jiǎn)述自下而上的分析方法。所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)；或者說從語(yǔ)法樹的末端開始，步步向上“歸約”，直到根節(jié)點(diǎn)。4簡(jiǎn)述代碼優(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)，正確的劃M錯(cuò)誤的劃X）（每個(gè)2分，共20分）

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

23、、填空題（每空1分，共10分）1計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫的程序主要有兩種途徑：_解釋_和_編譯2 .掃描器是_詞法分析器，它接受輸入的源程序，對(duì)源程序進(jìn)行_詞法分析并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。3 .自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、接受等四種操作。4 .一個(gè)LR分析器包括兩部分：一個(gè)總控程序和1張分析表_。5 .后綴式abc-/所代表的表達(dá)式是a/（b-c）。6 .局部?jī)?yōu)化是在基本塊范圍內(nèi)進(jìn)行的一種優(yōu)化。、是非題:1 .一個(gè)上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。()( )( )( )( )2 .一個(gè)句型的直接短語(yǔ)是唯一的。3 .已經(jīng)證明文

24、法的二義性是可判定的。4 .每個(gè)基本塊可用一個(gè)DA砧示。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 .編譯過程中，語(yǔ)法分析器的任務(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è)出口。（）

25、16 .一個(gè)LL（1）文法一定是無二義的。（）17 .逆波蘭法表示的表達(dá)試亦稱前綴式。（）18 .目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。（）19 .正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無關(guān)文法來描述。（）20 .一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。（）21 .3型文法一定是2型文法。（）()x 9. V 10. x22.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則文法是二義性的。答案：1.X2.X3.X4.V5.V6.X7.X8.11. X12. V13.義14.V15.V16.V17.義18.V19.V20.義21.V22.V、填空題：2 .編譯過程可分為（詞法分析），（語(yǔ)法

26、分析），（語(yǔ)義分析與中間代碼生成），（優(yōu)化）和（目標(biāo)代碼生成）五個(gè)階段。3 .如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則稱這個(gè)文法是（二義性的）。4 .從功能上說，程序語(yǔ)言的語(yǔ)句大體可分為（執(zhí)行性）語(yǔ)句和（說明性）語(yǔ)句兩大類。5 .語(yǔ)法分析器的輸入是（單詞符號(hào)），其輸出是（語(yǔ)法單位）。6 .掃描器的任務(wù)是從（源程序中）中識(shí)別出一個(gè)個(gè)（單詞符號(hào)）。7 .符號(hào)表中的信息欄中登記了每個(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)分配和（堆式

27、）動(dòng)態(tài)分配。11 .一個(gè)名字的屬性包括（類型）和（作用域）。12 .常用的參數(shù)傳遞方式有（傳地址），（傳值），（傳名）13 .根據(jù)優(yōu)化所涉及的程序范圍，可將優(yōu)化分成為（局部?jī)?yōu)化），（循環(huán)優(yōu)化），（全局優(yōu)化）三個(gè)級(jí)別。14 .語(yǔ)法分析的方法大致可分為兩類，一類是（自上而下）分析法，另一類是（自下而上）分析法。15 .預(yù)測(cè)分析程序是使用一張（分析表）和一個(gè)（符號(hào)棧）進(jìn)行聯(lián)合控制的。17.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是（初）態(tài)；而且實(shí)際上至少要有一個(gè)（終）態(tài)。19.語(yǔ)法分析是依據(jù)語(yǔ)言的（語(yǔ)法）規(guī)則進(jìn)行。中間代碼產(chǎn)生是依據(jù)語(yǔ)言的（語(yǔ)義）規(guī)則進(jìn)行的。21 .一個(gè)文法G,若它的預(yù)測(cè)分析表M

28、不含多重定義，則該文法是（LL（1）文法）文法。22 .對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN用（靜態(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)化稱（局部?jī)?yōu)化）。30 .2型文法又稱為（上下文無關(guān)）文法；3型文法又稱為（正則）文法。32 .每條指令的執(zhí)行代價(jià)定義為（指令訪問主存次數(shù)加1）33 .算符優(yōu)先分析法每次都是對(duì)（最左素短語(yǔ)）進(jìn)行歸約。三、名詞解釋題：1 .局部?jī)?yōu)化局限于基本塊范圍

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

30、G是一個(gè)文法，S劃文法的開始符號(hào)，假定a38是文法G的一個(gè)句型，如果有士aAS且A=>3,則稱3是句型a3§相對(duì)非終結(jié)符A的短語(yǔ)。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è)句型的最左直接短語(yǔ)。16 .語(yǔ)法制導(dǎo)翻譯-在語(yǔ)法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義程序進(jìn)行翻譯的方法叫做語(yǔ)法制導(dǎo)翻譯。17 .規(guī)范句型-

31、由規(guī)范推導(dǎo)所得到的句型。18 .素短語(yǔ)-素短語(yǔ)是指這樣一個(gè)短語(yǔ)，至少含有一個(gè)終結(jié)符，并且，除它自身外不再含任何更小的素短語(yǔ)。19 .語(yǔ)法-是組規(guī)則，用它可形成和產(chǎn)生一個(gè)合式的程序。_20 .待用信息-如果在一個(gè)基本塊中，四元式i對(duì)A定值，四元式j(luò)要引用A值，而從i到j(luò)之間沒有A的其它定值，則稱j是四元式i的變量A的待用信息。21 .語(yǔ)義-定義程序的意義的一組規(guī)則。1 .編譯程序首先要識(shí)別出源程序中每個(gè)(單詞),然后再分析每個(gè)(包王)并翻譯其意義。2 .編譯器常用的語(yǔ)法分析方法有(自底向上)和(自頂向下)兩種。3 .通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語(yǔ)法和語(yǔ)義分析是對(duì)源程序的(

32、分析)，中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對(duì)源程序的(紜盒)。4 .程序設(shè)計(jì)語(yǔ)言的發(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ú)立意義的最小語(yǔ)法單位,并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token),送給語(yǔ)法分析程序。2 .LL(1)文法若文法的任何兩個(gè)產(chǎn)生式A|都滿足下面兩個(gè)條件：(1) FIRST()FIRST(

33、)=;(2)若*,那么FIRST()FOLLOW(A)=。我們把滿足這兩個(gè)條件的文法叫做LL(1)文法，其中的第一個(gè)L代表從左向右掃描輸入，第二個(gè)L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3 .語(yǔ)法樹句子的樹結(jié)構(gòu)表示法稱為語(yǔ)法樹(語(yǔ)法分析樹或語(yǔ)法推導(dǎo)樹)。給定文法G=(VN,Vt,P,S),對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹。這棵樹具有下列特征：(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)記從左向右的

34、排列次序?yàn)锳1A2ar,那么AAAAr一定是P中的一條產(chǎn)生式。(4)若一標(biāo)記為A的節(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則A_X。(5)若樹的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w,則w是文法G的句型；若w中僅含終結(jié)符號(hào)，則w為文法G所產(chǎn)生的句子。4 .LR(0)所i胃LR(0)分析，是指從左至右掃描和自底向上的語(yǔ)法分析，且在分析的每一步，只須根據(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)行歸約等)。5 .語(yǔ)百和文法文法就是語(yǔ)言結(jié)構(gòu)的定義和描述，

35、是有窮非空的產(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)）。這里，VnAVt=,S出。V=VNUVt,稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號(hào)的集合。文法G所描述的語(yǔ)言用L（G）表示，它由文法G所產(chǎn)生的全部句子組成，即L（G尸x|S*x，其中S為文法開始符號(hào)，且xVT上簡(jiǎn)單的說，文法描述的語(yǔ)言是該文法一切句子的集合。四、簡(jiǎn)答題（共4小題，每小題5分，共20分）1 .編譯程序和高級(jí)語(yǔ)言有什么區(qū)別？用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫的程序，必須先

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

37、C語(yǔ)言就是解釋型高級(jí)語(yǔ)言。編譯型編譯程序?qū)⒓?jí)語(yǔ)言編寫的程序，一次就會(huì)部翻譯成機(jī)器語(yǔ)言表示的程序，而且過程進(jìn)行很快,在過程中，不能進(jìn)行人機(jī)對(duì)話修改。FORTRA語(yǔ)言就是編譯型高級(jí)語(yǔ)言。2 .編譯程序的工作分為那幾個(gè)階段？詞法分析、語(yǔ)法分析和語(yǔ)義分析是對(duì)源程序進(jìn)行的分析（稱為編譯程序的前端），而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱為對(duì)源程序進(jìn)行綜合（稱為編譯程序的后端），它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。3.簡(jiǎn)述自下而上的分析方法。所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行歸約”，直至歸約到文法的開始符號(hào)；或者說從語(yǔ)法樹的末端開始，步步向上歸約”，直到根節(jié)點(diǎn)。4 .簡(jiǎn)述

38、代碼優(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的語(yǔ)言相同）,則稱文法G1和G2是等價(jià)的。4 .對(duì)于文法GE:E-<|E+TT-F|T*FF-PAF|PPn（E）|i,句型T+T*F+i的句柄是T,最左素短語(yǔ)是T*F_。5 .最右推導(dǎo)的逆過程稱為規(guī)范歸約,也稱為最左歸約。6 .規(guī)范規(guī)約中的可規(guī)約串是也，算符優(yōu)先分析中的可規(guī)約串是最左素短語(yǔ)7 .（AVB）A（CV?DAE）的逆

39、波蘭式是ABVCD?EAVA。8 .在屬性文法中文法符號(hào)的兩種屬性分別稱為繼承屬性和綜合屬性（次序可換）。9 .符號(hào)表的每一項(xiàng)是由名字欄和地址分配兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號(hào)表是地址分配的依據(jù)。10 .一個(gè)過程的DISPLAYS的內(nèi)容是它的直接外層的DISPLAY!羨的內(nèi)容加上本過程的SP的地址1.什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系？解答：S-屬性文法是只含有綜合屬性的屬性文法。（2分）L-屬性文法要求對(duì)于每個(gè)產(chǎn)生式AX1X2Xn,其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj的一個(gè)繼承屬性，且該屬性僅依賴于：（1）產(chǎn)生式Xj的左邊符號(hào)X1,X2Xj-1

40、的屬性；（2）A的繼承屬性。（2分）S-屬性文法是L-屬性文法的特例。（2分）2 .什么是句柄？什么是素短語(yǔ)？一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。（3分）素短語(yǔ)是這樣的一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符并且不包含更小的素短語(yǔ)。（3分）3 .劃分程序的基本塊時(shí)，確定基本塊的入口語(yǔ)句的條件是什么?解答：（1）程序第一個(gè)語(yǔ)句，或（2）能由條件轉(zhuǎn)移語(yǔ)句或無條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或（3）緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。4 .（6分）運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diapla

41、y.假定現(xiàn)在進(jìn)入白過程層次為i,則它的diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、直至最外層（主程序，0層）等每層過程的最新活動(dòng)記錄的起始地址。通過DISPLAYS可以訪問其外層過程的變量。二、判斷1 .計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。（X）2 .在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。（X）3 .甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。（V）4 .正則文法其產(chǎn)生式為A->a,A->Bb,A,BCVN,a、bVT。（5 .每個(gè)文法都能改寫為L(zhǎng)L（1）文法。（V）6 .遞歸下降法不允

42、許任一非終極符是直接左遞歸的。（V）7 .算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。（X）8 .自底而上語(yǔ)法分析方法的主要問題是候選式的選擇。（X）9 .LR法是自頂向下語(yǔ)法分析方法。（X）10 .簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。（X）11 “用高級(jí)語(yǔ)言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行12 .若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（x）13 .一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。（V）14 .在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。（x）15 .僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。（V）16 .削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基

43、本塊內(nèi)僅被定義一次的特性。（V）17 在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。（18 .數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。（x）19 .編譯程序與具體的機(jī)器有關(guān)，與具體的語(yǔ)言無關(guān)。（X）20 .遞歸下降分析法是自頂向上分析方法。（,）21 .產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。（X）22 .LR法是自頂向下語(yǔ)法分析方法。（X）23 .在SLR（1）分析法的名稱中，S的含義是簡(jiǎn)單的。（V）24.綜合屬性是用于“自上而下”傳遞信息。（X）25符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占地址等等。（X）26 .程序語(yǔ)言的語(yǔ)言處理程序是一

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

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

46、好。（X）X）”這種說法。（X ）單元大小、（V） 30 .目標(biāo)（v ）（V ） 39 .逆波（x ）47 .LR分析器的任務(wù)就是產(chǎn)生LR分析表。（V）沖突（X ）48 .歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（V）49 .同心集的合并有可能產(chǎn)生新的“移進(jìn)”/“歸約”50.1R分析技術(shù)無法適用二義文法。（X）51樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。（X）52序中的表達(dá)式語(yǔ)句在語(yǔ)義翻譯時(shí)不需要回填技術(shù)。（V）三、填空1 .編譯程序的工作過程一般可以劃分為詞法分析，語(yǔ)法分析，語(yǔ)義分析，中間代碼生成，代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有表格處理_和出錯(cuò)處理_。2 .若源程序是用高級(jí)

47、語(yǔ)言編寫的,目標(biāo)程序是機(jī)器語(yǔ)言程序或匯編程序,則其翻譯程序稱為編譯程序03 .編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。4 .對(duì)編譯程序而言，輸入數(shù)據(jù)是_源程序_,輸出結(jié)果是目標(biāo)程序。5.產(chǎn)生式是用于定義語(yǔ)法成分的一種書寫規(guī)則。6 .語(yǔ)法分析最常用的兩類方法是自上而下和自下而上分析法7 .設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S->x（其中xCVT*）,則稱x是文法的一個(gè)一句子。8 .遞歸下降法不允許任一非終極符是直接_左一遞歸的。9,自頂向下的語(yǔ)法分析方法的基本思想是：從文法的開始符號(hào)開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的一

48、句子,使之與給定的輸入串匹配。10.自底向上的語(yǔ)法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行直接歸約_,力求歸約到文法的開始符號(hào)_。11常用的參數(shù)傳遞方式有_傳地址傳值和傳名。12 .在使用高級(jí)語(yǔ)言編程時(shí)，首先可通過編譯程序發(fā)現(xiàn)源程序的全部語(yǔ)法錯(cuò)誤和語(yǔ)義的部分錯(cuò)誤。13 .一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的句柄_。14 .對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為語(yǔ)義規(guī)則。15 .一個(gè)典型的編譯程序中，不僅包括詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。16 .從功能上說，程序語(yǔ)言的語(yǔ)句大體可分為執(zhí)行性

49、語(yǔ)句和_說明性語(yǔ)句兩大類。17 .產(chǎn)生式是用于定義語(yǔ)法范疇的一種書寫規(guī)則。18 .語(yǔ)法分析是依據(jù)語(yǔ)言的語(yǔ)法規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的語(yǔ)義_規(guī)進(jìn)行的。19 .語(yǔ)法分析器的輸入是單詞符號(hào)串，其輸出是語(yǔ)法單位。20 .產(chǎn)生式是用于定義語(yǔ)法成分的一種書寫規(guī)則。21 .逆波蘭式ab+c+d*e-所表達(dá)的表達(dá)式為（a+b+c）*d-e。22 .語(yǔ)法分析最常用的兩類方法是自上而下和_自下而上分析法。23 .計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫的程序主要有兩種途徑：解釋_和編譯。24 .掃描器是一詞法分析器，它接受輸入的源程序，對(duì)源程序進(jìn)行詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用

50、。25 .自上而下分析法采用移進(jìn)_、歸約、錯(cuò)誤處理、接受等四種操作。26 .一個(gè)LR分析器包括兩部分：一個(gè)總控程序和一張分析表_。27 .后綴式abc-/所代表的表達(dá)式是a/（b-c）_。28 .局部?jī)?yōu)化是在基本塊范圍內(nèi)進(jìn)行的一種優(yōu)化。29 .詞法分析基于一正則文法進(jìn)行，即識(shí)別的單詞是該類文法的句子。30 .語(yǔ)法分析基于上下文無關(guān)_文法進(jìn)行，即識(shí)別的是該類文法的句子。語(yǔ)法分析的有效工具是語(yǔ)法樹。31 .分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是最左素短語(yǔ)，而應(yīng)用LR分析技術(shù)時(shí)，每步被直接歸約的是句柄_。32 .語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有逆波蘭、三元式表示與

51、四元式表示等。33 .按Chomsky分類法，文法按照規(guī)則定義的形式進(jìn)行分類。二、判斷題（對(duì)的打，錯(cuò)的打“X”，每小題1分，共10分）1、編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。（）2、含有優(yōu)化部分的編譯程序的執(zhí)行效率高。（）3、DFA和NFA都能正確地識(shí)別正規(guī)集。（）4、由文法的開始符號(hào)經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是句子。（）5、算符優(yōu)先分析法是一種規(guī)范歸約的分析方法。（）6、采用自下而上分析，必須消除回溯。（）7、樹形表示和三元式不便于優(yōu)化，四元式和間接三元式則便于優(yōu)化。（）8、一個(gè)語(yǔ)義子程序描述了一個(gè)文法對(duì)應(yīng)的翻譯工作。（）9、若過程procm第K次被調(diào)用，則其DISPL

52、AY表中就有K+1個(gè)元素。（）10、生成目標(biāo)代碼時(shí)應(yīng)該充分考慮提高寄存器的使用效率。（）、判斷題（對(duì)的打，錯(cuò)的打“X”，每小題1分，共10分）12345678910VXVXXXVXXV、判斷題（對(duì)的打，錯(cuò)的打“X”，每小題1分，共10分）1、生成目標(biāo)代碼時(shí)應(yīng)該著重考慮如何使生成的目標(biāo)程序最短。（）2、含有優(yōu)化部分的編譯程序的執(zhí)行效率高。（）3、在編譯過程中，符號(hào)表的作用主要是輔助語(yǔ)法錯(cuò)誤檢查。（）4、一個(gè)屬性文法包含一個(gè)上下文無關(guān)文法和一系列語(yǔ)義規(guī)則。（）5、語(yǔ)法制導(dǎo)翻譯法是一種形式化分析方法。（）6、算符優(yōu)先分析法不是一種規(guī)范歸約的分析方法。（）7、一個(gè)LR（1）文法決不會(huì)是二義性文法。（）

53、8、一個(gè)DFA只包含有限個(gè)狀態(tài)，其中只有一個(gè)初態(tài)，也只有一個(gè)終態(tài)。（）9、若一個(gè)語(yǔ)言是無窮集合，定義該語(yǔ)言的文法一定是遞歸的。（）10、一個(gè)句型中出現(xiàn)的某一產(chǎn)生式的右部即是該句型的句柄。（）、判斷題（對(duì)的打，錯(cuò)的打“X”，每小題1分，共10分）12345678910VXXVXVVXVX二、填空題（本大題共5小題，每小題2分，共10分）1 .編譯程序首先要識(shí)別出源程序中每個(gè)（單詞），然后再分析每個(gè)（句子）并翻譯其意義。2 編譯器常用的語(yǔ)法分析方法有(自底向上)和(自頂向下)兩種。3 通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語(yǔ)法和語(yǔ)義分析是對(duì)源程序的(分析)，中間代碼生成、代碼優(yōu)化與目

54、標(biāo)代碼的生成則是對(duì)源程序的(綜合)。4 程序設(shè)計(jì)語(yǔ)言的發(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ú)立意義的最小語(yǔ)法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語(yǔ)法分析程序。2 LL(1)文法若文法的任何兩個(gè)產(chǎn)生式A|都滿足下面兩個(gè)條件：( 1) FIRST()FIRST()=；(2)若*，那么FIRST()FOLLOW(A)=。我們把滿足這兩個(gè)條件的文法叫做LL(1)文法，其中的第一個(gè)L代表從左向右掃描輸入，第二個(gè)L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語(yǔ)法樹句子的樹結(jié)構(gòu)表示法稱為語(yǔ)法樹(語(yǔ)法分析樹或語(yǔ)法推導(dǎo)樹)。給定文法G=(VN，VT，P，S)，對(duì)于G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹。這棵樹具有下列特征：(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)