1.1 內容組織

如圖1.1所示，本書分為七章，除了第1章為概述和第7章為結束語之外，中間五章重點介紹編譯器設計與實現的五個核心階段，它們分別為：第2章詞法分析和語法分析、第3章語義分析、第4章中間代碼生成、第5章目標代碼生成，以及第6章中間代碼優化。這五章中每章的主要內容分別討論相關內容的理論方法、實踐技術和實踐內容。其中，理論方法部分關注編譯過程中各個關鍵步驟的理論知識，介紹相關的核心算法和技術原理；實踐技術部分則基于理論知識，介紹編譯器實現過程中的技術要點，涵蓋當前使用較為廣泛的工具，并用代碼呼應前面的理論知識和算法；實踐內容部分則設計了具有不同難度的編譯器實現任務，幫助學生加深理解前面介紹的理論方法和實踐技術。同時，從第2章至第6章的實踐內容可形成一個流程完整、現實可用和功能完備的編譯器。其中，第2、3和4章的實踐內容前后銜接，逐步完成編譯的過程（從源程序到中間代碼）。而第5章和第6章的實踐內容，均依賴于第4章的實踐內容中中間代碼生成器的輸出。其中，第5章的實踐內容完成從中間代碼到目標代碼的翻譯，而第6章的實踐內容則以中間代碼為輸入，在完成機器無關的優化之后，再輸出中間代碼，這可以作為第5章實踐內容的輸入，繼續完成從中間代碼到目標代碼的翻譯。

在第2章詞法分析和語法分析中，對于詞法分析的理論方法，我們重點介紹正則表達式、有限狀態自動機，以及狀態最小化算法；對于語法分析的理論方法，我們重點介紹上下文無關文法，并詳細討論自頂向下和自底向上這兩種語法分析算法。對應于這些理論方法，在實踐技術部分，我們結合當前使用廣泛的Flex和Bison工具，介紹當前編譯器實踐中常用的實現技術和工具的使用方法。本章的實踐內容為基于Flex和Bison實現面向C--語言的詞法分析和語法分析器，該分析器以C--源代碼為輸入，其輸出內容會成為第3章語義分析實踐內容的輸入。

圖1.1 本書內容的組織框架圖

在第3章語義分析中，我們重點介紹語義分析的理論方法，并結合示例深入討論上下文相關的分析和語法制導的翻譯等內容。在實踐技術部分，我們重點討論屬性文法和符號表的設計與實現原理，并介紹支持多層作用域的符號表和語義分析過程中的提示信息實現技術。本章的實踐內容是在第2章實踐內容的基礎上構建語義分析器，實現對源代碼的語義分析，檢測其中的多種類型錯誤，并反饋錯誤信息。

在第4章中間代碼生成中，我們重點介紹中間代碼的設計與表示，并詳細介紹中間代碼的內存模型及其技術原理。在實踐技術部分，我們重點介紹中間代碼的線形表示和樹形表示，以及運行時環境的設計與實現，詳細介紹基本表達式、語句、函數調用以及數組和結構體的翻譯模式；同時，我們還介紹中間代碼生成實踐的額外提示實現方法。前面的章節完成了詞法和語法分析，并實現了語義分析器，本章的實踐內容是根據語義分析的結構，將C--語言書寫的源程序翻譯為中間代碼程序。

在第5章目標代碼生成中，我們重點介紹目標代碼生成的設計，以及目標代碼的內存模型設計和管理。同時，為了討論目標代碼生成過程中的寄存器選擇問題，我們介紹寄存器分配算法和活躍變量分析算法。最后，我們詳細介紹目標代碼生成過程中的指令選擇問題。基于這些理論方法，我們在實踐技術部分詳細介紹目標代碼的MIPS模擬器QtSpim的安裝與使用，并討論目標代碼MIPS32的語法和書寫規范。基于對MIPS32的討論，我們進一步介紹指令選擇的實現。并且，對應于理論部分的內容，我們也介紹寄存器分配算法和活躍變量分析算法的具體實現。最后，我們介紹代碼生成實踐的額外提示實現方法。本章的實踐內容基于第4章實踐內容生成的中間代碼表示形式，進一步將中間代碼翻譯為我們的目標語言MIPS32匯編代碼。

在第6章中間代碼優化中，主要的理論內容是基于程序分析技術的中間代碼優化。我們首先概要性地介紹程序分析技術，并重點介紹基本塊的定義和控制流圖的構建與分析技術。接著，我們進一步介紹局部分析與優化，詳細介紹數據流分析的算法與理論。在完成局部分析的理論介紹之后，我們進一步討論全局和過程間的分析與優化的方法。基于理論方法的討論，我們在實踐技術部分重點介紹基于三地址碼的符號表和有向無環圖構造過程中的實現細節。我們也詳細討論了基于迭代的數據流分析算法的實現細節，并進一步討論全局優化算法的實現。本章的實踐內容的輸入格式與第5章中相同，均基于第4章實踐內容生成的中間代碼表示形式，但本章重點考察基于中間代碼的優化，目標是將輸入的中間代碼經過本章理論方法部分介紹的算法優化之后，以更好的中間代碼的形式輸出。