編譯原理學(xué)習(xí)導(dǎo)論

1、第一章 編譯原理學(xué)習(xí)導(dǎo)論 大學(xué)課程為什么要開(kāi)設(shè)編譯原理呢？這門(mén)課程關(guān)注的是編譯器方面的產(chǎn)生原理和技術(shù)問(wèn)題，似乎和計(jì)算機(jī)的基礎(chǔ)領(lǐng)域不沾邊，可是編譯原理卻一直作為大學(xué)本科的必修課程，同時(shí)也成為了研究生入學(xué)考試的必考內(nèi)容。編譯原理及技術(shù)從本質(zhì)上來(lái)講就是一個(gè)算法問(wèn)題而已，當(dāng)然由于這個(gè)問(wèn)題十分復(fù)雜，其解決算法也相對(duì)復(fù)雜。我們學(xué)的數(shù)據(jù)結(jié)構(gòu)與算法分析也是講算法的，不過(guò)講的基礎(chǔ)算法，換句話說(shuō)講的是算法導(dǎo)論，而編譯原理這門(mén)課程講的就是比較專(zhuān)注解決一種的算法了。在20世紀(jì)50年代，編譯器的編寫(xiě)一直被認(rèn)為是十分困難的事情，第一Fortran的編譯器據(jù)說(shuō)花了18年的時(shí)間才完成。在人們嘗試編寫(xiě)編譯器的同時(shí)，誕

2、生了許多跟編譯相關(guān)的理論和技術(shù)，而這些理論和技術(shù)比一個(gè)實(shí)際的編譯器本身價(jià)值更大。就猶如數(shù)學(xué)家們?cè)诮鉀Q著名的哥德巴赫猜想一樣，雖然沒(méi)有最終解決問(wèn)題，但是其間誕生不少名著的相關(guān)數(shù)論。1.1 推薦參考書(shū)雖然編譯理論發(fā)展到今天，已經(jīng)有了比較成熟的部分，但是作為一個(gè)大學(xué)生來(lái)說(shuō)，要自己寫(xiě)出一個(gè)像Turboc C,Java那樣的編譯器來(lái)說(shuō)還是太難了。不僅寫(xiě)編譯器困難，學(xué)習(xí)編譯原理這門(mén)課程也比較困難。正是因?yàn)榫幾g原理學(xué)習(xí)相對(duì)困難，那么就要求有好的教師和好的教材。教師方面不是我們能自己更改的，而在教材方面我們卻可以按自己的意愿來(lái)閱讀。我下面推薦幾本好的編譯原理的教材。我推薦的書(shū)籍都是國(guó)外的經(jīng)典教材，因?yàn)樵趪?guó)內(nèi)的

3、教材中，確實(shí)還沒(méi)發(fā)現(xiàn)什么讓人滿(mǎn)意的。 第一本書(shū)的原名叫Compilers Principles,Techniques,and Tools,另外一個(gè)響亮的名字就是龍書(shū)。原因是這本書(shū)的封面上有條紅色的龍，也因?yàn)檫@本書(shū)在編譯原理基礎(chǔ)領(lǐng)域確實(shí)太有名氣了,所以很多國(guó)外的學(xué)者都直接取名為龍書(shū)。最近機(jī)械工業(yè)出版社已經(jīng)出版了此書(shū)的中文版，名字就叫編譯原理。該書(shū)出的比較早，大概是在85或86年編寫(xiě)完成的，作者之一還是著名的貝爾實(shí)驗(yàn)室的科學(xué)家。里面講解的核心編譯原理至今都沒(méi)有變過(guò)，所以一直到今天，它的價(jià)值都非凡。這本書(shū)最大的特點(diǎn)就是一開(kāi)始就通過(guò)一個(gè)實(shí)際的小例子，把編譯原理的大致內(nèi)容羅列出來(lái)，讓很多編譯原

4、理的初學(xué)者很快心里有了個(gè)底,也知道為什么會(huì)有這些理論，怎么運(yùn)用這些理論。而這一點(diǎn)是我感覺(jué)國(guó)內(nèi)的教材缺乏的東西，所以國(guó)內(nèi)的教材都不是寫(xiě)給愿意自學(xué)的讀者，總之讓人看了半天，卻不知道里面的東西有什么用。第二本書(shū)的原名叫Modern Compiler Design,中文名字叫做現(xiàn)代編譯程序設(shè)計(jì)。該書(shū)由人民郵電出版社所出。此書(shū)比較關(guān)注的是編譯原理的實(shí)踐，書(shū)中給出了不少的實(shí)際程序代碼，還有很多實(shí)際的編譯技術(shù)問(wèn)題等等。此書(shū)另外一個(gè)特點(diǎn)就是其“現(xiàn)代”而字。在傳統(tǒng)的編譯原理教材中，你是不可能看到如同Java中的“垃圾回收”等算法的。因?yàn)镴ava這樣的解釋執(zhí)行語(yǔ)言是在近幾年才流行起來(lái)的東西。如果你想深入學(xué)習(xí)編譯原

