1、編譯技術(shù)的發(fā)展和應(yīng)用據(jù)說(shuō)第一個(gè)編譯程序的出現(xiàn)是在20世紀(jì)50年代早期，很難講出確切的時(shí)間，因?yàn)楫?dāng)初大量的實(shí)驗(yàn)和實(shí)現(xiàn)工作是由不同的小組獨(dú)立完成的，多數(shù)早期的編譯工作是將算術(shù)公式翻譯成機(jī)器代碼。用現(xiàn)在的標(biāo)準(zhǔn)來(lái)衡量，當(dāng)時(shí)的編譯程序能完成的工作十分初步，如只允許簡(jiǎn)單的單目運(yùn)算，數(shù)據(jù)元素的命名方式有很多限制。然而它們奠定了對(duì)高級(jí)語(yǔ)言編譯系統(tǒng)的研究和開(kāi)發(fā)的基礎(chǔ)。20世紀(jì)50年代中期出現(xiàn)了FORTRAN等一批高級(jí)語(yǔ)言，相應(yīng)的一批編譯系統(tǒng)開(kāi)發(fā)成功。隨著編譯技術(shù)的發(fā)展和社會(huì)對(duì)編譯程序需求的不斷增長(zhǎng)，20世紀(jì)50年代末有人開(kāi)始研究編譯程序的自動(dòng)生成工具，提出并研制編譯程序的編譯程序。它的功能是以任一語(yǔ)言的詞法規(guī)則

2、、語(yǔ)法規(guī)則和語(yǔ)義解釋出發(fā)，自動(dòng)產(chǎn)生該語(yǔ)言的編譯程序。目前很多自動(dòng)生成工具已廣泛使用，如詞法分析程序的生成系統(tǒng)LEX，語(yǔ)法分析程序的生成系統(tǒng)YACC等。20世紀(jì)60年代起，不斷有人使用自展技術(shù)來(lái)構(gòu)造編譯程序。自展的主要特征是用被編譯的語(yǔ)言來(lái)書(shū)寫(xiě)該語(yǔ)言自身的編譯程序。1971年，PASCAL的編譯程序用自展技術(shù)生成后，其影響就越來(lái)越大。隨著并行技術(shù)和并行語(yǔ)言的發(fā)展，處理并行語(yǔ)言的并行編譯技術(shù)，將串行程序轉(zhuǎn)換成并行程序的自動(dòng)并行編譯技術(shù)也正在深入研究之中。 另外嵌入式應(yīng)用迅速增長(zhǎng)的需求，推動(dòng)了交叉編譯技術(shù)的發(fā)展.還有系統(tǒng)芯片設(shè)計(jì)方法和關(guān)鍵EDA技術(shù)的研究，也帶動(dòng)了專(zhuān)用語(yǔ)言VHDL等及其編譯技術(shù)的不斷

3、深化。編譯實(shí)現(xiàn)方式的發(fā)展手工機(jī)器語(yǔ)言匯編系統(tǒng)程序設(shè)計(jì)語(yǔ)言自動(dòng)構(gòu)造工具lex yacc gcc推動(dòng)編譯技術(shù)發(fā)展的因素語(yǔ)言范型（計(jì)算模式）計(jì)算機(jī)體系結(jié)構(gòu)語(yǔ)言范型命令式(imperative language)應(yīng)用式(applicative)基于規(guī)則的（rule-based）面向?qū)ο蟮模╫bject-oriented）并行計(jì)算(parallel computing)體系結(jié)構(gòu)萬(wàn)諾曼機(jī)體系結(jié)構(gòu)并行體系結(jié)構(gòu)嵌入系統(tǒng)編譯程序執(zhí)行環(huán)境批處理交互環(huán)境嵌入系統(tǒng)環(huán)境為了提高軟件開(kāi)發(fā)的效率和保證質(zhì)量，人們除了要在軟件工程中對(duì)軟件開(kāi)發(fā)過(guò)程所要遵循的規(guī)范化或標(biāo)準(zhǔn)化外，還盡量使用先進(jìn)的軟件開(kāi)發(fā)技術(shù)和相應(yīng)的軟件工具，而大部分

