編譯器與解釋器
-
編譯器：（相當于一次性翻譯完）
程式設計語言是向人以及計算機描述計算過程的記号。但是，在一個程式可以運作之前，它首先需要被翻譯成一種能夠被計算機執行的形式。完成這項翻譯工作的軟體系統成為編譯器(Compiler)。
簡單地說，一個編譯器就是一個程式，它可以閱讀以某一種語言（源語言）編寫的程式，并把程式翻譯成為一個等價的、用另一種語言（目智語言）編寫的程式。
編譯器的重要任務之一是報告它在翻譯過程中發現的源程式中的錯誤。
如果目标程式是一個可執行的機器語言程式，那麼它就可以被使用者調用，處理輸入并産生輸出。
-
解釋器：（相當于同聲傳譯）
解釋器(Interpreter)是另一種常見的語言處理器。它并不通過翻譯的方式生成目标程式。從使用者的角度看，解釋器直接利用使用者提供的輸入執行源程式中指定的操作。
在把使用者輸入映射成為輸出的過程中，由一個編譯器産生的機器語言目标程式通常比一個解釋器快很多。然而，解釋器的錯誤診斷效果通常比編譯器更好，因為它逐個語句地執行源程式。
語言處理過程
如上圖所示，除了編譯器之外，建立一個可執行的目标程式還需要一些其他程式。
- 一個源程式可能被分割成為多個子產品，并存放于獨立的檔案中，把源檔案聚合在一起的任務有時會由一個被稱為預處理器(Preprocessor)的程式獨立完成。預處理器還負責把那些稱為宏的縮寫形式轉換為源語言的語句、删除注釋等。
- 然後，将經過預處理的源程式作為輸入傳遞給一個編譯器(Compiler)。編譯器可能産生生一個彙編語言程式作為其輸出，因為彙編語言比較容易輸出和調試。
- 接着，這個彙編語言程式由稱為彙編器(Assembler)的程式進行處理，并生成可重定位的機器代碼。
- 大型程式經常被分成多個部分進行編譯，是以，可重定位的機器代碼有必要和其他可重定位的目标檔案以及庫檔案連接配接到一起，形成真正在機器上運作的代碼。一個檔案的代碼可能指向另一個檔案中的位置，而連結器(Linker)能夠解決外部記憶體位址的問題。
- 最後加載器(Loader)把所有的可執行目标檔案放到記憶體中執行。
語言處理執行個體
由上面我們可以了解到語言處理的整個過程，那麼放到實際的例子當中是怎麼處理的呢？
下面我們以C語言列印Hello,World!為例子。
預處理→編譯→彙編→連結
- 預處理階段(.c→.i)：編譯器将C程式的頭檔案編譯進來，還有宏的替換、删除注釋等。
科普：頭檔案作為一種包含功能函數、資料接口聲明的載體檔案，主要用于儲存程式的聲明，而定義檔案用于儲存程式的實作。
- 編譯(.i→.s)：轉換為彙編語言檔案：這個階段編譯器主要做詞法分析、文法分析、語義分析等，在檢查無錯誤後，把代碼翻譯成彙編語言。
- 彙編階段(.s→.o)得到機器語言：彙編器将hello.s翻譯成機器語言儲存在hello.o中（二進制文本形式）。
- 連結階段(.s→.exe)：printf函數存在于一個名為printf.o的單獨預編譯目标檔案中。必須得将其并入到hello.o的程式中，連結器就是負責處理這兩個的并入，結果得到hello.exe檔案，他就是一個可執行的目标檔案。
編譯器編譯的過程
我們把編譯器看作一個黑盒子，它能夠把源程式映射為在語義上等價的目标程式。如果把黑盒子稍微打開一點，我們就會看到這個映射過程由兩個部分組成：前端部分和後端部分。
- 分析(analysis)部分：通常被稱為編譯器的前端(front end)，它把源程式分解成為多個組成要素，并在這些要素之上加上文法結構。然後，它使用這個結構來建立該源程式的一個中間表示。如果分析部分檢查出源程式沒有按照正确的文法構成，或者語義上不一緻，它就必須提供有用的資訊，使得使用者可以按此進行改正。分析部分還會收集有關源程式的資訊，并把資訊存放在一個成為符号表(symbol table)的資料結構中。符号表将和中間表示形式一起傳送給綜合部分。
【編譯原理】代碼在編譯器中的完整處理過程 - 綜合(synthesis)部分：通常被稱為編譯器的後端(back end)，它根據中間表示和符号表中的資訊來構造使用者期待的目标程式。
- 詞法分析器：（也稱為掃描器）詞法分析是編譯過程的基礎，任務是掃描源程式，根據語言的詞法規則分解和識别出每個單詞，并把單詞翻譯成相應的機内表示。在識别單詞的過程中同時也做詞法檢查。
- 文法分析器：（有時簡稱為分析器）文法分析是在詞法分析的基礎上進行的。任務是根據語言的文法規則把單詞符号流分解成格内文法機關，如 表達式、語句等。通過文法分析确定整個輸入符号流是否構成一個文法正确的程式。
- 語義分析器：任務是對源程式進行語義檢查，其目的是保證辨別符和常數的正常使用，把必要的資訊收集儲存到符号表或中間代碼程式中，并進行相應的處理。
- 中間代碼生成器：必不可少的階段，任務是在文法分析和語義分析基礎上把文法成分的語義對其繼續翻譯，翻譯的結果是某種中間代碼形式，這種中間代碼的結果簡單，接近計算機的指令形式，能夠很容易被翻澤成計算機指令，常用的中間代碼有三元式、四元式和逆波蘭式。
- 代碼優化器：對程式代碼進行等價（即 不改變程字的運作中間表示形式結果）變換。程式代碼可以是中間代碼（如 四元式代碼），也可以是目标代碼。等價的含義是使得交換後的代碼運作結果與變換前代碼運作結果相同，優化的含義是使最終生成的目标代碼短（運作時間更知、占用空間更小），時空效率優化。原則上，優化可以在編譯的各個階段進行，但最主要的一類是對中間代碼進行優化，這類優化不依賴于具體的計算機。
- 目标代碼生成器：将中間代碼或優化之後的中間代碼轉換為等價的目标代碼，即 機器指令或彙編語言。由中間代碼很容易生成目标程式（位址指令序列），這部分工作與機器關系密切，是以要根據機器進行。在做這部分工作時（要注意充分利用累加器），也可以進行優化處理。
- 表格管理：編譯過程中源程式的各種資訊被保留在種種不同的表格，編譯各階段的工作都涉及到構造、查找、或更新有關的表格。編譯程式的公共輔助部分，對源程式中的各種量進行管理，登記在相應的表格。編譯程式處理時通過查表得到所需的資訊。
還記得Debug調試的時候觀察變量值的變化的那個表格嗎？
- 出錯處理：如果編譯過程中發現源程式有錯誤，編譯程式應報告錯誤的性質和錯誤的發生的地點，并且将錯誤所造成的影響限制在盡可能小的範圍内，使得源程式的其餘部分能繼續被編譯下去，有些編譯程式還能自動糾正錯誤，這些工作由錯誤處理程式完成。需要注意的是，一般編譯器隻做文法檢查和最簡單的語義檢查，而不檢查程式的邏輯。
詞法分析器
詞法分析器的任務是将程式的字元流轉換到記号流。
字元流:被編譯的語言例如C、JAVA、ASCII、Inicode.
記号流:編譯器内部定義的資料結構，編碼所識别出的詞法單元。
例如讀入一個程式語句:
if (x>0)
y="NEMO"; //詞法分析器設定成自動忽略空格，以下空格用\x20表示 詞法分析器依次讀入：i、f、\x20. (、x、)、0、)、\n、y、=、"NEMO"、;。
進行分析後得到:
IF LPARE IDENT(x) GT INT (0) RPAREN
IDENT(y) ASSIGN STRING ( "NEMO" ) SEMICOLON EOF 我們對這些“詞語記号“進行資料結構定義:
enum type {IF. LPAREN. ID. INLIT,...}
struct token {
enum type k;
char *lexeme; //單詞
}; //例如if (x>0)， 我們就可以程式設計為: token{k= IF, lexeme =0};
token{k= LPAREN. lexeme=0}; token{k = ID, lexeme= “x”}; 目前至少有兩種實作方案:
- 手工編碼實作法（相對複雜，且容易出錯目前非常流行的GCC、LLVM 等）；
- 詞法分析器的生成器（自動的，可以快速原型、代碼量較少，但是控制細節難）
文法分析器
文法分析器的主要任務是對詞法分析的輸出結果記号流單詞序列進行分析，識别合法的文法單元并将其轉換輸出為下一階段可以識别的文法樹。
實作方法:
- 手工方式:遞歸下降分析器
- 使用文法分析器的自動生成著: LL(1)、 LR(1)
兩種方式在實際的編譯器中都有廣泛的應用，其中自動的方式更适合快速對系統進行原型開發，手工的方式更适台對系統進行調優。
語義分析器
文法樹（分析樹）是句子結構的圖形表示，它代表了句子的推導結果，有利于了解句子文法結構的層次。簡單來說，文法樹就是按照某一規則進行推導時所形成的樹。和推導所用的順序無關（最左、最右、其他）
特點：
- 樹中每個内部節點代表非終結符
- 每個葉子節點代表終結符
- 每一步推導代表如何從雙親結點生成它的直接孩子節點
二義性：若對于一個文法的某一句子存在兩顆不同的文法樹，則該文法是二義性文法；否則是無二義性文法。（包含二義性的句子）
從編譯器角度，二義性文法存在的問題：
同一個程式會有不同的含義，是以程式運作的結果不是唯一的。
解決方法：文法的重寫