（3）：詞法分析器 · 手把手教你做一個 C 語言編譯器

# 手把手教你做一個 C 語言編譯器（3）：詞法分析器本章我們要講解如何構建詞法分析器。 **本系列：** 1. [手把手教你做一個 C 語言編譯器（0）：前言](http://blog.jobbole.com/97332/) 2. [手把手教你做一個 C 語言編譯器（1）：設計](http://blog.jobbole.com/97350/) 3. [手把手教你做一個 C 語言編譯器（2）：虛擬機](http://blog.jobbole.com/97359/) ## 什么是詞法分析器簡而言之，詞法分析器用于對源碼字符串做預處理，以減少語法分析器的復雜程度。詞法分析器以源碼字符串為輸入，輸出為標記流（token stream），即一連串的標記，每個標記通常包括： `(token, token value)` 即標記本身和標記的值。例如，源碼中若包含一個數字 `'998'` ，詞法分析器將輸出 `(Number, 998)`，即（數字，998）。再例如： ``` 2 + 3 * (4 - 5) => (Number, 2) Add (Number, 3) Multiply Left-Bracket (Number, 4) Subtract (Number, 5) Right-Bracket ``` 通過詞法分析器的預處理，語法分析器的復雜度會大大降低，這點在后面的語法分析器我們就能體會。 ## 詞法分析器與編譯器要是深入詞法分析器，你就會發現，它的本質上也是編譯器。我們的編譯器是以標記流為輸入，輸出匯編代碼，而詞法分析器則是以源碼字符串為輸入，輸出標記流。 ``` +-------+ +--------+ -- source code --> | lexer | --> token stream --> | parser | --> assembly +-------+ +--------+ ``` 在這個前提下，我們可以這樣認為：直接從源代碼編譯成匯編代碼是很困難的，因為輸入的字符串比較難處理。所以我們先編寫一個較為簡單的編譯器（詞法分析器）來將字符串轉換成標記流，而標記流對于語法分析器而言就容易處理得多了。 ## 詞法分析器的實現由于詞法分析的工作很常見，但又枯燥且容易出錯，所以人們已經開發出了許多工具來生成詞法分析器，如 `lex, flex`。這些工具允許我們通過正則表達式來識別標記。這里注意的是，我們并不會一次性地將所有源碼全部轉換成標記流，原因有二： 1. 字符串轉換成標記流有時是有狀態的，即與代碼的上下文是有關系的。 2. 保存所有的標記流沒有意義且浪費空間。所以實際的處理方法是提供一個函數（即前幾篇中提到的 `next()`），每次調用該函數則返回下一個標記。 ### 支持的標記在全局中添加如下定義： ``` // tokens and classes (operators last and in precedence order) enum { Num = 128, Fun, Sys, Glo, Loc, Id, Char, Else, Enum, If, Int, Return, Sizeof, While, Assign, Cond, Lor, Lan, Or, Xor, And, Eq, Ne, Lt, Gt, Le, Ge, Shl, Shr, Add, Sub, Mul, Div, Mod, Inc, Dec, Brak }; ``` 這些就是我們要支持的標記符。例如，我們會將 `=` 解析為 `Assign`；將 `==` 解析為`Eq`；將 `!=` 解析為 `Ne` 等等。所以這里我們會有這樣的印象，一個標記（token）可能包含多個字符，且多數情況下如此。而詞法分析器能減小語法分析復雜度的原因，正是因為它相當于通過一定的編碼（更多的標記）來壓縮了源碼字符串。當然，上面這些標記是有順序的，跟它們在 C 語言中的優先級有關，如 `*(Mul)` 的優先級就要高于 `+(Add)`。它們的具體使用在后面的語法分析中會提到。最后要注意的是還有一些字符，它們自己就構成了標記，如右方括號 `]` 或波浪號 `~`等。我們不另外處理它們的原因是： 1. 它們是單字符的，即并不是多個字符共同構成標記（如 `==` 需要兩個字符）； 2. 它們不涉及優先級關系。 ### 詞法分析器的框架即 `next()` 函數的主體： ``` void next() { char *last_pos; int hash; while (token = *src) { ++src; // parse token here } return; } ``` 這里的一個問題是，為什么要用 `while` 循環呢？這就涉及到編譯器（記得我們說過詞法分析器也是某種意義上的編譯器）的一個問題：如何處理錯誤？對詞法分析器而言，若碰到了一個我們不認識的字符該怎么處理？一般處理的方法有兩種： 1. 指出錯誤發生的位置，并退出整個程序 2. 指出錯誤發生的位置，跳過當前錯誤并繼續編譯這個 `while` 循環的作用就是跳過這些我們不識別的字符，我們同時還用它來處理空白字符。我們知道，C 語言中空格是用來作為分隔用的，并不作為語法的一部分。因此在實現中我們將它作為“不識別”的字符，這個 `while` 循環可以用來跳過它。 ### 換行符換行符和空格類似，但有一點不同，每次遇到換行符，我們需要將當前的行號加一： ``` // parse token here ... if (token == '\n') { ++line; } ... ``` ### 宏定義 C 語言的宏定義以字符 `#` 開頭，如 `# include <stdio.h>`。我們的編譯器并不支持宏定義，所以直接跳過它們。 ``` else if (token == '#') { // skip macro, because we will not support it while (*src != 0 && *src != '\n') { src++; } } ``` ### 標識符與符號表標識符（identifier）可以理解為變量名。對于語法分析而言，我們并不關心一個變量具體叫什么名字，而只關心這個變量名代表的唯一標識。例如 `int a;` 定義了變量`a`，而之后的語句 `a = 10`，我們需要知道這兩個 `a` 指向的是同一個變量。基于這個理由，詞法分析器會把掃描到的標識符全都保存到一張表中，遇到新的標識符就去查這張表，如果標識符已經存在，就返回它的唯一標識。那么我們怎么表示標識符呢？如下： ``` struct identifier { int token; int hash; char * name; int class; int type; int value; int Bclass; int Btype; int Bvalue; } ``` 這里解釋一下具體的含義： 1. `token`：該標識符返回的標記，理論上所有的變量返回的標記都應該是 `Id`，但實際上由于我們還將在符號表中加入關鍵字如 `if`, `while` 等，它們都有對應的標記。 2. `hash`：顧名思義，就是這個標識符的哈希值，用于標識符的快速比較。 3. `name`：存放標識符本身的字符串。 4. `class`：該標識符的類別，如數字，全局變量或局部變量等。 5. `type`：標識符的類型，即如果它是個變量，變量是 `int` 型、`char` 型還是指針型。 6. `value`：存放這個標識符的值，如標識符是函數，剛存放函數的地址。 7. `BXXXX`：C 語言中標識符可以是全局的也可以是局部的，當局部標識符的名字與全局標識符相同時，用作保存全局標識符的信息。由上可以看出，我們實現的詞法分析器與傳統意義上的詞法分析器不太相同。傳統意義上的符號表只需要知道標識符的唯一標識即可，而我們還存放了一些只有語法分析器才會得到的信息，如 `type` 。由于我們的目標是能自舉，而我們定義的語法不支持 `struct`，故而使用下列方式。 ``` Symbol table: ----+-----+----+----+----+-----+-----+-----+------+------+---- .. |token|hash|name|type|class|value|btype|bclass|bvalue| .. ----+-----+----+----+----+-----+-----+-----+------+------+---- |<--- one single identifier --->| ``` 即用一個整型數組來保存相關的ID信息。每個ID占用數組中的9個空間，分析標識符的相關代碼如下： ``` int token_val; // value of current token (mainly for number) int *current_id, // current parsed ID *symbols; // symbol table // fields of identifier enum {Token, Hash, Name, Type, Class, Value, BType, BClass, BValue, IdSize}; void next() { ... else if ((token >= 'a' && token <= 'z') || (token >= 'A' && token <= 'Z') || (token == '_')) { // parse identifier last_pos = src - 1; hash = token; while ((*src >= 'a' && *src <= 'z') || (*src >= 'A' && *src <= 'Z') || (*src >= '0' && *src <= '9') || (*src == '_')) { hash = hash * 147 + *src; src++; } // look for existing identifier, linear search current_id = symbols; while (current_id[Token]) { if (current_id[Hash] == hash && !memcmp((char *)current_id[Name], last_pos, src - last_pos)) { //found one, return token = current_id[Token]; return; } current_id = current_id + IdSize; } // store new ID current_id[Name] = (int)last_pos; current_id[Hash] = hash; token = current_id[Token] = Id; return; } ... } ``` 查找已有標識符的方法是線性查找 `symbols` 表。 ### 數字數字中較為復雜的一點是需要支持十進制、十六進制及八進制。邏輯也較為直接，可能唯一不好理解的是獲取十六進制的值相關的代碼。 ``` token_val = token_val * 16 + (token & 16) + (token >= 'A' ? 9 : 0); ``` 這里要注意的是在ASCII碼中，字符`a`對應的十六進制值是 `61`, `A`是`41`，故通過`(token & 16)` 可以得到個位數的值。其它就不多說了，這里這樣寫的目的是裝B（其實是抄 c4 的源代碼的）。 ``` void next() { ... else if (token >= '0' && token <= '9') { // parse number, three kinds: dec(123) hex(0x123) oct(017) token_val = token - '0'; if (token_val > 0) { // dec, starts with [1-9] while (*src >= '0' && *src <= '9') { token_val = token_val*10 + *src++ - '0'; } } else { // starts with number 0 if (*src == 'x' || *src == 'X') { //hex token = *++src; while ((token >= '0' && token <= '9') || (token >= 'a' && token <= 'f') || (token >= 'A' && token <= 'F')) { token_val = token_val * 16 + (token & 15) + (token >= 'A' ? 9 : 0); token = *++src; } } else { // oct while (*src >= '0' && *src <= '7') { token_val = token_val*8 + *src++ - '0'; } } } token = Num; return; } ... } ``` ### 字符串在分析時，如果分析到字符串，我們需要將它存放到前一篇文章中說的 `data` 段中。然后返回它在 `data` 段中的地址。另一個特殊的地方是我們需要支持轉義符。例如用`\n` 表示換行符。由于本編譯器的目的是達到自己編譯自己，所以代碼中并沒有支持除`\n` 的轉義符，如 `\t`, `\r` 等，但仍支持 `\a` 表示字符 `a` 的語法，如 `\"` 表示 `"`。在分析時，我們將同時分析單個字符如 `'a'` 和字符串如 `"a string"`。若得到的是單個字符，我們以 `Num` 的形式返回。相關代碼如下： ``` void next() { ... else if (token == '"' || token == '\'') { // parse string literal, currently, the only supported escape // character is '\n', store the string literal into data. last_pos = data; while (*src != 0 && *src != token) { token_val = *src++; if (token_val == '\\') { // escape character token_val = *src++; if (token_val == 'n') { token_val = '\n'; } } if (token == '"') { *data++ = token_val; } } src++; // if it is a single character, return Num token if (token == '"') { token_val = (int)last_pos; } else { token = Num; } return; } } ``` ### 注釋在我們的 C 語言中，只支持 `//` 類型的注釋，不支持 `/* comments */` 的注釋。 ``` void next() { ... else if (token == '/') { if (*src == '/') { // skip comments while (*src != 0 && *src != '\n') { ++src; } } else { // divide operator token = Div; return; } } ... } ``` 這里我們要額外介紹 `lookahead` 的概念，即提前看多個字符。上述代碼中我們看到，除了跳過注釋，我們還可能返回除號 `/(Div)` 標記。提前看字符的原理是：有一個或多個標記是以同樣的字符開頭的（如本小節中的注釋與除號），因此只憑當前的字符我們并無法確定具體應該解釋成哪一個標記，所以只能再向前查看字符，如本例需向前查看一個字符，若是 `/` 則說明是注釋，反之則是除號。我們之前說過，詞法分析器本質上也是編譯器，其實提前看字符的概念也存在于編譯器，只是這時就是提前看k個“標記”而不是“字符”了。平時聽到的 `LL(k)` 中的 `k` 就是需要向前看的標記的個數了。另外，我們用詞法分析器將源碼轉換成標記流，能減小語法分析復雜度，原因之一就是減少了語法分析器需要“向前看”的字符個數。 ### 其它其它的標記的解析就相對容易一些了，我們直接貼上代碼： ``` void next() { ... else if (token == '=') { // parse '==' and '=' if (*src == '=') { src ++; token = Eq; } else { token = Assign; } return; } else if (token == '+') { // parse '+' and '++' if (*src == '+') { src ++; token = Inc; } else { token = Add; } return; } else if (token == '-') { // parse '-' and '--' if (*src == '-') { src ++; token = Dec; } else { token = Sub; } return; } else if (token == '!') { // parse '!=' if (*src == '=') { src++; token = Ne; } return; } else if (token == '<') { // parse '<=', '<<' or '<' if (*src == '=') { src ++; token = Le; } else if (*src == '<') { src ++; token = Shl; } else { token = Lt; } return; } else if (token == '>') { // parse '>=', '>>' or '>' if (*src == '=') { src ++; token = Ge; } else if (*src == '>') { src ++; token = Shr; } else { token = Gt; } return; } else if (token == '|') { // parse '|' or '||' if (*src == '|') { src ++; token = Lor; } else { token = Or; } return; } else if (token == '&') { // parse '&' and '&&' if (*src == '&') { src ++; token = Lan; } else { token = And; } return; } else if (token == '^') { token = Xor; return; } else if (token == '%') { token = Mod; return; } else if (token == '*') { token = Mul; return; } else if (token == '[') { token = Brak; return; } else if (token == '?') { token = Cond; return; } else if (token == '~' || token == ';' || token == '{' || token == '}' || token == '(' || token == ')' || token == ']' || token == ',' || token == ':') { // directly return the character as token; return; } ... } ``` 代碼較多，但主要邏輯就是向前看一個字符來確定真正的標記。 ### 關鍵字與內置函數雖然上面寫完了詞法分析器，但還有一個問題需要考慮，那就是“關鍵字”，例如 `if`,`while`, `return` 等。它們不能被作為普通的標識符，因為有特殊的含義。一般有兩種處理方法： 1. 詞法分析器中直接解析這些關鍵字。 2. 在語法分析前將關鍵字提前加入符號表。這里我們就采用第二種方法，將它們加入符號表，并提前為它們賦予必要的信息（還記得前面說的標識符 `Token` 字段嗎？）。這樣當源代碼中出現關鍵字時，它們會被解析成標識符，但由于符號表中已經有了相關的信息，我們就能知道它們是特殊的關鍵字。內置函數的行為也和關鍵字類似，不同的只是賦值的信息，在`main`函數中進行初始化如下： ``` // types of variable/function enum { CHAR, INT, PTR }; int *idmain; // the `main` function void main() { ... src = "char else enum if int return sizeof while " "open read close printf malloc memset memcmp exit void main"; // add keywords to symbol table i = Char; while (i <= While) { next(); current_id[Token] = i++; } // add library to symbol table i = OPEN; while (i <= EXIT) { next(); current_id[Class] = Sys; current_id[Type] = INT; current_id[Value] = i++; } next(); current_id[Token] = Char; // handle void type next(); idmain = current_id; // keep track of main ... program(); } ``` ## 代碼本章的代碼可以在 [Github](https://github.com/lotabout/write-a-C-interpreter/tree/step-2) 上下載，也可以直接 clone ``` git clone -b step-2 https://github.com/lotabout/write-a-C-interpreter ``` 上面的代碼運行后會出現 ‘Segmentation Falt’，這是正常的，因為它會嘗試運行我們上一章創建的虛擬機，但其中并沒有任何匯編代碼。 ## 小結本章我們為我們的編譯器構建了詞法分析器，通過本章的學習，我認為有幾個要點需要強調： 1. 詞法分析器的作用是對源碼字符串進行預處理，作用是減小語法分析器的復雜程度。 2. 詞法分析器本身可以認為是一個編譯器，輸入是源碼，輸出是標記流。 3. `lookahead(k)` 的概念，即向前看 `k` 個字符或標記。 4. 詞法分析中如何處理標識符與符號表。下一章中，我們將介紹遞歸下降的語法分析器。我們下一章見。