4、軟件工具的開(kāi)發(fā)，常常要用到編譯技術(shù)和方法。實(shí)際上編譯程序本身也是一種軟件開(kāi)發(fā)工具。為了提高編程效率，縮短調(diào)試時(shí)間，軟件工作人員研制了不少對(duì)源程序處理的工具。這些工具的開(kāi)發(fā)不同程度地用到編譯技術(shù)和方法。下面僅是一些例子。1、語(yǔ)言的結(jié)構(gòu)化編輯器 結(jié)構(gòu)化編輯器是引導(dǎo)用戶(hù)在語(yǔ)言的語(yǔ)法制導(dǎo)下編制程序，能自動(dòng)地提供關(guān)鍵字和與其匹配的關(guān)鍵字，如if后必須有then，begin和end的配對(duì)，左右括號(hào)的配對(duì)等，這樣可以減少語(yǔ)法上的錯(cuò)誤，可加快對(duì)源程序的調(diào)試，提高效率和質(zhì)量。2、語(yǔ)言程序的調(diào)試工具 調(diào)試是軟件開(kāi)發(fā)過(guò)程中一個(gè)重要環(huán)節(jié)，結(jié)構(gòu)化編輯器只能解決語(yǔ)法錯(cuò)誤的問(wèn)題，而對(duì)一個(gè)已通過(guò)編譯的程序來(lái)說(shuō)，需進(jìn)一步了解的

5、是程序執(zhí)行的結(jié)果與編程人員的意圖是否一致，程序的執(zhí)行是否實(shí)現(xiàn)預(yù)計(jì)的算法和功能。這種對(duì)算法的錯(cuò)誤或程序沒(méi)能反應(yīng)算法的功能等錯(cuò)誤就需用調(diào)試器來(lái)協(xié)助解決。調(diào)試器的功能愈強(qiáng)，實(shí)現(xiàn)愈復(fù)雜，但它必須與語(yǔ)法分析、語(yǔ)義處理有緊密聯(lián)系。3、語(yǔ)言程序測(cè)試工具 語(yǔ)言程序的測(cè)試工具有兩種：靜態(tài)分析器和動(dòng)態(tài)測(cè)試器靜態(tài)分析器是對(duì)源程序進(jìn)行靜態(tài)地分析。它對(duì)源程序進(jìn)行語(yǔ)法分析并制定相應(yīng)表格，檢查變量定值與引用的關(guān)系。如某變量未被賦值就被引用，或定值后未被引用，或多余的源代碼等一些編譯程序的語(yǔ)法分析發(fā)現(xiàn)不了的錯(cuò)誤。動(dòng)態(tài)測(cè)試工具是在源程序的適當(dāng)位置插入某些信息，并用測(cè)試用例記錄(顯示語(yǔ)句或函數(shù))程序運(yùn)行時(shí)的實(shí)際路徑。將運(yùn)行結(jié)果與

6、期望的結(jié)果進(jìn)行比較分析，幫助編程人員查找問(wèn)題。這種測(cè)試工具在國(guó)內(nèi)已有開(kāi)發(fā)，如FORTRAN語(yǔ)言和C語(yǔ)言的測(cè)試工具。4、高級(jí)語(yǔ)言之間的轉(zhuǎn)換工具 由于計(jì)算機(jī)硬件的不斷更新?lián)Q代，更新更好的程序設(shè)計(jì)語(yǔ)言的推出為提高計(jì)算機(jī)的使用效率提供了良好條件，然而一些已有的非常成熟的軟件如何在新機(jī)器新語(yǔ)言情況下使用呢?為了減少重新編制程序所耗費(fèi)的人力和時(shí)間，就要解決如何把一種高級(jí)語(yǔ)言轉(zhuǎn)換成另一種高級(jí)語(yǔ)言，乃至匯編語(yǔ)言轉(zhuǎn)換成高級(jí)語(yǔ)言的問(wèn)題。這種轉(zhuǎn)換工作要對(duì)被轉(zhuǎn)換的語(yǔ)言進(jìn)行詞法和語(yǔ)法分析，只不過(guò)生成的目標(biāo)語(yǔ)言是另一種高級(jí)語(yǔ)言而已。這與實(shí)現(xiàn)一個(gè)完整的編譯程序相比工作量要少些。在國(guó)內(nèi)已研制出C，PASCAL，F(xiàn)ORTRAN

