作者：櫻雨樓

來(lái)源：https://home.cnblogs.com/u/yingyulou

源碼：https://github.com/yingyulou/CMM

編譯器實(shí)現(xiàn)之旅——第一章 編譯器概觀

編譯器，近在咫尺卻又遠(yuǎn)在天邊。當(dāng)我們寫(xiě)下任何非機(jī)器語(yǔ)言代碼后，我們都需要借助編譯器將這些代碼變?yōu)橥ㄟ^(guò)計(jì)算機(jī)可運(yùn)行的狀態(tài)。但是，就是這樣一個(gè)使用率極高的程序，我們對(duì)其卻知之甚少。什么是編譯器？編譯器對(duì)我們的代碼做了什么？又是怎么做的呢？如果你也懷有這些疑問(wèn)，想要深入編譯器內(nèi)部一探究竟的話，那就隨我一起踏上這趟編譯器實(shí)現(xiàn)的旅程吧。

1. 什么是編譯器

廣義上，編譯器是這樣一個(gè)程序：其讀入A語(yǔ)言代碼，并輸出B語(yǔ)言代碼。如下圖所示：

                +-------+
    A語(yǔ)言代碼 -> | 編譯器 | -> B語(yǔ)言代碼
                +-------+

僅從定義上看，A、B可以是同一種語(yǔ)言。也就是說(shuō)，如果我們寫(xiě)了一個(gè)只是具有“復(fù)制粘貼”功能的程序，其也可以被稱為是一個(gè)編譯器。但顯然，這樣的編譯器是無(wú)意義的。在實(shí)際中，編譯器的輸入一般是高級(jí)語(yǔ)言代碼，如C語(yǔ)言、Python語(yǔ)言等，而編譯器的輸出一般是低級(jí)語(yǔ)言代碼，如匯編語(yǔ)言、各種字節(jié)碼等。匯編語(yǔ)言代碼經(jīng)由匯編語(yǔ)言編譯器繼續(xù)編譯，最終產(chǎn)生機(jī)器語(yǔ)言，以供計(jì)算機(jī)執(zhí)行；而字節(jié)碼可由能夠執(zhí)行此字節(jié)碼的虛擬機(jī)執(zhí)行。這樣，就完成了一個(gè)程序從編寫(xiě)到執(zhí)行的過(guò)程。

2. 編譯器的結(jié)構(gòu)組成

編譯器的內(nèi)部并不是一個(gè)整體，而是由多個(gè)組件分工合作，共同完成編譯功能。這些組件總體上可被分為兩個(gè)部分：編譯器前端和編譯器后端。如下圖所示：

                +----------+               +----------+
    A語(yǔ)言代碼 -> | 編譯器前端 | -> 中間代碼 -> | 編譯器后端 | -> B語(yǔ)言代碼
                +----------+               +----------+

由于我們寫(xiě)下的高級(jí)語(yǔ)言代碼并不是編譯器比較喜歡的形式，故編譯器通過(guò)編譯器前端讀取、檢查并重新組織源代碼，使之等價(jià)變換為編譯器喜歡的形式，即中間代碼；一般來(lái)說(shuō)，語(yǔ)法錯(cuò)誤也由編譯器前端負(fù)責(zé)檢查。接下來(lái)，編譯器后端就拿著中間代碼進(jìn)行進(jìn)一步的檢查、優(yōu)化，最終生成目標(biāo)代碼。

事實(shí)上，編譯器前后端又分別可以進(jìn)一步細(xì)分為多個(gè)組件，這些組件將在我們接下來(lái)的旅程中逐一講述。

3. 我們將要實(shí)現(xiàn)什么

在這次旅程的終點(diǎn)，我們將實(shí)現(xiàn)一個(gè)名為CMM（即C Minus Minus）語(yǔ)言的編譯器，這個(gè)編譯器的輸出將是由我們自己設(shè)計(jì)的一套指令集中的指令所構(gòu)成的指令文件。所以，我們還將實(shí)現(xiàn)一套虛擬機(jī)程序，以運(yùn)行編譯器輸出的指令文件。

