文章中引用的代碼均來自https://github.com/vczh/tinymoe。

?

實(shí)現(xiàn)Tinymoe的第一步自然是一個(gè)詞法分析器。詞法分析其所作的事情很簡單，就是把一份代碼分割成若干個(gè)token，記錄下他們所在文件的位置，以及丟掉不必要的信息。但是Tinymoe是一個(gè)按行分割的語言，自然token列表也就是二維的，第一維是行，第二維是每一行的token。在繼續(xù)講詞法分析器之前，先看看Tinymoe包含多少token：

• 符號：(、)、,、:、&、+、-、*、/、\、%、<、>、<=、>=、=、<>
• 關(guān)鍵字：module、using、phrase、sentence、block、symbol、type、cps、category、expression、argument、assignable、list、end、and、or、not
• 數(shù)字：123、456.789
• 字符串："abc\r\ndef"
• 標(biāo)識符：tinymoe
• 注釋：-- this is a comment

?

Tinymoe對于token有一個(gè)特殊的規(guī)定，就是字符串和注釋都是單行的。因此如果一個(gè)字符串在沒有結(jié)束之前就遇到了換行，那么這種寫法定義為你遇到了一個(gè)沒有右雙引號的字符串，需要報(bào)個(gè)錯(cuò)，然后下一行就不是這個(gè)字符串的內(nèi)容了。

?

一個(gè)詞法分析器所需要做的事情，就是把一個(gè)字符串分解成描述此法的數(shù)據(jù)結(jié)構(gòu)。既然上面已經(jīng)說到Tinymoe的token列表是二維的，因此數(shù)據(jù)結(jié)構(gòu)肯定會體現(xiàn)這個(gè)觀點(diǎn)。Tinymoe的詞法分析器代碼可以在這里找到：https://github.com/vczh/tinymoe/blob/master/Development/Source/Compiler/TinymoeLexicalAnalyzer.h。

?

首先是token：

CodeTokenType是一個(gè)枚舉類型，標(biāo)記一個(gè)token的類型。這個(gè)類型比較細(xì)化，每一個(gè)關(guān)鍵字有自己的類型，每一個(gè)符號也有自己的類型，剩下的按種類來分。我們可以看到token需要記錄的最關(guān)鍵的東西只有三個(gè)：類型、內(nèi)容和代碼位置。在token記錄代碼位置是十分重要的，正確地記錄代碼位置可以讓你能夠報(bào)告帶位置的錯(cuò)誤、從語法樹的節(jié)點(diǎn)還原成代碼位置、甚至在調(diào)試的時(shí)候可以把指令也換成位置。

?

這里需要提到的是，string_t是一個(gè)typedef，具體的聲明可以在這里看到：https://github.com/vczh/tinymoe/blob/master/Development/Source/TinymoeSTL.h。Tinymoe是完全由標(biāo)準(zhǔn)的C++11和STL寫成的，但是為了適應(yīng)不同情況的需要，Tinymoe分為依賴code page的版本和Unicode版本。如果編譯Tinymoe代碼的時(shí)候聲明了全局的宏UNICODE_TINYMOE的話，那Tinymoe所有的字符處理將使用wchar_t，否則使用char。char的類型和Tinymoe編譯器在運(yùn)行的時(shí)候操作系統(tǒng)當(dāng)前的code page是綁定的。所以這里會有類似string_t啊、ifstream_t啊、char_t等類型，會在不同的編譯選項(xiàng)的影響下指向不同的STL類型或者原生的C++類型。github上的VC++2013工程使用的是wchar_t的版本，所以string_t就是std::wstring。

?

Tinymoe的詞法分析器除了token的類型以外，肯定還需要定義整個(gè)文件結(jié)構(gòu)在詞法分析后的結(jié)果：

這個(gè)數(shù)據(jù)結(jié)構(gòu)體現(xiàn)了"Tinymoe的token列表是二維的"的這個(gè)觀點(diǎn)。一個(gè)文件會被詞法分析器處理成一個(gè)shared_ptr<CodeFIle>對象，CodeFile::lines記錄了所有非空的行，CodeLine::tokens記錄了該行的所有token。

?

現(xiàn)在讓我們來看詞法分析的具體過程。關(guān)于如何從正則表達(dá)式構(gòu)造詞法分析器可以在這里（http://www.shnenglu.com/vczh/archive/2008/05/22/50763.html）看到，不過我們今天要講一講如何人肉構(gòu)造詞法分析器。方法其實(shí)是一樣的，首先人肉構(gòu)造狀態(tài)機(jī)，然后把用狀態(tài)機(jī)分析輸入的字符串的代碼抄過來就可以了。但是很少有人會解耦得那么開，因?yàn)檫@樣寫很容易看不懂，其次有可能會遇到一些極端情況是你無法用純粹的正則表達(dá)式來分詞的，譬如說C++的raw string literal：R"tinymoe(這里的字符串沒有轉(zhuǎn)義)tinymoe"。一個(gè)用【R"<一些字符>(】開始的字符串只能由【)<同樣的字符>"】來結(jié)束，要順利分析這種情況，只能通過在狀態(tài)機(jī)里面做hack才能解決。這就是為什么我們?nèi)巳鈽?gòu)造詞法分析器的時(shí)候，會把狀態(tài)和動作都混在一起寫，因?yàn)檫@樣便于處理特殊情況。