7、到Ada的翻譯器和IBM 4700匯編到C的轉(zhuǎn)換器，其效果很好。近年來(lái),由于JAVA語(yǔ)言的發(fā)展,國(guó)內(nèi)外也已研制出不少其他語(yǔ)言到JAVA的轉(zhuǎn)換系統(tǒng),如c到JAVA的轉(zhuǎn)換系統(tǒng),cobol到JAVA的轉(zhuǎn)換系統(tǒng)等等。 編譯實(shí)現(xiàn)方式的發(fā)展主要分一下五類(lèi)：手工、機(jī)器語(yǔ)言、匯編、系統(tǒng)程序設(shè)計(jì)語(yǔ)言、自動(dòng)構(gòu)造工具lex yacc gcc。推動(dòng)編譯技術(shù)發(fā)展的因素主要包括:語(yǔ)言范型（計(jì)算模式）、計(jì)算機(jī)體系結(jié)構(gòu)語(yǔ)言范型主要包括:命令式(imperative language) 、應(yīng)用式(applicative) 、基于規(guī)則的（rule-based）、面向?qū)ο蟮模╫bject-oriented）、并行計(jì)算(parall

8、el computing)。體系結(jié)構(gòu)主要包括:萬(wàn)諾曼機(jī)體系結(jié)構(gòu)、并行體系結(jié)構(gòu)、嵌入系統(tǒng)。編譯程序執(zhí)行環(huán)境主要包括:批處理、交互環(huán)境、嵌入系統(tǒng)環(huán)境、并行編譯技術(shù)、交叉編譯。 編譯程序在一個(gè)機(jī)器（宿主機(jī)）上運(yùn)行，產(chǎn)生另一個(gè)機(jī)器（目標(biāo)機(jī)）的匯編語(yǔ)言。嵌入式系統(tǒng)中的應(yīng)用程序正是借助這樣的編譯程序生成。目標(biāo)處理器MIPSX是MIPS系列芯片的種，屬于RISC體系結(jié)構(gòu)，來(lái)源于斯坦福大學(xué)的MIPS計(jì)劃。由于該系列CPU不是采用加州大學(xué)伯克利分校的RISC窗口技術(shù)而是采用消除流水線各級(jí)互鎖的微處理器MIPS(MicroprocessorWithout Interlocking Pipeline Stage)技

9、術(shù)，因此而得名。MIPS是將IBM公司對(duì)優(yōu)化編譯程序的研究和加州大學(xué)伯克利分校的大規(guī)模集成電路的思想結(jié)合起來(lái)的產(chǎn)品。  由于RISC指令集的簡(jiǎn)單和整齊，為了達(dá)到更好地利用計(jì)算機(jī)的性能，MIPS系列芯片中很好地應(yīng)用了流水線策略。流水線是現(xiàn)代各類(lèi)微處理器都采用的指令執(zhí) 行技巧，即將若干條指令的取指、譯碼和執(zhí)行過(guò)程部分重疊在流水線中同時(shí)執(zhí)行。以前在CISC計(jì)算機(jī)中，由于指令多而復(fù)雜，處理每條指令的所需時(shí)間不固定， 當(dāng)后面指令需要前條指令的結(jié)果時(shí)，往往造成指令互鎖，因此無(wú)法實(shí)現(xiàn)流水線。而斯坦福大學(xué)的MIPS計(jì)劃就是在編譯的過(guò)程中，利用編譯程序優(yōu)化處理器的流水 線以求提高處理器流水線的效率。由