5、理的理論知識(shí)，那么你肯定得看前面那本龍書(shū)，如果你想自己動(dòng)手做一個(gè)先進(jìn)的編譯器，那么你得看這本現(xiàn)代編譯程序設(shè)計(jì)。第三本書(shū)就是很多國(guó)內(nèi)的編譯原理學(xué)者都推薦的那本編譯原理及實(shí)踐。或許是這本書(shū)引入國(guó)內(nèi)比較早吧，我記得我是在高中就買(mǎi)了這本書(shū)，不過(guò)也是在前段時(shí)間才把整本書(shū)看完。此書(shū)作為入門(mén)教程也的確是個(gè)不錯(cuò)的選擇。書(shū)中給出的編譯原理講解也相當(dāng)細(xì)致，雖然不如前面的龍書(shū)那么深入，但是很多地方都是點(diǎn)到為止，作為大學(xué)本科教學(xué)已經(jīng)是十分深入了。該書(shū)的特點(diǎn)就是注重實(shí)踐，不過(guò)感覺(jué)還不如前面那本現(xiàn)代編譯程序設(shè)計(jì)的實(shí)踐味道更重。此書(shū)的重點(diǎn)還是在原理上的實(shí)踐，而非前面那本那樣的技術(shù)實(shí)踐。編譯原理及實(shí)踐在講解編譯原理的各個(gè)部分

6、的同時(shí)，也在逐步實(shí)踐一個(gè)現(xiàn)代的編譯器Tiny C.等你把整本書(shū)看完，差不多自己也可以寫(xiě)一個(gè)Tiny C了。作者還對(duì)Lex和Yacc這兩個(gè)常用的編譯相關(guān)的工具進(jìn)行了很詳細(xì)的說(shuō)明，這一點(diǎn)也是很難在國(guó)內(nèi)的教材中看到的。推薦了這三本教材，都有英文版和中文版的。很多英文好的同學(xué)只喜歡看原版的書(shū)，不我的感覺(jué)是這三本書(shū)的翻譯都很不錯(cuò)，沒(méi)有必要特別去買(mǎi)英文版的。理解理論的實(shí)質(zhì)比理解表面的文字更為重要。1.2  編譯原理的實(shí)質(zhì)前面已經(jīng)說(shuō)過(guò)，學(xué)習(xí)編譯原理其實(shí)也就是學(xué)習(xí)算法而已，沒(méi)什么特別的。只不過(guò)這些算法的產(chǎn)生已經(jīng)形成了一套理論。下面我來(lái)看看編譯原理里面到底有什么高深的理論吧。幾乎每本編譯原理的教材都是

7、分成詞法分析，語(yǔ)法分析（LL算法，遞歸下降算法，LR算法），語(yǔ)義分析，運(yùn)行時(shí)環(huán)境，中間代碼，代碼生成，代碼優(yōu)化這些部分。其實(shí)現(xiàn)在很多編譯原理的教材都是按照85,86出版的那本龍書(shū)來(lái)安排教學(xué)內(nèi)容的，所以那本龍書(shū)的內(nèi)容格式幾乎成了現(xiàn)在編譯原理教材的定式，包括國(guó)內(nèi)的教材也是如此。一般來(lái)說(shuō)，大學(xué)里面的本科教學(xué)是不可能把上面的所有部分都認(rèn)真講完的，而是比較偏重于前面幾個(gè)部分。像代碼優(yōu)化那部分東西，就像個(gè)無(wú)底洞一樣，如果要認(rèn)真講，就是單獨(dú)開(kāi)一個(gè)學(xué)期的課也不可能講得清楚。所以，一般對(duì)于本科生，對(duì)詞法分析和語(yǔ)法分析掌握要求就相對(duì)要高一點(diǎn)了。 詞法分析相對(duì)來(lái)說(shuō)比較簡(jiǎn)單。可能是詞法分析程序本身實(shí)現(xiàn)起來(lái)很

8、簡(jiǎn)單吧，很多沒(méi)有學(xué)過(guò)編譯原理的人也同樣可以寫(xiě)出各種各樣的詞法分析程序。不過(guò)編譯原理在講解詞法分析的時(shí)候，重點(diǎn)把正則表達(dá)式和自動(dòng)機(jī)原理加了進(jìn)來(lái)，然后以一種十分標(biāo)準(zhǔn)的方式來(lái)講解詞法分析程序的產(chǎn)生。這樣的做法道理很明顯，就是要讓詞法分析從程序上升到理論的地步。 語(yǔ)法分析部分就比較麻煩一點(diǎn)了?，F(xiàn)在一般有兩種語(yǔ)法分析算法，LL自頂向下算法和LR自底向上算法。LL算法還好說(shuō)，到了LR算法的時(shí)候，困難就來(lái)了。很多自學(xué)編譯原理的都是遇到LR算法的理解成問(wèn)題后就放棄了自學(xué)。其實(shí)這些東西都是只要大家理解就可以了，又不是像詞法分析那樣非得自己寫(xiě)出來(lái)才算真正的會(huì)。像LR算法的語(yǔ)法分析器，一般都是用工具Yac

