千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦編譯原理試題答案編譯原理期末測試題

專業班級：_________學號：_________姓名：__________總分

一、單項挑選題(共10小題，每小題2分)（題分20分）

1．語言是

A．句子的集合

B．產生式的集合

C．符號串的集合

D．句型的集合2．編譯程序前三個階段完成的工作是A．詞法分析、語法分析和代碼優化B．代碼生成、代碼優化和詞法分析

C．詞法分析、語法分析、語義分析和中間代碼生成

D．詞法分析、語法分析和代碼優化

3．一個句型中稱為句柄的是該句型的最左

A．非終結符號

B．短語

C．句子

D．直接短語4．下推自動機識別的語言是

A．0型語言

B．1型語言

C．2型語言

D．3型語言

5．掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有自立含義的最小語法單位即

A．字符

B．單詞

C．句子

D．句型6．對應Chomsky四種文法的四種語言之間的關系是A．L0?L1?L2?L3B．L3?L2?L1?L0C．L3=L2?L1?L0D．L0?L1?L2=L37．詞法分析的任務是

A．識別單詞

B．分析句子的含義

C．識別句子

D．生成目標代碼8．常用的中間代碼形式不含

A．三元式

B．四元式

C．逆波蘭式

D．語法樹

9．代碼優化的目的是

A．節約時光

B．節約空間

C．節約時光和空間

D．把編譯程序舉行等價交換10．代碼生成階段的主要任務是A．把高級語言翻譯成匯編語言

裝訂線

得分

B．把高級語言翻譯成機器語言

C．把中間代碼變換成依靠詳細機器的目標代碼

D．把匯編語言翻譯成機器語言

二、填空題（本大題共5小題，每小題2分）（題分10分）

1．編譯程序首先要識別出源程序中每個()，然后再分析每個()并翻譯其意義。

2．編譯器常用的語法分析辦法有()和()兩種。3．通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的()，中間代碼生成、代碼優化與目標代碼的生成則是對源程序的()。4．程序設計語言的進展帶來了日漸多變的運行時存儲管理計劃，主要分為兩大類，即：()計劃和()計劃。

5．對編譯程序而言，輸入數據是()，輸出結果是()。

三、名詞解釋題(共5小題，每小題4分)（題分20分）1．詞法分析2．LL(1)文法3．語法樹

4．LR(0)分析器5．語言和文法

四、簡答題(共4小題，每小題5分)（題分20分）

1．編譯程序和高級語言有什么區分?2．編譯程序的工作分為那幾個階段?3．簡述自下而上的分析辦法。4．簡述代碼優化的目的和意義。

五、綜合應用題(共3小題，每小題10分)（題分30分）

1．證實下述文法G：

S→aSbS|aS|d

是二義性文法。

2．對于文法G[S]：S→AB，A→Aa|bB，B→a|Sb求句型baSb的所有短語、直接短語

得分

得分

得分

得分

和句柄？

句型baSb的語法樹如圖五(2)所示。

圖五(2)句型baSb的的語法樹

3．設有非確定的有自限動機NFAM=({A，B，C}，{0，1}，δ，{A}，{C})，其中：δ(A，0)={C}δ(A，1)={A，B}δ(B，1)={C}δ(C，1)={C}。請畫出狀態轉換距陣和狀態轉換圖。

參考答案

一、單項挑選題(共10小題，每小題2分，共20分)

ASB

bB

Sa

b

1．語言是

A．句子的集合B．產生式的集合

C．符號串的集合D．句型的集合

2．編譯程序前三個階段完成的工作是

A．詞法分析、語法分析和代碼優化

B．代碼生成、代碼優化和詞法分析

C．詞法分析、語法分析、語義分析和中間代碼生成

D．詞法分析、語法分析和代碼優化

3．一個句型中稱為句柄的是該句型的最左

A．非終結符號B．短語C．句子D．直接短語

4．下推自動機識別的語言是

A．0型語言B．1型語言

C．2型語言D．3型語言

5．掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有自立含義的最小語法單位即

A．字符B．單詞C．句子D．句型

6．對應Chomsky四種文法的四種語言之間的關系是

A．L0?L1?L2?L3B．L3?L2?L1?L0

C．L3=L2?L1?L0D．L0?L1?L2=L3

7．詞法分析的任務是

A．識別單詞B．分析句子的含義

C．識別句子D．生成目標代碼

8．常用的中間代碼形式不含

A．三元式B．四元式C．逆波蘭式D．語法樹

9．代碼優化的目的是

A．節約時光B．節約空間

C．節約時光和空間D．把編譯程序舉行等價交換

10．代碼生成階段的主要任務是

A．把高級語言翻譯成匯編語言

B．把高級語言翻譯成機器語言

C．把中間代碼變換成依靠詳細機器的目標代碼

D．把匯編語言翻譯成機器語言

二、填空題（本大題共5小題，每小題2分，共10分）

1．編譯程序首先要識別出源程序中每個(單詞)，然后再分析每個(句子)并翻譯其意義。

2．編譯器常用的語法分析辦法有(自底向上)和(自頂向下)兩種。