10、于采用了硬件連線控制來(lái)執(zhí)行數(shù)目不多的簡(jiǎn)單指令，而且還能重組軟件流水線，這樣就減少了硬件復(fù)雜性。但是由于存在數(shù)據(jù)和指令轉(zhuǎn)移的相關(guān)性，這會(huì)引起流水線的停頓，降低流水線整體的執(zhí)行速率。為了調(diào)整這些相關(guān)性，又開(kāi)發(fā)出了代碼重組技術(shù)，其中一種是延遲轉(zhuǎn)移(delayed branch)，另一種叫延遲裝入，提升了性能。 MIPS公司的R系列就是在此基礎(chǔ)上開(kāi)發(fā)的RISC工業(yè)產(chǎn)品的微處理器。這些系列產(chǎn)品被很多計(jì)算機(jī)公司采用生產(chǎn)各種工作站和計(jì)算機(jī)系統(tǒng)。R系 列遵循按比例提高性能設(shè)計(jì)技術(shù)，按不同工藝技術(shù)實(shí)現(xiàn)基本相同的體系結(jié)構(gòu)，其適用范圍從低端的嵌入式控制器、個(gè)人計(jì)算機(jī)到高端的超級(jí)小型機(jī)、服務(wù)器甚至大型 機(jī)和

11、巨型機(jī)，而且系統(tǒng)軟件和應(yīng)用程序都是兼容的。MIPS公司在1986年推出82000處理器，1988年推出83000處理器，1991年推出第一款 64位商用微處理器84000。之后，又陸續(xù)推出88000(于1994年)、810000(于1996年)和812000(于1997年)等型號(hào)。 1999年，MIPS公司發(fā)布MIPS 32和MIPS 64架構(gòu)標(biāo)準(zhǔn)。2000年，MIPS公司發(fā)布了針對(duì)MIPS 32 4Kc的新版本以及未來(lái)64位MIPS 64 20Kc處理器內(nèi)核。 在整個(gè)R系列中82000/82010是最基礎(chǔ)的原型;83000/83010是82000/82010的增強(qiáng)型產(chǎn)品;由于840

12、00采用高 精度的CMOS工藝，因此其性能很高，用途很廣;而86000/86010是ECL電路化的高速品種，但是由于86000/86010的功耗大，成本高， 所以其應(yīng)用受到很大限制。但是MIPSX并不屬于以上提到的CPU中的任何一種，它是由20世紀(jì)80年代后期由美國(guó)國(guó)防部高級(jí)研究項(xiàng)目署(DARPA)資 助的一個(gè)項(xiàng)目的成果。因此，基于MIPSX的交叉編譯工具鏈研究雖然現(xiàn)有的GNU交叉編譯工具鏈對(duì)MIPS公司R系列芯片的支持很好，但還是缺乏對(duì) MIPSX的有效支持，所以還是需要進(jìn)行移植。進(jìn)行移植工作前，必須首先了解MIPSX的體系結(jié)構(gòu)。經(jīng)過(guò)實(shí)驗(yàn)室前幾屆師兄的分析，我們得知MIPSX的體 系結(jié)構(gòu)與M

13、IPS公司R系列芯片中的82000最為接近，當(dāng)然它們?cè)诤芏嗟胤竭€是存在著差別，比如具體指令集的不同，比如MIPSX沒(méi)有浮點(diǎn)操 作;MIPSX指令的基本操作碼只占5位;MIPSX在跳轉(zhuǎn)指令中的延時(shí)槽有兩條等。簡(jiǎn)單講，編譯器就是將“一種語(yǔ)言（通常為高級(jí)語(yǔ)言）”翻譯為“另一種語(yǔ)言（通常為低級(jí)語(yǔ)言）”的程序。一個(gè)現(xiàn)代編譯器的主要工作流程：源代碼 (source code) 預(yù)處理器 (preprocessor) 編譯器 (compiler) 目標(biāo)代碼 (object code) 鏈接器 (Linker) 可執(zhí)行程序 (executables)高級(jí)計(jì)算機(jī)語(yǔ)言便于人編寫(xiě)，閱讀交流，維護(hù)。機(jī)器語(yǔ)言是計(jì)算機(jī)能

14、直接解讀、運(yùn)行的。編譯器將匯編或高級(jí)計(jì)算機(jī)語(yǔ)言源程序（Source program）作為輸入，翻譯成目標(biāo)語(yǔ)言（Target language）機(jī)器代碼的等價(jià)程序。源代碼一般為高級(jí)語(yǔ)言 (High-level language)， 如Pascal、C、C+、Java、漢語(yǔ)編程等或匯編語(yǔ)言，而目標(biāo)則是機(jī)器語(yǔ)言的目標(biāo)代碼（Object code），有時(shí)也稱(chēng)作機(jī)器代碼（Machine code）。對(duì)于C#、VB等高級(jí)語(yǔ)言而言，此時(shí)編譯器完成的功能是把源碼（SourceCode）編譯成通用中間語(yǔ)言（MSIL/CIL）的字節(jié)碼（ByteCode）。最后運(yùn)行的時(shí)候通過(guò)通用語(yǔ)言運(yùn)行庫(kù)的轉(zhuǎn)換，編程最終可以被CP