9、c來(lái)生成，實(shí)踐中完全沒(méi)有比較自己來(lái)實(shí)現(xiàn)。對(duì)于LL算法中特殊的遞歸下降算法，因?yàn)槠鋵?shí)踐十分簡(jiǎn)單，那么就應(yīng)該要求每個(gè)學(xué)生都能自己寫(xiě)。當(dāng)然，現(xiàn)在也有不少好的LL算法的語(yǔ)法分析器，不過(guò)要是換在非C平臺(tái)，比如Java,Delphi,你不能運(yùn)用YACC工具了，那么你就只有自己來(lái)寫(xiě)語(yǔ)法分析器。 等學(xué)到詞法分析和語(yǔ)法分析時(shí)候，你可能會(huì)出現(xiàn)這樣的疑問(wèn)：“詞法分析和語(yǔ)法分析到底有什么？”。就從編譯器的角度來(lái)講，編譯器需要把程序員寫(xiě)的源程序轉(zhuǎn)換成一種方便處理的數(shù)據(jù)結(jié)構(gòu)（抽象語(yǔ)法樹(shù)或語(yǔ)法樹(shù)）,那么這個(gè)轉(zhuǎn)換的過(guò)程就是通過(guò)詞法分析和語(yǔ)法分析的。其實(shí)詞法分析并非一開(kāi)始就被列入編譯器的必備部分，只是我們?yōu)榱撕?jiǎn)化語(yǔ)法

10、分析的過(guò)程，就把詞法分析這種繁瑣的工作單獨(dú)提取出來(lái)，就成了現(xiàn)在的詞法分析部分。除了編譯器部分，在其它地方，詞法分析和語(yǔ)法分析也是有用的。比如我們?cè)贒OS,Unix,Linux下輸入命令的時(shí)候，程序如何分析你輸入的命令形式，這也是簡(jiǎn)單的應(yīng)用。總之，這兩部分的工作就是把不“規(guī)則”的文本信息轉(zhuǎn)換成一種比較好分析好處理的數(shù)據(jù)結(jié)構(gòu)。那么為什么編譯原理的教程都最終把要分析的源分析轉(zhuǎn)換成“樹(shù)”這種數(shù)據(jù)結(jié)構(gòu)呢？數(shù)據(jù)結(jié)構(gòu)中有Stack, Line, List這么多數(shù)據(jù)結(jié)構(gòu)，各自都有各自的特點(diǎn)。但是Tree這種結(jié)構(gòu)有很強(qiáng)的遞歸性，也就是說(shuō)我們可以把Tree的任何結(jié)點(diǎn)Node提取出來(lái)后，它依舊是一顆完整的Tree。

11、這一點(diǎn)符合我們現(xiàn)在編譯原理分析的形式語(yǔ)言，比如我們?cè)诤瘮?shù)里面使用函樹(shù)，循環(huán)中使用循環(huán)，條件中使用條件等等，那么就可以很直觀地表示在Tree這種數(shù)據(jù)結(jié)構(gòu)上。同樣，我們?cè)趫?zhí)行形式語(yǔ)言的程序的時(shí)候也是如此的遞歸性。在編譯原理后面的代碼生成的部分，就會(huì)介紹一種堆棧式的中間代碼，我們可以根據(jù)分析出來(lái)的抽象語(yǔ)法樹(shù)，很容易，很機(jī)械地運(yùn)用遞歸遍歷抽象語(yǔ)法樹(shù)就可以生成這種指令代碼。而這種代碼其實(shí)也被廣泛運(yùn)用在其它的解釋型語(yǔ)言中。像現(xiàn)在流行的Java,.NET，其底層的字節(jié)碼bytecode,可以說(shuō)就是這中基于堆棧的指令代碼的。 關(guān)于語(yǔ)義分析，語(yǔ)法制導(dǎo)翻譯，類(lèi)型檢查等等部分，其實(shí)都是一種完善前面得到的抽

12、象語(yǔ)法樹(shù)的過(guò)程。比如說(shuō)，我們寫(xiě)C語(yǔ)言程序的時(shí)候，都知道，如果把一個(gè)浮點(diǎn)數(shù)直接賦值給一個(gè)整數(shù)，就會(huì)出現(xiàn)類(lèi)型不匹配，那么C語(yǔ)言的編譯器是怎么知道的呢？就是通過(guò)這一步的類(lèi)型檢查。像C+語(yǔ)言這中支持多態(tài)函數(shù)的語(yǔ)言，這部分要處理的問(wèn)題就更多更復(fù)雜了。大部編譯原理的教材在這部分都是講解一些比較好的處理策略而已。因?yàn)樾碌膯?wèn)題總是在發(fā)生，舊的辦法不見(jiàn)得足夠解決。 本來(lái)說(shuō)，作為一個(gè)編譯器，起作用的部分就是用戶(hù)輸入的源程序到最終的代碼生成。但是在講解最終代碼生成的時(shí)候，又不得不講解機(jī)器運(yùn)行環(huán)境等內(nèi)容。因?yàn)槿绻悴恢罊C(jī)器是怎么執(zhí)行最終代碼的，那么你當(dāng)然無(wú)法知道如何生成合適的最終代碼。這部分內(nèi)容我自我感覺(jué)

13、其意義甚至超過(guò)了編譯原理本身。因?yàn)樗鼤?huì)把一個(gè)計(jì)算機(jī)的程序的運(yùn)行過(guò)程都通通排在你面前，你將來(lái)可能不會(huì)從事編譯器的開(kāi)發(fā)工作，但是只要是和計(jì)算機(jī)軟件開(kāi)發(fā)相關(guān)的領(lǐng)域,都會(huì)涉及到程序的執(zhí)行過(guò)程。運(yùn)行時(shí)環(huán)境的講解會(huì)讓你更清楚一個(gè)計(jì)算機(jī)程序是怎么存儲(chǔ)，怎么裝載，怎么執(zhí)行的。關(guān)于部分的內(nèi)容，我強(qiáng)烈建議大家看看龍書(shū)上的講解，作者從最基本的存儲(chǔ)組織，存儲(chǔ)分配策略，非局部名字的訪問(wèn)，參數(shù)傳遞，符號(hào)表到動(dòng)態(tài)存儲(chǔ)分配(malloc,new)都作了十分詳細(xì)的說(shuō)明。這些東西都是我們編寫(xiě)平常程序的時(shí)候經(jīng)常要做的事情，但是我們卻少去探求其內(nèi)部是如何完成。 關(guān)于中間代碼生成，代碼生成,代碼優(yōu)化部分的內(nèi)容就實(shí)在不好說(shuō)了。

