編譯原理簡(jiǎn)答題

1、名詞解釋題：Display表: 嵌套層次顯示表由于過(guò)程嵌套允許內(nèi)層過(guò)程引用外層過(guò)程定義的數(shù)據(jù)，因此，當(dāng)一個(gè)過(guò)程運(yùn)行時(shí)必須跟蹤它的所有外層過(guò)程的最新活動(dòng)記錄起始地址， display表就是用于登記每個(gè)外層過(guò)程的最新活動(dòng)記錄起始地址。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

2、代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。LR(0)分析器所謂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)行歸約等)。編譯程序大致有哪幾種開發(fā)技術(shù)？答案：（1）自編譯（2）交叉編譯 （3）自展 （4）移植：編譯程序的工作分為那幾個(gè)階段?答：詞法分析、語(yǔ)法分析和語(yǔ)義分析是對(duì)源

3、程序進(jìn)行的分析(稱為編譯程序的前端) ，而中間代碼生成、代碼優(yōu)化和代碼生成三個(gè)階段合稱為對(duì)源程序進(jìn)行綜合(稱為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序。編譯程序的實(shí)現(xiàn)應(yīng)考慮的問(wèn)題有那些？答案：編譯程序的實(shí)現(xiàn)應(yīng)考慮：開發(fā)周期、目標(biāo)程序的效率、可移植性、可調(diào)試性、可維護(hù)性、可擴(kuò)充性等。編譯程序和高級(jí)語(yǔ)言有什么區(qū)別?答：用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫的程序，必須先送入計(jì)算機(jī)，經(jīng)過(guò)轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的目標(biāo)程序（這個(gè)過(guò)程即編譯），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過(guò)程的程序叫編譯程序。匯編程序是指沒有編譯過(guò)的匯編語(yǔ)言源文件。編譯程序轉(zhuǎn)換過(guò)的叫目標(biāo)程序，也就是機(jī)器語(yǔ)言。 編譯程序的工作情況

4、有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來(lái)將匯編語(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ǔ)言表示的程序，而且過(guò)程進(jìn)行很快，在過(guò)程中，不能進(jìn)行人機(jī)對(duì)話修改。FORTRAN語(yǔ)言就是編譯型高級(jí)語(yǔ)言。編譯過(guò)程中可進(jìn)行的優(yōu)化如何分類？

5、答案：依據(jù)優(yōu)化所涉及的程序范圍，可以分為：局部?jī)?yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)，按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語(yǔ)法分析程序。從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對(duì)循環(huán)的優(yōu)化可以有哪三種？ 答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部?jī)?yōu)化和全局優(yōu)化兩類；對(duì)循環(huán)的優(yōu)化有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計(jì)算強(qiáng)度削減。對(duì)下列錯(cuò)誤信息，請(qǐng)指出可能是編譯的哪個(gè)階段（詞法分析、語(yǔ)法分析、語(yǔ)義分析、代碼生成）報(bào)告的。（1） else 沒有匹配的if（2） 數(shù)組下標(biāo)越界（

6、3） 使用的函數(shù)沒有定義（4） 在數(shù)中出現(xiàn)非數(shù)字字符答案：（1） 語(yǔ)法分析（2） 語(yǔ)義分析（3） 語(yǔ)法分析（4） 詞法分析何謂代碼優(yōu)化？進(jìn)行優(yōu)化所需要的基礎(chǔ)是什么？答案：對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加快或占用存儲(chǔ)空間減少，或兩者都有。優(yōu)化所需要的基礎(chǔ)是在中間代碼生成之后或目標(biāo)代碼生成之后。何謂翻譯程序、編譯程序和解釋程序？答案：翻譯程序是指將用某種語(yǔ)言編寫的程序轉(zhuǎn)換成另一種語(yǔ)言形式的程序的程序，如編譯程序和匯編程序等。編譯程序是把用高級(jí)語(yǔ)言編寫的源程序轉(zhuǎn)換（加工）成與之等價(jià)的另一種用低級(jí)語(yǔ)言編寫的目標(biāo)程序的翻譯程序。解釋程序是解釋、執(zhí)行高級(jí)語(yǔ)

7、言源程序的程序。劃分程序的基本塊時(shí)，確定基本塊的入口語(yǔ)句的條件是什么？答：程序第一個(gè)語(yǔ)句，或能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫的程序有哪些途徑?它們之間的主要區(qū)別是什么?答案：計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫的程序主要途徑有兩種，即解釋與編譯。像Basic 之類的語(yǔ)言，屬于解釋型的高級(jí)語(yǔ)言。它們的特點(diǎn)是計(jì)算機(jī)并不事先對(duì)高級(jí)語(yǔ)言進(jìn)行全盤翻譯，將其變?yōu)闄C(jī)器代碼，而是每讀入一條高級(jí)語(yǔ)句，就用解釋器將其翻譯為一條機(jī)器代碼，予以執(zhí)行，然后再讀入下一條高級(jí)語(yǔ)句，翻譯為機(jī)器代碼，再執(zhí)行，如此反復(fù)?？偠灾沁叿g邊執(zhí)行。像C，Pascal 之類的