15、U直接計(jì)算的機(jī)器碼（NativeCode）。在20世紀(jì)40年代，由于馮·諾伊曼在存儲(chǔ)-程序編譯原理實(shí)驗(yàn)程序計(jì)算機(jī)方面的先鋒作用，編寫(xiě)一串代碼或程序已成必要，這樣計(jì)算機(jī)就可以執(zhí)行所需的計(jì)算。開(kāi)始時(shí)，這些程序都是用機(jī)器語(yǔ)言 （machine language ）編寫(xiě)的。機(jī)器語(yǔ)言就是表示機(jī)器實(shí)際操作的數(shù)字代碼，例如：C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86處理器將數(shù)字2移至地址0 0 0 0 （16進(jìn)制）的指令。但編寫(xiě)這樣的代碼是十分費(fèi)時(shí)和乏味的，這種代碼形式很快就被匯編語(yǔ)言（assembly language ）代替了。在匯編語(yǔ)言中，都是

16、以符號(hào)形式給出指令和存儲(chǔ)地址的。例如，匯編語(yǔ)言指令 MOV X,2 就與前面的機(jī)器指令等價(jià)（假設(shè)符號(hào)存儲(chǔ)地址X是0 0 0 0 ）。匯編程序（assembler ）將匯編語(yǔ)言的符號(hào)代碼和存儲(chǔ)地址翻譯成與機(jī)器語(yǔ)言相對(duì)應(yīng)的數(shù)字代碼。匯編語(yǔ)言大大提高了編程的速度和準(zhǔn)確度，人們至今仍在使用著它，在編碼需要極快的速度和極高的簡(jiǎn)潔程度時(shí)尤為如此。但是，匯編語(yǔ)言也有許多缺點(diǎn)：編寫(xiě)起來(lái)也不容易，閱讀和理解很難；而且匯編語(yǔ)言的編寫(xiě)嚴(yán)格依賴(lài)于特定的機(jī)器，所以為一臺(tái)計(jì)算機(jī)編寫(xiě)的代碼在應(yīng)用于另一臺(tái)計(jì)算機(jī)時(shí)必須完全重寫(xiě)。發(fā)展編程技術(shù)的下一個(gè)重要步驟就是以一個(gè)更類(lèi)似于數(shù)學(xué)定義或自然語(yǔ)言的簡(jiǎn)潔形式來(lái)編寫(xiě)程序的操作，它應(yīng)與任

17、何機(jī)器都無(wú)關(guān)，而且也可由一個(gè)程序翻譯為可執(zhí)行的代碼。例如，前面的匯編語(yǔ)言代碼可以寫(xiě)成一個(gè)簡(jiǎn)潔的與機(jī)器無(wú)關(guān)的形式 x = 2。在1954年至1957年期間，IBM的John Backus帶領(lǐng)的一個(gè)研究小組對(duì)FORTRAN語(yǔ)言及其編譯器的開(kāi)發(fā)，使得上面的擔(dān)憂(yōu)不必要了。但是，由于當(dāng)時(shí)處理中所涉及到的大多數(shù)程序設(shè)計(jì)語(yǔ)言的翻譯并不為人所掌握，所以這個(gè)項(xiàng)目的成功也伴隨著巨大的辛勞。幾乎與此同時(shí)，人們也在開(kāi)發(fā)著第一個(gè)編譯器， Noam Chomsky開(kāi)始了他的自然語(yǔ)言結(jié)構(gòu)的研究。他的發(fā)現(xiàn)最終使得編譯器結(jié)構(gòu)異常簡(jiǎn)單，甚至還帶有了一些自動(dòng)化。Chomsky的研究導(dǎo)致了根據(jù)語(yǔ)言文法（grammar ，指定其結(jié)構(gòu)的