14、國(guó)內(nèi)很多教材到了這部分都會(huì)很簡(jiǎn)單地走馬觀花講過(guò)去，學(xué)生聽(tīng)了也只是作為了解，不知道如何運(yùn)用。不過(guò)這部分內(nèi)容的東西如果要認(rèn)真講，單獨(dú)開(kāi)一學(xué)期的課程都講不完。在編譯原理及實(shí)踐的書(shū)上，對(duì)于這部分的講解就恰到好處。作者主要講解的還是一種以堆棧為基礎(chǔ)的指令代碼，十分通俗易懂，讓人看了后，很容易模仿，自己下來(lái)后就可以寫(xiě)自己的代碼生成。當(dāng)然，對(duì)于其它代碼生成技術(shù)，代碼優(yōu)化技術(shù)的講解就十分簡(jiǎn)單了。如果要仔細(xì)研究代碼生成技術(shù)，其實(shí)另外還有本叫做Advance Compiler Desgin and Implement,那本書(shū)現(xiàn)在由機(jī)械工業(yè)出版社引進(jìn)的，十分厚重，而且是英文原版。不過(guò)這本書(shū)我沒(méi)有把它列為推薦書(shū)給大家

15、，畢竟能把龍書(shū)的內(nèi)容搞清楚，在中國(guó)已經(jīng)就算很不錯(cuò)的高手了，到那個(gè)時(shí)候再看這本Advance Compiler Desgin and Implement也不遲。代碼優(yōu)化部分在大學(xué)本科教學(xué)中還是一個(gè)不太重要的部分，就是算是實(shí)踐過(guò)程中，相信大家也不太運(yùn)用得到。畢竟，自己做的編譯器能正確生成執(zhí)行代碼已經(jīng)很不錯(cuò)了，還談什么優(yōu)化呢？1.3 關(guān)于實(shí)踐編譯原理的課程畢竟還只是講解原理的課程，不是專(zhuān)門(mén)的編譯技術(shù)課程。這兩門(mén)課程是有很大的區(qū)別的。編譯技術(shù)更關(guān)注實(shí)際的編寫(xiě)編譯器過(guò)程中運(yùn)用到的技術(shù)，而原理的課關(guān)注講解其基本理論。但是計(jì)算機(jī)科學(xué)本身就是一門(mén)實(shí)踐性很強(qiáng)的課程，如果能夠?qū)W以致用，那才叫真正的學(xué)會(huì)。李陽(yáng)在講解

16、瘋狂英語(yǔ)的時(shí)候就說(shuō)到，只要當(dāng)你會(huì)實(shí)際中運(yùn)用一個(gè)單詞一個(gè)詞組的時(shí)候你才能叫學(xué)會(huì)了這個(gè)單詞或者詞組，而不是只是知道了它的拼寫(xiě)和意思。其實(shí)任何學(xué)習(xí)都是一樣的，如果缺少了實(shí)踐的結(jié)合，你不能算學(xué)會(huì)。 編譯原理的課程主要就是講解編譯器產(chǎn)生的理論和原理，那么很簡(jiǎn)單，自己寫(xiě)個(gè)編譯器就是最好的實(shí)踐過(guò)程了。不過(guò)你得小心，編譯系統(tǒng)可能是所有軟件系統(tǒng)中最復(fù)雜的系統(tǒng)之一,不然為什么大學(xué)里面還會(huì)把編譯器的編寫(xiě)開(kāi)成一門(mén)叫做編譯原理的課程來(lái)講？我很佩服那些學(xué)了操作系統(tǒng)原理就開(kāi)始自己寫(xiě)操作系統(tǒng)，學(xué)了編譯原理就開(kāi)始自己寫(xiě)編譯器的人們，確實(shí)，在中國(guó)，敢這么做的學(xué)生太少了。且不管你這樣做能不能做成功，至少有了這個(gè)嘗試，會(huì)讓

17、你的程序設(shè)計(jì)，系統(tǒng)規(guī)劃安排的功底增進(jìn)不少。我下面給出一些關(guān)于實(shí)踐過(guò)程中可能會(huì)遇到的困難，希望能夠在你陷入困境的前幫你一把。 1.       Lex和Yacc. 這兩工具是作為詞法分析很語(yǔ)法分析的工具。如果你自己寫(xiě)一個(gè)編譯器，我十分不建議你連詞法分析這種事情都親手來(lái)寫(xiě)。Lex和Yacc應(yīng)該是作為每本編譯原理的教材的必備內(nèi)容，可是在國(guó)內(nèi)的教材中缺很少看到。這兩個(gè)工具是Unix系統(tǒng)下的小東西，如果你要在Windows中運(yùn)用，那么你最好去下在cygwin這個(gè)軟件。它是個(gè)在Windows下模擬Unix的東西，里面就包含了flex.e

