北方工業(yè)大學(xué)編譯原理第1、2章習(xí)題.pdf

考核辦法考核辦法 平時作業(yè)完成情況占平時作業(yè)完成情況占 10 實驗作業(yè)完成情況占實驗作業(yè)完成情況占 20 期末考試成績期末考試成績占占 70 教材教材 陳火旺等 陳火旺等 程序設(shè)計語言編譯原理程序設(shè)計語言編譯原理 國防國防 工業(yè)工業(yè)出版社出版社 第一章 第二章習(xí)題第一章 第二章習(xí)題 第一章第一章 引論引論 作業(yè) 作業(yè) 1 1 1 2 1 1 請給出編譯程序的總體結(jié)構(gòu)圖 并簡述請給出編譯程序的總體結(jié)構(gòu)圖 并簡述各個部分各個部分 的主要功能的主要功能 解 解 詞法分析器 詞法分析器 輸入源程序 識別出單詞符號 把需要存放的單詞輸入源程序 識別出單詞符號 把需要存放的單詞 放到符號表中 如變量名等 放到符號表中 如變量名等 語法分析器 語法分析器 在詞法分析的基礎(chǔ)上 根據(jù)語言的語法規(guī)則的要求把單在詞法分析的基礎(chǔ)上 根據(jù)語言的語法規(guī)則的要求把單 詞符號串組合成各類語法單位 詞符號串組合成各類語法單位 語義分析與中間代碼產(chǎn)生器 語義分析與中間代碼產(chǎn)生器 對每種語法范疇對每種語法范疇進行語義分析 將語法進行語義分析 將語法 分析器得到的語法單位根據(jù)分析器得到的語法單位根據(jù)語義語義規(guī)則翻譯成中間代碼 規(guī)則翻譯成中間代碼 優(yōu)化器 優(yōu)化器 對前階段產(chǎn)生的中間代碼對前階段產(chǎn)生的中間代碼進行優(yōu)化處理 以產(chǎn)生更為進行優(yōu)化處理 以產(chǎn)生更為高效的高效的 目標(biāo)代碼目標(biāo)代碼 目標(biāo)代碼生成器 目標(biāo)代碼生成器 把把中間代碼翻譯成目標(biāo)程序 中間代碼翻譯成目標(biāo)程序 表格管理程序 表格管理程序 負(fù)責(zé)建立 填寫和查找等一系列表格工作 表格的作負(fù)責(zé)建立 填寫和查找等一系列表格工作 表格的作 用是記錄源程序的各類信息和編譯各階段的進展情況 編譯的每個階用是記錄源程序的各類信息和編譯各階段的進展情況 編譯的每個階 段所需信息多數(shù)都從表格中讀取 產(chǎn)生的中間結(jié)果都記錄在相應(yīng)的表段所需信息多數(shù)都從表格中讀取 產(chǎn)生的中間結(jié)果都記錄在相應(yīng)的表 格中 格中 錯誤處理程序 錯誤處理程序 處理和校正源程序中存在的詞法 語法和語義錯誤 處理和校正源程序中存在的詞法 語法和語義錯誤 當(dāng)編譯程序發(fā)現(xiàn)源程序中的錯誤時 錯誤處理程序負(fù)責(zé)報告出錯的位當(dāng)編譯程序發(fā)現(xiàn)源程序中的錯誤時 錯誤處理程序負(fù)責(zé)報告出錯的位 置和錯誤性質(zhì)等信息 同時對發(fā)現(xiàn)的錯誤進行適當(dāng)?shù)男Ｕ?修復(fù) 置和錯誤性質(zhì)等信息 同時對發(fā)現(xiàn)的錯誤進行適當(dāng)?shù)男Ｕ?修復(fù) 目的是使編譯程序能夠繼續(xù)向下進行分析和處理 目的是使編譯程序能夠繼續(xù)向下進行分析和處理 1 2 何謂源程序 目標(biāo)程序 翻譯程序 何謂源程序 目標(biāo)程序 翻譯程序 編譯程序編譯程序和解釋程序和解釋程序 它們它們之間可能有何種關(guān)系之間可能有何種關(guān)系 解 解 源程序 源程序 是是指以某種程序設(shè)計語言所編寫的程序指以某種程序設(shè)計語言所編寫的程序 目標(biāo)程序 目標(biāo)程序 目標(biāo)語言書寫的程序稱為目標(biāo)程序 目標(biāo)語言書寫的程序稱為目標(biāo)程序 翻譯程序 翻譯程序 是將源程序轉(zhuǎn)換為與其等價的目標(biāo)程序 是將源程序轉(zhuǎn)換為與其等價的目標(biāo)程序 編譯程序與解釋編譯程序與解釋 程序均為翻譯程序 但二者工作方法不同 程序均為翻譯程序 但二者工作方法不同 編譯程序 編譯程序 源語言為高級語言 源語言為高級語言 目標(biāo)程序為目標(biāo)程序為匯編語言或匯編語言或機器語言程序 機器語言程序 解釋程序 解釋程序 源語言程序作為輸入 但不產(chǎn)生目標(biāo)程序 而是邊解釋邊源語言程序作為輸入 但不產(chǎn)生目標(biāo)程序 而是邊解釋邊 執(zhí)行源程序本身執(zhí)行源程序本身 編譯程序與解釋程序最主要的區(qū)別是 編譯程序與解釋程序最主要的區(qū)別是 是否生成目標(biāo)程序 是否生成目標(biāo)程序 廣義上講 廣義上講 編譯程序和解釋程序都屬于翻譯程序 但它們的翻譯方式不同 解釋編譯程序和解釋程序都屬于翻譯程序 但它們的翻譯方式不同 解釋 程序是邊翻譯 解釋 邊執(zhí)行 不產(chǎn)生目標(biāo)代碼 輸出源程序的運行程序是邊翻譯 解釋 邊執(zhí)行 不產(chǎn)生目標(biāo)代碼 輸出源程序的運行 結(jié)果 而編譯程序只負(fù)責(zé)把源程序翻譯成目標(biāo)程序 輸出與源程序等結(jié)果 而編譯程序只負(fù)責(zé)把源程序翻譯成目標(biāo)程序 輸出與源程序等 價的目標(biāo)程序 而目標(biāo)程序的執(zhí)行任務(wù)由操作系統(tǒng)來完成 即只翻譯價的目標(biāo)程序 而目標(biāo)程序的執(zhí)行任務(wù)由操作系統(tǒng)來完成 即只翻譯 不執(zhí)行 不執(zhí)行 作業(yè) 作業(yè) 2 1 2 6 2 7 2 8 2 9 第二章第二章 高級語言及其語法描述高級語言及其語法描述 2 1 設(shè)有文法設(shè)有文法G A A bA cc 判斷符號串判斷符號串bbc bbbcc bbA bbAc是否是是否是G A 的句型或的句型或 句子 句子 解 解 由于由于A bA bbA bbbA bbbcc 所以所以 bbA是是G A 的的句型 句型 bbbcc是是G A 的的句子 句子 而而 bbAc和和bbc不能由文法不能由文法 G A 的開始符號推導(dǎo)出來的開始符號推導(dǎo)出來 所以 所以 bbAc不是不是G A 的的句型 句型 bbc不是不是G A 的句子 的句子 2 6 令文法令文法G6為為 N D ND D 0 1 2 3 4 5 6 7 8 9 解 解 1 G6的語言的語言L G6 是什么 是什么 L G6 為由為由0到到9這這10個數(shù)字組成個數(shù)字組成的的 長度 長度大于大于0的的字符串 字符串 或者 或者 可以以可以以0開頭的開頭的 非負(fù)整數(shù)集合非負(fù)整數(shù)集合 2 給出句子 給出句子0127 34和和568的最左推導(dǎo)和最右推導(dǎo) 的最左推導(dǎo)和最右推導(dǎo) 0127的最左推導(dǎo) 的最左推導(dǎo) N ND NDD NDDD DDDD 0DDD 01DD 012D 0127 最右推導(dǎo) 最右推導(dǎo) N ND N7 ND7 N27 ND27 N127 D127 0127 34的最左推的最左推導(dǎo)導(dǎo) N ND DD 3D 34 最右推最右推導(dǎo)導(dǎo) N ND N4 D4 34 568的最左推的最左推導(dǎo)導(dǎo) N ND NDD DDD 5DD 56D 568 最右推最右推導(dǎo)導(dǎo) N ND N8 ND8 N68 D68 568 解 解 1 不允許 不允許0 開頭的偶正整數(shù)集合的文法開頭的偶正整數(shù)集合的文法 E NT D T FT G N D 1 3 5 7 9 D 2 4 6 8 F N 0 G D 0 2 允許 允許0 開頭的偶正整數(shù)集合的文法開頭的偶正整數(shù)集合的文法 E NT D T NT D N D 1 3 5 7 9 D 0 2 4 6 8 2 7 寫一個文法 使其語言是偶正整數(shù)的集合 要求 寫一個文法 使其語言是偶正整數(shù)的集合 要求 1 不允許 不允許0 打頭 打頭 2 允許 允許0 打頭 打頭 2 8 令文法為令文法為 E T E T E T T F T F T F F E i 1 給出 給出i i i i i i 的最左推導(dǎo)和最右推導(dǎo)的最左推導(dǎo)和最右推導(dǎo) 解 解 i i i最左推導(dǎo) 最左推導(dǎo) E E T T T F T i T i T F i F F i i F i i i 最右推導(dǎo) 最右推導(dǎo) E E T E T F E T i E F i E i i T i i F i i i i i i i i 最左推導(dǎo) 最左推導(dǎo) E T T F F F i F i E i E T i T T i F T i i T i i F i i i 最右推導(dǎo) 最右推導(dǎo) E T T F T E T E T T E F T E i T T i T F i T i i F i i i i i 2 給出 給出i i i i i i和和i i i的語法樹 的語法樹 解 解 E E T ET F T i F i Fi E T ET F T i F i F i E E T ET F T i F i Fi i i i語法樹語法樹i i i語法樹語法樹i i i語法樹語法樹 2 9 證明下面的文法證明下面的文法G S 是二義的 是二義的 S Ac aB A ab B bc 證明證明 二義性定義二義性定義 如果一個文法存在某個句子 如果一個文法存在某個句子對應(yīng)兩棵對應(yīng)兩棵 不同的