一. 選擇題(2分*10=20分)
注意：請將選擇題答案填寫到以下選擇題答題卡中
題號 1 2 3 4 5 6 7 8 9 10
答案 D B D C D B C A C C

編譯程序絕大多數時間花在____D_____上 。
A. 詞法分析 B. 語法分析
C. 語義分析 D. 表格管理

匯編程序是將_____ B__ 翻譯成__;編譯程序是將________翻譯成________。
①高級語言 ②匯編語言 ③機器語言 ④高級語言或匯編語言
⑤匯編語言或機器語言
A．①③①⑤ B. ②③①⑤ C. ④③①③ D. ②③①③

給定文法G[A]：
A→bA|cc
下面____D_____是該文法的句子。
A.bcbc B.bcbcc
C.bccbcc D.bbbcc

已知語言{anbnci | n>=1,i>=0 }，則下述文法中，___C___可以產生該語言。
A. S→AB, A→aAb|ab, B→cB|c B. S→aAb, A→aBb, B→cB|c
C.S→AB, A→aAb|ab, B→cB|ε D. S→aSb|A, A→bAc|c

在通常的語法分析方法中，___D____特別適用于表達式的分析。
A．LR(1)分析法 B. LL(1)分析法
C. 遞歸下降分析法 D. 算符優先分析法

在DFA的最小化過程中，初始應該把集合根據_____ B ____劃分子集。
A. 初態和非初態 B. 終態和非終態
C. 是否含有ε出邊 D. 是否有出邊

基本塊內的優化為___C____
A．代碼外提，刪除歸納變量 B.強度削弱，代碼外提
C. 刪除多余運算，刪除無用賦值 D. 循環展開，循環合并

若文法G定義的語言是無限集，則文法必然是____A_____。
A. 遞歸的 B. 二義性的
C. 前后文無關的 D. 無二義性的

下列_____C____優化方法不是針對循環優化進行的。
A. 強度削弱 B. 刪除歸納變量
C. 刪除公共子表達式 D. 代碼外提

錯誤的局部化是指_____C_____。
A. 把錯誤理解成局部的錯誤
B. 對錯誤在局部范圍內進行糾正
C. 當發現錯誤時，跳過錯誤所在的語法單位繼續分析下去
D. 當發現錯誤時立即停止編譯，待用戶改正錯誤后再繼續編譯
二．(7分)編譯程序的總體結構、階段劃分、掃描遍的設計對人們進行一個軟件系統的設計有什么啟發？
答：復雜軟件系統可以通過分解為不同的階段，每個階段完成一個相對比較簡單的功能；能將計算學科一系列方法應用到目標實現當中，自動計算、自動實現也會成為可能。

三．(7分)請簡單描述LR分析的優缺點。
優點：比遞歸下降、LL（1）、算符優先分析法的限制少，大多數用無二義的上下文無關文法描述的語言都可以用LR分析器予以識別，速度快，能準確及時地指出輸入串的任何語法錯誤及出錯位置
缺點：若用手工構造分析器工作量大
四．(10分)編譯器的工作過程和遍。
1． 一個編譯過程可分為一遍、兩遍或多遍完成。請簡要的描述多遍完成的編譯程序的優點，缺點。
2． 描述一般的編譯程序可分為哪些階段，每個階段的目的是什么？不同階段是如何連接在一起的？每個階段的輸入和輸出分別是什么？
1．優點：更好的代碼生成、更優的代碼、更高效的代碼、支持更多的源語言可能性（某些語言需要多遍生成，如包含function聲明的語言，而function的定義在聲明之后）等
缺點：更長的編譯時間、更多的內存需求等
2．

詞法分析：輸入-語言的源程序，輸出-單詞序列
語法分析：輸入-單詞序列，輸出-抽象語法樹
語義分析：輸入-抽象語法樹，輸出-抽象語法樹
中間代碼生成：輸入-抽象語法樹，輸出-中間代碼
優化：輸入-中間代碼，輸出-優化后的中間代碼
目標代碼生成：輸入-中間代碼，輸出-目標代碼（可能是匯編語言）
五．(10分)正規語言和自動機理論
考慮語言L={w | w∈(0,1)+, 并且w中包含兩個連續的0，即"00"，而且w以"1"結尾}。
1． 請寫出該語言L的正規式。
2． 請根據你寫出的正規式，畫出與之相對應的NFA。
1．(0|1)* 00 (0|1)* 1
2.

六．(10分)形式語言分類
請判斷下列產生式集所對應的文法屬于0-3型文法的那一類，請說明理由。
1． S→aSBC 2. S→ACaB 3. S→Ac 4. S→aS
S→aBC Ca→aaC S→Sc S→aA
CB→DB CB→DB A→ab A→bA
DB→DC CB→E A→aAb A→bB
DC→BC aD→Da B→cB
aB→ab AD→AC B→c
bB→bb aE→Ea
bC→bc AE→ε
cC→cc
1．1型文法
2．0型文法
3．2型文法
4．3型文法

七．(12分)設文法G[S] 的產生式集如下：
S→aAa | bAb | e | c | t
A→SS
(1)試給出句子a c b e t b a的最右推導過程以及語法樹;
(2)指出此句型的所有短語、直接短語、句柄和素短語和最左素短語。

(1)

S=>aAa=>aSSa=>aSbAba=>aSbSSba=>aSbStba=>aSbetba=>acbetba

(2)
短語: e c t et betb cbetb acbetba
直接短語: e c t
句柄: c
素短語: c e t
最左素短語: c

八． （14分）設語言L是由奇數個m和偶數（可以是0）個t組成的符號串之集。
(1) 構造識別L的最簡DFA；(2) 給出定義L的正規文法。

1. 見圖：

2.

S→mB|tC
D→mC|tB
B→mS|tD|ε
C→mD|tS
九．（10分）對于基本塊P：
T0=3.14
T1=2T0
T2=R+r
A=T1T2
B=A
T3=2T0
T4=Rr
T5=T3T4
T6=R-r
B=T5T6
（1）用DAG圖對基本塊P進行優化；
（2）假定出基本塊后只有A、B是活躍的，寫出優化后的四元式序列。

(1)

(2) T2=R+r
A=6.28T2
T4=Rr
T5=6.28T4
T6=R-r
B=T5T

總結

以上是生活随笔為你收集整理的编译原理练习题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。