CMM語(yǔ)言是一門(mén)將C語(yǔ)言的語(yǔ)法進(jìn)行縮減后得到的語(yǔ)言。其主要特點(diǎn)如下：

• 只有一種類型：int
• 支持賦值、四則運(yùn)算與比較運(yùn)算
• 支持if、while語(yǔ)句
• 支持函數(shù)
• 支持?jǐn)?shù)組
• 區(qū)分全局作用域與局部作用域

接下來(lái)，就讓我們深入編譯器前端一探究竟吧。請(qǐng)看下一章：

編譯器實(shí)現(xiàn)之旅——第二章 編譯器前端概觀

在這一章的旅程中，我們將要深入編譯器前端一探究竟。看看編譯器前端到底由哪些組件組成，其分別又是在做什么。

1. 編譯器前端的結(jié)構(gòu)組成

似乎比我們想象的要簡(jiǎn)單，編譯器前端僅由兩個(gè)組件組成，詞法分析器與語(yǔ)法分析器。請(qǐng)看下圖：

             +----------+             +-----------+
    源代碼 -> | 詞法分析器 | -> 記號(hào)流 -> | 語(yǔ)法分析器 | -> 抽象語(yǔ)法樹(shù)
             +----------+             +-----------+

2. 什么是詞法分析器

詞法分析器（Lexer）是“前端中的前端”。作為整個(gè)編譯器的第一個(gè)組件，詞法分析器負(fù)責(zé)閱讀并分割源代碼，將編譯器看來(lái)“胡子連著辮子”的源代碼，分割為一個(gè)個(gè)的記號(hào)（Token）流，同時(shí)，詞法分析器還負(fù)責(zé)識(shí)別并歸類每一個(gè)記號(hào)。當(dāng)然了，一旦詞法分析器發(fā)現(xiàn)了一個(gè)不應(yīng)該出現(xiàn)的字符，其就會(huì)產(chǎn)生一個(gè)錯(cuò)誤信息。詞法分析器的工作內(nèi)容如下圖所示：

             +----------+
    源代碼 -> | 詞法分析器 | -> (記號(hào)的類別, 記號(hào)字符串), (記號(hào)的類別, 記號(hào)字符串), ...
             +----------+

我們將在詞法分析器的相關(guān)章節(jié)進(jìn)一步講述詞法分析器的故事。

3. 什么是語(yǔ)法分析器

源代碼在經(jīng)過(guò)詞法分析器無(wú)情的切割后，就到了語(yǔ)法分析器該上場(chǎng)的時(shí)候了。不難發(fā)現(xiàn)，詞法分析器所做的工作雖然很厲害，但其終究只是完成了類似于數(shù)據(jù)清洗的工作，輸出的只是線性的記號(hào)流，這就像一大段沒(méi)有章節(jié)，甚至沒(méi)有標(biāo)點(diǎn)的文字，根本沒(méi)法閱讀。

語(yǔ)法分析器利用詞法分析器的工作成果，將線性的，扁平的記號(hào)流，根據(jù)語(yǔ)法規(guī)則重新組織為一棵立體的巨大的樹(shù)，這就是抽象語(yǔ)法樹(shù)（AST）。抽象語(yǔ)法樹(shù)在整個(gè)編譯器中起著舉足輕重的地位，其是整個(gè)編譯器后端都很喜歡，并需要不斷訪問(wèn)的一種數(shù)據(jù)結(jié)構(gòu)。語(yǔ)法分析器的工作內(nèi)容如下圖所示：

                                                         +-----------+
    (記號(hào)的類別, 記號(hào)字符串), (記號(hào)的 類別, 記號(hào)字符串), ... -> | 語(yǔ)法分析器 | -> 抽象語(yǔ)法樹(shù)
                                                         +-----------+

我們將在語(yǔ)法分析器的相關(guān)章節(jié)進(jìn)一步講述語(yǔ)法分析器的故事。

接下來(lái)，就讓我們來(lái)看看這“前端中的前端”：詞法分析器，是怎么實(shí)現(xiàn)的吧。請(qǐng)看下一章：

