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

內(nèi)容概要

作為編譯器設(shè)計的教程，本書重點主要放在解決在設(shè)計語言翻譯器過程中所普遍面對的一些問題上而并不考慮源語言或者目標機器。本書共12章：第一章介紹了編譯器的基本結(jié)構(gòu)；第二章給出了一個將前綴表達式轉(zhuǎn)換成后綴表達式的編譯器，主要使用本書的一些基本技巧來構(gòu)建；第三章闡述了詞法分析、正則表達式、有限自動機和掃描生成器工具，這章中的技術(shù)廣泛應(yīng)用于文本處理；第四章詳細闡述了主要的分析技術(shù)，從適合手工實現(xiàn)的遞歸下降算法到在分析生成器中使用的LR算法；第五章介紹了語法制導(dǎo)翻譯中的主要思想，本書的其它部分都用本章來說明和實現(xiàn)翻譯；第六章提出了完成靜態(tài)語義檢查的主要思想，并對類型檢查和類型的統(tǒng)一進行了詳細的討論；第七章討論了支持應(yīng)用程序運行時環(huán)境的存儲組織；第八章從中間語言的討論開始，說明了編程語言結(jié)構(gòu)翻譯成中間代碼；第九章闡述了目標代碼的生成，包含基本的on_the_fly代碼生成方法、為表達式生成代碼的優(yōu)化方法、Peephole優(yōu)化和代碼生成器；第十章是代碼優(yōu)化的總述。除了關(guān)于數(shù)據(jù)流分析方法的詳細說明，還有關(guān)于如何進行全局優(yōu)化的基本方法；第十一章討論了在編譯器實現(xiàn)過程中可能會產(chǎn)生的一些實際問題；第十二章提出一些使用本書中的技術(shù)構(gòu)建的一些編譯器的學習用例。    本書可作為高校計算機專業(yè)本科和研究生編譯原理的教科書，也可供從事計算機軟件開發(fā)的人員參考。

作者簡介

Alfred V.Aho是美國AT&T貝爾實驗室計算機原理研究員的負責人。他在多倫多大學獲得工程物理專業(yè)應(yīng)用科學學士學位，在普林斯頓大學獲得博士學位。

書籍目錄

第1章	編譯器概述1.1	編譯器1.2	源程序代碼的分析1.3	編譯器的各個階段1.4	編譯器的預(yù)處理器1.5	階段組合1.6	編譯器構(gòu)造工具小結(jié)：編寫編譯器的規(guī)則和技術(shù)如此普遍，以至于書中的思想可以被計算機科學家在他們的工作生涯中多次使用。書寫編譯器覆蓋了程序語言、機器系統(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	從正則表達式到NFA3.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.7	LR分析算法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	恰當設(shè)計的文法將一個結(jié)構(gòu)傳給應(yīng)用程序語言。這個程序語言對于將源程序翻譯成正確的目標代碼以及進行錯誤的檢測都是非常有用的。工具有利于將基于文法的翻譯描述轉(zhuǎn)換成能用的應(yīng)用程序。l	隨著時間的推移，語言增加了一些新的結(jié)構(gòu)，同時又實現(xiàn)了一些別的工作。這些新的結(jié)構(gòu)可以更容易地添加到語言中，特別是當存在一個基于語言文法描述的實現(xiàn)時。這一章描述了編譯器中使用的分析方法。我們提出的首先是基本概念；接著是適合手工實現(xiàn)的技術(shù)；最后是自動化工具中使用的算法。由于程序可能包含語法錯誤，我們擴展了這個分析方法以使它們能夠從產(chǎn)生的普通錯誤中恢復(fù)。第5章	語法制導(dǎo)翻譯5.1	語法制導(dǎo)定義5.2	語法樹的構(gòu)造5.3	S－屬性定義的自下而上的求值5.4	L－屬性的定義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)。其中的一些可以被集成到其它一些行為中。舉例來說，當我們將名字的信息存到符號表中時。我們可以確定名字的聲明是唯一的。許多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é)討論。由類型檢查器收集的類型信息可能是需要的，特別是當生成代碼的時候。舉例來說，算術(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.9	Fortran中的動態(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.5	Case語句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.9	Peephole 優(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ù)學上來說，生成優(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ù)學的預(yù)處理器，即EQN12.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 CompilingChapter 2 A Simple One-Pass CompilerChapter 3 Lexical AnalysisChapter 4 Syntax AnalysisChapter 5 Syntax-Directed TranslationChapter 6 Type CheckingChapter 7 Run-Time EnvironmentsChapter 8 Intermediate Code GenerationChapter 9 Code GenerationChapter 10 Code OptimizationChapter 11 Want to Write a Compiler?Chapter 12 A Look at Some CompilersAppendix A Compiler ProjectBibliographyIndex

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    編譯原理 技術(shù)與工具 PDF格式下載

---