18、xe和bison.exe(yacc)這兩個(gè)工具.這兩個(gè)工具使用起來(lái)還挺麻煩的(其實(shí)unix下的很多十分有用的工具都是這樣), 不過(guò)在編譯原理與實(shí)踐這本書(shū)上對(duì)于這兩個(gè)工具的講解十分詳細(xì),還列舉了不少實(shí)際的例子。2.       做解釋型語(yǔ)言比做生成機(jī)器代碼的編譯器簡(jiǎn)單。雖然說(shuō)，做解釋型的編譯器，像Java那樣的，你還得自己去寫(xiě)解釋器，不過(guò)這樣你就不必去查找機(jī)器代碼的資料了。如果你做生成的最終機(jī)器代碼編譯器可能會(huì)遇到問(wèn)題還有就是寄存器為基礎(chǔ)的代碼生成方法。前面說(shuō)過(guò)，如果你生成的是以堆棧為基礎(chǔ)的代碼，那么其代碼生成過(guò)程十分簡(jiǎn)單，需要考慮的東

19、西也不多，如果你考慮最終的機(jī)器代碼生成的話，你必須考慮機(jī)器的寄存器如何分配等麻煩的問(wèn)題。3.       考慮用別人已經(jīng)生成的語(yǔ)法文件，盡量不要自己動(dòng)手寫(xiě)詞法文件和語(yǔ)法文件.以前一個(gè)朋友曾經(jīng)說(shuō)過(guò),寫(xiě)出一個(gè)好的程序語(yǔ)言的語(yǔ)法定義,就幾乎完成了一個(gè)編譯器的一半.確實(shí)是這樣,語(yǔ)法文件的編寫(xiě)是個(gè)很難的事情.現(xiàn)在網(wǎng)上到處都可以找到比如C語(yǔ)言,C+, Java, Tiny C, Minus C等語(yǔ)言的詞法文件和語(yǔ)法文件,你完全可以自己下下來(lái)來(lái)用. 在編譯原理及實(shí)踐的書(shū)中，作者給出了一個(gè)Tiny C的全部代碼.我自我感覺(jué)作者的這個(gè)編譯器做

20、得很不錯(cuò),相對(duì)于其它php, perl等語(yǔ)言的源代碼來(lái)說(shuō),簡(jiǎn)單得多,容易看懂,而且很清晰地展現(xiàn)了一個(gè)完成的編譯系統(tǒng)的實(shí)現(xiàn)過(guò)程.其源代碼可以在作者的網(wǎng)站上下載.1.4 后話編譯原理的學(xué)習(xí)可能算是一個(gè)困難的歷程,特別是對(duì)于那些不對(duì)編譯系統(tǒng)感興趣的同學(xué)來(lái)說(shuō).既然它已經(jīng)作為了大學(xué)本科的必修課程,那么就說(shuō)明的它引申出來(lái)的一套理論在整個(gè)計(jì)算機(jī)科學(xué)領(lǐng)域還是占有相對(duì)重要的地位.如果我們考究一下歷史,就會(huì)發(fā)現(xiàn)很多被稱(chēng)為程序設(shè)計(jì)大師的人都是編譯領(lǐng)域的高手.寫(xiě)出第一個(gè)微型機(jī)上運(yùn)行的Basic語(yǔ)言的比爾蓋茨,設(shè)計(jì)出Delphi的Borland的“世界上最厲害的程序員”, Sun的JAVA之父, 貝爾實(shí)驗(yàn)室的C+之父&

21、#160;第二章 編譯原理與技術(shù)的參考書(shū)籍介紹2.1 編譯原理 技術(shù)與工具（英文版）2.1.1 書(shū)本信息書(shū)    名編譯原理 技術(shù)與工具（英文版）頁(yè)數(shù)796作    者Alfred V.Aho Ravi Se開(kāi)本16責(zé)任編輯李際字?jǐn)?shù)1009千字出 版 社人民郵電出版社印張50.75出版時(shí)間2002年2月第1版頁(yè)數(shù)796再版時(shí)間2004年8月第5次書(shū)號(hào)09916裝    幀平裝定價(jià) 63元 帶盤(pán)否 2.1.2 內(nèi)容提要    作為編譯器設(shè)計(jì)的教程，本書(shū)重點(diǎn)主要放在解決

22、在設(shè)計(jì)語(yǔ)言翻譯器過(guò)程中所普遍面對(duì)的一些問(wèn)題上而并不考慮源語(yǔ)言或者目標(biāo)機(jī)器。本書(shū)共12章：第一章介紹了編譯器的基本結(jié)構(gòu)；第二章給出了一個(gè)將前綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的編譯器，主要使用本書(shū)的一些基本技巧來(lái)構(gòu)建；第三章闡述了詞法分析、正則表達(dá)式、有限自動(dòng)機(jī)和掃描生成器工具，這章中的技術(shù)廣泛應(yīng)用于文本處理；第四章詳細(xì)闡述了主要的分析技術(shù)，從適合手工實(shí)現(xiàn)的遞歸下降算法到在分析生成器中使用的LR算法；第五章介紹了語(yǔ)法制導(dǎo)翻譯中的主要思想，本書(shū)的其它部分都用本章來(lái)說(shuō)明和實(shí)現(xiàn)翻譯；第六章提出了完成靜態(tài)語(yǔ)義檢查的主要思想，并對(duì)類(lèi)型檢查和類(lèi)型的統(tǒng)一進(jìn)行了詳細(xì)的討論；第七章討論了支持應(yīng)用程序運(yùn)行時(shí)環(huán)境的存儲(chǔ)組織；第

