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

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