編譯原理試題及答案

1、.裝訂線 一、單項選擇題(共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下推自動機識別的語言是 CA0型語言 B1型語言 C2型語言 D3型語言5掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即 B A 字符 B單詞 C句子 D句型6對應Chomsk

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

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

4、分，共20分)1詞法分析詞法分析的主要任務是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉(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)生最左推導，1代表在決定分析器的每步動

5、作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。3語法樹 句子的樹結(jié)構表示法稱為語法樹(語法分析樹或語法推導樹)。給定文法G=(VN，VT，P，S)，對于G的任何句型都能構造與之關聯(lián)的語法樹。這棵樹具有下列特征：(1)根節(jié)點的標記是開始符號S。(2)每個節(jié)點的標記都是V中的一個符號。(3)若一棵子樹的根節(jié)點為A，且其所有直接子孫的標記從左向右的排列次序為A1A2AR，那么A®A1A2AR一定是P中的一條產(chǎn)生式。(4)若一標記為A的節(jié)點至少有一個除它以外的子孫，則AVN。(5)若樹的所有葉節(jié)點上的標記從左到右排列為字符串w，則

6、w是文法G的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。4LR(0)分析器 所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作 (是移進還是按某一產(chǎn)生式進行歸約等)。5語言和文法文法就是語言結(jié)構的定義和描述，是有窮非空的產(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īng)過轉(zhuǎn)換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。

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

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

10、程序運行時所需要的時間短，同時所占用的存儲空間少。五、綜合應用題(共3小題，每小題10分，共30分)1證明下述文法G：S®aSbS|aS|d是二義性文法。解：一個文法，如果存在某個句子有不只一棵語法分析樹與之對應，那么稱這個文法是二義性文法。句子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的