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

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