18、規(guī)則）的難易程度以及識(shí)別它們所需的算法來(lái)為語(yǔ)言分類(lèi)。正如現(xiàn)在所稱(chēng)的-與喬姆斯基分類(lèi)結(jié)構(gòu)（Chomsky hierarchy ）一樣-包括了文法的4個(gè)層次：0型、1型、2型和3型文法，且其中的每一個(gè)都是其前者的專(zhuān)門(mén)化。2型（或上下文無(wú)關(guān)文法（context-free grammar ）被證明是程序設(shè)計(jì)語(yǔ)言中最有用的，而且今天它已代表著程序設(shè)計(jì)語(yǔ)言結(jié)構(gòu)的標(biāo)準(zhǔn)方式。分析問(wèn)題（ parsing problem ，用于限定上下文無(wú)關(guān)語(yǔ)言的識(shí)別的有效算法）的研究是在20世紀(jì)60年代和70年代，它相當(dāng)完善地解決了這一問(wèn)題， 現(xiàn)在它已是編譯理論的一個(gè)標(biāo)準(zhǔn)部分。它們與喬姆斯基的3型文法相對(duì)應(yīng)。對(duì)它們的研究與喬姆

19、斯基的研究幾乎同時(shí)開(kāi)始，并且引出了表示程序設(shè)計(jì)語(yǔ)言的單詞（或稱(chēng)為記號(hào)）的符號(hào)方式。人們接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其誤稱(chēng)為優(yōu)化技術(shù)（optimization technique ），但因其從未真正地得到過(guò)被優(yōu)化了的目標(biāo)代碼而僅僅改進(jìn)了它的有效性，因此實(shí)際上應(yīng)稱(chēng)作代碼改進(jìn)技術(shù)（code improvement technique ）。這些程序最初被稱(chēng)為編譯程序-編譯器，但更確切地應(yīng)稱(chēng)為分析程序生成器 （parser generator ），這是因?yàn)樗鼈儍H僅能夠自動(dòng)處理編譯的一部分。這些程序中最著名的是 Yacc （y

20、et another compiler- compiler），它是由Steve Johnson在1975年為Unix系統(tǒng)編寫(xiě)的。類(lèi)似地，有窮自動(dòng)機(jī)的研究也發(fā)展了另一種稱(chēng)為掃描程序生成器 （scanner generator ）的工具，Lex （與Yacc同時(shí)，由Mike Lesk為Unix系統(tǒng)開(kāi)發(fā)的）是這其中的佼佼者。在20世紀(jì)70年代后期和80年代早期，大量的項(xiàng)目都關(guān)注于編譯器其他部分的生成自動(dòng)化，這其中就包括代碼生成。這些嘗試并未取得多少成功，這大概是因?yàn)椴僮魈珡?fù)雜而人們又對(duì)其不甚了解。編譯器設(shè)計(jì)最近的發(fā)展包括：首先，編譯器包括了更為復(fù)雜的算法的應(yīng)用程序，它用于推斷或簡(jiǎn)化程序中的

21、信息；這又與更為復(fù)雜的程序設(shè)計(jì)語(yǔ)言（可允許此類(lèi)分析）的發(fā)展結(jié)合在一起。其中典型的有用于函數(shù)語(yǔ)言編譯的Hindle y - Milner類(lèi)型檢查的統(tǒng)一算法。其次，編譯器已越來(lái)越成為基于窗口的交互開(kāi)發(fā)環(huán)境（interactive development environment，IDE ）的一部 分，它包括了編輯器、鏈接程序、調(diào)試程序以及項(xiàng)目管理程序。這樣的IDE的標(biāo)準(zhǔn)并沒(méi)有多少， 但是已沿著這一方向?qū)?biāo)準(zhǔn)的窗口環(huán)境進(jìn)行開(kāi)發(fā)了。 編輯器（editor）：編譯器通常接受由任何生成標(biāo)準(zhǔn)文件（例如ASCII文件）的編輯器編寫(xiě)的源程序。現(xiàn)在， 編譯器已與另一個(gè)編輯器和其他程序捆綁進(jìn)一個(gè)交互的開(kāi)發(fā)環(huán)境-IDE