編譯器實(shí)現(xiàn)之旅——第三章 實(shí)現(xiàn)詞法分析器前的準(zhǔn)備

在這一章的旅程中，我們將要為整個(gè)編譯器的“前端中的前端”：詞法分析器的實(shí)現(xiàn)做好充足的準(zhǔn)備。

1. 詞法分析器概觀

縱觀編譯器的輸入：源代碼，我們不難發(fā)現(xiàn)，源代碼說(shuō)白了也就是一個(gè)很長(zhǎng)很長(zhǎng)的字符串。而說(shuō)到字符串，我們不難想到字符串的分割函數(shù)。這類分割函數(shù)以空格，或任意的什么字符或字符串作為分隔符，將一個(gè)字符串分割成多個(gè)小字符串片段。這不就是詞法分析器么？你可能會(huì)想。但是，我們將遇到這樣的問(wèn)題：

    "1 + 1" -> ("1", "+", "1")
    "1+1"   -> ?

確實(shí)，使用普通的字符串分割函數(shù)可以很輕易的將上面第一個(gè)字符串進(jìn)行分割，但我們發(fā)現(xiàn)，無(wú)論怎么設(shè)置分隔符，我們都無(wú)法將第二個(gè)字符串也分割成同樣的結(jié)果了。也就是說(shuō)，普通的字符串分割函數(shù)及其算法是不能勝任詞法分析器的工作的，我們必須另想辦法。

要想分割一個(gè)字符串，其思路無(wú)非就是尋找一個(gè)分割點(diǎn)，然后將當(dāng)前起點(diǎn)到分割點(diǎn)的這段字符串分割出去，再將當(dāng)前起點(diǎn)設(shè)置于分割點(diǎn)之后，并繼續(xù)尋找下一個(gè)分割點(diǎn)，不斷重復(fù)這個(gè)過(guò)程，直至到達(dá)字符串的結(jié)尾。那么，為什么字符串分割函數(shù)不能勝任詞法分析器的工作呢？略加思索不難發(fā)現(xiàn)原因：字符串分割函數(shù)的“尋找下一個(gè)分割點(diǎn)”的邏輯過(guò)于簡(jiǎn)單了，只是一個(gè)相等性判斷。而我們所需要的邏輯更復(fù)雜，比如：看到一個(gè)空格，就分割；再比如：看到一個(gè)不是數(shù)字的字符，就分割；等等。所以，只要我們擴(kuò)充字符串分割函數(shù)的“尋找下一個(gè)分割點(diǎn)”的邏輯，我們就能實(shí)現(xiàn)出詞法分析器了。

2. 詞法分析器的狀態(tài)

我們首先需要做什么呢？我們需要為詞法分析器定義許多不同的狀態(tài)，處于不同狀態(tài)的詞法分析器執(zhí)行不同的行為。顯然，詞法分析器需要一個(gè)開(kāi)始狀態(tài)，一個(gè)完成狀態(tài)，其可能還需要一個(gè)或多個(gè)中間狀態(tài)。詞法分析器從開(kāi)始狀態(tài)開(kāi)始，不斷讀取源代碼中的每個(gè)字符，最終結(jié)束于完成狀態(tài)，當(dāng)詞法分析器處于完成狀態(tài)時(shí)，其就分割出了一個(gè)記號(hào)。詞法分析器不斷執(zhí)行這樣的“開(kāi)始, ..., 完成”過(guò)程，直至到達(dá)字符串的結(jié)尾。

為了獲知詞法分析器到底需要哪些狀態(tài)，我們需要看一看CMM語(yǔ)言對(duì)于記號(hào)的定義。請(qǐng)注意，這里的記號(hào)是廣義的，其不僅代表一個(gè)英文單詞，還代表一個(gè)符號(hào)，一串?dāng)?shù)字等，即，一個(gè)記號(hào)就是詞法分析器需要分割出來(lái)的一段字符串。CMM語(yǔ)言對(duì)于記號(hào)的定義如下所示：

