文章中引用的代碼均來(lái)自https://github.com/vczh/tinymoe。
?
實(shí)現(xiàn)Tinymoe的第一步自然是一個(gè)詞法分析器。詞法分析其所作的事情很簡(jiǎn)單，就是把一份代碼分割成若干個(gè)token，記錄下他們所在文件的位置，以及丟掉不必要的信息。但是Tinymoe是一個(gè)按行分割的語(yǔ)言，自然token列表也就是二維的，第一維是行，第二維是每一行的token。在繼續(xù)講詞法分析器之前，先看看Tinymoe包含多少token：
符號(hào)：(、)、,、:、&、+、-、*、/、\、%、<、>、<=、>=、=、<>
關(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)識(shí)符：tinymoe
注釋：-- this is a comment
?
Tinymoe對(duì)于token有一個(gè)特殊的規(guī)定，就是字符串和注釋都是單行的。因此如果一個(gè)字符串在沒(méi)有結(jié)束之前就遇到了換行，那么這種寫(xiě)法定義為你遇到了一個(gè)沒(méi)有右雙引號(hào)的字符串，需要報(bào)個(gè)錯(cuò)，然后下一行就不是這個(gè)字符串的內(nèi)容了。
?
一個(gè)詞法分析器所需要做的事情，就是把一個(gè)字符串分解成描述此法的數(shù)據(jù)結(jié)構(gòu)。既然上面已經(jīng)說(shuō)到Tinymoe的token列表是二維的，因此數(shù)據(jù)結(jié)構(gòu)肯定會(huì)體現(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è)符號(hào)也有自己的類型，剩下的按種類來(lái)分。我們可以看到token需要記錄的最關(guān)鍵的東西只有三個(gè)：類型、內(nèi)容和代碼位置。在token記錄代碼位置是十分重要的，正確地記錄代碼位置可以讓你能夠報(bào)告帶位置的錯(cuò)誤、從語(yǔ)法樹(shù)的節(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寫(xiě)成的，但是為了適應(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是綁定的。所以這里會(huì)有類似string_t啊、ifstream_t啊、char_t等類型，會(huì)在不同的編譯選項(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è)文件會(huì)被詞法分析器處理成一個(gè)shared_ptr<CodeFIle>對(duì)象，CodeFile::lines記錄了所有非空的行，CodeLine::tokens記錄了該行的所有token。
?
現(xiàn)在讓我們來(lái)看詞法分析的具體過(guò)程。關(guān)于如何從正則表達(dá)式構(gòu)造詞法分析器可以在這里（http://m.shnenglu.com/vczh/archive/2008/05/22/50763.html）看到，不過(guò)我們今天要講一講如何人肉構(gòu)造詞法分析器。方法其實(shí)是一樣的，首先人肉構(gòu)造狀態(tài)機(jī)，然后把用狀態(tài)機(jī)分析輸入的字符串的代碼抄過(guò)來(lái)就可以了。但是很少有人會(huì)解耦得那么開(kāi)，因?yàn)檫@樣寫(xiě)很容易看不懂，其次有可能會(huì)遇到一些極端情況是你無(wú)法用純粹的正則表達(dá)式來(lái)分詞的，譬如說(shuō)C++的raw string literal：R"tinymoe(這里的字符串沒(méi)有轉(zhuǎn)義)tinymoe"。一個(gè)用【R"<一些字符>(】開(kāi)始的字符串只能由【)<同樣的字符>"】來(lái)結(jié)束，要順利分析這種情況，只能通過(guò)在狀態(tài)機(jī)里面做hack才能解決。這就是為什么我們?nèi)巳鈽?gòu)造詞法分析器的時(shí)候，會(huì)把狀態(tài)和動(dòng)作都混在一起寫(xiě)，因?yàn)檫@樣便于處理特殊情況。
?
不過(guò)幸好的是，Tinymoe并沒(méi)有這種情況發(fā)生。所以我們可以直接從狀態(tài)機(jī)入手。為了簡(jiǎn)單起見(jiàn)，我在下面的狀態(tài)機(jī)中去掉所有不是+和-的符號(hào)。首先，我們需要一個(gè)起始狀態(tài)和一個(gè)結(jié)束狀態(tài)：
?
首先我們添加整數(shù)和標(biāo)識(shí)符進(jìn)去：
?
其次是加減和浮點(diǎn)：
?
最后把字符串和注釋補(bǔ)全：
?
這樣狀態(tài)機(jī)就已經(jīng)完成了。讀過(guò)編譯原理的可能會(huì)問(wèn)，為什么終結(jié)狀態(tài)都是由虛線而不是帶有輸入的實(shí)現(xiàn)指向的？因?yàn)樘摼€在這里有特殊的意義，也就是說(shuō)它不能移動(dòng)輸入的字符串的指針，而且他還要負(fù)責(zé)添加一個(gè)token。當(dāng)狀態(tài)跳到End之后，那他就會(huì)變成Start，所以實(shí)際上Start和End是同一個(gè)狀態(tài)。這個(gè)狀態(tài)機(jī)也不是輸入什么字符都能跳轉(zhuǎn)到下一個(gè)狀態(tài)的。所以當(dāng)你發(fā)現(xiàn)輸入的字符讓你無(wú)路可走的時(shí)候，你就是遇到了一個(gè)詞法錯(cuò)誤。
?
這樣我們的設(shè)計(jì)就算完成了，接下來(lái)就是如何用C++來(lái)實(shí)現(xiàn)它了。為了讓代碼更容易閱讀，我們應(yīng)該給Start和1-9這么多狀態(tài)起名字，做法如下：
在這里類似狀態(tài)3這樣的狀態(tài)被我省略掉了，因?yàn)檫@個(gè)狀態(tài)唯一的出路就是虛線，所以跳到這個(gè)狀態(tài)意味著你要立刻執(zhí)行虛線，也就是說(shuō)你不需要做"跳到這個(gè)狀態(tài)"這個(gè)動(dòng)作。因此它不需要有一個(gè)名字。
?
然后你只要按照下面的做法翻譯這個(gè)狀態(tài)機(jī)就可以了：
?
只要寫(xiě)到這里，那么我們就初步完成了詞法分析器了。其實(shí)任何系統(tǒng)的主要功能都是相對(duì)容易實(shí)現(xiàn)的，往往是次要的功能才需要花費(fèi)大量的精力來(lái)完成，而且還很容易出錯(cuò)。在這里"次要的功能"就是——記錄token的行列號(hào)，還有維護(hù)CodeFile::lines避免空行的出現(xiàn)！
?
盡管我已經(jīng)做過(guò)了那么多次詞法分析器，但是我仍然無(wú)法一氣呵成寫(xiě)對(duì)，仍然會(huì)出一些bug。面對(duì)編譯器這種純計(jì)算程序，debug的最好方法就是寫(xiě)單元測(cè)試。不過(guò)對(duì)于不熟悉單元測(cè)試的人來(lái)講可能很難一下子想到要做什么測(cè)試，在這里我可以把我給Tinymoe謝的一部分單元測(cè)試在這里貼一下。
?
第一個(gè)，當(dāng)然是傳說(shuō)中的"Hello, world!"測(cè)試了：
?
TEST_CASE和TEST_ASSERT（這里暫時(shí)沒(méi)有直接用到TEST_ASSERT）是我為了開(kāi)發(fā)Tinymoe隨手?jǐn)]的一個(gè)宏，可以在Tinymoe的代碼里看到。為了檢查我們有沒(méi)有粗心大意，我們有必要檢查詞法分析器的任何一個(gè)輸出的數(shù)據(jù)，譬如每一行有多少token，譬如每一個(gè)token的行號(hào)列好內(nèi)容和類型。我為了讓這些枯燥的測(cè)試用例容易看懂，在這個(gè)文件（
?
第二個(gè)測(cè)試用例針對(duì)的是整數(shù)和浮點(diǎn)的輸出和報(bào)錯(cuò)上，重點(diǎn)在于檢查每一個(gè)token的列號(hào)是不是正確的計(jì)算了出來(lái)：
?
第三個(gè)測(cè)試用例的重點(diǎn)主要是-符號(hào)和—注釋的分析：
?
第四個(gè)測(cè)試用例則是測(cè)試字符串的escaping和在面對(duì)換行的時(shí)候是否正確的處理（之前提到字符串不能換行，遇到一個(gè)突然的換行將會(huì)被看成缺少雙引號(hào)）：
?
鑒于詞法分析本來(lái)內(nèi)容也不多，所以這篇文章也不會(huì)太長(zhǎng)。相信有前途的程序員也會(huì)在這里得到一些編譯原理以外的知識(shí)。下一篇文章將會(huì)描述Tinymoe的函數(shù)頭的語(yǔ)法分析部分，將會(huì)描述一個(gè)編譯器的不帶歧義的語(yǔ)法分析是如何人肉出來(lái)的。敬請(qǐng)期待。