編譯

編譯程式

將某一種程式設計語言寫的程式翻譯成等價的另一種語言的程式的程式, 稱之為編譯程式(compiler) .

詞法分析的任務是對由字元組成的單詞進行處理，從左至右逐個字元地對源程式進行掃描，產生一個個的單詞符號，把作為字元串的源程式改造成為單詞符號串的中間程式。執行詞法分析的程式稱為詞法分析程式或掃描器。

源程式中的單詞符號經掃描器分析，一般產生二元式：單詞種別；單詞自身的值。單詞種別通常用整數編碼，如果一個種別只含一個單詞符號，那么對這個單詞符號，種別編碼就完全代表它自身的值了。若一個種別含有許多個單詞符號，那么，對於它的每個單詞符號，除了給出種別編碼以外，還應給出自身的值。

詞法分析器一般來說有兩種方法構造：手工構造和自動生成。手工構造可使用狀態圖進行工作，自動生成使用確定的有限自動機來實現。

編譯程式的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程式，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程式是最終的一個語法單位。編譯程式的語法規則可用上下文無關文法來刻畫。

語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。而自下而上分析法採用的是移進歸約法，基本思想是：用一個暫存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。

中間代碼是源程式的一種內部表示，或稱中間語言。中間代碼的作用是可使編譯程式的結構在邏輯上更為簡單明確，特別是可使目標代碼的最佳化比較容易實現中間代碼，即為中間語言程式，中間語言的複雜性介於源程式語言和機器語言之間。中間語言有多種形式，常見的有逆波蘭記號、四元式、三元式和樹。

代碼最佳化是指對程式進行多種等價變換，使得從變換後的程式出發，能生成更有效的目標代碼。所謂等價，是指不改變程式的運行結果。所謂有效，主要指目標代碼運行時間較短，以及占用的存儲空間較小。這種變換稱為最佳化。

有兩類最佳化：一類是對語法分析後的中間代碼進行最佳化，它不依賴於具體的計算機；另一類是在生成目標代碼時進行的，它在很大程度上依賴於具體的計算機。對於前一類最佳化，根據它所涉及的程式範圍可分為局部最佳化、循環最佳化和全局最佳化三個不同的級別。