1. 一串連續(xù)的，由大寫(xiě)或小寫(xiě)字母構(gòu)成的字符串
2. 一串連續(xù)的，由數(shù)字構(gòu)成的字符串
3. 這些符號(hào)：+ - * / < <= > >= == != = ; , ( ) [ ] { }
4. /* ... */ 構(gòu)成注釋
5. 關(guān)鍵詞：void int if else while return

這里需要說(shuō)明的是：所謂關(guān)鍵詞，僅僅是上述第1條的一種特例。即：當(dāng)我們分割出一個(gè)單詞時(shí)，我們需要額外判定一下這個(gè)單詞是不是關(guān)鍵詞，如果是，則我們需要將這個(gè)單詞的類別從“單詞”變?yōu)椤瓣P(guān)鍵詞XX”。例如：當(dāng)我們分割出字符串“abc”時(shí)，我們將其歸類為“單詞”；而當(dāng)我們分割出字符串“if”時(shí)，我們就需要將其歸類為“關(guān)鍵詞if”。

有了CMM語(yǔ)言對(duì)于記號(hào)的定義，我們就可以著手考慮詞法分析器到底需要哪些狀態(tài)了。我們不妨以上述第一條規(guī)則為例進(jìn)行思考，即：為了分割出一個(gè)單詞，詞法分析器需要哪些狀態(tài)？

首先，詞法分析器從“開(kāi)始”狀態(tài)開(kāi)始，如果此時(shí)詞法分析器讀入了一個(gè)大寫(xiě)或小寫(xiě)字母，則我們知道：接下來(lái)讀取到的將是一個(gè)單詞了；但同時(shí)，僅憑讀取到的這個(gè)字符，我們永遠(yuǎn)不可能知道當(dāng)前的這個(gè)單詞是否已經(jīng)讀取結(jié)束；我們只有看到一個(gè)不是大寫(xiě)或小寫(xiě)字母的字符時(shí)，才能確定剛剛的這個(gè)單詞已經(jīng)讀取結(jié)束了，我們應(yīng)令詞法分析器進(jìn)入“完成”狀態(tài)。為了處理這種情況，我們引入中間狀態(tài)“正在讀取單詞”。當(dāng)詞法分析器讀入一個(gè)大寫(xiě)或小寫(xiě)字母時(shí)，其應(yīng)立即由“開(kāi)始”狀態(tài)轉(zhuǎn)入“正在讀取單詞”狀態(tài)；詞法分析器應(yīng)保持這個(gè)狀態(tài)，并不斷讀入新的字符，直至當(dāng)前讀入的字符不是大寫(xiě)或小寫(xiě)字母，此時(shí)，詞法分析器應(yīng)立即由“正在讀取單詞”狀態(tài)轉(zhuǎn)入“完成”狀態(tài)，完成此次分割。

那么，如何利用上述思路，使詞法分析器跳過(guò)注釋呢？請(qǐng)看：

首先，詞法分析器還是從“開(kāi)始”狀態(tài)開(kāi)始，當(dāng)其讀入一個(gè)“/”時(shí)，我們此時(shí)并不知道這個(gè)“/”是一個(gè)除號(hào)，還是注釋的開(kāi)始，故我們先令詞法分析器進(jìn)入“正在讀取除號(hào)”這個(gè)中間狀態(tài)。在此狀態(tài)中，如果詞法分析器讀入的下一個(gè)字符是一個(gè)“”，則此時(shí)我們就可以確定詞法分析器現(xiàn)在進(jìn)入了注釋中，我們就再令詞法分析器轉(zhuǎn)入“正在讀取注釋”狀態(tài)；反之，如果詞法分析器讀入的下一個(gè)字符不是一個(gè)“”，我們也可以確定詞法分析器這次讀取到的真的是一個(gè)除號(hào)，此時(shí)，我們當(dāng)然是令詞法分析器進(jìn)入“完成”狀態(tài)。

當(dāng)詞法分析器處于“正在讀取注釋”狀態(tài)中時(shí)，我們需要關(guān)注兩件事：

1. 詞法分析器應(yīng)丟掉任何讀取到的字符
2. 詞法分析器應(yīng)努力的逃離注釋

