編譯原理試題及答案

1、.裝訂線 一、單項(xiàng)選擇題(共10小題，每小題2分，共20分)1語言是 AA句子的集合 B產(chǎn)生式的集合 C符號串的集合 D句型的集合2編譯程序前三個階段完成的工作是 CA詞法分析、語法分析和代碼優(yōu)化 B代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語法分析、語義分析和中間代碼生成 D詞法分析、語法分析和代碼優(yōu)化3一個句型中稱為句柄的是該句型的最左 D A非終結(jié)符號 B短語 C句子 D直接短語4下推自動機(jī)識別的語言是 CA0型語言 B1型語言 C2型語言 D3型語言5掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有獨(dú)立含義的最小語法單位即 B A 字符 B單詞 C句子 D句型6對應(yīng)Chomsk

2、y四種文法的四種語言之間的關(guān)系是 B AL0ÌL1ÌL2ÌL3 BL3ÌL2ÌL1ÌL0 CL3=L2ÌL1ÌL0 DL0ÌL1ÌL2=L37詞法分析的任務(wù)是 A A識別單詞 B分析句子的含義 C識別句子 D生成目標(biāo)代碼8常用的中間代碼形式不含 D A三元式 B四元式 C逆波蘭式 D語法樹9 代碼優(yōu)化的目的是 C A節(jié)省時間 B節(jié)省空間 C節(jié)省時間和空間 D把編譯程序進(jìn)行等價交換10代碼生成階段的主要任務(wù)是 C A把高級語言翻譯成匯編語言 B把高級語言翻譯成機(jī)器語言 C把中間代碼變換成依賴具體機(jī)

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

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

5、作時向前看一個輸入符號。除了沒有公共左因子外，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)每個節(jié)點(diǎn)的標(biāo)記都是V中的一個符號。(3)若一棵子樹的根節(jié)點(diǎn)為A，且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳1A2AR，那么A®A1A2AR一定是P中的一條產(chǎn)生式。(4)若一標(biāo)記為A的節(jié)點(diǎn)至少有一個除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則

6、w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。4LR(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)生式的

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

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

9、TRAN語言就是編譯型高級語言。2編譯程序的工作分為那幾個階段? 詞法分析、語法分析和語義分析是對源程序進(jìn)行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進(jìn)行綜合(稱為編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價的目標(biāo)程序。3簡述自下而上的分析方法。 所謂自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點(diǎn)。4簡述代碼優(yōu)化的目的和意義。 代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進(jìn)行一種等價變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)

10、程序運(yùn)行時所需要的時間短，同時所占用的存儲空間少。五、綜合應(yīng)用題(共3小題，每小題10分，共30分)1證明下述文法G：S®aSbS|aS|d是二義性文法。解：一個文法，如果存在某個句子有不只一棵語法分析樹與之對應(yīng)，那么稱這個文法是二義性文法。句子aadbd有兩棵語法樹。如下圖：SaSSabSdddSSabSSad(1) (2)由此可知，S®aSbS|aS|d定義的文法是二義性文法。2對于文法GS：S®AB，A®Aa|bB，B®a|Sb求句型baSb的全部短語、直接短語和句柄？句型baSb的語法樹如圖五(2)所示。ASBbBSab圖五(2) 句型baSb的的語法樹解：baSb為句型baSb的相對于S的短語，ba為句型baSb的相對于A的短語，Sb為句型baSb的相對于B的短語，且為直接短語，a為句型baSb的