2008計算機函授本科編譯原理期末試卷(a)答案及評分標準
一、填空題(20分,每空2分)
1、 傳值;傳位址
2、 從左向右分析;最右推導的逆過程;向右檢視k個輸入符
3、 二義性的
4、 最左素短語
5、 200
6、 aab*d-abd*-*d/-
7、 詞法分析器
二、選擇題(20分,每個選項2分)
1、d 2、b 3、d 4、b 5、c 6、c 7、c 8、d 9、d 10、a
三、簡答題(10分)
1、 因為存在推導序列: e e+t e + * f 所以 e+t*f是文法g[e]的乙個句型(2分)
句型 e+t*f的
短語有:e+t*f,t*f (2分)
直接短語有:t*f (1分)
控制代碼為:t*f(1分)
2、最左推導
n=>nd=>ndd=>nddd=>dddd=>0ddd=>06dd=>062d=>0625 (2分)
最右推導
n=>nd=>n5=>nd5=>n25=>nd25=>n625=>d625=>0625 (2分)
四、綜合應用題(50分)
1、解:對應的nfa(6分),確定化後的dfa(9分)如圖所示
2、 (1) 將a->sb代入s的產生式,得:
s->sba | b
消除左遞迴,改寫為文法g1:
s->bs'
s』->bas』 |ε
b->ab(4分)
(2)在g1中,有兩個關於s』的產生式,它們不含左公共因子,相應的select集分別如下:select(s』->bas』)=firset(bas』)=
select(s』->ε)=follow(s』)=
select(s』->bas』) 與select(s』->ε)的交集為空集,所以g1是ll(1)文法 (5分)
(3)(4分)
3、%digit [0-92分)
number 350-\n (3分)
%% (1分)
.*\n (1分)
%%main()
{yylex();
return 02分)
int yywrap()
{ return 11分)
4、 編譯程式把乙個源程式翻譯成目標程式的工作過程分為五個階段:詞法分析;語法分析;中間**生成;**優化;目標**生成。主要是進行詞法分析和語法分析,又稱為源程式分析,分析過程中發現有語法錯誤,給出提示資訊。
(1) 詞法分析
詞法分析的任務是對由字元組成的單詞進行處理,從左至右逐個字元地對源程式進行掃瞄,產生乙個個的單詞符號,把作為字串的源程式改造成為單詞符號串的中間程式。執行詞法分析的程式稱為詞法分析程式或掃瞄器。
源程式中的單詞符號經掃瞄器分析,一般產生二元式:單詞種別;單詞自身的值。單詞種別通常用整數編碼,如果乙個種別只含乙個單詞符號,那麼對這個單詞符號,種別編碼就完全代表它自身的值了。
若乙個種別含有許多個單詞符號,那麼,對於它的每個單詞符號,除了給出種別編碼以外,還應給出自身的值。
詞法分析器一般來說有兩種方法構造:手工構造和自動生成。手工構造可使用狀態圖進行工作,自動生成使用確定的有限自動機來實現。
(2) 語法分析
編譯程式的語法分析器以單詞符號作為輸入,分析單詞符號串是否形成符合語法規則的語法單位,如表示式、賦值、迴圈等,最後看是否構成乙個符合要求的程式,按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構,程式是最終的乙個語法單位。編譯程式的語法規則可用上下文無關文法來刻畫。
語法分析的方法分為兩種:自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發,向下推導,推出句子。
而自下而上分析法採用的是移進歸約法,基本思想是:用乙個寄存符號的先進後出棧,把輸入符號乙個乙個地移進棧裡,當棧頂形成某個產生式的乙個候選式時,即把棧頂的這一部分歸約成該產生式的左鄰符號。
(3) 中間**生成
中間**是源程式的一種內部表示,或稱中間語言。中間**的作用是可使編譯程式的結構在邏輯上更為簡單明確,特別是可使目標**的優化比較容易實現。中間**即為中間語言程式,中間語言的複雜性介於源程式語言和機器語言之間。
中間語言有多種形式,常見的有逆波蘭記號、四元式、三元式和樹。
(4) **優化
**優化是指對程式進行多種等價變換,使得從變換後的程式出發,能生成更有效的目標**。所謂等價,是指不改變程式的執行結果。所謂有效,主要指目標**執行時間較短,以及占用的儲存空間較小。
這種變換稱為優化。
有兩類優化:一類是對語法分析後的中間**進行優化,它不依賴於具體的計算機;另一類是在生成目標**時進行的,它在很大程度上依賴於具體的計算機。對於前一類優化,根據它所涉及的程式範圍可分為區域性優化、迴圈優化和全域性優化三個不同的級別。
(5) 目標**生成
目標**生成是編譯的最後乙個階段。目標**生成器把語法分析後或優化後的中間**變換成目標**。目標**有三種形式:
① 可以立即執行的機器語言**,所有位址都重定位;
② 待裝配的機器語言模組,當需要執行時,由連線裝入程式把它們和某些執行程式連線起來,轉換成能執行的機器語言**;
③ 組合語言**,須經過匯程式設計序彙編後,成為可執行的機器語言**。
目標**生成階段應考慮直接影響到目標**速度的三個問題:一是如何生成較短的目標**;二是如何充分利用計算機中的暫存器,減少目標**訪問儲存單元的次數;三是如何充分利用計算機指令系統的特點,以提高目標**的質量。
計算機原理1卷答案
一 單項選擇題 1 b 2 a 3 c 4 a 5 c 6 c 7 d 8 b 9 c 10 d 11 b 12 c 13 14 b 15 c 16 a 17 a 18 d 19 c 20 b 二填充題 21 基帶調製 22 x 23 資料通訊 24 資料鏈路層 25 客戶 伺服器 26 資訊交流資...
計算機原理答案
1.在8086cpu的9個標誌位中,有3位為控制標誌,它們是df,if 及 tf 2.主機與外設之間的資料傳送控制方式通常有三種,它們是程式控制方式,dma方式及 中斷 其中 dma方式的資料傳輸率最高。3.乙個中斷向量佔 4 個位元組。4.8259a設定為固定優先順序時,ir0優先順序 高 ir7...
電腦科學與技術專業編譯原理實踐
電腦科學與技術專業 編譯原理課程實踐 教學大綱 2011年 課時 12學時 一 課程設計的性質 目的和任務 編譯原理課程實踐 是 編譯原理 課程學習後的乙個綜合性實踐教學環節,主要培養學生綜合運用已學過的基本理論和原理去分析和解決實際問題的能力,對加深課程理論的理解和應用 增強學生的實踐動手能力和創...