編譯原理是計算機(jī)專業(yè)的一門重要專業(yè)課，旨在介紹編譯程序構(gòu)造的一般原理和基本方法。內(nèi)容包括語言和文法、詞法分析、語法分析、語法制導(dǎo)翻譯、中間代碼生成、存儲管理、代碼優(yōu)化和目標(biāo)代碼生成。
編譯原理是計算機(jī)專業(yè)設(shè)置的一門重要的專業(yè)課程。雖然只有少數(shù)人從事編譯方面的工作，但是這門課在理論、技術(shù)、方法上都對學(xué)生提供了系統(tǒng)而有效的訓(xùn)練，有利于提高軟件人員的素質(zhì)和能力。目前各個大學(xué)使用的教材機(jī)械工業(yè)出版社、國防工業(yè)出版社出版的《編譯原理》。
基本概念
編譯器是將匯編或高級計算機(jī)語言翻譯為二進(jìn)制機(jī)器語言代碼的計算機(jī)程序。編譯器將源程序（source language）編寫的程序作為輸入，翻譯產(chǎn)生目標(biāo)語言（target language）機(jī)器代碼的等價程序。通常地，源程序為高級語言（high-level language），像C或C++、漢語語言程序等，而目標(biāo)則是機(jī)器語言的目標(biāo)代碼（object code，有時也稱作機(jī)器代碼（machine code）），也就是可以在計算機(jī)硬件中運(yùn)行的機(jī)器代碼軟件。這一過程可以表示為：
源程序→編譯器→目標(biāo)機(jī)器代碼程序
發(fā)展歷程
在20世紀(jì)40年代，由于約翰·馮·諾依曼在存儲-程序計算機(jī)方面的先鋒作用，編寫一串代碼或程序已成必要，這樣計算機(jī)就可以執(zhí)行所需的計算。開始時，這些程序都是用機(jī)器語言（machine language ）編寫的。機(jī)器語言就是表示機(jī)器實(shí)際操作的數(shù)字代碼，例如：
C7 06 0000 0002 表示在IBM PC 上使用的英特爾 8x86處理器將數(shù)字2移至地址0 0 0 0 （16進(jìn)制）的指令。
但編寫這樣的代碼是十分費(fèi)時和乏味的，這種代碼形式很快就被匯編語言（assembly language ）代替了。在匯編語言中，都是以符號形式給出指令和存儲地址的。例如，匯編語言指令 MOV X,2 就與前面的機(jī)器指令等價（假設(shè)符號存儲地址X是0 0 0 0 ）。匯編程序（assembler ）將匯編語言的符號代碼和存儲地址翻譯成與機(jī)器語言相對應(yīng)的數(shù)字代碼。
匯編語言大大提高了編程的速度和準(zhǔn)確度，人們至今仍在使用著它，在編碼需要極快的速度和極高的簡潔程度時尤為如此。但是，匯編語言也有許多缺點(diǎn)：編寫起來也不容易，閱讀和理解很難；而且匯編語言的編寫嚴(yán)格依賴于特定的機(jī)器，所以為一臺計算機(jī)編寫的代碼在應(yīng)用于另一臺計算機(jī)時必須完全重寫。
發(fā)展編程技術(shù)的下一個重要步驟就是以一個更類似于數(shù)學(xué)定義或自然語言的簡潔形式來編寫程序的操作，它應(yīng)與任何機(jī)器都無關(guān)，而且也可由一個程序翻譯為可執(zhí)行的代碼。例如，前面的匯編語言代碼可以寫成一個簡潔的與機(jī)器無關(guān)的形式 x = 2。
在1954年至1957年期間，IBM的John Backus帶領(lǐng)的一個研究小組對Fortran及其編譯器的開發(fā)，使得上面的擔(dān)憂不必要了。但是，由于當(dāng)時處理中所涉及到的大多數(shù)程序設(shè)計語言的翻譯并不為人所掌握，所以這個項目的成功也伴隨著巨大的辛勞。幾乎與此同時，人們也在開發(fā)著第一個編譯器， Noam Chomsky開始了他的自然語言結(jié)構(gòu)的研究。他的發(fā)現(xiàn)最終使得編譯器結(jié)構(gòu)異常簡單，甚至還帶有了一些自動化。Chomsky的研究導(dǎo)致了根據(jù)語言文法（grammar ，指定其結(jié)構(gòu)的規(guī)則）的難易程度以及識別它們所需的算法來為語言分類。正如現(xiàn)在所稱的-與諾姆·喬姆斯基分類結(jié)構(gòu)（Chomsky hierarchy ）一樣-包括了文法的4個層次：0型、1型、2型和3型文法，且其中的每一個都是其前者的專門化。2型（或上下文無關(guān)文法（context-free grammar ））被證明是程序設(shè)計語言中最有用的，而且今天它已代表著程序設(shè)計語言結(jié)構(gòu)的標(biāo)準(zhǔn)方式。
分析問題（ parsing problem ，用于限定上下文無關(guān)語言的識別的有效算法）的研究是在20世紀(jì)60年代和70年代，它相當(dāng)完善地解決了這一問題，現(xiàn)在它已是編譯理論的一個標(biāo)準(zhǔn)部分。它們與諾姆·喬姆斯基的3型文法相對應(yīng)。對它們的研究與喬姆斯基的研究幾乎同時開始，并且引出了表示程序設(shè)計語言的單詞（或稱為記號）的符號方式。
人們接著又深化了生成有效的目標(biāo)代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其誤稱為優(yōu)化技術(shù)（optimization technique ），但因其從未真正地得到過被優(yōu)化了的目標(biāo)代碼而僅僅改進(jìn)了它的有效性，因此實(shí)際上應(yīng)稱作代碼改進(jìn)技術(shù)（code improvement technique ）。
這些程序最初被稱為編譯計算機(jī)程序編譯器，但更確切地應(yīng)稱為分析程序生成器（parser generator ），這是因為它們僅僅能夠自動處理編譯的一部分。這些程序中最著名的是 Yacc （yet another 編譯器- compiler），它是由Steve Johnson在1975年為unix系統(tǒng)編寫的。
類似地，有窮自動機(jī)的研究也發(fā)展了另一種稱為掃描程序生成器（掃描儀 generator ）的工具，Lex （與Yacc同時，由Mike Lesk為Unix系統(tǒng)開發(fā)的）是這其中的佼佼者。在20世紀(jì)70年代后期和80年代早期，大量的項目都關(guān)注于編譯器其他部分的生成自動化，這其中就包括代碼生成。這些嘗試并未取得多少成功，這大概是因為操作太復(fù)雜而人們又對其不甚了解。
編譯器設(shè)計最近的發(fā)展包括：首先，編譯器包括了更為復(fù)雜的算法的應(yīng)用程序，它用于推斷或簡化程序中的信息；這又與更為復(fù)雜的程序設(shè)計語言（可允許此類分析）的發(fā)展結(jié)合在一起。其中典型的有用于函數(shù)語言編譯的Hindle y - Milner類型檢查的統(tǒng)一算法。
其次，編譯器已越來越成為基于窗口的交互集成開發(fā)環(huán)境（interactive development environment，IDE ）的一部 分，它包括了編輯器、鏈接程序、調(diào)試程序以及項目管理程序。這樣的集成開發(fā)環(huán)境的標(biāo)準(zhǔn)并沒有多少，但是已沿著這一方向?qū)?biāo)準(zhǔn)的窗口環(huán)境進(jìn)行開發(fā)了。
編譯器
c語言編譯器是一種現(xiàn)代化的設(shè)備，其需要借助計算機(jī)編譯程序，C語言編譯器的設(shè)計是一項專業(yè)性比較強(qiáng)的工作，設(shè)計人員需要考慮計算機(jī)程序繁瑣的設(shè)計流程，還要考慮計算機(jī)用戶的需求。計算機(jī)的種類在不斷增加，所以，在對C語言編譯器進(jìn)行設(shè)計時，一定要增加其適用性。C語言具有較強(qiáng)的處理能力，其屬于結(jié)構(gòu)化語言，而且在計算機(jī)系統(tǒng)維護(hù)中應(yīng)用比較多，C語言具有高效率的優(yōu)點(diǎn)，在其不同類型的計算機(jī)中應(yīng)用比較多。
C語言編譯器前端設(shè)計
編譯過程一般是在計算機(jī)系統(tǒng)中實(shí)現(xiàn)的，是將源代碼轉(zhuǎn)化為計算機(jī)通用語言的過程。編譯器中包含入口點(diǎn)的地址、名稱以及機(jī)器代碼。編譯器是計算機(jī)程序中應(yīng)用比較多的工具，在對編譯器進(jìn)行前端設(shè)計時，一定要充分考慮影響因素，還要對詞法、語法、語義進(jìn)行分析。
1.詞法分析
詞法分析是編譯器前端設(shè)計的基礎(chǔ)階段，在這一階段，編譯器會根據(jù)設(shè)定的語法規(guī)則，對源程序進(jìn)行標(biāo)記，在標(biāo)記的過程中，每一處記號都代表著一類單詞，在做記號的過程中，主要有標(biāo)識符、關(guān)鍵字、特殊符號等類型，編譯器中包含詞法分析器、輸入源程序、輸出識別記號符，利用這些功能可以將字號轉(zhuǎn)化為熟悉的單詞。
2.語法分析
語法分析是指利用設(shè)定的語法規(guī)則，對記號中的結(jié)構(gòu)進(jìn)行標(biāo)識，這包括句子、短語等方式，在標(biāo)識的過程中，可以形成特殊的結(jié)構(gòu)語法樹。語法分析對編譯器功能的發(fā)揮有著重要影響，在設(shè)計的過程中，一定要保證標(biāo)識的準(zhǔn)確性。
3.語義分析
語義分析也需要借助語法規(guī)則，在對語法單元的靜態(tài)語義進(jìn)行檢查時，要保證語法規(guī)則設(shè)定的準(zhǔn)確性。在對詞法或者語法進(jìn)行轉(zhuǎn)化時，一定要保證語法結(jié)構(gòu)設(shè)置的合法性。在對語法、詞法進(jìn)行檢查時，語法結(jié)構(gòu)設(shè)定不合理，則會出現(xiàn)編譯錯誤的問題。前端設(shè)計對精確性要求比較好，設(shè)計人員能夠要做好校對工作，這會影響到編譯的準(zhǔn)確性，如果前端設(shè)計存在失誤，則會影響c語言編譯的效果。
C語言編譯器總體設(shè)計
C語言編譯器是一種先進(jìn)的設(shè)備，其可以將繁瑣復(fù)雜的程序轉(zhuǎn)換為機(jī)器語言，具有化繁為簡的功能，在對C語言編譯器進(jìn)行劃分的過程中，需要了解語法構(gòu)成原理，設(shè)計人員需要靈活掌握語言語法知識，還要應(yīng)用C語言代碼轉(zhuǎn)化方式，在對C語言編譯器進(jìn)行總體設(shè)計時，需要從以下幾個方面入手。
1.詞法分析
C語言程序具有一定的復(fù)雜性，語法分析是編譯的初級階段，這一過程主要是對詞法進(jìn)行掃描，所以詞法分析階段，編譯器也被用作是掃描器，其主要的任務(wù)是將源程序中的字符進(jìn)行連接，并且對其中的詞語進(jìn)行識別，并且對詞匯進(jìn)行轉(zhuǎn)化，將其轉(zhuǎn)換為內(nèi)部編碼，并且對其語法進(jìn)行分析與標(biāo)記。單詞符號在編譯的過程中，一般會被轉(zhuǎn)化為二元式，單詞類別主要有二進(jìn)制、分隔符、單詞等，計算機(jī)在正常工作時，會通過掃描器自動完成詞法掃描工作，這一過程也會自動將注釋進(jìn)行刪除，會將源程序中的單詞進(jìn)行自動識別，還會將其轉(zhuǎn)換為內(nèi)部編碼。從工作方式角度來分析，編譯流程與語法屬于兩種接口方式，若是從功能上講，編譯器詞法分分析的過程主要就是將相應(yīng)的字符源程序進(jìn)行轉(zhuǎn)換處理，從而變成單詞串的形式。
2.語義分析
將編譯程序轉(zhuǎn)換為一種內(nèi)部表現(xiàn)形式后，我們將該種內(nèi)部表現(xiàn)形式稱之為中間語言或者是中間代碼，它含義明確、結(jié)構(gòu)簡單，屬于一種記號系統(tǒng)。比如一些編譯程序，基本上沒有中間代碼，但是為了在實(shí)際應(yīng)用中，確保機(jī)器的獨(dú)立運(yùn)行，易于實(shí)現(xiàn)目標(biāo)代碼的優(yōu)化，在許多的編譯程序中均設(shè)置了中間語言。這種中間語言介于機(jī)器語言和源程序語言中，程序相對復(fù)雜，而c語言編譯器卻在很大程度上改變以上現(xiàn)狀，其語義分析和語法分析相對成熟，理論和算法比較完善，可仍舊存在的問題是沒有公認(rèn)的形式系統(tǒng)，中間代碼仍舊接近于形式化的方法。
3.語法分析
語法分析主要是以單詞串形式的源程序作為分析與輸入對象，其最為根本的目標(biāo)和任務(wù)就是為了以設(shè)計語言的語法規(guī)則為標(biāo)準(zhǔn)，對源程序的語法結(jié)構(gòu)進(jìn)行具體的分析，根據(jù)設(shè)計語言的語法規(guī)則，對組成這些源程序的語法成分進(jìn)行分析，如函數(shù)、下標(biāo)變量、各種程序語句、各種表達(dá)式等等，并且要通過正確性的語法檢查，將中間代碼進(jìn)行階段處理。但是要注意的一點(diǎn)是根據(jù)需要進(jìn)行了歸約處理，必然存在著相應(yīng)語法錯誤，那么可以將其中全部輸入的符號刪除，改變上述格局，進(jìn)行移進(jìn)和歸約分析，并且在此基礎(chǔ)上，不斷地尋找一個相應(yīng)的策略，從而形成有效的語法分析方法。
編譯原理課程
《編譯原理》作為計算機(jī)專業(yè)的一門重要專業(yè)課程，是日后深入研究專業(yè)領(lǐng)域知識的基礎(chǔ)。這門課作為計算機(jī)科學(xué)與技術(shù)的專業(yè)課，融合了離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、計算機(jī)組成原理等多個學(xué)科的知識，屬于綜合性與理論性較強(qiáng)的一門課，由于編譯原理課程內(nèi)容的以上特點(diǎn)，目前在實(shí)驗教學(xué)中仍存在一些問題。編譯原理實(shí)驗部分若要設(shè)計制作完整的編譯器，實(shí)驗周期長，涉及的模塊較多，各模塊間銜接較復(fù)雜，不易立即看到整體效果。
傳統(tǒng)編譯原理課程教學(xué)中存在的問題
計算機(jī)類專業(yè)本科生學(xué)習(xí)本專業(yè)的第一門語言課程是c語言。C語言由于其類型不安全性，容易出現(xiàn)一些難以捉摸的錯誤，使得學(xué)生難以定位和解決問題。如果能讓學(xué)生根據(jù)編譯器提供的提示信息，精確定位程序中的錯誤類型和位置，把編譯原理中所學(xué)用于實(shí)際C語言編程需求，這既完成了課程的教學(xué)內(nèi)容，也提升了學(xué)生的軟件編程和系統(tǒng)分析的能力。
從普通高等院校的編譯原理教學(xué)實(shí)際出發(fā)，其課程覆蓋范圍一般僅限于編譯器的前端，即詞法分析、語法分析和語法制導(dǎo)翻譯等內(nèi)容。這其中包括大量抽象且邏輯復(fù)雜的理論知識點(diǎn)，如形式語言理論、正規(guī)式、有限自動機(jī)、上下文無關(guān)文法、屬性文法和語法制導(dǎo)翻譯等。傳統(tǒng)的教學(xué)方式強(qiáng)調(diào)知識點(diǎn)的灌輸，讓學(xué)生解決孤立的單一問題，缺乏各知識點(diǎn)之間的關(guān)聯(lián)。這種“只見樹木，不見森林”的教學(xué)方式會極大地削弱學(xué)生的學(xué)習(xí)積極性，導(dǎo)致整體效果不佳。
以實(shí)踐為導(dǎo)向的互助式編譯原理教學(xué)
(一) 理論與實(shí)踐相銜接
理論知識的來源一般都有其確定的問題背景。脫離實(shí)際問題來進(jìn)行理論教學(xué)，對學(xué)生實(shí)際能力的提升沒有益處。編譯原理課程中的大量理論知識，存在一種銜接遞進(jìn)的關(guān)系，每個知識點(diǎn)的引入和拓展，都是對于現(xiàn)實(shí)遇到問題的解決路徑再現(xiàn)。因此，整個授課過程就在重現(xiàn)這種解決方案演變的變化歷程。而實(shí)現(xiàn)這一目標(biāo)的關(guān)鍵之處，是教師從之前的“站到講臺前”變到現(xiàn)在的“坐在學(xué)生中”。這一變化絕不僅僅是簡單地將所有問題留給學(xué)生，從“講授”變成“答疑”，而是從問題設(shè)計、思考啟迪、討論引導(dǎo)到過程管理等各方面都對教師提高了要求。特別是現(xiàn)代高級語言發(fā)展日新月異，各種新問題層出不窮，如何在面對開放性的未知問題時，從系統(tǒng)和整體的角度給出學(xué)生解決問題的方式方法，而不是給出具體每個問題的回答，這是對教師能力的一種新考驗。
(二) 編譯器設(shè)計實(shí)現(xiàn)方案
編譯原理課程教學(xué)理想情況，學(xué)生應(yīng)該能夠獨(dú)立自主完成小型編譯系統(tǒng)的構(gòu)造。實(shí)際教學(xué)中，學(xué)生只需吃透關(guān)鍵的幾條原理知識，如NFA的確定化，LL (1) 文法中FIRST和FOLLOW集合的構(gòu)造,LR (1) 文法中識別活前綴DFA構(gòu)造等，基本上已經(jīng)滿足了課程考試要求。然而，僅靠理論學(xué)習(xí)對實(shí)現(xiàn)一個基礎(chǔ)編譯器來說是遠(yuǎn)遠(yuǎn)不足的。相比較于學(xué)生對理論知識的接受程度，學(xué)生自主動手完成編譯系統(tǒng)的能力缺乏就更為明顯。如何面對全體學(xué)生，制定出一套適用的實(shí)踐方案，是課程實(shí)際效用的關(guān)鍵。
有關(guān)程序
解釋程序
解釋器（interpreter）：解釋程序是如同編譯器的一種語言翻譯程序。它與編譯器的不同之處在于：它立即執(zhí)行源程序而不是生成在翻譯完成之后才執(zhí)行的目標(biāo)代碼。從原理上講，任何程序設(shè)計語言都可被解釋或被編譯，但是根據(jù)所使用的語言和翻譯情況，很可能會選用解釋程序而不用編譯器。例如，我們經(jīng)常解釋BASIc語言而不是去編譯它。類似地，諸如LISP 的函數(shù)語言也常常是被解釋的。
解釋程序也經(jīng)常用于教育和軟件的開發(fā)，此處的程序很有可能被翻譯若干次。而另一方面，當(dāng)執(zhí)行的速度是最為重要的因素時就使用編譯器，這是因為被編譯的目標(biāo)代碼比被解釋的源代碼要快得多，有時要快10倍或更多。但是，解釋程序具有許多與編譯器共享的操作，而兩者之間也有一些混合之處。
匯編程序
匯編程序（assembler）：匯編程序是用于特定計算機(jī)上的匯編語言的翻譯程序。正如前面所提到的，匯編語言是計算機(jī)的機(jī)器語言的符號形式，它極易翻譯。有時，編譯器會生成匯編語言以作為其目標(biāo)語言，然后再由一個匯編程序?qū)⑺g成目標(biāo)代碼。
連接程序
連接程序（linker）：編譯器和匯編程序都經(jīng)常依賴于連接程序，它將分別在不同的目標(biāo)文件中編譯或匯編的代碼收集到一個可直接執(zhí)行的文件中。在這種情況下，目標(biāo)代碼，即還未被連接的機(jī)器代碼，與可執(zhí)行的機(jī)器代碼之間就有了區(qū)別。連接程序還連接目標(biāo)程序和用于標(biāo)準(zhǔn)庫函數(shù)的代碼，以及連接目標(biāo)程序和由計算機(jī)的操作系統(tǒng)提供的資源（例如，存儲分配程序及輸入與輸出設(shè)備）。連接程序現(xiàn)在正在完成編譯器最早的一個主要活動（這也是“編譯”一詞的用法，即通過收集不同的來源來構(gòu)造）。連接過程對操作系統(tǒng)和處理器有極大的依賴性。
裝入程序
裝入程序（loader）：編譯器、匯編程序或連接程序生成的代碼經(jīng)常還不完全適用或不能執(zhí)行，但是它們的主要存儲器訪問卻可以在存儲器的任何位置中且與一個不確定的起始位置相關(guān)。這樣的代碼被稱為是可重定位的（relocatable ），而裝入程序可處理所有的與指定的基地址或起始地址有關(guān)的可重定位的地址。裝入程序使得可執(zhí)行代碼更加靈活，但是裝入處理通常是在后臺（作為操作環(huán)境的一部分）或與連接相聯(lián)合時才發(fā)生，裝入程序極少會是實(shí)際的獨(dú)立程序。
預(yù)處理器
預(yù)處理器（preprocessor ）：預(yù)處理器是在真正的翻譯開始之前由編譯器調(diào)用的獨(dú)立程序。預(yù)處理器可以刪除注釋、包含其他文件以及執(zhí)行宏（宏macro是一段重復(fù)文字的簡短描寫）替代。預(yù)處理器可由語言（如 C ）要求或以后作為提供額外功能（諸如為Fortran提供Ratfor預(yù)處理器）的附加軟件。
調(diào)試程序
調(diào)試程序（debugger ）：調(diào)試程序是可在被編譯了的程序中判定執(zhí)行錯誤的程序，它也經(jīng)常與編譯器一起放在IDE 中。運(yùn)行一個帶有調(diào)試程序的程序與直接執(zhí)行不同，這是因為調(diào)試程序保存著所有的或大多數(shù)源代碼信息（諸如行數(shù)、變量名和過程）。它還可以在預(yù)先指定的位置（稱為斷點(diǎn)（breakpoint ））暫停執(zhí)行，并提供有關(guān)已調(diào)用的函數(shù)以及變量的當(dāng)前值的信息。為了執(zhí)行這些函數(shù)，編譯器必須為調(diào)試程序提供恰當(dāng)?shù)姆栃畔?，而這有時卻相當(dāng)困難，尤其是在一個要優(yōu)化目標(biāo)代碼的編譯器中。因此，調(diào)試又變成了一個編譯問題。
描述器
描述器（profiler）：描述器是在執(zhí)行中搜集目標(biāo)程序行為統(tǒng)計的程序。程序員特別感興趣的統(tǒng)計是每一個過程的調(diào)用次數(shù)和每一個過程執(zhí)行時間所占的百分比。這樣的統(tǒng)計對于幫助程序員提高程序的執(zhí)行速度極為有用。有時編譯器也甚至無需程序員的干涉就可利用描述器的輸出來自動改進(jìn)目標(biāo)代碼。
項目管理程序
項目管理程序（project manager）：軟件項目通常大到需要由一組程序員來完成，這時對那些由不同人員操作的文件進(jìn)行整理就非常重要了，而這正是項目管理程序的任務(wù)。例如，項目管理程序應(yīng)將由不同的程序員制作的文件的各個獨(dú)立版本整理在一起，它還應(yīng)保存一組文件的更改歷史，這樣就能維持一個正在開發(fā)的程序的連貫版本了（這對那些由單個程序員管理的項目也很有用）。項目管理程序的編寫可與語言無關(guān)，但當(dāng)其與編譯器捆綁在一起時，它就可以保持有關(guān)特定的編譯器和建立一個完整的可執(zhí)行程序的鏈接程序操作的信息。在Unix系統(tǒng)中有兩個流行的項目管理程序：sccs （source code ctrl system ）和rcs （revision control system ）。
步驟
編譯器內(nèi)部包括了許多步驟或稱為階段源代碼（phase），它們執(zhí)行不同的邏輯操作。將這些階段設(shè)想為編譯器中一個個單獨(dú)的片斷是很有用的，盡管在應(yīng)用中它們是經(jīng)常組合在一起的，但它們掃描程序確實(shí)是作為單獨(dú)的代碼操作來編寫的。
掃描程序
掃描程序（掃描儀）：在這個階段編譯器實(shí)際閱讀源程序（通常以分析程序字符流的形式表示）。掃描程序執(zhí)行詞法分析注釋樹符號表（Lexical analysis ）：它將字符序列收集到稱作記號錯誤處（token ）的有意義單元中，記號同自然語言，如英源代碼理器語中的字詞相似。因此可以認(rèn)為掃描程序執(zhí)行與優(yōu)化程序拼寫相似的任務(wù)。中間代碼例如在下面的代碼行（它可以是C程序的一部分）中：代碼生成器 a [index] = 4 + 2 這個代碼包括了1 2個非空字符，但只有 8個目標(biāo)代碼記號：a 標(biāo)識符目標(biāo)代碼優(yōu)化程序 [ 左括號 i n d e x 標(biāo)識符 ] 右括號 = 賦值目標(biāo)代碼 4 數(shù)字編譯器的階段 + 加號 2 數(shù)字 每一個記號均由一個或多個字符組成，在進(jìn)一步處理之前它已被收集在一個單元中。掃描程序還可完成與識別記號一起執(zhí)行的其他操作。例如，它可將標(biāo)識符輸入到符號表中，將文字（litral）輸入到文字表中（文字包括諸如3 . 1415926535的數(shù)字常量，以及諸如“Hello,world ! ”的引用字符串）。
語法分析
語法分析（parser ）：語法分析程序從掃描程序中獲取記號形式的源代碼，并完成定義程序結(jié)構(gòu)的語法分析（syntax analysis ），這與自然語言中句子的語法分析類似。語法分析定義了程序的結(jié)構(gòu)元素及其關(guān)系。通常將語法分析的結(jié)果表示為分析樹（parse tree）或語法樹（syntax tree）。例如，還是那行C代碼，它表示一個稱為表達(dá)式的結(jié)構(gòu)元素，該表達(dá)式是一個由左邊為下標(biāo)表達(dá)式、右邊為整型表達(dá)式的賦值表達(dá)式組成。這個結(jié)構(gòu)可按下面的形式表示為一個分析樹：請注意，分析樹的內(nèi)部節(jié)點(diǎn)均由其表示的結(jié)構(gòu)名標(biāo)示出，而分析樹的葉子則表示輸入中的記號序列（結(jié)構(gòu)名以不同字體表示以示與記號的區(qū)別）。分析樹對于顯示程序的語法或程序元素很有幫助，但是對于表示該結(jié)構(gòu)卻顯得力不從心了。分析程序更趨向于生成語法樹，語法樹是分析樹中所含信息的濃縮（有時因為語法樹表示從分析樹中的進(jìn)一步抽取，所以也被稱為抽象的語法樹（abstract syntax tree ））。下面是一個C賦值語句的抽象語法樹的例子：請注意，在語法樹中，許多節(jié)點(diǎn)（包括記號節(jié)點(diǎn)在內(nèi)）已經(jīng)消失。例如，如果知道表達(dá)式是一個下標(biāo)運(yùn)算，則不再需要用括號“[”和“]”來表示該操作是在原始輸入中。
語義分析
語義分析（semantic analyzer ）：程序的語義就是它的“意思”，它與語法或結(jié)構(gòu)不同。程序的語義確定程序的運(yùn)行，但是大多數(shù)的程序設(shè)計語言都具有在執(zhí)行之前被確定而不易由語法表示和由分析程序分析的特征。這些特征被稱作靜態(tài)語義（static semantic），而語義分析程序的任務(wù)就是分析這樣的語義（程序的“動態(tài)”語義具有只有在程序執(zhí)行時才能確定的特性，由于編譯器不能執(zhí)行程序，所以它不能由編譯器來確定）。一般的程序設(shè)計語言的典型靜態(tài)語義包括聲明和類型檢查。由語義分析程序計算的額外信息（諸如數(shù)據(jù)類型）被稱為屬性（attribute），它們通常是作為注釋或“裝 飾”增加到樹中（還可將屬性添加到符號表中）。在正運(yùn)行的C表達(dá)式 a [index] = 4 + 2 中，該行分析之前收集的典型類型信息可能是：a是一個整型值的數(shù)組，它帶有來自整型子范圍的下標(biāo)；index則是一個整型變量。接著，語義分析程序?qū)⒂盟械淖颖磉_(dá)式類型來標(biāo)注語法樹，并檢查賦值是否使這些類型有意義了，如若沒有，則聲明一個類型匹配錯誤。在上例中，所有的類型均有意義，有關(guān)語法樹的語義分析結(jié)果可用以下注釋了的樹來表示。
優(yōu)化程序
優(yōu)化程序（source code optimizer）：編譯器通常包括許多代碼改進(jìn)或優(yōu)化步驟。絕大多數(shù)最早的優(yōu)化步驟是在語義分析之后完 成的，而此時代碼改進(jìn)可能只依賴于源代碼。這種可能性是通過將這一操作提供為編譯過程中的單獨(dú)階段指出的。每個編譯器不論在已完成的優(yōu)化種類方面還是在優(yōu)化階段的定位中都有很大的差異。在上例中，我們包括了一個源代碼層次的優(yōu)化機(jī)會，也就是：表達(dá)式4 + 2可由編譯器計算先得到結(jié)果6 （這種優(yōu)化稱為常量合并（constant folding ））。當(dāng)然，還會有更復(fù)雜的情況。還是在上例中，通過將根節(jié)點(diǎn)右面的子樹合并為它的常量值，這個優(yōu)化就可以直接在（注釋）語法樹上完成：盡管許多優(yōu)化可以直接在樹上完成，但是在很多情況下，優(yōu)化接近于匯編代碼線性化形式的樹更為簡便。這樣節(jié)點(diǎn)的變形有許多，但是三元式代碼（three-address code ）（之所以這樣稱呼是因為它在存儲器中包含了3個（或3個以上）位置的地址）卻是標(biāo)準(zhǔn)選擇。另一個常見的選 擇是P -代碼（P - code ），它常用于Pascal編譯器中。在前面的例子中，原先的C表達(dá)式的三元式代碼應(yīng)是：t = 4 + 2 a [ index] = t （請注意，這里利用了一個額外的臨時變量t 存放加法的中間值）。這樣，優(yōu)化程序就將這個代碼改進(jìn)為兩步。首先計算加法的結(jié)果：t = 6 a [index] = t 接著，將t替換為該值以得到三元語句 a [index] = 6 ，指出源代碼優(yōu)化程序可能通過將其輸出稱為中間代碼（intermediate code ）來使用三元式代碼。中間代碼一直是指一種位于源代碼和目標(biāo)代碼（例如三元式代碼或類似的線性表示）之間的代碼表示形式。但是，我們可以更概括地認(rèn)為它是編譯器使用的源代碼的任何一個內(nèi)部表示。此時，也可將語法樹稱作中間代碼，源代碼優(yōu)化程序則確實(shí)能繼續(xù)在其輸出中使用這個表示。有時，這個中間代碼也稱作中間表示（intermediate 表征,IR）。
代碼生成
代碼生成（code generator）：代碼生成器得到中間代碼（IR），并生成目標(biāo)機(jī)器的代碼。正是在編譯的這個階段中，目標(biāo)機(jī)器的特性成為了主要因素。當(dāng)它存在于目標(biāo)機(jī)器時，使用指令不僅是必須的而且數(shù)據(jù)的形式表示也起著重要的作用。例如，整型數(shù)據(jù)類型的變量和浮點(diǎn)數(shù)據(jù)類型的變量在存儲器中所占的字節(jié)數(shù)或字?jǐn)?shù)也很重要。在上面的示例中，現(xiàn)在必須決定怎樣存儲整型數(shù)來為數(shù)組索引生成代碼。例如，下面是所給表達(dá)式的一個可能的樣本代碼序列（在假設(shè)的匯編語言中）：
M O V R0,index ;;
value of index -> R0 M U L R0,2 ;;
double value in R0 M O V R1,&a ;;
address of a -> R1 A D D R1,R0 ;;
add R0 to R1 M O V *R1,6 ;;
constant 6 -> address in R1
在以上代碼中，為編址模式使用了一個類似C的協(xié)定，因此& a是a的地址（也就是數(shù)組的基地址），* R1則意味著間接寄存器地址（因此最后一條指令將值6存放在R1包含的地址中）。這個代碼還假設(shè)機(jī)器執(zhí)行字節(jié)編址，并且整型數(shù)占據(jù)存儲器的兩個字節(jié)（所以在第2條指令中用2作為乘數(shù)）。
目標(biāo)代碼
目標(biāo)代碼（target code optimizer ）：在這個階段中，編譯器嘗試著改進(jìn)由代碼生成器生成的目標(biāo)代碼。這種改進(jìn)包括選擇編址模式以提高性能、將速度慢的指令更換成速度快的，以及刪除多余的操作。在上面給出的樣本目標(biāo)代碼中，還可以做許多更改：在第2條指令中，利用移位指令替代乘法（通常地，乘法很費(fèi)時間），還可以使用更有效的編址模式（例如用索引地址來執(zhí)行數(shù)組 存儲）。使用了這兩種優(yōu)化后，目標(biāo)代碼就變成：
MOV R0,index ;;
value of index -> R0 SHL R0 ;;
double value in R0 MOV &a[R0],6 ;;
constant 6 -> address a + R0
到這里就是編譯原理的簡要描述，但還應(yīng)特別強(qiáng)調(diào)編譯器在其結(jié)構(gòu)細(xì)節(jié)上差別很大。
數(shù)據(jù)結(jié)構(gòu)
編譯原理一直是計算機(jī)學(xué)習(xí)的必修課.
當(dāng)然，由編譯器的階段使用的算法與支持這些階段的數(shù)據(jù)結(jié)構(gòu)之間的交互是非常強(qiáng)大的。編譯器的編寫者盡可能有效實(shí)施這些方法且不引起復(fù)雜性。理想的情況是：與程序大小成線性比例的時間內(nèi)編譯器，換言之就是，在0 （ n ）時間內(nèi)，n是程序大小的度量（通常是字符數(shù)）。本節(jié)將講述一些主要的數(shù)據(jù)結(jié)構(gòu)，它們是其操作部分階段所需要的，并用來在階段中交流信息。
記號
記號（token）：當(dāng)掃描程序?qū)⒆址占揭粋€記號中時，它通常是以符號表示這個記號；這也就是說，作為一個枚舉數(shù)據(jù)類型的值來表示源程序的記號集。有時還必須保留字符串本身或由此派生出的其他信息（例如：與標(biāo)識符記號相關(guān)的名字或數(shù)字記號值）。在大多數(shù)語言中，掃描程序一次只需要生成一個記號（這稱為單符號先行（single symbol lookahead））。在這種情況下，可以用全程變量放置記號信息；而在別的情況（最為明顯的是Fortran）下，則可能會需要一個記號數(shù)組。
語法樹
語法樹（syntax tree）：如果分析程序確實(shí)生成了語法樹，它的構(gòu)造通常為基于指針的標(biāo)準(zhǔn)結(jié)構(gòu)，在進(jìn)行分析時動態(tài)分配該結(jié)構(gòu)，則整棵樹可作為一個指向根節(jié)點(diǎn)的單個變量保存。結(jié)構(gòu)中的每一個節(jié)點(diǎn)都是一個記錄，它的域表示由分析程序和之后的語義分析程序收集的信息。例如，一個表達(dá)式的數(shù)據(jù)類型可作為表達(dá)式的語法樹節(jié)點(diǎn)中的域。有時為了節(jié)省空間，這些域也是動態(tài)分配或存放在諸如符號表的其他數(shù)據(jù)結(jié)構(gòu)中，這樣就可以有選擇地進(jìn)行分配和釋放。實(shí)際上，根據(jù)它所表示的語言結(jié)構(gòu)的類型（例如：表達(dá)式節(jié)點(diǎn)對于語句節(jié)點(diǎn)或聲明節(jié)點(diǎn)都有不同的要求），每一個語法樹節(jié)點(diǎn)本身都可能要求存儲不同的屬性。在這種情況下，可由不同的記錄表示語法樹中的每個節(jié)點(diǎn)，每個節(jié)點(diǎn)類型只包含與本身相關(guān)的信息。
符號表
符號表（symbol table）：這個數(shù)據(jù)結(jié)構(gòu)中的信息與標(biāo)識符有關(guān)：函數(shù)、變量、常量以及數(shù)據(jù)類型。符號表幾乎與編譯器的所有階段交互：掃描程序、分析程序或?qū)?biāo)識符輸入到表格中的語義分析程序；語義分析程序?qū)⒃黾訑?shù)據(jù)類型和其他信息；優(yōu)化階段和代碼生成階段也將利用由符號表提供的信息選 出恰當(dāng)?shù)拇a。因為對符號表的訪問如此頻繁，所以插入、刪除和訪問操作都必須比常規(guī)操作更有效。盡管可以使用各種樹的結(jié)構(gòu)，但雜湊表卻是達(dá)到這一要求的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)。有時在一個列表或棧中可使用若干個表格。
常數(shù)表
常數(shù)表（literal table）：常數(shù)表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常數(shù)表中也十分重要。但是，在其中卻無需刪除，這是因為它的數(shù)據(jù)全程應(yīng)用于程序而且常量或字符串在該表中只出現(xiàn)一次。通過允許重復(fù)使用常量和字符串，常數(shù)表對于縮小程序在存儲器中的大小顯得非常重要。在代碼生成器中也需要常數(shù)表來構(gòu)造用于常數(shù)和在目標(biāo)代碼文件中輸入數(shù)據(jù)定義的符號地址。
中間代碼
中間代碼（intermediate code）：根據(jù)中間代碼的類型（例如三元式代碼和P -代碼）和優(yōu)化的類型，該代碼可以是文本串的數(shù)組、臨時文本文件或是結(jié)構(gòu)的連接列表。對于進(jìn)行復(fù)雜優(yōu)化的編譯器，應(yīng)特別注意選擇允許簡單重組的表示。
臨時文件
臨時文件（temporary file）：計算機(jī)過去一直未能在編譯器時將整個程序保留在存儲器中。這一問題已經(jīng)通過使用臨時文件來保存翻譯時中間步驟的結(jié)果或通過“匆忙地”編譯（也就是只保留源程序早期部分的足夠信息用以處理翻譯）解決了。存儲器的限制現(xiàn)在也只是一個小問題了，現(xiàn)在可以將整個編譯單元放在存儲器之中，特別是在可以分別編譯的語言中時。但是偶爾還是會發(fā)現(xiàn)需要在某些運(yùn)行步驟中生成中間文件。其中典型的是代碼生成時需要反填（backpatch）地址。例如，當(dāng)翻譯如下的條件語句時 if x = 0 then ... else ... 在知道else部分代碼的位置之前必須由文本跳到else部分：
CMP X,0 JNE NEXT ;;
location of NEXT not yet known < code for then-part > NEXT : < code for else-part >
通常，必須為NEXT的值留出一個空格，一旦知道該值后就會將該空格填上，利用臨時文件可以很容易地做到這一點(diǎn)。
如果想利用上面的編譯原理開發(fā)一套屬于自己的編程語言，或者想在一個產(chǎn)品中嵌入編程語言，可以參考zengl開源網(wǎng)開發(fā)的zengl編程語言，該編程語言為國人使用c語言開發(fā)，里面包含兩個部分，一個是編譯器，一個是解釋執(zhí)行中間代碼的虛擬機(jī)。編譯器包含了詞法掃描，語法分析，中間代碼輸出等，虛擬機(jī)則類似JAVA一樣解釋執(zhí)行中間代碼。作者將所有的版本都公布出來，好讓讀者可以由淺入深的做研究，并且為了證明該編程語言的實(shí)用性，還結(jié)合SDL游戲開發(fā)庫開發(fā)了一款圖形界面和命令行界面的21點(diǎn)撲克小游戲。
zengl編程語言目前適用平臺為windows和Linux (最開始在Linux下使用gcc開發(fā)，后來移植到windows平臺)
其他問題
可從許多不同的角度來觀察編譯器的結(jié)構(gòu)，還有其他一些可能的觀點(diǎn)：編譯器的物理結(jié)構(gòu)、操作的順序等等。由于編譯器的結(jié)構(gòu)對其可靠性、有效性、可用性以及可維護(hù)性都有很大的影響，所以編譯器的編寫者應(yīng)熟悉盡可能多的有關(guān)編譯器結(jié)構(gòu)的觀點(diǎn)。
分析和綜合
在這個觀點(diǎn)中，已將分析源程序以計算其特性的編譯器操作歸為編譯器的分析（analysis）部分，而將生成翻譯代碼時所涉及到的操作稱作編譯器的綜合（synthesis ）部分。當(dāng)然，詞法分析、語法分析和語義分析均屬于分析部分，而代碼生成卻是綜合部分。在優(yōu)化步驟中，分析和綜合都有。分析正趨向于易懂和更具有數(shù)學(xué)性，而綜合則要求更深的專業(yè)技術(shù)。因此，將分析步驟和綜合步驟兩者區(qū)分開來以便發(fā)生變化時互不影響是很有用的。
前端和后端
本觀點(diǎn)認(rèn)為，將編譯器分成了只依賴于源語言（前端（front end ））的操作和只依賴于目標(biāo)語言（后端（back end ））的操作兩部分。這與將其分成分析和綜合兩部分是類似的：掃描程序、分析程序和語義分析程序是前端，代碼生成器是后端。但是一些優(yōu)化分析可以依賴于目標(biāo)語言，這樣就是屬于后端了，然而中間代碼的綜合卻經(jīng)常與目標(biāo)語言無關(guān)，因此也就屬于前端了。在理想情況下，編譯器被嚴(yán)格地分成這兩部分，而中間表示則作為其間的交流媒介。這一結(jié)構(gòu)對于編譯器的可移植性（portability）十分重要，此時設(shè)計的編譯器既能改變源代碼（它涉及到重寫前端），又能改變目標(biāo)代碼（它還涉及到重寫后端）。在實(shí)際中，這是很難 做到的，而且稱作可移植的編譯器仍舊依賴于源語言和目標(biāo)語言。其部分原因是程序設(shè)計語言和機(jī)器構(gòu)造的快速發(fā)展以及根本性的變化，但是有效地保持移植一個新的目標(biāo)語言所需的信息 或使數(shù)據(jù)結(jié)構(gòu)普遍地適合改變?yōu)橐粋€新的源語言所需的信息卻十分困難。然而人們不斷分離前端和后端的努力會帶來更方便的可移植性。
遍
編譯器發(fā)現(xiàn)，在生成代碼之前多次處理整個源程序很方便。這些重復(fù)就是遍（ pass）。首遍是從源中構(gòu)造一個語法樹或中間代碼，在它之后的遍是由處理中間表示、向它增加信息、更換結(jié)構(gòu)或生成不同的表示組成。遍可以和階段相應(yīng)，也可無關(guān)-遍中通常含有若干個階段。實(shí)際上，根據(jù)語言的不同，編譯器可以是一遍（one pass ）-所有的階段由一遍完成，其結(jié)果是編譯得很好，但（通常）代碼卻不太有效。Pascal語言和C 語言均允許單遍編譯。（Modula - 2語言的結(jié)構(gòu)則要求編譯器至少有兩遍）。大多數(shù)帶有優(yōu)化的編譯器都需要超過一遍：典型的安排是將一遍用于掃描和分析，將另一遍用于語義分析和源代碼層優(yōu)化，第3遍用于代 碼生成和目標(biāo)層的優(yōu)化。更深層的優(yōu)化則可能需要更多的遍：5遍、6遍、甚至8遍都是可能的。
語言定義和編譯器
程序設(shè)計語言的詞法和語法結(jié)構(gòu)通常用形式的術(shù)語指定，并使用正則表達(dá)式和上下文無關(guān)文法。但是，程序設(shè)計語言的語義通常仍然是由英語（或其他的自然語言）描述的。這些描述（與形式的詞法及語法結(jié)構(gòu)一起）一般是集中在一個語言參考手冊（language reference manual ）或語言定義（language definition）之中。因為編譯器的編寫者掌握的技術(shù)對于語言的定義有很大的影響，所以在使用了一種新的語言之后，語言的定義和編譯器同時也能夠得到開發(fā)。類似地，一種語言的定義對于構(gòu)造編譯器所需的技術(shù)也有很 大的關(guān)系。編譯器的編寫者更經(jīng)常遇到的情況是：正在實(shí)現(xiàn)的語言是眾所周知的并已有了語言定義。有時這個語言定義已達(dá)到了某個語言標(biāo)準(zhǔn)（language standard ）的層次，語言標(biāo)準(zhǔn)是指得到諸如美國國家標(biāo)準(zhǔn)協(xié)會（American National Standards Institute ，ANSI ）或國際標(biāo)準(zhǔn)化組織（.int Organization for Standardization，ISO ）的官方標(biāo)準(zhǔn)組織批準(zhǔn)的標(biāo)準(zhǔn)。Fortran、 Pascal和c語言就具有ANSI標(biāo)準(zhǔn)，Ada有一個通過了美國政府批準(zhǔn)的標(biāo)準(zhǔn)。在這種情況下，編譯器的編寫者必須解釋語言的定義并執(zhí)行符合語言定義的編譯器。通常做到這一點(diǎn)并不容易，但是有時由于有了標(biāo)準(zhǔn)測試程序集（測試組（test suite ）），就能夠測試編譯器（Ada有這樣一個測試組），這又變得簡單起來了。有時候，一種語言可從數(shù)學(xué)術(shù)語的形式定義（formal definition ）中得到它的語義。現(xiàn)在人們已經(jīng)使用了許多方法，盡管一個稱作表示語義（denotational 語義學(xué) ）的方法已經(jīng)成為較為常用的方法，在函數(shù)編程共同體中尤為如此，但現(xiàn)在仍然沒有一種可成為標(biāo)準(zhǔn)的方法。當(dāng)語言有一個形式定義時，那么在理論上就有可能給出編譯器與該定義一致的數(shù)學(xué)證明，但是由于這太難了，而幾乎從未有人做過。無論怎樣，運(yùn)行時環(huán)境的結(jié)構(gòu)和行為是尤其受到語言定義影響的編譯器構(gòu)造的一個方面。
編輯器
編輯器（editor）：編譯器通常接受由任何生成標(biāo)準(zhǔn)文件（例如ASCII文件）的編輯器編寫的源程序。現(xiàn)在，編譯器已與另一個編輯器和其他程序捆綁進(jìn)一個交互的開發(fā)環(huán)境-IDE中。此時，盡管編輯器仍然生成標(biāo)準(zhǔn)文件，但會轉(zhuǎn)向正被討論的程序設(shè)計語言的格式或結(jié)構(gòu)。這樣的編輯器稱為基于結(jié)構(gòu)的（structure based ），且它早已包括了編譯器的某些操作；因此，程序員就會在程序的編寫時而不是在編譯時就得知錯誤了。從編輯器中也可調(diào)用編譯器以及與它共用的程序，這樣程序員無需離開編輯器就可執(zhí)行程序。
課程
這門課程關(guān)注的是編譯器方面的產(chǎn)生原理和技術(shù)問題，似乎和計算機(jī)的基礎(chǔ)領(lǐng)域不沾邊，可是編譯原理卻一直作為大學(xué)本科的 必修課程，同時也成為了研究生入學(xué)考試的必考內(nèi)容。編譯原理及技術(shù)從本質(zhì)上來講就是一個算法問題而已，當(dāng)然由于這個問題十分復(fù)雜，其解決算法也相對復(fù)雜。我們學(xué)的數(shù)據(jù)結(jié)構(gòu)與算法分析也是講算法的，不過講的基礎(chǔ)算法，換句話說講的是算法導(dǎo)論，而編譯原理這門課程講的就是比較專注解決一種的算法了。在20世紀(jì) 50年代，編譯器的編寫一直被認(rèn)為是十分困難的事情，第一Fortran的編譯器據(jù)說花了18年的時間才完成。在人們嘗試編寫編譯器的同時，誕生了許多跟 編譯相關(guān)的理論和技術(shù)，而這些理論和技術(shù)比一個實(shí)際的編譯器本身價值更大。就猶如數(shù)學(xué)家們在解決著名的哥德巴赫猜想一樣，雖然沒有最終解決問題，但是其間 誕生不少名著的相關(guān)數(shù)論。
編譯過程概述
c語言的源程序和對應(yīng)的可執(zhí)行程序執(zhí)行時在內(nèi)存中的運(yùn)行結(jié)構(gòu)，實(shí)現(xiàn)這一轉(zhuǎn)換的最主要的過程就是編譯。
源程序是給人看的，本質(zhì)上就是文本文件，可以用Linux中的vi或Windows中的記事本之類的文本編輯程序打開、編寫，但計算機(jī)無法直接執(zhí)行源程序，需要通過一個專門的程序?qū)⒃闯绦蚓幾g為計算機(jī)可執(zhí)行程序，這個專門的程序就是編譯器。編譯過程主要分為詞法分析、語法分析、中間代碼生成、目標(biāo)代碼生成（忽略預(yù)處理、語義分析、優(yōu)化等）。下面我們依次簡要講解編譯的主要過程。
詞法分析
人眼中看到的源代碼是這樣的：
這里看不出關(guān)鍵字、運(yùn)算符、標(biāo)識符，甚至看不出哪幾個字符屬于同一個符號。編譯的第一階段是詞法分析，目的就是在連續(xù)的字符中識別出一個一個的符號，并盡可能地識別出符號的屬性。
人們在看c語言源程序時，借助空格、括號等一眼就可以看出標(biāo)識符、關(guān)鍵字。與人相比，現(xiàn)在計算機(jī)的智能還是相當(dāng)?shù)偷?，無法像人那樣同時看多個字符，只能依據(jù)一個非常機(jī)械的“電子版”詞法，一個字符一個字符地識別?！半娮影妗痹~法是將狀態(tài)轉(zhuǎn)換圖的思路融匯在flex詞法分析器的代碼中得以體現(xiàn)的。詞法分析器從源程序的字符串中識別出一個個符號（token），并按序保存。
在詞法分析階段能夠識別出一些符號的含義，它們包括關(guān)鍵字、數(shù)字、字符串、分隔符，這些符號的含義不需要其他符號的輔助就能確定本身的含義。比如，“int”一定代表整數(shù)類型，它不可能是一個變量名稱，也不可能是一個運(yùn)算符。
而另外一些符號需要通過前后的其他符號才能確定出準(zhǔn)確含義。比如“m”，在詞法階段僅能判斷這是一個標(biāo)識符，但是如果不對所在的句做分析，就無法得知這個標(biāo)識符代表一個變量還是一個函數(shù)。更多詳細(xì)的信息需要對符號所在的句型做分析才能獲得。這部分工作由語法分析來完成。
語法分析
如果說詞法分析的作用是從連續(xù)的字符中識別出標(biāo)識符、關(guān)鍵字、數(shù)字、運(yùn)算符并存儲為符號（token）流，語法分析的作用就是從詞法分析識別出的符號流中識別出符合c語言語法的語句。
因為計算機(jī)無法像人那樣同時看多個標(biāo)識符、關(guān)鍵字、數(shù)字、運(yùn)算符，無法像人那樣一眼看出這是一個函數(shù)聲明，那是一個if語句，只能非常笨拙地一個符號一個符號去識別。與詞法分析器有些類似，語法分析器也是依據(jù)用計算機(jī)表示的語法，一個符號一個符號地識別出符合C語言語法的語句。語法的計算機(jī)表示就是產(chǎn)生式。在語法分析器中把通過產(chǎn)生式產(chǎn)生的C語言語法映射成一套模板，并把這套模板融匯在語法分析器的程序中。語法分析器的作用就是將詞法分析器識別出的符號（token）一個一個地與這套模板進(jìn)行匹配，匹配上這套模板中的某個語法，就可以識別出一句完整的語句，并確定這條語句的語法。
我們以案例中“int fun(int a，int b);”這條函數(shù)聲明語句為例描述這個過程，它與語句模板的匹配情景如圖1-38所示。
這段token流最終與函數(shù)聲明模板相匹配，在匹配成功后，計算機(jī)就認(rèn)為此語句為函數(shù)聲明語句，并以語法樹的形式在內(nèi)存中記錄下來。
以樹型結(jié)構(gòu)來記錄分析出的語句是一個非常巧妙、深謀遠(yuǎn)慮、通盤考慮的選擇。一方面，樹型結(jié)構(gòu)能夠“記住”源程序全部的“意思”，另一方面，樹型結(jié)構(gòu)更容易對應(yīng)到運(yùn)行時結(jié)構(gòu)。
從語法樹到中間代碼再到目標(biāo)代碼
至此，語法樹已經(jīng)承載了源程序的全部信息，后續(xù)的轉(zhuǎn)換工作就和源程序沒關(guān)系了。
如果希望一步到位，從語法樹轉(zhuǎn)換為目標(biāo)代碼，理論上和實(shí)際上都是可行的。但計算機(jī)存在多種CPU硬件平臺，考慮到程序在不同CPU之間的可移植性，先轉(zhuǎn)換成一個通用的、抽象的“CPU指令”，這就是中間代碼最初的設(shè)計思想。然后根據(jù)具體選定的CPU，將中間代碼落實(shí)到具體CPU的目標(biāo)代碼。
語法樹是個二維結(jié)構(gòu)，中間代碼是準(zhǔn)一維結(jié)構(gòu)，語法樹到中間代碼的轉(zhuǎn)換過程，本質(zhì)上是將二維結(jié)構(gòu)轉(zhuǎn)換為準(zhǔn)一維結(jié)構(gòu)的過程。中間代碼特別是RTL已經(jīng)可以和運(yùn)行時結(jié)構(gòu)一一對應(yīng)了。
運(yùn)行時結(jié)構(gòu)也是一維的，圖1-40左側(cè)部分的轉(zhuǎn)換結(jié)果將更貼近運(yùn)行時結(jié)構(gòu)。
選定具體的CPU、操作系統(tǒng)后，中間代碼就可以轉(zhuǎn)換為目標(biāo)代碼——匯編代碼（我們配置的是AT&T匯編），這時操作系統(tǒng)的影響還比較小。然后由匯編器依照選定操作系統(tǒng)的目標(biāo)文件格式，將.s文件轉(zhuǎn)換為具體的目標(biāo)文件，對于Linux而言是.o文件，對于Windows而言是.obj文件。目標(biāo)文件中已經(jīng)是選定的CPU的機(jī)器指令了。
最后鏈接器把一個或多個目標(biāo)文件（庫文件本質(zhì)上也是目標(biāo)文件）鏈接成符合選定操作系統(tǒng)指定格式的可執(zhí)行文件。
通過操作系統(tǒng)，可執(zhí)行程序就可以被載入內(nèi)存執(zhí)行，形成前兩節(jié)我們所看到的運(yùn)行時結(jié)構(gòu)。
本書后續(xù)內(nèi)容將詳細(xì)講解編譯的主要過程：詞法分析、語法分析、中間代碼到目標(biāo)代碼，然后是匯編與鏈接，最后講解預(yù)處理。
參考資料 >