編譯原理

出版者的話
譯者序
前言
第1章 引論
　1.1 語(yǔ)言處理器
　1.2 一個(gè)編譯器的結(jié)構(gòu)
　　1.2.1 詞法分析
　　1.2.2 語(yǔ)法分析
　　1.2.3 語(yǔ)義分析
　　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ì)語(yǔ)言的發(fā)展歷程
　　1.3.1 走向高級(jí)程序設(shè)計(jì)語(yǔ)言
　　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ì)語(yǔ)言的實(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ì)語(yǔ)言基礎(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章的參考書目
第2章 一個(gè)簡(jiǎn)單的語(yǔ)法制導(dǎo)翻譯器
　2.1 引言
　2.2 語(yǔ)法定義
　　2.2.1 文法定義
　　2.2.2 推導(dǎo)
　　2.2.3 語(yǔ)法分析樹
　　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 語(yǔ)法制導(dǎo)翻譯
　　2.3.1 后綴表示
　　2.3.2 綜合屬性
　　2.3.3 簡(jiǎn)單語(yǔ)法制導(dǎo)定義
　　2.3.4 樹的遍歷
　　2.3.5 翻譯方案
　　2.3.6 2.3節(jié)的練習(xí)
　2.4 語(yǔ)法分析
　　2.4.1 自頂向下分析方法
　　2.4.2 預(yù)測(cè)分析法
　　2.4.3 何時(shí)使用產(chǎn)生式
　　2.4.4 設(shè)計(jì)一個(gè)預(yù)測(cè)語(yǔ)法分析器
　　2.4.5 左遞歸
　　2.4.6 2.4節(jié)的練習(xí)
　2.5 簡(jiǎn)單表達(dá)式的翻譯器
　　2.5.1抽象語(yǔ)法和具體語(yǔ)法
　　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 語(yǔ)法樹的構(gòu)造
　　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 輸入緩沖
　　3.2.1 緩沖區(qū)對(duì)
　　3.2.2 哨兵標(biāo)記
　3.3 詞法單元的規(guī)約
　3.3.1 串和語(yǔ)言
　　3.3.2 語(yǔ)言上的運(yùn)算
　　3.3.3 正則表達(dá)式
　　3.3.4 正則定義
　　3.3.5 正則表達(dá)式的擴(kuò)展
　　3.3.6 3.3節(jié)的練習(xí)
　3.4 詞法單元的識(shí)別
　　3.4.1 狀態(tài)轉(zhuǎn)換圖
　　3.4.2 保留字和標(biāo)識(shí)符的識(shí)別
　　3.4.3 完成我們的連續(xù)性例子
　　3.4.4 基于狀態(tài)轉(zhuǎn)換圖的詞法分析器的體系結(jié)構(gòu)
　　3.4.5 3.4節(jié)的練習(xí)
　3.5 詞法分析器生成工具Lex
　　3.5.1 Lex的使用
　　3.5.2 Lex程序的結(jié)構(gòu)
　　3.5.3 Lex中的沖突解決
　　3.5.4 向前看運(yùn)算符
　　3.5.5 3.5節(jié)練習(xí)
　3.6 有窮自動(dòng)機(jī)
　　3.6.1 不確定的有窮自動(dòng)機(jī)
　　3.6.2 轉(zhuǎn)換表
　　3.6.3 NFA接受輸入字符串
　　3.6.4 確定的有窮自動(dòng)機(jī)
　　3.6.5 3.6節(jié)的練習(xí)
　3.7 從正則表達(dá)式到自動(dòng)機(jī)
　　3.7.1 從NFA到DFA的轉(zhuǎn)換
　　3.7.2 NFA的模擬
　　3.7.3 NFA模擬效率
　　3.7.4 從正則表達(dá)式構(gòu)造NFA
　　3.7.5 字符串處理算法的效率
　　3.7.6 3.7節(jié)的練習(xí)
　3.8 詞法分析器生成工具的設(shè)計(jì)
　　3.8.1 被生成的詞法分析器的結(jié)構(gòu)
　　3.8.2 基于NFA的模式匹配
　　3.8.3 詞法分析器使用的DFA
　　3.8.4 實(shí)現(xiàn)向前看運(yùn)算符
　　3.8.5 3.8的練習(xí)
　3.9 基于DFA的模式匹配器的優(yōu)化
　　3.9.1 NFA的重要狀態(tài)
　　3.9.2 根據(jù)抽象語(yǔ)法樹計(jì)算得到的函數(shù)
　　3.9.3 計(jì)算nullable、firstpos及l(fā)astpos
　　3.9.4 計(jì)算followpos
　　3.9.5 根據(jù)正則表達(dá)式構(gòu)建DFA
　　3.9.6 最小化一個(gè)DFA的狀態(tài)數(shù)
　　3.9.7 詞法分析器的狀態(tài)最小化
　　3.9.8 在DFA模擬中用時(shí)間換取空間
　　3.9.9 3.9節(jié)的練習(xí)
　　3.9.10 第3章的總結(jié)
　3.11 第3章參考文獻(xiàn)
第4章 語(yǔ)法分析
　4.1 引論
　　4.1.1 語(yǔ)法分析器的角色
　　4.1.2 代表性的文法
　　4.1.3 語(yǔ)法錯(cuò)誤的處理
　　4.1.4 錯(cuò)誤恢復(fù)策略
　4.2 上下文無(wú)關(guān)文法
　　4.2.1 上下文無(wú)關(guān)文法的正式定義
　　4.2.2 符號(hào)表示的慣例
　 4.2.3 推導(dǎo)
4.2.4 語(yǔ)法分析樹和推導(dǎo)
　 4.2.5 二義性
　　4.2.6 驗(yàn)證文法生成的語(yǔ)言
　　4.2.7上下文無(wú)關(guān)文法和正則表達(dá)式
　　4.2.8 4.2節(jié)的練習(xí)
　4.3 設(shè)計(jì)文法
　　4.3.1 詞法分析和語(yǔ)法分析
　　4.3.2 消除二義性
　　4.3.3 左遞歸的消除
　　4.3.4 提取左公因子
　　4.3.5 非上下文無(wú)關(guān)的語(yǔ)言構(gòu)造
　　4.3.6 4.3節(jié)的練習(xí)
　4.4 自頂向下的語(yǔ)法分析
　　4.4.1 遞歸下降的語(yǔ)法分析
　　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 自底向上的語(yǔ)法分析
　　4.5.1 歸約
　　4.5.2 句柄剪枝
　　4.5.3 移入-歸約語(yǔ)法分析技術(shù)
　　4.5.4 移入-歸約語(yǔ)法分析中的沖突
　　4.5.5 4.5節(jié)的練習(xí)
　4.6 LR語(yǔ)法分析技術(shù)介紹：簡(jiǎn)單LR技術(shù)
　　4.6.1 為什么使用LR語(yǔ)法分析器？
　　4.6.2 項(xiàng)和LR(0)自動(dòng)機(jī)
　　4.6.3 LR-語(yǔ)法分析算法
　　4.6.4 構(gòu)造SLR-分析表
　　4.6.5 可行前綴
　　4.6.6 4.6節(jié)的練習(xí)
　4.7 更強(qiáng)大的LR語(yǔ)法分析器
　　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語(yǔ)法分析表
　　4.7.5 LALR語(yǔ)法分析表的高效構(gòu)造方法
　　4.7.6 LR語(yǔ)法分析表的壓縮
　　4.7.7 4.7節(jié)的練習(xí)
　4.8 使用二義性文法
　　4.8.1 用優(yōu)先級(jí)和結(jié)合性解決沖突
　　4.8.2 “懸空-else”二義性
　　4.8.3 LR語(yǔ)法分析中的錯(cuò)誤恢復(fù)
　　4.8.4 4.8節(jié)的練習(xí)
　4.9 語(yǔ)法分析器的生成工具
　　4.9.1 語(yǔ)法分析器的生成工具Yacc
　　4.9.2 使用Yacc處理二義性文法
　　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章 語(yǔ)法制導(dǎo)的翻譯
　5.1 語(yǔ)法制導(dǎo)定義
　　5.1.1 繼承屬性和綜合屬性
　　5.1.2 在一棵語(yǔ)法分析樹的結(jié)點(diǎn)上對(duì)一個(gè)SDD求值
　　5.1.3 5.1節(jié)的練習(xí)
　5.2 SDD的求值順序
　　5.2.1 依賴圖
　　5.2.2 屬性求值的順序
　　5.2.3 S-屬性定義
　　5.2.4 L-屬性定義
　　5.2.5 具有受控副作用的語(yǔ)義規(guī)則
　　5.2.6 5.2節(jié)的練習(xí)
　5.3 語(yǔ)法制導(dǎo)翻譯的應(yīng)用
　　5.3.1 抽象語(yǔ)法樹的構(gòu)造
　　5.3.2 類型的結(jié)構(gòu)
　　5.3.3 5.3節(jié)的練習(xí)
　5.4 語(yǔ)法制導(dǎo)的翻譯方案
　　5.4.1 后綴翻譯方案
　　5.4.2 后綴SDT的語(yǔ)法分析棧實(shí)現(xiàn)
　　5.4.3 產(chǎn)生式內(nèi)部帶有語(yǔ)義動(dòng)作的SDT
　　5.4.4 從SDT中消除左遞歸
　　5.4.5 L-屬性定義的SDT
　　5.4.6 5.4節(jié)的練習(xí)
　5.5 實(shí)現(xiàn)L-屬性的SDD
　　5.5.1 在遞歸下降語(yǔ)法分析過程中進(jìn)行翻譯
　　5.5.2 邊掃描邊生成代碼
　　5.5.3 L-屬性的SDD和LL語(yǔ)法分析
　　5.5.4 L-屬性的SDD的自底向上語(yǔ)法分析
　　5.5.5 5.5節(jié)的練習(xí) 　
　5.6 第5章的總結(jié)
　5.7 第5章的參考文獻(xiàn)
第6章 中間代碼生成
第7章 運(yùn)行時(shí)刻環(huán)境
第7章 總結(jié)
第8章 代碼生成
第9章 機(jī)器無(wú)關(guān)優(yōu)化
第10章 指令級(jí)并行
第11章 并行性和局部性的優(yōu)化
第12章 過程間分析