22、中。此時(shí)，盡管編輯器仍然生成標(biāo)準(zhǔn)文件，但會(huì)轉(zhuǎn)向正被討論的程序設(shè)計(jì)語(yǔ)言的格式或結(jié)構(gòu)。這樣的編輯器稱(chēng)為基于結(jié)構(gòu)的（structure based ），且它早已包括了編譯器的某些操作；因此，程序員就會(huì)在程序的編寫(xiě)時(shí)而不是在編譯時(shí)就得知錯(cuò)誤了。從編輯器中也可調(diào)用編譯器以及與它共用的程序，這樣程序員無(wú)需離開(kāi)編輯器就可執(zhí)行程序。編譯原理是計(jì)算機(jī)專(zhuān)業(yè)的一門(mén)重要專(zhuān)業(yè)課，旨在介紹編譯程序構(gòu)造的一般原理和基本方法。內(nèi)容包括語(yǔ)言和文法、詞法分析、語(yǔ)法分析、語(yǔ)法制導(dǎo)翻譯、中間代碼生成、存儲(chǔ)管理、代碼優(yōu)化和目標(biāo)代碼生成。 編譯原理是計(jì)算機(jī)專(zhuān)業(yè)設(shè)置的一門(mén)重要的專(zhuān)業(yè)課程。雖然只有少數(shù)人從事編譯方面的工作，但是這門(mén)課在理論、

23、技術(shù)、方法上都對(duì)學(xué)生提供了系統(tǒng)而有效的訓(xùn)練，有利于提高軟件人員的素質(zhì)和能力。 目前各個(gè)大學(xué)使用的教材機(jī)械工業(yè)出版社、國(guó)防工業(yè)出版社出版的編譯原理。大學(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ě)一

24、直被認(rèn)為是十分困難的事情，第一Fortran的編譯器據(jù)說(shuō)花了18年的時(shí)間才完成。在人們嘗試編寫(xiě)編譯器的同時(shí)，誕生了許多跟編譯相關(guān)的理論和技術(shù)，而這些理論和技術(shù)比一個(gè)實(shí)際的編譯器本身價(jià)值更大。就猶如數(shù)學(xué)家們?cè)诮鉀Q著名的哥德巴赫猜想一樣，雖然沒(méi)有最終解決問(wèn)題，但是其間誕生不少名著的相關(guān)數(shù)論。推薦參考書(shū)雖然編譯理論發(fā)展到今天，已經(jīng)有了比較成熟的部分，但是作為一個(gè)大學(xué)生來(lái)說(shuō)，要自己寫(xiě)出一個(gè)像TurbocC,Java那樣的編譯器來(lái)說(shuō)還是太難了。不僅寫(xiě)編譯器困難，學(xué)習(xí)編譯原理這門(mén)課程也比較困難。第一本書(shū)的原名叫CompilersPrinciples,Techniques,andTools,另外一個(gè)響亮的名

25、字就是龍書(shū)。原因是這本書(shū)的封面上有條紅色的龍，也因?yàn)殁本书栽r嘁朐?砘?嘴域確實(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)，讓很多編譯原理的初學(xué)者很快心里有了個(gè)底,也知道為什么會(huì)有這些理論，怎么運(yùn)用這些理論。而這一點(diǎn)是我感覺(jué)國(guó)內(nèi)的教材缺乏的東西，所以國(guó)內(nèi)的教材都不是寫(xiě)給愿意自學(xué)的讀者，總之讓人看了半天，卻不

26、知道里面的東西有什么用。第二本書(shū)的原名叫ModernCompilerDesign,中文名字叫做現(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í)編譯原理的理論知識(shí)，那么你肯定得看前面那本龍書(shū)，如果你想自己動(dòng)手做一個(gè)先進(jìn)的編譯器，那么你得看這本現(xiàn)代編譯程序設(shè)計(jì)。第三本書(shū)就是很多國(guó)內(nèi)的編譯原理學(xué)者都推薦的那本編譯原理及實(shí)踐。或許是這本書(shū)

27、引入國(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è)部分的同時(shí)，也在逐步實(shí)踐一個(gè)現(xiàn)代的編譯器TinyC.等你把整本書(shū)看完，差不多自己也可以寫(xiě)一個(gè)TinyC了。作者還對(duì)Lex和Yacc這兩個(gè)常用的編譯相關(guān)的工具進(jìn)行了很詳細(xì)的說(shuō)明，這一點(diǎn)也是很

