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

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