編譯程序設(shè)計藝術(shù)理論與實踐

出版者的話
譯者序
前言
第1章 編譯程序理論概述
1.1 簡介
1.2 語言與翻譯程序
1.3 文法的作用
1.4 若干例子
1.5 編譯程序的結(jié)構(gòu)
1.5.1 詞法分析
1.5.2 字符串表
1.5.3 語法分析
1.5.4 約束
1.5.5 符號表
1.5.6 代碼生成
1.5.7 優(yōu)化
符號
縮略詞
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第2章 文法：喬姆斯基層次
2.1 簡介
2.2 文法
2.2.1 字母表與串
2.2.2 非終結(jié)符與產(chǎn)生式
2.2.3 若干文法例子
2.3 喬姆斯基層次
2.4 文法及其機器
2.4.1 圖靈機
2.4.2 線性有界自動機
2.4.3 下推自動機
2.4.4 刪除空產(chǎn)生式
2.4.5 比較上下文無關(guān)文法和上下文敏感文法
2.4.6 有窮狀態(tài)自動機
2.5 空串與空語言
2.6 規(guī)范推導
2.7 二義性
2.8 文法思維的藝術(shù)
2.8.1 有窮狀態(tài)自動機的局限性
2.8.2 上下文無關(guān)文法的計數(shù)
2.8.3 對上下文敏感
小結(jié)
符號
縮略詞
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第3章 掃描程序和正則語言
3.1 詞法分析簡介
3.2 正則表達式
3.2.1 正則表達式代數(shù)
3.2.2 正則表達式的形式化特性
3.3 文法與正則表達式的轉(zhuǎn)換
3.4 有窮狀態(tài)自動機
3.5 不確定的有窮狀態(tài)自動機
3.6 將文法轉(zhuǎn)換為自動機
3.7 自動機的轉(zhuǎn)換
3.7.1 刪除空環(huán)路
3.7.2 刪除空變遷
3.7.3 自動機的確定化
3.7.4 自動機的約簡
3.8 將自動機轉(zhuǎn)換為文法
3.9 左線性文法
3.10 在計算機上實現(xiàn)有窮狀態(tài)自動機
3.11 掃描程序的特殊實現(xiàn)問題
3.11.1 輸入字母表的大小
3.11.2 掃描程序自動機中的停機狀態(tài)
3.11.3 過濾空格與注釋
3.11.4 單詞的輸出
3.12 字符串表的實現(xiàn)
3.12.1 基于線性查找的實現(xiàn)
3.12.2 基于散列表的實現(xiàn)
3.12.3 基于查找樹的實現(xiàn)
3.12.4 不同實現(xiàn)的性能比較
3.13 保留字
3.14 使用掃描程序生成工具
小結(jié)
符號
縮略詞
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第4章 分析程序和上下文無關(guān)語言
4.1 簡介
4.2 下推自動機
4.2.1 停機條件的等價性
4.2.2 根據(jù)上下文無關(guān)文法構(gòu)造下推自動機
4.3 LL（k）條件
4.3.1 First和和Follow集
4.3.2 選擇集
4.4 左遞歸
4.5 公共左因子
4.6 為上下文無關(guān)文法擴展正則表達式運算符
4.7 使用分析程序生成工具
4.7.1 使用TAG編譯程序
4.7.2 使用YACC
4.8 遞歸下降分析程序
4.9 遞歸下降分析程序作為下推自動機
小結(jié)
縮略詞
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第5章 語義分析與屬性文法
5.1 簡介
5.2 屬性文法
5.2.1 繼承屬性和綜合屬性
5.2.2 屬性值流
5.3 非終結(jié)符作為屬性求值函數(shù)
5.4 符號表作為屬性
5.5 Micro-Modula的屬性文法
5.6 在TAG編譯程序中使用屬性
5.7 作用域與標識符類別
5.7.1 標識符作用域的文法
5.7.2 標識符作用域例子分析
5.7.3 符號表的其他問題
5.8 在遞歸下降中實現(xiàn)屬性
5.9 實現(xiàn)符號表
小結(jié)
符號
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第6章 語法制導代碼生成
6.1 簡介
6.2 計算機硬件體系結(jié)構(gòu)
6.3 棧機器的表達式求值
6.4 IttyBitty棧機器
6.5 帶屬性的代碼生成
6.5.1 運算符優(yōu)先級與結(jié)合性質(zhì)
6.5.2 程序結(jié)構(gòu)的語義
6.5.3 向前分支問題
6.6 過程和函數(shù)的代碼生成
6.7 塊結(jié)構(gòu)的棧幀管理
6.7.1 幀與幀指針
6.7.2 靜態(tài)鏈與動態(tài)鏈
6.7.3 幀指針的Display向量
6.8 其他數(shù)據(jù)類型
6.9 結(jié)構(gòu)化數(shù)據(jù)類型
6.9.1 指針類型
6.9.2 記錄結(jié)構(gòu)
6.9.3 數(shù)組的語義
6.10 其他數(shù)據(jù)結(jié)構(gòu)
6.11 Itty Bitty棧機器的輸入和輸出
6.12 語法制導語義的局限
6.13 手工編寫編譯程序的代碼生成
6.14 語法制導語義的應(yīng)用
6.14.1 TinyBASIC解釋程序
6.14.2 Micro-Modula美化打印工具
小結(jié)
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第7章 自底向上分析程序的自動化
設(shè)計
7.1 簡介
7.2 LR（k）分析程序
7.2.1 構(gòu)造LR（k）狀態(tài)機
7.2.2 一個LR（2）分析程序
7.2.3 歸約與移進操作
7.3 沖突
7.4 例子：文法G2的沖突解析
7.5 在棧中保存狀態(tài)
7.6 其他LR（k）分析程序：SLR
7.7 LALR（k）分析程序
7.8 自底向上分析程序的實現(xiàn)
7.9 出錯恢復
7.10 LR分析程序中的屬性求值
小結(jié)
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第8章 變換屬性文法
8.1 簡介
8.2 程序的樹表示
8.3 樹變換文法
8.3.1 非生成的文法
8.3.2 一個TAG例子
8.3.3 求值次序
8.3.4 信息流與存儲
8.3.5 帶樹值的屬性
8.3.6 不確定的分析
8.4.組合串文法與樹文法
8.5 TAG中的類型檢查
8.6 基于變換的代碼優(yōu)化
8.6.1 數(shù)據(jù)流分析
8.6.2 數(shù)據(jù)流分析中使用屬性文法
8.7 中間代碼樹表示的替代方案
8.7.1 四元式的數(shù)據(jù)流
8.7.2 循環(huán)的數(shù)據(jù)流分析
8.8 實用優(yōu)化變換綜述
8.8.1 模擬執(zhí)行優(yōu)化的類別
8.8.2 常量折疊分析
8.8.3 使用值編號檢測公共子表達式
8.8.4 左移動提升
8.8.5 右移動提升
8.8.6 無用代碼以及其他從右到左的數(shù)據(jù)流分析
8.8.7 數(shù)學等式與代碼選擇
8.8.8 循環(huán)結(jié)構(gòu)分析
8.9 實現(xiàn)抽象語法樹
8.10 實現(xiàn)TAG驅(qū)動的樹變換
小結(jié)
符號
縮略詞
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第9章 代碼生成與優(yōu)化
9.1 簡介
9.2 循環(huán)優(yōu)化
9.2.1 循環(huán)的范圍分析
9.2.2 歸納變量
9.2.3 循環(huán)展開
9.3 寄存器與內(nèi)存分配
9.3.1 寄存器分配算法
9.3.2 表達式中的寄存器分配
9.3.3 更好的寄存器分配數(shù)據(jù)流分析
9.3.4 循環(huán)的寄存器分配
9.3.5 尋址模式
9.3.6 分支尋址選擇
9.3.7 分支鏈
9.4 代碼生成的復雜性
9.4.1 指令選擇
9.4.2 強度削弱
9.5 專用指令
9.5.1 RISC和流水線處理器調(diào)度
9.5.2 向量處理器
9.6 代碼優(yōu)化的變形
9.6.1 代碼優(yōu)化的分類
9.6.2 窺孔優(yōu)化
小結(jié)
縮略詞
關(guān)鍵術(shù)語
練習
復習小測驗
編譯程序?qū)嶒烅椖?br />進一步閱讀
第10章 非過程式語言
10.1 簡介
10.2 應(yīng)用式語言的編譯
10.2.1 Lisp語言的一些概念
10.2.2 尾遞歸
10.2.3 實現(xiàn)一個應(yīng)用式語言的編譯程序
10.3 變換屬性文法的編譯程序
10.3.1 TAG編譯程序的組成部分
10.3.2 文法中的迭代運算符
10.3.3 向用戶報告語法錯誤
10.3.4 自動構(gòu)造掃描程序
10.3.5 TAG編譯程序的語法分析
10.3.6 樹變換
10.3.7 語法錯誤停機
小結(jié)
關(guān)鍵術(shù)語
練習
復習小測驗
進一步閱讀
附錄A Itty Bitty Modula語法圖
附錄B TAG編譯程序的TAG
附錄C IttyBitty棧機器的指令集
附錄D 四種計算機的代碼生成表