28、難在國(guó)內(nèi)的教材中看到的。推薦了這三本教材，都有英文版和中文版的。很多英文好的同學(xué)只喜歡看原版的書(shū)，不我的感覺(jué)是這三本書(shū)的翻譯都很不錯(cuò)，沒(méi)有必要特別去買(mǎi)英文版的。理解理論的實(shí)質(zhì)比理解表面的文字更為重要。編譯原理的實(shí)質(zhì)幾乎每本編譯原理的教材都是分成詞法分析，語(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)真講完的，而是比較偏重于前面幾

29、個(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)很簡(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)了。現(xiàn)在一般有兩種語(yǔ)法分析算法，LL自頂向下算法和LR自底向上算法。LL算法還好說(shuō)，到了LR

30、算法的時(shí)候，困難就來(lái)了。很多自學(xué)編譯原理的都是遇到LR算法的理解成問(wèn)題后就放棄了自學(xué)。其實(shí)這些東西都是只要大家理解就可以了，又不是像詞法分析那樣非得自己寫(xiě)出來(lái)才算真正的會(huì)。像LR算法的語(yǔ)法分析器，一般都是用工具Yacc來(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)講

31、，編譯器需要把程序員寫(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ǔ)法分析的過(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)中有

32、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。這一點(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ǔ)言中。

33、像現(xiàn)在流行的Java,.NET，其底層的字節(jié)碼bytecode,可以說(shuō)就是這中基于堆棧的指令代碼的。關(guān)于語(yǔ)義分析，語(yǔ)法制導(dǎo)翻譯，類(lèi)型檢查等等部分，其實(shí)都是一種完善前面得到的抽象語(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ù)輸入的源程序到最終的代碼生成。但是

34、在講解最終代碼生成的時(shí)候，又不得不講解機(jī)器運(yùn)行環(huán)境等內(nèi)容。因?yàn)槿绻悴恢罊C(jī)器是怎么執(zhí)行最終代碼的，那么你當(dāng)然無(wú)法知道如何生成合適的最終代碼。這部分內(nèi)容我自我感覺(jué)其意義甚至超過(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ō)明

35、。這些東西都是我們編寫(xiě)平常程序的時(shí)候經(jīng)常要做的事情，但是我們卻少去探求其內(nèi)部是如何完成。關(guān)于中間代碼生成，代碼生成,代碼優(yōu)化部分的內(nèi)容就實(shí)在不好說(shuō)了。國(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í)另外還有本叫做AdvanceComp

36、ilerDesginandImplement,那本書(shū)現(xiàn)在由機(jī)械工業(yè)出版社引進(jìn)的，十分厚重，而且是英文原版。不過(guò)這本書(shū)我沒(méi)有把它列為推薦書(shū)給大家，畢竟能把龍書(shū)的內(nèi)容搞清楚，在中國(guó)已經(jīng)就算很不錯(cuò)的高手了，到那個(gè)時(shí)候再看這本AdvanceCompilerDesginandImplement也不遲。代碼優(yōu)化部分在大學(xué)本科教學(xué)中還是一個(gè)不太重要的部分，就是算是實(shí)踐過(guò)程中，相信大家也不太運(yùn)用得到。畢竟，自己做的編譯器能正確生成執(zhí)行代碼已經(jīng)很不錯(cuò)了，還談什么優(yōu)化呢？編譯原理的課程畢竟還只是講解原理的課程，不是專(zhuān)門(mén)的編譯技術(shù)課程。這兩門(mén)課程是有很大的區(qū)別的。編譯技術(shù)更關(guān)注實(shí)際的編寫(xiě)編譯器過(guò)程中運(yùn)用到的技術(shù)，而原理的課第一個(gè)編譯程序的出現(xiàn)是在20世紀(jì)50年代早期，很難講出確切的時(shí)間，因?yàn)楫?dāng)初大量的實(shí)驗(yàn)和實(shí)現(xiàn)工作是由不同的小組獨(dú)立完成的，多數(shù)早期的編譯工作是將