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

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