23、八章從中間語(yǔ)言的討論開(kāi)始，說(shuō)明了編程語(yǔ)言結(jié)構(gòu)翻譯成中間代碼；第九章闡述了目標(biāo)代碼的生成，包含基本的on_the_fly代碼生成方法、為表達(dá)式生成代碼的優(yōu)化方法、Peephole優(yōu)化和代碼生成器；第十章是代碼優(yōu)化的總述。除了關(guān)于數(shù)據(jù)流分析方法的詳細(xì)說(shuō)明，還有關(guān)于如何進(jìn)行全局優(yōu)化的基本方法；第十一章討論了在編譯器實(shí)現(xiàn)過(guò)程中可能會(huì)產(chǎn)生的一些實(shí)際問(wèn)題；第十二章提出一些使用本書(shū)中的技術(shù)構(gòu)建的一些編譯器的學(xué)習(xí)用例。    本書(shū)可作為高校計(jì)算機(jī)專(zhuān)業(yè)本科和研究生編譯原理的教科書(shū)，也可供從事計(jì)算機(jī)軟件開(kāi)發(fā)的人員參考。 2.1.3 目錄第1章編譯器概述1.1編譯器1.2源程

24、序代碼的分析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抽象的棧

25、機(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á)式到NFA3.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)

26、的表。然后將這個(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ō)，U

27、NIX命令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)化成不同角度線段的"字符串"。詞法分析器尋找那些同線段"字符串"中的缺陷相對(duì)應(yīng)的模式。詞法分析器生成器的主要優(yōu)點(diǎn)是它使用的是最著名的模式匹配算法，因此為那些在模式匹配技術(shù)中并不是專(zhuān)家的人們創(chuàng)造了高效的詞法分析。第4章文法分析4.1分析器的角色4.2上下文無(wú)關(guān)文法4.3編寫(xiě)一個(gè)文法

28、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ò)

29、程可以顯示出語(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è)分

30、析方法以使它們能夠從產(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ò)將屬性掛接到代表結(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é)從而

31、將用戶(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é)果。語(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)顯示屬性之間

32、的依賴(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ò)；舉例

33、來(lái)說(shuō)，如果一個(gè)數(shù)組變量和一個(gè)函數(shù)變量相加的話。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ǔ)句不存在的話將導(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)檢查

34、都是慣例程序并且可以運(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)型必須正確等等。一

35、個(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

36、存儲(chǔ)組織7.3存儲(chǔ)分配策略7.4非局部名稱(chē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和L

37、isp語(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)代

38、碼。目標(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.

39、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ì)量，這意味著能

40、更好的利用目標(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)化代碼的符

41、號(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í)

42、行部分，并使這些部分產(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ù)的豐富集

43、合。編譯器中進(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ě)

44、一個(gè)編譯器：如果提前進(jìn)行規(guī)劃的話，我們可以進(jìn)行的更快更好。這章提出了一些編譯器構(gòu)建中出現(xiàn)的實(shí)現(xiàn)問(wèn)題。大多數(shù)討論注意力集中在使用UNIX操作系統(tǒng)和它的工具來(lái)編寫(xiě)編譯器上。第12章看一下一些編譯器12.1 排版數(shù)學(xué)的預(yù)處理器，即EQN12.2 Pascal編譯器12.3 C編譯器12.4 Fortran H編譯器12.5 Bliss11編譯器12.6 Modula2優(yōu)化編譯器小結(jié)：討論了Pascal、C、Fortran、Bliss和Modula 2的編譯器。我們的意圖并不是支持某項(xiàng)設(shè)計(jì)而排除其它的，而是企圖描述編譯器實(shí)現(xiàn)過(guò)程中可能出現(xiàn)的各種情況。 2.2 編譯原理（英文版）2.2.1 書(shū)本信息書(shū)&

45、#160;   名編譯原理頁(yè)數(shù)524作    者美Alfred V.Aho等開(kāi)本16責(zé)任編輯楊海玲字?jǐn)?shù)千字出 版 社機(jī)械工業(yè)出版社印張34出版時(shí)間2003年8月第1版頁(yè)數(shù)524再版時(shí)間2004年8月第4次書(shū)號(hào)111-12349-2裝    幀平裝定價(jià) 55元 帶盤(pán)否 2.2.2 內(nèi)容提要本書(shū)深入討論了編譯器設(shè)計(jì)的重要主題，包括詞法分析、語(yǔ)法分析、語(yǔ)法制導(dǎo)分析、類(lèi)型檢查、運(yùn)行環(huán)境、中間代碼生成、代碼生成、代碼優(yōu)化等，并在最后兩章中討論了實(shí)現(xiàn)編譯器的一些編程問(wèn)題和幾個(gè)編譯器實(shí)例，每章都提供了大量的練習(xí)和參考文獻(xiàn)。本書(shū)從

46、介紹編譯的原理性概念開(kāi)始，然后通過(guò)構(gòu)建一個(gè)簡(jiǎn)單的一遍編譯器來(lái)逐一解釋這些概念。 本書(shū)是編譯原理課程的經(jīng)典教材，作者曾多次使用本書(shū)的內(nèi)容在貝爾實(shí)驗(yàn)室、哥倫比亞大學(xué)、普林斯頓大學(xué)和斯坦福大學(xué)向本科生和研究生講授初等及高等編譯課程。 本書(shū)作者Alfred VAho、Ravi Sethi和Jeffrey DUllman是世界著名的計(jì)算機(jī) 科學(xué)家，他們?cè)谟?jì)算機(jī)科學(xué)理論、數(shù)據(jù)庫(kù)等很多領(lǐng)域都做出了杰出貢獻(xiàn)。本書(shū) 是編譯領(lǐng)域無(wú)可替代的經(jīng)典著作，被廣大計(jì)算機(jī)專(zhuān)業(yè)人士譽(yù)為“龍書(shū)”。本書(shū)一 直被世界各地的著名高等院校和科研機(jī)構(gòu)(如貝爾實(shí)

47、驗(yàn)室、哥倫比亞大學(xué)、普 林斯頓大學(xué)和斯坦福大學(xué)等)廣泛用作本科生和研究生編譯原理與技術(shù)課程的 教材，本書(shū)對(duì)我國(guó)計(jì)算機(jī)教育界也具有重大影響。 書(shū)中深入討論了編譯器設(shè)計(jì)的重要主題，包括詞法分析、語(yǔ)法分析、語(yǔ)法制 導(dǎo)分析、類(lèi)型檢查、運(yùn)行環(huán)境、中間代碼生成、代碼生成、代碼優(yōu)化等，并在 最后兩章中討論了實(shí)現(xiàn)編譯器的一些編程問(wèn)題和幾個(gè)編譯器實(shí)例，而且每章都 提供了大量的練習(xí)和參考文獻(xiàn)。 本書(shū)可以作為高等院校計(jì)算機(jī)專(zhuān)業(yè)本科生和研究生編譯原理與技術(shù)課程的 教材，也可以作為計(jì)算機(jī)技術(shù)人員必讀的專(zhuān)業(yè)參考書(shū)之一。2.2.3 目錄出版者的