?

不過幸好的是，Tinymoe并沒有這種情況發(fā)生。所以我們可以直接從狀態(tài)機(jī)入手。為了簡單起見，我在下面的狀態(tài)機(jī)中去掉所有不是+和-的符號。首先，我們需要一個(gè)起始狀態(tài)和一個(gè)結(jié)束狀態(tài)：

?

首先我們添加整數(shù)和標(biāo)識符進(jìn)去：

?

其次是加減和浮點(diǎn)：

?

最后把字符串和注釋補(bǔ)全：

?

這樣狀態(tài)機(jī)就已經(jīng)完成了。讀過編譯原理的可能會問，為什么終結(jié)狀態(tài)都是由虛線而不是帶有輸入的實(shí)現(xiàn)指向的？因?yàn)樘摼€在這里有特殊的意義，也就是說它不能移動輸入的字符串的指針，而且他還要負(fù)責(zé)添加一個(gè)token。當(dāng)狀態(tài)跳到End之后，那他就會變成Start，所以實(shí)際上Start和End是同一個(gè)狀態(tài)。這個(gè)狀態(tài)機(jī)也不是輸入什么字符都能跳轉(zhuǎn)到下一個(gè)狀態(tài)的。所以當(dāng)你發(fā)現(xiàn)輸入的字符讓你無路可走的時(shí)候，你就是遇到了一個(gè)詞法錯(cuò)誤。

?

這樣我們的設(shè)計(jì)就算完成了，接下來就是如何用C++來實(shí)現(xiàn)它了。為了讓代碼更容易閱讀，我們應(yīng)該給Start和1-9這么多狀態(tài)起名字，做法如下：

在這里類似狀態(tài)3這樣的狀態(tài)被我省略掉了，因?yàn)檫@個(gè)狀態(tài)唯一的出路就是虛線，所以跳到這個(gè)狀態(tài)意味著你要立刻執(zhí)行虛線，也就是說你不需要做"跳到這個(gè)狀態(tài)"這個(gè)動作。因此它不需要有一個(gè)名字。

?

然后你只要按照下面的做法翻譯這個(gè)狀態(tài)機(jī)就可以了：

?

只要寫到這里，那么我們就初步完成了詞法分析器了。其實(shí)任何系統(tǒng)的主要功能都是相對容易實(shí)現(xiàn)的，往往是次要的功能才需要花費(fèi)大量的精力來完成，而且還很容易出錯(cuò)。在這里"次要的功能"就是——記錄token的行列號，還有維護(hù)CodeFile::lines避免空行的出現(xiàn)！

?

盡管我已經(jīng)做過了那么多次詞法分析器，但是我仍然無法一氣呵成寫對，仍然會出一些bug。面對編譯器這種純計(jì)算程序，debug的最好方法就是寫單元測試。不過對于不熟悉單元測試的人來講可能很難一下子想到要做什么測試，在這里我可以把我給Tinymoe謝的一部分單元測試在這里貼一下。

?

第一個(gè)，當(dāng)然是傳說中的"Hello, world!"測試了：

?

TEST_CASE和TEST_ASSERT（這里暫時(shí)沒有直接用到TEST_ASSERT）是我為了開發(fā)Tinymoe隨手?jǐn)]的一個(gè)宏，可以在Tinymoe的代碼里看到。為了檢查我們有沒有粗心大意，我們有必要檢查詞法分析器的任何一個(gè)輸出的數(shù)據(jù)，譬如每一行有多少token，譬如每一個(gè)token的行號列好內(nèi)容和類型。我為了讓這些枯燥的測試用例容易看懂，在這個(gè)文件（

?

第二個(gè)測試用例針對的是整數(shù)和浮點(diǎn)的輸出和報(bào)錯(cuò)上，重點(diǎn)在于檢查每一個(gè)token的列號是不是正確的計(jì)算了出來：

?

第三個(gè)測試用例的重點(diǎn)主要是-符號和—注釋的分析：

?

第四個(gè)測試用例則是測試字符串的escaping和在面對換行的時(shí)候是否正確的處理（之前提到字符串不能換行，遇到一個(gè)突然的換行將會被看成缺少雙引號）：

?

鑒于詞法分析本來內(nèi)容也不多，所以這篇文章也不會太長。相信有前途的程序員也會在這里得到一些編譯原理以外的知識。下一篇文章將會描述Tinymoe的函數(shù)頭的語法分析部分，將會描述一個(gè)編譯器的不帶歧義的語法分析是如何人肉出來的。敬請期待。