《編譯原理》是編譯原理課程方面的經(jīng)典教材,全面、深入地探討了編譯器設(shè)計(jì)方面的重要主題,包括詞法分析、語法分析、語法制導(dǎo)定義和語法制導(dǎo)翻譯、運(yùn)行時(shí)刻環(huán)境、目標(biāo)代碼生成、代碼優(yōu)化技術(shù)、并行性檢測(cè)以及過程間分析技術(shù),并在相關(guān)章節(jié)中給出大量的實(shí)例。與上一版相比,本書進(jìn)行了全面修訂,涵蓋了編譯器開發(fā)方面最新進(jìn)展。每章中都提供了大量的實(shí)例及參考文獻(xiàn)。
本書基于該書第2版進(jìn)行改編,內(nèi)容更加精練和實(shí)用,體系更加符合國(guó)內(nèi)教學(xué)情況,適合作為高等院校計(jì)算機(jī)及相關(guān)專業(yè)本科生的編譯原理課程的教材,也是廣大研究人員和技術(shù)人員的極佳參考讀物。
本書是編譯領(lǐng)域無可替代的經(jīng)典著作,被廣大計(jì)算機(jī)專業(yè)人士譽(yù)為“龍書”。本書上一版自1986年出版以來,被世界各地的著名高等院校和研究機(jī)構(gòu)(包括美國(guó)哥倫比亞大學(xué)。斯坦福大學(xué)、哈佛大學(xué)、普林斯頓大學(xué)。貝爾實(shí)驗(yàn)室)作為本科生和研究生的編譯原理課程的教材。該書對(duì)我國(guó)高等計(jì)算機(jī)教育領(lǐng)域也產(chǎn)生了重大影響。
第2版對(duì)每一章都進(jìn)行了全面的修訂,以反映自上一版出版20多年來軟件工程、程序設(shè)計(jì)語言和計(jì)算機(jī)體系結(jié)構(gòu)方面的發(fā)展對(duì)編譯技術(shù)的影響。第2版全面介紹了編譯器的設(shè)計(jì),并強(qiáng)調(diào)編譯技術(shù)在軟件設(shè)計(jì)和開發(fā)中的廣泛應(yīng)用。每章中都包含大量的習(xí)題和豐富的參考文獻(xiàn)。
本書基于該書第2版進(jìn)行改編,保留其中的基本內(nèi)容,壓縮或刪除了一些高級(jí)內(nèi)容,更適合作為國(guó)內(nèi)高校計(jì)算機(jī)及相關(guān)專業(yè)本科生編譯原理課程教材。
《編譯原理(本科教學(xué)版第2版)》是編譯領(lǐng)域無可替代的經(jīng)典著作,被廣大計(jì)算機(jī)專業(yè)人士譽(yù)為“龍書”!毒幾g原理(本科教學(xué)版第2版)》上一版自1986年出版以來,被世界各地的著名高等院校和研究機(jī)構(gòu)(包括美國(guó)哥倫比亞大學(xué)、斯坦福大學(xué)、哈佛大學(xué)、普林斯頓大學(xué)、貝爾實(shí)驗(yàn)室)作為本科生和研究生的編譯原理課程的教材。該書對(duì)我國(guó)高等計(jì)算機(jī)教育領(lǐng)域也產(chǎn)生了重大影響。編譯領(lǐng)域里程碑式的經(jīng)典著作——龍書,20年后終于出版新版!這是一個(gè)延綿30年的故事,這是一部關(guān)于龍書的傳奇!最新版本,增添兩章節(jié)內(nèi)容,使龍書地位更權(quán)威!
第2版對(duì)每一章都進(jìn)行了全面的修訂,以反映自上一版出版20多年來軟件工程。程序設(shè)計(jì)語言和計(jì)算機(jī)體系結(jié)構(gòu)方面的發(fā)展對(duì)編譯技術(shù)的影響!毒幾g原理(本科教學(xué)版第2版)》全面介紹了編譯器的設(shè)計(jì),并強(qiáng)調(diào)編譯技術(shù)在軟件設(shè)計(jì)和開發(fā)中的廣泛應(yīng)用。每章中都包含大量的習(xí)題和豐富的參考文獻(xiàn)。
《編譯原理(本科教學(xué)版第2版)》適合作為高等院校計(jì)算機(jī)專業(yè)本科生和研究生的編譯原理與技術(shù)課程的教材,也可供廣大計(jì)算機(jī)技術(shù)人員參考。
1977年,Alfred V.Aho和Jeffrey D.Ullman合作出版了《Principies of Compilet Design》,封面是一位騎士和一只恐龍,那恐龍是綠色的,因此被稱為龍書或綠龍書。
1986年,原來的兩位作者加上Ravi Sethi,升級(jí)了前一《編譯原理(本科教學(xué)版第2版)》,書名改為《compiIers:Principles,Techniques and Tools》,封面依然沿用騎士和恐龍,那恐龍是紅色的,因此被稱為龍書二或者紅龍書。
又過了一個(gè)9年又一個(gè)9年,編譯領(lǐng)域的巨無霸——龍書始終都沒有升級(jí)。
終于在2006年底,龍書升級(jí)了。作者又增加了Monica S.Lam,名字與龍書二相同,封面依然沿用恐龍和武士的設(shè)計(jì),這次的龍是紫色的,因此被稱為龍書三或者紫龍書。
出版者的話
改編者序
前言
第1章 引論
1.1 語言處理器
1.2 一個(gè)編譯器的結(jié)構(gòu)
1.2.1 詞法分析
1.2.2 語法分析
1.2.3 語義分析
1.2.4 中間代碼生成
1.2.5 代碼優(yōu)化
1.2.6 代碼生成
1.2.7 符號(hào)表管理
1.2.8 將多個(gè)步驟組合成趟
1.2.9 編譯器構(gòu)造工具
1.3 程序設(shè)計(jì)語言的發(fā)展歷程
1.3.1 走向高級(jí)程序設(shè)計(jì)語言
1.3.2 對(duì)編譯器的影響
1.3.3 1.3節(jié)的練習(xí)
1.4 構(gòu)建一個(gè)編譯器的相關(guān)科學(xué)
1.4.1 編譯器設(shè)計(jì)和實(shí)現(xiàn)中的建模
1.4.2 代碼優(yōu)化的科學(xué)
1.5 編譯技術(shù)的應(yīng)用
1.5.1 高級(jí)程序設(shè)計(jì)語言的實(shí)現(xiàn)
1.5.2 針對(duì)計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化
1.5.3 新計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì)
1.5.4 程序翻譯
1.5.5 軟件生產(chǎn)率工具
1.6 程序設(shè)計(jì)語言基礎(chǔ)
1.6.1 靜態(tài)和動(dòng)態(tài)的區(qū)別
1.6.2 環(huán)境與狀態(tài)
1.6.3 靜態(tài)作用域和塊結(jié)構(gòu)
1.6.4 顯式訪問控制
1.6.5 動(dòng)態(tài)作用域
1.6.6 參數(shù)傳遞機(jī)制
1.6.7 別名
1.6.8 1.6節(jié)的練習(xí)
1.7 第1章總結(jié)
1.8 第1章參考文獻(xiàn)
第2章 一個(gè)簡(jiǎn)單的語法制導(dǎo)翻譯器
2.1 引言
2.2 語法定義
2.2.1 文法定義
2.2.2 推導(dǎo)
2.2.3 語法分析樹
2.2.4 二義性
2.2.5 運(yùn)算符的結(jié)合性
2.2.6 運(yùn)算符的優(yōu)先級(jí)
2.2.7 2.2節(jié)的練習(xí)
2.3 語法制導(dǎo)翻譯
2.3.1 后綴表示
2.3.2 綜合屬性
2.3.3 簡(jiǎn)單語法制導(dǎo)定義
2.3.4 樹的遍歷
2.3.5 翻譯方案
2.3.6 2.3節(jié)的練習(xí)
2.4 語法分析
2.4.1 自頂向下分析方法
2.4.2 預(yù)測(cè)分析法
2.4.3 何時(shí)使用產(chǎn)生式
2.4.4 設(shè)計(jì)一個(gè)預(yù)測(cè)分析器
2.4.5 左遞歸
2.4.6 2.4節(jié)的練習(xí)
2.5 簡(jiǎn)單表達(dá)式的翻譯器
2.5.1 抽象語法和具體語法
2.5.2 調(diào)整翻譯方案
2.5.3 非終結(jié)符號(hào)的過程
2.5.4 翻譯器的簡(jiǎn)化
2.5.5 完整的程序
2.6 詞法分析
2.6.1 剔除空白和注釋
2.6.2 預(yù)讀
2.6.3 常量
2.6.4 識(shí)別關(guān)鍵字和標(biāo)識(shí)符
2.6.5 詞法分析器
2.6.6 2.6節(jié)的練習(xí)
2.7 符號(hào)表
2.7.1 為每個(gè)作用域設(shè)置一個(gè)符號(hào)表
2.7.2 符號(hào)表的使用
2.8 生成中間代碼
2.8.1 兩種中間表示形式
2.8.2 語法樹的構(gòu)造
2.8.3 靜態(tài)檢查
2.8.4 三地址碼
2.8.5 2.8節(jié)的練習(xí)
2.9 第2章總結(jié)
2.5.5 完整的程序
2.6 詞法分析
2.6.1 剔除空白和注釋
2.6.2 預(yù)讀
2.6.3 常量
2.6.4 識(shí)別關(guān)鍵字和標(biāo)識(shí)符
2.6.5 詞法分析器
2.6.6 2.6節(jié)的練習(xí)
2.7 符號(hào)表
2.7.1 為每個(gè)作用域設(shè)置—個(gè)符號(hào)表
2.7.2 符號(hào)表的使用
2.8 生成中間代碼
2.8.1 兩種中間表示形式
2.8.2 語法樹的構(gòu)造
2.8.3 靜態(tài)檢查
2.8.4 三地址碼
2.8.5 2.8節(jié)的練習(xí)
2.9 第2章總結(jié)
第3章 詞法分析
3.1 詞法分析器的作用
3.1.1 詞法分析及語法分析
3.1.2 詞法單元、模式和詞素
3.1.3 詞法單元的屬性
3.1.4 詞法錯(cuò)誤
3.1.5 3.1節(jié)的練習(xí)
3.2 詞法單元的規(guī)約
3.2.1 串和語言
3.2.2 語言上的運(yùn)算
3.2.3 正則表達(dá)式
3.2.4 正則定義
3.2.5 正則表達(dá)式的擴(kuò)展
3.2.6 3.2 節(jié)的練習(xí)
3.3 詞法單元的識(shí)別
3.3.1 狀態(tài)轉(zhuǎn)換圖
3.3.2 保留字和標(biāo)識(shí)符的識(shí)別
3.3.3 完成我們的例子
3.3.4 基于狀態(tài)轉(zhuǎn)換圖的詞法分析器的體系結(jié)構(gòu)
3.3.5 3.3 節(jié)的練習(xí)
3.4 詞法分析器生成工具Lex
3.4.1 Lex的使用
3.4.2 Lex程序的結(jié)構(gòu)
3.4.3 Lex中的沖突解決
3.4.4 向前看運(yùn)算符
3.4.5 3.4節(jié)的練習(xí)
3.5 有窮自動(dòng)機(jī)
3.5.1 不確定的有窮自動(dòng)機(jī)
3.5.2 轉(zhuǎn)換表
3.5.3 自動(dòng)機(jī)中輸入字符串的接受
3.5.4 確定的有窮自動(dòng)機(jī)
3.5.5 3.5節(jié)的練習(xí)
3.6 從正則表達(dá)式到自動(dòng)機(jī)
3.6.1 從NFA到DFA的轉(zhuǎn)換
3.6.2 最小化一個(gè)DFA的狀態(tài)數(shù)
3.6.3 從正則表達(dá)式構(gòu)造NFA
3.6.4 字符串處理算法的效率
3.6.5 3.6節(jié)的練習(xí)
3.7 詞法分析器生成工具的設(shè)計(jì)
3.7.1 生成的詞法分析器的結(jié)構(gòu)
3.7.2 詞法分析器使用的DFA
3.7.3 詞法分析器的狀態(tài)最小化
3.7.4 實(shí)現(xiàn)向前看運(yùn)算符
3.7.5 3.7節(jié)的練習(xí)
3.8 第3章總結(jié)
3.9 第3章參考文獻(xiàn)
夥4章 語法分析
4.1 引論
4.1.1 語法分析器的作用
4.1.2 代表性的文法
4.1.3 語法錯(cuò)誤的處理
4.1.4 錯(cuò)誤恢復(fù)策略
4.2 上下文無關(guān)文法
4.2.1 上下文無關(guān)文法的正式定義
4.2.2 符號(hào)表示的約定
4.2.3 推導(dǎo)
4.2.4 語法分析樹和推導(dǎo)
4.2.5 二義性
4.2.6 驗(yàn)證文法生成的語言
4.2.7 上下文無關(guān)文法和正則表達(dá)式
4.2.8 4.2節(jié)的練習(xí)
4.3 設(shè)計(jì)文法
4.3.1 詞法分析和語法分析
4.3.2 消除二義性
4.3.3 左遞歸的消除
4.3.4 提取左公因子
4.3.5 非上下文無關(guān)語言的構(gòu)造
4.3.6 4.3節(jié)的練習(xí)
4.4 自頂向下的語法分析
4.4.1 遞歸下降的語法分析
4.4.2 FIRST和FOLLOW
4.4.3 LL(1)文法
4.4.4 非遞歸的預(yù)測(cè)分析
4.4.5 預(yù)測(cè)分析中的錯(cuò)誤恢復(fù)
4.4.6 4.4節(jié)的練習(xí)
4.5 自底向上的語法分析
4.5.1 歸約
4.5.2 句柄剪枝
4.5.3 移人一歸約語法分析技術(shù)
4.5.4 移入一歸約語法分析中的沖突
4.5.5 4.5節(jié)的練習(xí)
4.6 LR語法分析技術(shù)介紹:簡(jiǎn)單LR技術(shù)
4.6.1 為什么使用LR語法分析器
4.6.2 項(xiàng)和LR(0)自動(dòng)機(jī)
4.6.3 LR語法分析算法
4.6.4 構(gòu)造SLR語法分析表
4.6.5 可行前綴
4.6.6 4.6節(jié)的練習(xí)
4.7 更強(qiáng)大的LR語法分析器
4.7.1 規(guī)范LR(1)項(xiàng)
4.7.2 構(gòu)造LR(1)項(xiàng)集
4.7.3 規(guī)范LR(1)語法分析表
4.7.4 構(gòu)造LALR語法分析表
4.7.5 高效構(gòu)造LALR語法分析表的方法
4.7.6 4.7節(jié)的練習(xí)
4.8 使用二義性文法
4.8.1 用優(yōu)先級(jí)和結(jié)合性解決沖突
4.8.2 “懸空=else”的二義性
4.8.3 LR語法分析中的錯(cuò)誤恢復(fù)
4.8.4 4.8節(jié)的練習(xí)
4.9 語法分析器生成工具
4.9.1 語法分析器生成工具Yacc
4.9.2 使用帶有二義性文法的Yacc規(guī)約
4.9.3 用Lex創(chuàng)建Yacc的詞法分析器
4.9.4 Yacc中的錯(cuò)誤恢復(fù)
4.9.5 4.9節(jié)的練習(xí)
4.10 第4章總結(jié)
4.11 第4章參考文獻(xiàn)
第5章 語法制導(dǎo)的翻譯
第6章 中間代碼生成
第7章 運(yùn)行時(shí)刻環(huán)境
第8章 代碼生成
第9章 機(jī)器無關(guān)優(yōu)化
附錄 一個(gè)完整的編譯器前端