48、話專(zhuān)家指導(dǎo)委員會(huì)譯者序前言第1章 編譯簡(jiǎn)介11.1 編譯器11.1.1 編譯的分析-綜合模型11.1.2 編譯器的前驅(qū)與后繼31.2 源程序分析31.2.1 詞法分析31.2.2 語(yǔ)法分析31.2.3 語(yǔ)義分析51.2.4 文本格式器中的分析51.3 編譯器的各階段61.3.1 符號(hào)表管理71.3.2 錯(cuò)誤檢測(cè)與報(bào)告71.3.3 各分析階段71.3.4 中間代碼生成91.3.5 代碼優(yōu)化91.3.6 代碼生成101.4 編譯器的伙伴101.4.1 預(yù)處理器101.4.2 匯編器111.4.3 兩遍匯編121.4.4 裝配器和連接編輯器121.5 編譯器各階段的分組131.5.1 前端與后端13

49、1.5.2 編譯器的遍131.5.3 減少編譯的遍數(shù)141.6 編譯器的構(gòu)造工具14參考文獻(xiàn)注釋15第2章 簡(jiǎn)單的一遍編譯器172.1 概述172.2 語(yǔ)法定義172.2.1 分析樹(shù)192.2.2 二義性202.2.3 操作符的結(jié)合規(guī)則202.2.4 操作符的優(yōu)先級(jí)212.3 語(yǔ)法制導(dǎo)翻譯222.3.1 后綴表示222.3.2 語(yǔ)法制導(dǎo)定義222.3.3 綜合屬性232.3.4 深度優(yōu)先遍歷242.3.5 翻譯模式252.3.6 翻譯的輸出252.4 語(yǔ)法分析262.4.1 自頂向下語(yǔ)法分析272.4.2 預(yù)測(cè)分析法292.4.3 何時(shí)使用產(chǎn)生式302.4.4 設(shè)計(jì)一個(gè)預(yù)測(cè)語(yǔ)法分析器302.4

50、.5 左遞歸312.5 簡(jiǎn)單表達(dá)式的翻譯器322.5.1 抽象語(yǔ)法和具體語(yǔ)法322.5.2 調(diào)整翻譯模式332.5.3 非終結(jié)符expr、term 和rest 的過(guò)程332.5.4 翻譯器的優(yōu)化352.5.5 完整程序352.6 詞法分析372.6.1 剔除空白符和注釋372.6.2 常數(shù)372.6.3 識(shí)別標(biāo)識(shí)符和關(guān)鍵字372.6.4 詞法分析器的接口382.6.5 詞法分析器382.7 符號(hào)表402.7.1 符號(hào)表接口402.7.2 處理保留的關(guān)鍵字412.7.3 符號(hào)表的實(shí)現(xiàn)方法412.8 抽象堆棧機(jī)422.8.1 算術(shù)指令422.8.2 左值和右值432.8.3 堆棧操作432.8.4

51、 表達(dá)式的翻譯432.8.5 控制流442.8.6 語(yǔ)句的翻譯442.8.7 輸出一個(gè)翻譯452.9 技術(shù)的綜合462.9.1 翻譯器的描述462.9.2 詞法分析器模塊lexer.c472.9.3 語(yǔ)法分析器模塊parser.c482.9.4 輸出模塊emitter.c482.9.5 符號(hào)表模塊symbol.c和init.c482.9.6 錯(cuò)誤處理模塊error.c482.9.7 編譯器的建立482.9.8 程序清單49練習(xí)53編程練習(xí)54參考文獻(xiàn)注釋55第3章 詞法分析573.1 詞法分析器的作用573.1.1 詞法分析中的問(wèn)題583.1.2 記號(hào)、模式、詞素583.1.3 記號(hào)的屬性59