8、語(yǔ)言，屬于編譯型的高級(jí)語(yǔ)言。它們的特點(diǎn)是計(jì)算機(jī)事先對(duì)高級(jí)語(yǔ)言進(jìn)行全盤翻譯，將其全部變?yōu)闄C(jī)器代碼，再統(tǒng)一執(zhí)行，即先翻譯，后執(zhí)行。從速度上看，編譯型的高級(jí)語(yǔ)言比解釋型的高級(jí)語(yǔ)言更快。寄存器分配的原則是什么？答案：寄存器分配的原則是：(1) 當(dāng)生成某變量的目標(biāo)代碼時(shí)，盡量讓變量的值或計(jì)算結(jié)果保留在寄存器中，直到寄存器不夠分配時(shí)為止。(2) 當(dāng)?shù)交緣K出口時(shí)，將變量的值存放在內(nèi)存中，因?yàn)橐粋€(gè)基本塊可能有多個(gè)后繼結(jié)點(diǎn)或多個(gè)前驅(qū)結(jié)點(diǎn)，同一個(gè)變量名在不同前驅(qū)結(jié)點(diǎn)的基本塊內(nèi)出口前存放的寄存器可能不同，或沒有定值，所以應(yīng)在出口前把寄存器的內(nèi)容放在內(nèi)存中，這樣從基本塊外入口的變量值都在內(nèi)存中。(3) 對(duì)于在一個(gè)基

9、本塊內(nèi)后邊不再被引用的變量所占用的寄存器應(yīng)盡早釋放，以提高寄存器的利用效率。簡(jiǎn)述編譯程序的工作過(guò)程。答：編譯程序的工作過(guò)程，是指從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過(guò)程，是非常復(fù)雜的，就其過(guò)程而言，一般可以劃分為五個(gè)工作階段：詞法分析，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的單詞；語(yǔ)法分析，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類語(yǔ)法單位；語(yǔ)義分析與中間代碼產(chǎn)生，即對(duì)各類語(yǔ)法單位，分析其漢一并進(jìn)行初步翻譯；代碼優(yōu)化，以期產(chǎn)生更高效的代碼；目標(biāo)代碼生成，把中間代碼變換成特定機(jī)器上的低級(jí)語(yǔ)言指令形式。簡(jiǎn)述代碼優(yōu)化的目的和意義。答：代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對(duì)

10、程序代碼進(jìn)行一種等價(jià)變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短，同時(shí)所占用的存儲(chǔ)空間少。簡(jiǎn)述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號(hào)；或者說(shuō)從語(yǔ)法樹的末端開始，步步向上“歸約”，直到根節(jié)點(diǎn)。決定目標(biāo)代碼的因素有哪些？答案：決定目標(biāo)代碼的因素主要取決于具體的機(jī)器結(jié)構(gòu)、指令格式、字長(zhǎng)及寄存器的個(gè)數(shù)和種類，并與指令的語(yǔ)義和所用操作系統(tǒng)、存儲(chǔ)管理等都密切相關(guān)。又由于目標(biāo)代碼的執(zhí)行效率在很大程度上依賴于寄存器的使用，所以目標(biāo)代碼與寄存器的分配算法也有關(guān)。什么是句柄？什么是素短語(yǔ)？一個(gè)句型的最左直接短語(yǔ)稱為該

11、句型的句柄。（3分）素短語(yǔ)是這樣的一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符并且不包含更小的素短語(yǔ)。（3分）什么是語(yǔ)法制導(dǎo)翻譯？中間代碼通常有哪幾種主要形式？答案：由一個(gè)源語(yǔ)言、一個(gè)目標(biāo)語(yǔ)言和一組翻譯規(guī)則組成，遮住規(guī)則可將任何源語(yǔ)言符號(hào)串翻譯成對(duì)應(yīng)的目標(biāo)語(yǔ)言。主要形式: 三元式、 四元式 、逆波蘭式為什么在代碼生成時(shí)要考慮充分利用寄存器？答案：因?yàn)楫?dāng)變量值存在寄存器時(shí)，引用的變量值可直接從寄存器中取，減少對(duì)內(nèi)存的存取次數(shù)，這樣便可提高運(yùn)行速度。因此如何充分利用寄存器是提高目標(biāo)代碼運(yùn)行效率的重要途徑。一個(gè)典型的編譯程序通常由哪些部分組成？各部分的主要功能是什么？答案：一個(gè)典型的編譯程序通常包含 8 個(gè)組成部分，它們是詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和錯(cuò)誤處理程序。語(yǔ)法分析的主要任務(wù)是什么？常分為哪二類方法？答案：任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語(yǔ)法短語(yǔ) .常分為：自頂而下，自底而上二類方法。運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)建立一張嵌套層次顯示表diapla