3．通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的(分析)，中間代碼生成、代碼優化與目標代碼的生成則是對源程序的(綜合)。4．程序設計語言的進展帶來了日漸多變的運行時存儲管理計劃，主要分為兩大類，即(靜態存儲分配)計劃和(動態存儲分配)計劃。

5．對編譯程序而言，輸入數據是(源程序)，輸出結果是(目標程序)。

三、名詞解釋題(共5小題，每小題4分，共20分)

1．詞法分析

詞法分析的主要任務是從左向右掃描每行源程序的符號，根據詞規矩則

從構成源程序的字符串中識別出一個個具有自立意義的最小語法單位，

并轉換成統一的內部表示(token)，送給語法分析程序。

2．LL(1)文法

若文法的任何兩個產生式A→α|β都滿足下面兩個條件：

（1）FIRST(α)?FIRST(β)=φ；

（2）若β?*ε，那么FIRST(α)?FOLLOW(A)=φ。

我們把滿足這兩個條件的文法叫做LL(1)文法，其中的第一個L代表從左

向右掃描輸入，其次個L表示產生最左推導，1代表在打算分析器的每步

動作時向前看一個輸入符號。除了沒有公共左因子外，LL(1)文法還有一

些顯然的性質，它不是二義的，也不含左遞歸。

3．語法樹

句子的樹結構表示法稱為語法樹(語法分析樹或語法推導樹)。

給定文法G=(VN，VT，P，S)，對于G的任何句型都能構造與之關聯的

語法樹。這棵樹具有下列特征：

(1)根節點的標記是開頭符號S。

(2)每個節點的標記都是V中的一個符號。

(3)若一棵子樹的根節點為A，且其全部直接子孫的標記從左向右的羅列

次序為A1A2…AR，那么A→A1A2…AR一定是P中的一條產生式。

(4)若一標記為A的節點至少有一個除它以外的子孫，則A∈VN。

(5)若樹的全部葉節點上的標記從左到右羅列為字符串w，則w是文法G

的句型；若w中僅含終結符號，則w為文法G所產生的句子。

4．LR(0)分析器

所謂LR(0)分析，是指從左至右掃描和自底向上的語法分析，且在分析的

每一步，只須按照分析棧當前已移進和歸約出的所有文法符號，并至多再

向前查看0個輸入符號，就能確定相對于某一產生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應實行的分析動作(是移進還是按某一產生式舉行歸約等)。

5．語言和文法

文法就是語言結構的定義和描述，是有窮非空的產生式集合。文法G定義為四元組的形式：

G=(VN，VT，P，S)

其中：VN是非空有窮集合，稱為非終結符號集合；VT是非空有窮集合，稱為終結符號集合；P是產生式的集合(非空)；S是開頭符號(或識別符號)。這里，VN∩VT=?，S∈VN。V=VN∪VT，稱為文法G的字母表，它是浮現

文法產生式中的一切符號的集合。

文法G所描述的語言用L(G)表示，它由文法G所產生的所有句子組成，即

L(G)={x|S?*x，其中S為文法開頭符號，且+

∈TVx}

容易的說，文法描述的語言是該文法一切句子的集合。

四、簡答題(共4小題，每小題5分，共20分)

1．編譯程序和高級語言有什么區分?

用匯編語言或高級語言編寫的程序，必需先送入計算機，經過轉換成用機器語言表示的目標程序（這個過程即編譯），才干由計算機執行。執行轉換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉換過的叫目標程序，也就是機器語言。

編譯程序的工作狀況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，根據一一對應的關系，轉換成用機器語言表示的程序。解釋型編譯程序將高級語言程序的一個語句，先解釋成為一組機器語言的指令，然后立刻執行，執行完了，取下一組語句解釋和執行，如此繼續到完成一個程序止。用解釋型編譯程序，執行速度很慢，但可以舉行人和計算機的"對話"，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序將級語言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程舉行很快，在過程中，不能舉行人機對話修改。FORTRAN語言就是編譯型高級語言。2．編譯程序的工作分為那幾個階段?

詞法分析、語法分析和語義分析是對源程序舉行的分析(稱為編譯程序的前端)，而中間代碼生成、代碼優化和代碼生成三個階段合稱為對源程序舉行綜合(稱為

編譯程序的后端)，它們從源程序的中間表示建立起和源程序等價的目標程序。

3．簡述自下而上的分析辦法。

所謂自下而上分析法就是從輸入串開頭，逐步舉行“歸約”，直至歸約到文法的

開頭符號；或者說從語法樹的末端開頭，步步向上“歸約”，直到根節點。

4．簡述代碼優化的目的和意義。

代碼優化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼舉行

一種等價變換，在保證變換前后代碼執行結果相同的前提下，盡量使目

標程序運行時所需要的時光短，同時所占用的存儲空間少。

五、綜合應用題(共3小題，每小題10分，共30分)

1．證實下述文法G：

S→aSbS|aS|d

是二義性文法。

解：

一個文法，假如存在某個句子有不只一棵語法分析樹與之對應，那么稱這個

文法是二義性文法。

句子aadbd有兩棵語法樹。如下圖：

(1)(2)

由此可知，S→aSbS|aS|d定義的文法是二義性文法。

2．對于文法G[S]：S→AB，A→Aa|bB，B→a|Sb求句型baSb的所有短語、直接短語和句柄？

句型baSb的語