52、3.1.4 詞法錯(cuò)誤603.2 輸入緩沖603.2.1 雙緩沖區(qū)613.2.2 標(biāo)志623.3 記號(hào)的描述623.3.1 串和語(yǔ)言623.3.2 語(yǔ)言上的運(yùn)算633.3.3 正規(guī)表達(dá)式643.3.4 正規(guī)定義653.3.5 縮寫(xiě)表示法663.3.6 非正規(guī)集663.4 記號(hào)的識(shí)別673.4.1 狀態(tài)轉(zhuǎn)換圖683.4.2 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)703.5 詞法分析器描述語(yǔ)言723.5.1 Lex說(shuō)明723.5.2 超前掃描操作753.6 有窮自動(dòng)機(jī)763.6.1 不確定的有窮自動(dòng)機(jī)773.6.2 確定的有窮自動(dòng)機(jī)783.6.3 從NFA到DFA的變換793.7 從正規(guī)表達(dá)式到NFA813.7.1 從正

53、規(guī)表達(dá)式構(gòu)造NFA813.7.2 NFA的雙堆棧模擬843.7.3 時(shí)間空間的權(quán)衡853.8 設(shè)計(jì)詞法分析器的生成器853.8.1 基于NFA的模式匹配863.8.2 詞法分析器的DFA883.8.3 實(shí)現(xiàn)超前掃描操作883.9 基于DFA的模式匹配器的優(yōu)化893.9.1 NFA的重要狀態(tài)893.9.2 從正規(guī)表達(dá)式到DFA893.9.3 最小化DFA的狀態(tài)數(shù)933.9.4 詞法分析器的狀態(tài)最小化953.9.5 表壓縮方法95練習(xí)97編程練習(xí)103參考文獻(xiàn)注釋103第4章 語(yǔ)法分析1054.1 語(yǔ)法分析器的作用1054.1.1 語(yǔ)法錯(cuò)誤的處理1064.1.2 錯(cuò)誤恢復(fù)策略1084.2 上下文無(wú)

54、關(guān)文法1094.2.1 符號(hào)的使用約定1104.2.2 推導(dǎo)1104.2.3 分析樹(shù)和推導(dǎo)1124.2.4 二義性1134.3 文法的編寫(xiě)1134.3.1 正規(guī)表達(dá)式和上下文無(wú)關(guān)文法的比較1144.3.2 驗(yàn)證文法所產(chǎn)生的語(yǔ)言1144.3.3 消除二義性1154.3.4 消除左遞歸1164.3.5 提取左因子1174.3.6 非上下文無(wú)關(guān)語(yǔ)言的結(jié)構(gòu)1184.4 自頂向下語(yǔ)法分析1204.4.1 遞歸下降語(yǔ)法分析法1204.4.2 預(yù)測(cè)語(yǔ)法分析器1214.4.3 預(yù)測(cè)語(yǔ)法分析器的狀態(tài)轉(zhuǎn)換圖1214.4.4 非遞歸的預(yù)測(cè)分析1234.4.5 FIRST和FOLLOW1244.4.6 預(yù)測(cè)分析表的構(gòu)

55、造1254.4.7 LL(1)文法1264.4.8 預(yù)測(cè)分析的錯(cuò)誤恢復(fù)1274.5 自底向上語(yǔ)法分析1284.5.1 句柄1294.5.2 句柄裁剪1304.5.3 用棧實(shí)現(xiàn)移動(dòng)歸約分析1314.5.4 活前綴1334.5.5 移動(dòng)歸約分析過(guò)程中的沖突1334.6 算符優(yōu)先分析法1344.6.1 使用算符優(yōu)先關(guān)系1354.6.2 從結(jié)合律和優(yōu)先級(jí)獲得算符優(yōu)先關(guān)系1364.6.3 處理一元操作符1374.6.4 優(yōu)先函數(shù)1374.6.5 算符優(yōu)先分析中的錯(cuò)誤恢復(fù)1394.7 LR語(yǔ)法分析器1424.7.1 LR語(yǔ)法分析算法1424.7.2 LR文法1454.7.3 構(gòu)造SLR語(yǔ)法分析表1464.7.4 構(gòu)造規(guī)范LR語(yǔ)法分析表1514.7.5 構(gòu)造LALR語(yǔ)法分析表1554.7.6 LALR語(yǔ)法分析表的有效構(gòu)造方法1584.7.7 LR語(yǔ)法分析表的壓縮1614.8 二義文法的應(yīng)用1634.8.1 使用優(yōu)先級(jí)和結(jié)合規(guī)則來(lái)解決分析動(dòng)作的沖突1634.8.2 懸空else的二義性1644.8.3 特例產(chǎn)生式引起的二義性1654.8.4 LR語(yǔ)法分析中的錯(cuò)誤恢復(fù)1674.9 語(yǔ)法分析器的生成器1684.9.1 語(yǔ)法分析器的生成器Yacc1694.9.2 用Yacc處理二義文法1714.9.3 用Lex建立Yacc的詞法分析器1734.9.4 Yacc的錯(cuò)誤恢復(fù)174練習(xí)174參考文獻(xiàn)