編譯原理 技術(shù)與工具

第1章編譯器概述
1.1編譯器
1.2源程序代碼的分析
1.3編譯器的各個(gè)階段
1.4編譯器的預(yù)處理器
1.5階段組合
1.6編譯器構(gòu)造工具
小結(jié)：
編寫編譯器的規(guī)則和技術(shù)如此普遍，以至于書中的思想可以被計(jì)算機(jī)科學(xué)家在他們的工作生涯中多次使用。書寫編譯器覆蓋了程序語言、機(jī)器系統(tǒng)結(jié)構(gòu)、語言理論、算法和軟件工程的內(nèi)容。幸運(yùn)的是，一些基本編譯器技術(shù)可以用來為許多種類的語言和機(jī)器來構(gòu)建翻譯器。這一章中，我們通過描述編譯器的各組成部分分別介紹了編譯器的主題，編譯器工作的環(huán)境，以及使得它較容易構(gòu)造編譯器的軟件工具。
第2章一個(gè)簡單的一遍掃描編譯器
2.1概述
2.2語法定義
2.3語法制導(dǎo)翻譯
2.4分析
2.5簡單表達(dá)式的翻譯機(jī)
2.6詞法分析
2.7符號(hào)表
2.8抽象的棧機(jī)器
2.9將這些技術(shù)組合在一起
小結(jié)：
這一章是這本書3到8章內(nèi)容的概述。它提出了一系列基本的編譯技術(shù)，這些編譯技術(shù)是通過能夠?qū)⑶熬Y表達(dá)式翻譯成后綴表達(dá)式的C工作程序開發(fā)來實(shí)現(xiàn)的。重點(diǎn)放在編譯器的前端上，也就是說放在詞法分析、語法分析和中間代碼的生成上。9、10章描述代碼生成和優(yōu)化。
第3章詞法分析
3.1詞法分析器的功能
3.2輸入緩沖（掃描處理）
3.3標(biāo)號(hào)說明
3.4符號(hào)識(shí)別
3.5識(shí)別詞法分析器的語言
3.6有窮自動(dòng)機(jī)
3.7從正則表達(dá)式到NFA
3.8詞法分析生成器的設(shè)計(jì)
3.9基于DFA模式匹配的優(yōu)化器
小結(jié)：
這一章處理識(shí)別和實(shí)現(xiàn)詞法分析器的技術(shù)。構(gòu)建詞法分析器的最簡單的一個(gè)方法是構(gòu)建一個(gè)描述原語言標(biāo)號(hào)結(jié)構(gòu)的表。然后將這個(gè)圖表手工翻譯成搜索標(biāo)號(hào)的程序。高效的詞法分析器可以通過這種方式產(chǎn)生。
用來實(shí)現(xiàn)詞法分析器的這種技術(shù)可以被應(yīng)用到其它地方像查詢語言和信息獲取系統(tǒng)中。每一個(gè)應(yīng)用程序中，最根本的問題就是執(zhí)行由字符串中的模式引發(fā)的行為的程序說明和設(shè)計(jì)。由于模式導(dǎo)引的編程是非常有用的，我們引入一個(gè)叫做Lex的模式行為語言來說明詞法分析器。在這種語言中，模式由正則表達(dá)式標(biāo)志，Lex的編譯器可以為正則表達(dá)式生成一個(gè)高效的有窮自動(dòng)機(jī)識(shí)別器。
一些語言使用正則表達(dá)式來描述模式。舉例來說，模式掃描語言AWK使用正則表達(dá)式來選擇輸入行進(jìn)行處理，UNIX系統(tǒng)外殼允許用戶通過書寫正則表達(dá)式來引用一系列文件名字。舉例來說，UNIX命令rm*.o，就是移走所有名字結(jié)尾為".o"的文件。
詞法分析器自動(dòng)構(gòu)造的軟件工具允許不同背景的人們在他們自己的應(yīng)用程序領(lǐng)域中使用模式匹配。舉例來說，Jarvis使用詞法分析生成器創(chuàng)建了一個(gè)在印刷電路板上識(shí)別缺陷的程序。這個(gè)電路可以進(jìn)行數(shù)字化掃描并能被轉(zhuǎn)化成不同角度線段的"字符串"。詞法分析器尋找那些同線段"字符串"中的缺陷相對應(yīng)的模式。詞法分析器生成器的主要優(yōu)點(diǎn)是它使用的是最著名的模式匹配算法，因此為那些在模式匹配技術(shù)中并不是專家的人們創(chuàng)造了高效的詞法分析。
第4章文法分析
4.1分析器的角色
4.2上下文無關(guān)文法
4.3編寫一個(gè)文法
4.4自頂向下的分析
4.5自下而上的分析
4.6算符優(yōu)先算法的分析
4.7LR分析算法
4.8使用二義性文法
4.9分析生成器
小結(jié)：
每一個(gè)編程語言都有一些描述已經(jīng)形成的程序的語法結(jié)構(gòu)的規(guī)則。Pascal中，舉例來說，一個(gè)應(yīng)用程序由塊組成的，塊由若干語句組成，語句由表達(dá)式組成，一個(gè)表達(dá)式由若干符號(hào)組成，等等。編程語言結(jié)構(gòu)的語法可以通過上下文無關(guān)文法或者BNF標(biāo)識(shí)來描述，文法為語言設(shè)計(jì)者和編譯器書寫者都提供了一些好處。
l文法給了一個(gè)精確的，而且很容易理解的程序語言的文法規(guī)則。
l從一個(gè)特定文法的一些類中我們可以自動(dòng)構(gòu)造一個(gè)高效的分析器來判斷一個(gè)源程序在語法上結(jié)構(gòu)是否是完整的。有一個(gè)額外的優(yōu)點(diǎn)就是分析器構(gòu)造過程可以顯示出語法的二義性以及一些其它較難分析的結(jié)構(gòu)，而那些結(jié)構(gòu)很可能在一個(gè)語言和編譯器的最初設(shè)計(jì)階段是很難檢查出來的。
l恰當(dāng)設(shè)計(jì)的文法將一個(gè)結(jié)構(gòu)傳給應(yīng)用程序語言。這個(gè)程序語言對于將源程序翻譯成正確的目標(biāo)代碼以及進(jìn)行錯(cuò)誤的檢測都是非常有用的。工具有利于將基于文法的翻譯描述轉(zhuǎn)換成能用的應(yīng)用程序。
l隨著時(shí)間的推移，語言增加了一些新的結(jié)構(gòu)，同時(shí)又實(shí)現(xiàn)了一些別的工作。這些新的結(jié)構(gòu)可以更容易地添加到語言中，特別是當(dāng)存在一個(gè)基于語言文法描述的實(shí)現(xiàn)時(shí)。
這一章描述了編譯器中使用的分析方法。我們提出的首先是基本概念；接著是適合手工實(shí)現(xiàn)的技術(shù)；最后是自動(dòng)化工具中使用的算法。由于程序可能包含語法錯(cuò)誤，我們擴(kuò)展了這個(gè)分析方法以使它們能夠從產(chǎn)生的普通錯(cuò)誤中恢復(fù)。
第5章語法制導(dǎo)翻譯
5.1語法制導(dǎo)定義
5.2語法樹的構(gòu)造
5.3S－屬性定義的自下而上的求值
5.4L－屬性的定義
5.5自頂向下的翻譯
5.6繼承性屬性自下而上的求值
5.7遞歸求值
5.8編譯時(shí)屬性值的空間
5.9編譯器構(gòu)造時(shí)分配空間
5.10語法制導(dǎo)定義的分析
小結(jié)：
這一章發(fā)展了2.3節(jié)的主題：上下文無關(guān)文法制導(dǎo)的語言翻譯。我們將信息同程序語言構(gòu)造聯(lián)系起來，主要是通過將屬性掛接到代表結(jié)構(gòu)的文法象征上實(shí)現(xiàn)的。屬性的值由同文法產(chǎn)生式相關(guān)聯(lián)的語義規(guī)則來計(jì)算。
將語義規(guī)則同產(chǎn)生式聯(lián)系要注意兩點(diǎn)：語法制導(dǎo)的定義和翻譯模式。語法制導(dǎo)定義是翻譯的高層次的說明。它們隱藏了許多實(shí)現(xiàn)細(xì)節(jié)從而將用戶從不得不明確說明翻譯發(fā)生的序列中解脫出來。翻譯模式表明語義規(guī)則求值的順序，從而允許一些實(shí)現(xiàn)細(xì)節(jié)暴露出來。我們在第六章使用這兩點(diǎn)來說明語義檢查，特別是類型判斷，而在第八章使用它們產(chǎn)生中間代碼。
概念上，使用語法制導(dǎo)定義和翻譯模式，我們將分析輸入標(biāo)號(hào)流，建立分析樹，接著根據(jù)需要遍歷樹從而對分析樹節(jié)點(diǎn)上的語義規(guī)則求值，將信息保存在符號(hào)表中，發(fā)布錯(cuò)誤信息，或者完成其它一些動(dòng)作。標(biāo)號(hào)流的翻譯是通過求值語義規(guī)則獲得的結(jié)果。
輸入字符串       分析樹     依賴表      語義規(guī)則的求值順序
語法制導(dǎo)翻譯的概念視圖
一個(gè)實(shí)現(xiàn)并不一定需要完全符合上圖。語法制導(dǎo)定義的特例也可以通過一遍來實(shí)現(xiàn)。主要是通過對遍中的語義規(guī)則進(jìn)行求值而不是明顯的定義一個(gè)分析樹或者一個(gè)圖表來顯示屬性之間的依賴關(guān)系。由于一遍的實(shí)現(xiàn)對于編譯的高效性有重要影響，這一章主要研究這些特例。一個(gè)重要的子類叫做L屬性的算法包含了實(shí)際上所有的翻譯，而這些翻譯無需明確構(gòu)造分析樹就能實(shí)現(xiàn)的。
第6章類型檢查
6.1類型系統(tǒng)
6.2一個(gè)簡單的類型檢查器的說明
6.3類型表達(dá)式的等價(jià)性
6.4類型轉(zhuǎn)換
6.5函數(shù)和操作符的重載
6.6多態(tài)函數(shù)
6.7統(tǒng)一性的一個(gè)算法
小結(jié)：
編譯器應(yīng)該檢查源程序是否遵循源語言的語法和語義。這種檢查，叫做靜態(tài)檢查（將它同目標(biāo)程序執(zhí)行時(shí)的動(dòng)態(tài)檢查區(qū)分開來），保證了特定類型的程序錯(cuò)誤將被檢測和報(bào)告出來。靜態(tài)檢查的例子包括：
1    類型檢查。比如如果一個(gè)操作符應(yīng)用到一個(gè)不兼容的操作數(shù)中時(shí)，編譯器應(yīng)該報(bào)告出錯(cuò)；舉例來說，如果一個(gè)數(shù)組變量和一個(gè)函數(shù)變量相加的話。
2控制流檢查。存在導(dǎo)致一個(gè)控制流離開構(gòu)造器的語句。舉例來說，C語言中的break語句將導(dǎo)致控制流離開最小的循環(huán)while，for和switch語句；如果這樣一個(gè)包含語句不存在的話將導(dǎo)致錯(cuò)誤。
3唯一性檢查。有些情況下一個(gè)對象只能被定義一次。舉例來說，Pascal語言中，標(biāo)識(shí)符應(yīng)該被聲明是唯一的，case語句中的標(biāo)簽也應(yīng)該是唯一的。
4相關(guān)名稱檢查。有時(shí)候，同樣的名字會(huì)多次出現(xiàn)。舉例來說，Ada中，循環(huán)或塊中都將有一個(gè)名字同時(shí)出現(xiàn)在構(gòu)造器的開始和結(jié)束。編譯器將檢查同樣的名字可以在兩端被使用。
這一章中，我們著重于類型檢查。像上面的例子表示的，大多數(shù)靜態(tài)檢查都是慣例程序并且可以運(yùn)用上一章的技術(shù)實(shí)現(xiàn)。其中的一些可以被集成到其它一些行為中。舉例來說，當(dāng)我們將名字的信息存到符號(hào)表中時(shí)。我們可以確定名字的聲明是唯一的。許多Pascal編譯器通過分析將靜態(tài)檢查和中間代碼生成集成為一部分。對于更多的復(fù)雜的結(jié)構(gòu)，就象Ada的，很可能是在分析和中間代碼生成之間有一個(gè)獨(dú)立的類型檢查的遍比較方便。
類型檢查核實(shí)結(jié)構(gòu)的類型同它期待的環(huán)境相匹配。舉例來說，Pascal中算術(shù)運(yùn)算符mod需要整型操作數(shù)，因此一個(gè)類型檢查器應(yīng)該保證mod的操作數(shù)都是整數(shù)類型，同樣的，類型檢查器核實(shí)引用必須用到一個(gè)指針，索引只在數(shù)組上操作，而一個(gè)用戶定義的函數(shù)應(yīng)用時(shí)參數(shù)個(gè)數(shù)和類型必須正確等等。一個(gè)簡單的類型檢測器的規(guī)則出現(xiàn)在6.2。類型表示和什么時(shí)候兩種類型匹配的問題將在6.3節(jié)討論。
由類型檢查器收集的類型信息可能是需要的，特別是當(dāng)生成代碼的時(shí)候。舉例來說，算術(shù)操作符像"＋"通常應(yīng)用到每一個(gè)整數(shù)和實(shí)數(shù)上。也有其它類型的可能，而且我們不得不觀察一下"＋"的上下文來決定它導(dǎo)向的意思。在不同的上下文中代表不同操作的符號(hào)叫做重載。重載伴隨著強(qiáng)制類型轉(zhuǎn)換，編譯器提供了一個(gè)操作符將操作數(shù)轉(zhuǎn)換成上下文期待的類型。
重載的明確概念就是多態(tài)。多態(tài)函數(shù)的主體是可以通過多種類型的參數(shù)來執(zhí)行的。這一章還包括推斷多態(tài)函數(shù)的類型的統(tǒng)一算法。
第7章運(yùn)行時(shí)環(huán)境
7.1源語言問題
7.2存儲(chǔ)組織
7.3存儲(chǔ)分配策略
7.4非局部名稱的訪問
7.5參數(shù)傳遞
7.6符號(hào)表
7.7動(dòng)態(tài)存儲(chǔ)分配的語言工具
7.8動(dòng)態(tài)存儲(chǔ)分配技術(shù)
7.9Fortran中的動(dòng)態(tài)存儲(chǔ)分配
小結(jié)：
在考慮代碼生成之前，我們需要將一個(gè)應(yīng)用程序的靜態(tài)源文本同運(yùn)行時(shí)的行為聯(lián)系起來來實(shí)現(xiàn)應(yīng)用程序。隨著執(zhí)行代碼的繼續(xù)，源文本中的同一個(gè)名字在目標(biāo)機(jī)器中可能意味著不同的數(shù)據(jù)對象。這兒就討論名字和數(shù)據(jù)對象之間的關(guān)系。
數(shù)據(jù)對象的分配和回收由run-time support package進(jìn)行管理，包括隨生成的目標(biāo)代碼一起裝載的例行程序。Run-time support package的設(shè)計(jì)受到過程的語義影響。像Fortran，Pascal和Lisp語言的支持包也可以使用本章中的技術(shù)來構(gòu)建。
每一個(gè)程序的執(zhí)行都可看作是這個(gè)過程的activation。如果一個(gè)程序是遞歸的，那么它的幾個(gè)動(dòng)作應(yīng)該是同時(shí)被激活的。每一個(gè)過程的調(diào)用都有可能導(dǎo)致分配給它使用的數(shù)據(jù)對象的操作激活。
運(yùn)行時(shí)數(shù)據(jù)對象的表示由它的類型決定。經(jīng)常的，像字符，整數(shù)和實(shí)數(shù)這樣的元素?cái)?shù)據(jù)類型，就是由目標(biāo)機(jī)器中等價(jià)的數(shù)據(jù)對象表示的?？墒牵駭?shù)組，字符串和結(jié)構(gòu)等聚集，通常由原始對象的集合來表示。
第8章中間代碼的生成
8.1中間語言
8.2聲明
8.3分配語句
8.4布爾表達(dá)式
8.5Case語句
8.6回填
8.7過程調(diào)用
小結(jié)：
編譯器分析合成的模型中，前端將源程序翻譯成中間表示，然后后端生成目標(biāo)代碼。目標(biāo)語言的細(xì)節(jié)盡可能地限制在后臺(tái)。盡管一個(gè)源程序能被直接翻譯成目標(biāo)語言。但使用獨(dú)立于機(jī)器的中間形式也是有好處的：
1.有利于重定位；不同機(jī)器的編譯器可以通過將新機(jī)器的后端掛接到現(xiàn)存的前端來創(chuàng)建。
2.獨(dú)立于機(jī)器的代碼優(yōu)化器可以被應(yīng)用到中間代碼的表示上。
這一章展示了第2章和第5章的語法制導(dǎo)方法如何將聲明、賦值以及流控制語句等翻譯成它們的中間形式的編程語言結(jié)構(gòu)。而為簡單起見，我們假定源程序已經(jīng)通過編譯和靜態(tài)檢查，大多數(shù)語法制導(dǎo)定義都能通過自下向上或者自上而下的分析來實(shí)現(xiàn)，因此中間代碼生成可根據(jù)具體需要合成到分析里。
第9章代碼生成
9.1代碼生成器設(shè)計(jì)中的一些問題
9.2目標(biāo)機(jī)器
9.3運(yùn)行時(shí)存儲(chǔ)管理
9.4基本塊和流程圖
9.5下一步要使用的信息
9.6一個(gè)簡單的代碼生成器
9.7寄存器分配
9.8基本塊的dag代表
9.9Peephole 優(yōu)化
9.10從dags產(chǎn)生代碼
9.11動(dòng)態(tài)編程代碼生成算法
9.12代碼－生成生成器
小結(jié)：
編譯器模型的最后階段是代碼生成器。它將源程序的中間表示作為輸入，從而產(chǎn)生等價(jià)的目標(biāo)程序作為輸出。這章中使用的代碼生成技術(shù)可以廣泛應(yīng)用，盡管在代碼生成之前優(yōu)化器階段未必就會(huì)發(fā)生像在一些所謂的優(yōu)化編譯器中那樣。這樣的階段企圖將中間代碼翻譯成表單因此會(huì)產(chǎn)生更加有效的目標(biāo)代碼。代碼優(yōu)化將在下一章中詳細(xì)討論。
傳統(tǒng)上對代碼生成器的要求是很嚴(yán)格的。輸出代碼應(yīng)該是正確的并具有較高的質(zhì)量，這意味著能更好的利用目標(biāo)機(jī)器的資源。還有，代碼生成器本身是非常高效的。
可是數(shù)學(xué)上來說，生成優(yōu)化代碼的問題是不確定的。實(shí)際上，我們應(yīng)該滿足于啟發(fā)式技術(shù)來產(chǎn)生較好的，并一定是最高效的代碼。啟發(fā)式的選擇是重要的，特別是精心設(shè)計(jì)的代碼生成算法能夠很容易產(chǎn)生一些代碼，它運(yùn)行起來能比匆忙設(shè)計(jì)的算法產(chǎn)生的代碼快好幾倍。
第10章代碼優(yōu)化
10.1簡介
10.2優(yōu)化的主要資源
10.3基本塊的優(yōu)化
10.4流程圖的循環(huán)
10.5介紹全局?jǐn)?shù)據(jù)流分析
10.6數(shù)據(jù)流方程的交互策略
10.7代碼優(yōu)化的改造
10.8處理別名
10.9結(jié)構(gòu)流圖的數(shù)據(jù)流分析
10.10高效的數(shù)據(jù)流算法
10.11數(shù)據(jù)流分析的工具
10.12類型的評估
10.13優(yōu)化代碼的符號(hào)性調(diào)試
小結(jié)：
理想中，編譯器應(yīng)該產(chǎn)生像手寫的一樣好的目標(biāo)代碼。事實(shí)是這種目標(biāo)只會(huì)在有限的用例中實(shí)現(xiàn)，而且難度還比較高?？墒?，直接編譯算法產(chǎn)生的代碼通常運(yùn)行的比較快或者使用較少的空間，或者兩個(gè)特征同時(shí)具備。這個(gè)改善是通過傳統(tǒng)上叫做優(yōu)化的程序改造來實(shí)現(xiàn)的，盡管"優(yōu)化"這個(gè)術(shù)語是一個(gè)誤導(dǎo)，因?yàn)閷?shí)際上它很少能保證結(jié)果代碼是盡可能優(yōu)化的。應(yīng)用代碼優(yōu)化改造的編譯器叫做優(yōu)化編譯器。
本章重點(diǎn)是獨(dú)立于機(jī)器的優(yōu)化，程序改造無須考慮目標(biāo)機(jī)器的任何屬性就可以改善目標(biāo)代碼。而像寄存器分配和特殊的機(jī)器指令序列等這些依賴于機(jī)器的優(yōu)化已經(jīng)在9章中討論了。
最少的努力獲得最好的效果就是我們找出那些常用程序的執(zhí)行部分，并使這些部分產(chǎn)生盡可能高的效果。有一個(gè)比較流行的說法：大多數(shù)的應(yīng)用程序在10％的代碼上花費(fèi)了90％的執(zhí)行時(shí)間。盡管實(shí)際的百分比會(huì)發(fā)生變化，通常情況下，小部分程序確會(huì)占據(jù)大多數(shù)的運(yùn)行時(shí)間。從輸入代表性數(shù)據(jù)看應(yīng)用程序運(yùn)行時(shí)的執(zhí)行時(shí)間可準(zhǔn)確地找出了問題的吃重運(yùn)行區(qū)域。不幸的是，一個(gè)編譯器通常沒有輸入數(shù)據(jù)的例子，因此它應(yīng)該盡可能猜測問題熱點(diǎn)所在。
實(shí)際上，應(yīng)用程序的內(nèi)在循環(huán)是改善應(yīng)用程序的一個(gè)極好的侯選。在一個(gè)強(qiáng)調(diào)像while和for控制結(jié)構(gòu)的語言中，循環(huán)從程序的語法角度看可能是非常明顯的；通常情況下，一個(gè)叫作控制流分析的過程在程序的流程圖中找出循環(huán)。
這章是一個(gè)有用的優(yōu)化改造和實(shí)現(xiàn)它們的技術(shù)的豐富集合。編譯器中進(jìn)行什么樣的改造是值得的決定這一點(diǎn)的最好的技術(shù)就是收集關(guān)于源程序的統(tǒng)計(jì)數(shù)據(jù)并且評估源程序典型例子上給定優(yōu)化集合的好處。第12章描述了在對不同語言的編譯器優(yōu)化中證明是有用的改造。
這章的主題是數(shù)據(jù)流分析，一個(gè)收集應(yīng)用程序中使用變量方法的信息的過程。一個(gè)應(yīng)用程序中不同點(diǎn)收集的信息可以通過簡單的集等價(jià)方程聯(lián)合起來。我們展示了幾個(gè)使用數(shù)據(jù)流分析收集信息的算法并在優(yōu)化中高效使用這些信息。我們?nèi)匀豢紤]過程和指針等語言結(jié)構(gòu)對優(yōu)化的影響。
第11章如何寫編譯器
11.1規(guī)劃一個(gè)編譯器
11.2編譯器開發(fā)的方法
11.3編譯器開發(fā)環(huán)境
11.4測試和維護(hù)
小結(jié)：
看了這些編譯設(shè)計(jì)的原則，技術(shù)和工具，假定我們需要編寫一個(gè)編譯器：如果提前進(jìn)行規(guī)劃的話，我們可以進(jìn)行的更快更好。這章提出了一些編譯器構(gòu)建中出現(xiàn)的實(shí)現(xiàn)問題。大多數(shù)討論注意力集中在使用UNIX操作系統(tǒng)和它的工具來編寫編譯器上。
第12章看一下一些編譯器
12.1  排版數(shù)學(xué)的預(yù)處理器，即EQN
12.2  Pascal編譯器
12.3  C編譯器
12.4  Fortran H編譯器
12.5  Bliss／11編譯器
12.6  Modula－2優(yōu)化編譯器
小結(jié)：
討論了Pascal、C、Fortran、Bliss和Modula 2的編譯器。我們的意圖并不是支持某項(xiàng)設(shè)計(jì)而排除其它的，而是企圖描述編譯器實(shí)現(xiàn)過程中可能出現(xiàn)的各種情況。
      Chapter 1 Introduction to Compiling
Chapter 2 A Simple One-Pass Compiler
Chapter 3 Lexical Analysis
Chapter 4 Syntax Analysis
Chapter 5 Syntax-Directed Translation
Chapter 6 Type Checking
Chapter 7 Run-Time Environments
Chapter 8 Intermediate Code Generation
Chapter 9 Code Generation
Chapter 10 Code Optimization
Chapter 11 Want to Write a Compiler?
Chapter 12 A Look at Some Compilers
Appendix A Compiler Project
Bibliography
Index