怎么逃離注釋呢？顯然，如果要逃離注釋，我們就需要同時(shí)滿足這兩個(gè)條件：

1. 遇到一個(gè)“*”
2. 緊接著，再遇到一個(gè)“/”

所以，當(dāng)詞法分析器被困在注釋中時(shí)，其一邊一視同仁的丟掉一切讀取到的字符，一邊也留心著讀取到的字符是不是“”，如果是，詞法分析器就看到了希望。此時(shí)，詞法分析器應(yīng)轉(zhuǎn)入“正在逃離注釋”狀態(tài)，在這個(gè)狀態(tài)下，如果詞法分析器又讀取到了“/”，那么恭喜，此時(shí)詞法分析器就成功的逃離了注釋，又回到了久違的“開(kāi)始”狀態(tài)；如果不是“/”，希望也沒(méi)有完全破滅，此時(shí)，如果詞法分析器讀取到的還是“”，那么其就還應(yīng)該停留在“正在逃離注釋”狀態(tài)；而如果讀取到的既不是“/”也不是“*”，那么很遺憾，逃離就徹底失敗了，詞法分析器又將回退到“正在讀取注釋”狀態(tài)。

利用上述思路舉一反三，我們即可得到詞法分析器所需要的所有狀態(tài)了。請(qǐng)看：

1. 顯然，我們需要“開(kāi)始”和“完成”狀態(tài)
2. 為了讀取單詞和數(shù)字，我們需要“正在讀取單詞”和“正在讀取數(shù)字”狀態(tài)
3. 為了處理注釋相關(guān)問(wèn)題，我們需要“正在讀取除號(hào)”、“正在讀取注釋”和“正在逃離注釋”狀態(tài)
4. 為了明確詞法分析器讀取到的到底是“<”還是“<=”、是“>”還是“>=”、是“=”還是“==”，我們需要“正在讀取小于號(hào)”、“正在讀取大于號(hào)”和“正在讀取等號(hào)”狀態(tài)
5. 為了使詞法分析器正確的讀取到“!=”（而不是“!” + 別的錯(cuò)誤符號(hào)），我們需要“正在讀取不等號(hào)”狀態(tài)

至此，我們就得到了詞法分析器所需要的所有狀態(tài)。代碼如下所示：

enum class LEXER_STAGE
{
    // Start
    START,

    // abc...
    //  ^^^^^
    IN_ID,

    // 123...
    //  ^^^^^
    IN_NUMBER,

    // /?
    //  ^
    IN_DIVIDE,

    // /* ...
    //    ^^^
    IN_COMMENT,

    // ... */
    //      ^
    END_COMMENT,

    // <?
    //  ^
    IN_LESS,

    // >?
    //  ^
    IN_GREATER,

    // =?
    //  ^
    IN_ASSIGN,

    // !?
    //  ^
    IN_NOT,

    // Done
    DONE,
};

3. 記號(hào)的類別

