《普通高等院校計(jì)算機(jī)專業(yè)(本科)實(shí)用教程系列:編譯原理實(shí)用教程(第2版)》共分7章,主要介紹編譯程序的基本原理和實(shí)現(xiàn)方法。內(nèi)容包括:詞法分析,形式語言和自動(dòng)機(jī)的基本概念,語法分析,符號(hào)表和靜態(tài)內(nèi)存分配,語法制導(dǎo)翻譯和中間代碼產(chǎn)生,目標(biāo)代碼生成。《普通高等院校計(jì)算機(jī)專業(yè)(本科)實(shí)用教程系列:編譯原理實(shí)用教程(第2版)》還介紹了作者本人的一些工作成果,如LR分析法在詞法分析器自動(dòng)構(gòu)造中的應(yīng)用,語法制導(dǎo)翻譯在匯編程序自動(dòng)構(gòu)造中的應(yīng)用。為了方便讀者學(xué)習(xí),各章都安排了一定數(shù)量的習(xí)題,并配有習(xí)題答案。
《普通高等院校計(jì)算機(jī)專業(yè)(本科)實(shí)用教程系列:編譯原理實(shí)用教程(第2版)》附錄B中的“課程實(shí)習(xí)指導(dǎo)”向讀者提供了一個(gè)較為完整的、切實(shí)可用的“編譯原理”課程實(shí)習(xí)方案,并附有參考程序,可供有關(guān)教師選用或參考。
《普通高等院校計(jì)算機(jī)專業(yè)(本科)實(shí)用教程系列:編譯原理實(shí)用教程(第2版)》可作為本科院校計(jì)算機(jī)專業(yè)“編譯原理”課程的教材,也可供有關(guān)教師、研究生以及從事計(jì)算機(jī)軟件設(shè)計(jì)和開發(fā)人員參考。
以編譯四個(gè)主要階段“詞法分析”,“語法分析”、“語義分析”和“目標(biāo)代碼生成”為線索,介紹各個(gè)階段常用的軟件技術(shù)和實(shí)現(xiàn)方法。各章安排了一定數(shù)量的習(xí)題,并附有習(xí)題答案。在《普通高等院校計(jì)算機(jī)專業(yè)(本科)實(shí)用教程系列:編譯原理實(shí)用教程(第2版)》中出現(xiàn)的源程序,除附錄B中兩個(gè)程序外,都可以從清華大學(xué)出版社主指定網(wǎng)站下載。另外,由本人編寫的“編譯原理”課程電子教案和試卷集錦可以從“中國高等學(xué)校教學(xué)資源網(wǎng)”下載。介紹了兩項(xiàng)新的編譯技術(shù)和方法,它們是“LR分析法在詞法分析器自動(dòng)構(gòu)造中的應(yīng)用”和“語法制導(dǎo)翻譯在匯編程序自動(dòng)構(gòu)造中的應(yīng)用”。附錄A介紹了用軟件實(shí)現(xiàn)的虛擬計(jì)算機(jī)和匯編程序使用方法。讀者可使用《普通高等院校計(jì)算機(jī)專業(yè)(本科)實(shí)用教程系列:編譯原理實(shí)用教程(第2版)》第7章介紹的匯編語言編寫程序,然后進(jìn)行詞法分析和LR分析法制導(dǎo)的語義翻譯,最終生成的目標(biāo)代碼可以在虛擬計(jì)算機(jī)上運(yùn)行。附錄B中的“課程實(shí)習(xí)指導(dǎo)”,向讀者提供了一個(gè)較為完整的,切實(shí)可用的“編譯原理”課程實(shí)習(xí)方案,并附有參考程序,可供有關(guān)教師選用或參考。
1982年2月本人畢業(yè)于上海交通大學(xué),2010年1月退休,在上海第二工業(yè)大學(xué)工作了近三十年。在此期間,主要從事“編譯程序”和“算法”這兩門學(xué)科的教學(xué)和科研。2005年4月清華大學(xué)出版社出版了由本人編著的《編譯原理實(shí)用教程》,該書至今仍用于我校和國內(nèi)其他普通高等院!熬幾g原理”課程的教學(xué)。該書從脫稿至今已近十年,先后共印刷了1萬冊(cè)左右。雖然印刷的數(shù)量不大,但是90%是外校師生所使用的,說明書的質(zhì)量得到了同行的認(rèn)可。
在第2版中,書的章節(jié)基本沒有變化,僅刪除了原書中的5.10.3小節(jié)(5.10.3 LR分析控制程序的修改),增加了6.11節(jié)(6.11 自上而下分析制導(dǎo)翻譯概述)。做出上述調(diào)整,主要考慮用于詞法分析的LR分析控制程序修改不大,一是增加了token數(shù)組,用于記錄構(gòu)成單詞的字符。在執(zhí)行移進(jìn)操作時(shí),除完成規(guī)定動(dòng)作外,還應(yīng)將當(dāng)前字符移入token數(shù)組;二是把“出錯(cuò)”理解為找到單詞尾。對(duì)于熟悉LR分析控制程序工作原理的讀者,在理解上不會(huì)有困難。在后繼章節(jié)中,對(duì)于用于詞法分析的LR分析控制程序有詳細(xì)介紹,沒有必要單獨(dú)列出。為了完整,在6.11節(jié)簡略討論了自上而下分析制導(dǎo)翻譯技術(shù)。原書中的附錄A和附錄B合并為新書的附錄A。原書的附錄C刪除,改為下載文件。原書的附錄D改為新書的附錄B.
在第2版中,各章節(jié)的知識(shí)點(diǎn)沒有變化,增加了算法偽代碼描述,對(duì)原書各章節(jié)中的所有源程序都做了比較大的修改。在原書中,算法除文字簡單描述外,基本用源程序表達(dá),這樣對(duì)算法的描述和理解有可能受到語言細(xì)節(jié)的束縛。在本書中,增加了算法偽代碼描述,這樣可避免語言的限制,更容易表達(dá)算法的基本思想?紤]有些讀者編程經(jīng)驗(yàn)不足,源程序仍保留了下來,但在編排上做了改進(jìn),使其更容易閱讀和理解。在本書中出現(xiàn)的源程序,除附錄B中兩個(gè)程序外,都可以從清華大學(xué)出版社指定網(wǎng)站下載。另外,由本人編寫的“編譯原理”課程電子教案和試卷集錦可以從“中國高等學(xué)校教學(xué)資源網(wǎng)”下載。
在寫第1版時(shí),主要考慮程序的正確性。在再版中,力求使程序?qū)懙酶啙、更易理解,并且注意前后統(tǒng)一。例如,本書介紹了三個(gè)詞法分析器,它們是Lex1、Lex2和 Lex3。三個(gè)詞法分析器都是由預(yù)處理程序和掃描器(單詞識(shí)別程序)兩個(gè)部分構(gòu)成。預(yù)處理程序是同一個(gè),差異在于如何實(shí)現(xiàn)掃描器。Lex1是利用狀態(tài)轉(zhuǎn)換圖來實(shí)現(xiàn)的,Lex2是利用確定有限自動(dòng)機(jī)來實(shí)現(xiàn)的,而Lex3是利用LR分析法來實(shí)現(xiàn)的。掃描器的程序結(jié)構(gòu)大同小異,讀者只需關(guān)注單詞識(shí)別時(shí)所使用的技術(shù)和方法。
借此機(jī)會(huì),向清華大學(xué)出版社表示感謝。是清華大學(xué)出版社向本人提供了機(jī)會(huì),使我能夠在退休之后,繼續(xù)為高等學(xué)校計(jì)算機(jī)教育盡自己微薄之力。繼2011年6月的“算法設(shè)計(jì)與分析”出版之后,這是本人主編的第2本教科書。
上海第二工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院教師王娜參與了本書各章的編寫(包括習(xí)題答案),上海第二工業(yè)大學(xué)成人與繼續(xù)教育學(xué)院教師楊坤參與了各章源程序的編寫。
溫敬和
2012年秋
第1章 編譯系統(tǒng)概述
習(xí)題
第2章 詞法分析
2.1 詞法分析器的設(shè)計(jì)考慮及手工構(gòu)造
2.1.1 單詞類型及二元式編碼
2.1.2 源程序的輸入及預(yù)處理
2.1.3 基本字的識(shí)別和超前搜索
2.1.4 狀態(tài)轉(zhuǎn)換圖和詞法分析器的手工構(gòu)造
2.1.5 詞法分析器手工構(gòu)造實(shí)例
2.2 正規(guī)式、自動(dòng)機(jī)及詞法分析器的自動(dòng)生成
2.2.1 基本概念
2.2.2 正規(guī)式與正規(guī)集
2.2.3 確定有限自動(dòng)機(jī)
2.2.4 非確定有限自動(dòng)機(jī)
2.2.5 NFA的確定化
2.2.6 正規(guī)式的NFA表示
2.2.7 正規(guī)式與確定有限自動(dòng)機(jī)的等價(jià)性
2.3 詞法分析器的自動(dòng)生成
2.3.1 自動(dòng)生成過程概述
2.3.2 掃描器控制程序工作原理
2.3.3 掃描器控制程序的實(shí)現(xiàn)
習(xí)題
習(xí)題答案
第3章 程序設(shè)計(jì)語言的語法描述
3.1 文法的引入
3.1.1 語法樹
3.1.2 語法規(guī)則和句子推導(dǎo)
3.1.3 遞歸規(guī)則和遞歸文法
3.2 上下文無關(guān)文法
3.2.1 文法和語言
3.2.2 文法的二義性
3.3 文法舉例
習(xí)題
習(xí)題答案
第4章 自上而下的語法分析
4.1 帶回溯的自上而下分析法概述
4.2 直接左遞歸的消除
4.3 不帶回溯的自上而下分析法的基本原理
4.4 提取左因子
4.5 first集和follow集
4.5.1 first集的定義及構(gòu)造算法
4.5.2 follow集的定義及構(gòu)造算法
4.6 遞歸下降分析法
4.7 預(yù)測(cè)分析法
4.7.1 預(yù)測(cè)分析表的構(gòu)造
4.7.2 預(yù)測(cè)分析控制程序
4.7.3 預(yù)測(cè)分析程序討論
4.7.4 應(yīng)用舉例
習(xí)題
習(xí)題答案
第5章 自下而上的語法分析
5.1 自下而上的語法分析概述
5.2 LR分析法的基本原理
5.3 LR(O)項(xiàng)目集規(guī)范族的構(gòu)造
5.4 有效項(xiàng)目
5.5 LR(O)分析表的構(gòu)造
5.6 SLR(1)分析表的構(gòu)造
5.7 LR語法分析器的控制程序
5.8 二義文法在LR分析法中的應(yīng)用
5.9 應(yīng)用舉例
5.10 LR分析法在詞法分析器自動(dòng)構(gòu)造中的應(yīng)用
5.10.1 模型語言的詞法描述及SLR分析表
5.10.2 使用SLR分析表識(shí)別單詞的基本原理
5.10.3 算法描述和程序?qū)崿F(xiàn)
5.10.4 LR-LEX中的分析表最小化
習(xí)題
習(xí)題答案
第6章 語法制導(dǎo)翻譯和中間代碼生成
6.1 語法制導(dǎo)翻譯概述
6.2 符號(hào)表和常數(shù)表
6.3 中間代碼
6.3.1 三元式
6.3.2 四元式
6.4 說明語句(簡單變量)的翻譯
6.5 整型算術(shù)表達(dá)式及賦值語句的翻譯
6.6 混合型算術(shù)表達(dá)式及賦值語句的翻譯
6.7 布爾表達(dá)式的翻譯
6.8 標(biāo)號(hào)和無條件轉(zhuǎn)移語句的翻譯
6.9 控制語句的翻譯
6.9.1 if-then語句的翻譯
6.9.2 if-then-else語句的翻譯
6.9.3 while-do語句的翻譯
6.9.4 復(fù)合語句的翻譯
6.10 小結(jié)
6.11 自上而下分析制導(dǎo)翻譯概述
習(xí)題
習(xí)題答案
第7章 目標(biāo)代碼生成
7.1 目標(biāo)計(jì)算機(jī)的虛擬實(shí)現(xiàn)
7.2 語法制導(dǎo)翻譯在匯編程序自動(dòng)構(gòu)造中的應(yīng)用
7.2.1 匯編語言文法和分析表構(gòu)造
7.2.2 單詞編碼表和詞法分析
7.2.3 匯編語言語義和語法制導(dǎo)翻譯
7.3 從四元式到匯編語言的翻譯
習(xí)題
習(xí)題答案
附錄A 虛擬機(jī)匯編程序使用說明
附錄B 課程實(shí)習(xí)指導(dǎo)
參考文獻(xiàn)