當(dāng)詞法分析器讀取到一個(gè)記號(hào)后，我們就需要將其進(jìn)行歸類。有了詞法分析器的各種狀態(tài)的輔助，這樣的歸類將變的十分容易。例如，當(dāng)我們從“正在讀取數(shù)字”狀態(tài)轉(zhuǎn)移至“完成”狀態(tài)時(shí)，我們當(dāng)然知道當(dāng)前的這個(gè)記號(hào)的類別是“數(shù)字”；而當(dāng)我們讀取到一個(gè)“(”時(shí)，我們當(dāng)然也知道這個(gè)記號(hào)的類別是“左圓括號(hào)”；以此類推。我們可以從上文中給出的記號(hào)的定義中，得到所有記號(hào)的類別。代碼如下所示：

enum class TOKEN_TYPE
{
    // Word
    ID,                    // ID
    NUMBER,                // Number

    // Keyword
    VOID,                  // void
    INT,                   // int
    IF,                    // if
    ELSE,                  // else
    WHILE,                 // while
    RETURN,                // return

    // Operator
    PLUS,                  // +
    MINUS,                 // -
    MULTIPLY,              // *
    DIVIDE,                // /
    LESS,                  // <
    LESS_EQUAL,            // <=
    GREATER,               // >
    GREATER_EQUAL,         // >=
    EQUAL,                 // ==
    NOT_EQUAL,             // !=
    ASSIGN,                // =
    SEMICOLON,             // ;
    COMMA,                 // ,
    LEFT_ROUND_BRACKET,    // (
    RIGHT_ROUND_BRACKET,   // )
    LEFT_SQUARE_BRACKET,   // [
    RIGHT_SQUARE_BRACKET,  // ]
    LEFT_CURLY_BRACKET,    // {
    RIGHT_CURLY_BRACKET,   // }

    // EOF
    END_OF_FILE,           // EOF

    // AST
    DECL_LIST,             // AST: DeclList
    VAR_DECL,              // AST: VarDecl
    FUNC_DECL,             // AST: FuncDecl
    PARAM_LIST,            // AST: ParamList
    PARAM,                 // AST: Param
    COMPOUND_STMT,         // AST: CompoundStmt
    LOCAL_DECL,            // AST: LocalDecl
    STMT_LIST,             // AST: StmtList
    IF_STMT,               // AST: IfStmt
    WHILE_STMT,            // AST: WhileStmt
    RETURN_STMT,           // AST: ReturnStmt
    EXPR,                  // AST: Expr
    VAR,                   // AST: Var
    SIMPLE_EXPR,           // AST: SimpleExpr
    ADD_EXPR,              // AST: AddExpr
    TERM,                  // AST: Term
    CALL,                  // AST: Call
    ARG_LIST,              // AST: ArgList
};

需要說(shuō)明的是，上述代碼的最后一部分是AST節(jié)點(diǎn)類別，與詞法分析器無(wú)關(guān)。我們將在后續(xù)的旅程中講述這部分類別的作用。

4. 其他準(zhǔn)備工作

在實(shí)現(xiàn)詞法分析器之前，我們還有一些比較簡(jiǎn)單的準(zhǔn)備工作需要做，列舉如下：

1. 我們需要定義一個(gè)用于保存記號(hào)的結(jié)構(gòu)體：

struct Token
{
    // Attribute
    TOKEN_TYPE tokenType;
    string tokenStr;
    int lineNo;
};

在這個(gè)結(jié)構(gòu)體中，我們保存了記號(hào)的類別、記號(hào)字符串，以及這個(gè)記號(hào)在源代碼中所處的行數(shù)。

1. 我們需要定義一個(gè)哈希表，以完成普通單詞到關(guān)鍵詞的識(shí)別與轉(zhuǎn)換：

const unordered_map<string, TOKEN_TYPE> KEYWORD_MAP
{
    {"void",   TOKEN_TYPE::VOID},
    {"int",    TOKEN_TYPE::INT},
    {"if",     TOKEN_TYPE::IF},
    {"else",   TOKEN_TYPE::ELSE},
    {"while",  TOKEN_TYPE::WHILE},
    {"return", TOKEN_TYPE::RETURN},
};

通過(guò)鍵的存在性檢測(cè)，我們就可以判定一個(gè)單詞是否是一個(gè)關(guān)鍵詞了；如果是，我們也可以得到這個(gè)關(guān)鍵詞所對(duì)應(yīng)的記號(hào)的類別。

1. 我們需要定義一個(gè)報(bào)錯(cuò)函數(shù)，用于在詞法分析器發(fā)現(xiàn)語(yǔ)法錯(cuò)誤時(shí)報(bào)錯(cuò)并退出：

void InvalidChar(char invalidChar, int lineNo)
{
    printf("Invalid char: %c in line: %d\n", invalidChar, lineNo);

    exit(1);
}

至此，我們就完成了所有準(zhǔn)備工作，可以開(kāi)始實(shí)現(xiàn)詞法分析器了。請(qǐng)看下一章：《實(shí)現(xiàn)詞法分析器》。

貓注：《編譯器實(shí)現(xiàn)之旅》共有 17 篇文章，剩余文章請(qǐng)移步小姐姐的博客查看。博客地址：https://home.cnblogs.com/u/yingyulou