自我感覺良好系列代碼：
    GacUI

• 官網[http://www.gaclib.net/]
• 討論群[231200072]        
• 項目主頁[https://github.com/vczh-libraries/Release]

    編程相關討論1000人群：點擊進入 
    IDE實驗項目Release提供下載！
    Cppblog博客下載小程序：點擊進入

語法分析推薦書籍：
    我推薦的書：《Parsing Techniques》，還有它的第二版（part1.rar和part2.rar）

編譯原理系列文章：
    跟vczh看實例學編譯原理：系列文章（零），（一），（二）。*new*
    如何開發可配置語法分析器：系列文章（一），（二），（三），（三點五），（四），（五），（六），（七）。
    如何設計一門語言：系列文章（一），（二），（三），（四），（五），（六），（七），（八），（九），（十），（十一），（十二）。
    淺談面向對象語言的類型運算。
    如何手寫語法分析器。《構造正則表達式引擎》和《構造可配置詞法分析器》。
    使用高階函數開發語法分析器。

使用我寫的庫開發語法分析器系列文章：
    Vczh Library++語法分析器開發指南。
    Vczh Library++3.0 C++輕量級可配置語法分析器，系列文章（一），（二），（三），（四）。
    C++輕量級可配置語法分析器。

    開發自己的IDE——Vczh Library++的IDE工程開發歷程：一，二，三，四，五，六，七，八，九，十，十一，十二。

挖了坑卻沒空填上系列文章：
    手把手教你寫腳本引擎（一），（二），（三），（四），（五）。Demo （一）。
    C++實用技巧：（一），（二），（三），（四）。

作品及代碼下載：
    JIT腳本引擎：CMinus 0.1版開放下載 
    Vczh Library++ 2.0 GUI Framework 預覽版代碼以及示例程序
    Vczh Free Script 2.0 beta發布 

本來我都忘記了，結果有網友提醒我要寫，我就來寫一寫。 現在的年終總結已經沒什么內容了，主要是GacUI （www.gaclib.net）的開發實在太漫長。我現在在做拖控件程序GacStudio，希望在做完之后可以有Blend編輯WPF的效果，在xml里面寫data binding的時候不同的地方會有不同的intellisense。這當然是很難的，所以才想做。因此今年就把GacUI做到可以有Control Template、Item Template、Data Binding、XML Resource和加載，于是終于可以開始做GacStudio了。GacStudio整個會使用GacUI推薦的Data Binding來寫。這有三個好處：1、檢驗Data Binding是否設計的好順便抓bug；2、檢驗性能；3、證明GacUI是屌的，大家都可以用。 我還在github開了一個數據庫項目，在https://github.com/vczh/herodb，不過因為現在沒有臺式機，筆記本太爛裝不了Ubuntu的虛擬機，所以暫停開發，等到我設備到了我再繼續寫。這個東西寫完之后會合并進GacUI作為擴展的一部分，可以開很多腦洞，這個我就不講了。 我覺得2014年最偉大的成就就是，我終于搬去西雅圖了，啊哈哈哈哈。

RT

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

?

看了前面的三篇文章，大家應該基本對Tinymoe的代碼有一個初步的感覺了。在正確分析"print sum from 1 to 100"之前，我們首先得分析"phrase sum from (lower bound) to (upper bound)"這樣的聲明。Tinymoe的函數聲明又很多關于block和sentence的配置，不過這里并不打算將所有細節，我會將重點放在如何寫一個針對無歧義語法的遞歸下降語法分析器上。所以我們這里不會涉及sentence和block的什么category和cps的配置。

?

雖然"print sum from 1 to 100"無法用無歧義的語法分析的方法做出來，但是我們可以借用對"phrase sum from (lower bound) to (upper bound)"的語法分析的結果，動態構造能夠分析"print sum from 1 to 100"的語法分析器。這種說法看起來好像很高大上，但是其實并沒有什么特別難的技巧。關于"構造"的問題我將在下一篇文章《跟vczh看實例學編譯原理——三：Tinymoe與有歧義語法分析》詳細介紹。

?

在我之前的博客里我曾經寫過《如何手寫語法分析器》，這篇文章講了一些簡單的寫遞歸下降語法分析器的規則，盡管很多人來信說這篇文章幫他們解決了很多問題，但實際上細節還不夠豐富，用來對編程語言做語法分析的話，還是會覺得復雜性太高。這篇文章也同時作為《如何手寫語法分析器》的補充。好了，我們開始進入無歧義語法分析的主題吧。

?

我們需要的第一個函數是用來讀token并判斷其內容是不是我們希望看到的東西。這個函數比較特別，所以單獨拿出來講。在詞法分析里面我們已經把文件分行，每一行一個CodeToken的列表。但是由于一個函數聲明獨占一行，因此在這里我們只需要對每一行進行分析。我們判斷這一行是否以cps、category、symbol、type、phrase、sentence或block開頭，如果是那Tinymoe就認為這一定是一個聲明，否則就是普通的代碼。所以這里假設我們找到了一行代碼以上面的這些token作為開頭，于是我們就要進入語法分析的環節。作為整個分析器的基礎，我們需要一個ConsumeToken的函數：

?

?

作為一個純粹的C++11的項目，我們應該使用STL的迭代器。其實在寫語法分析器的時候，基于迭代器的代碼也比基于"token在數組里的下表"的代碼要簡單得多。這個函數所做的內容是這樣的，它查看it指向的那個token，如果token的類型跟tokenType描述的一樣，他就it++然后返回true；否則就是用content和ownerToken來產生一個錯誤信息加入errors列表里，然后返回false。當然，如果傳進去的參數it本身就等于end，那自然要產生一個錯誤。自然，函數體也十分簡單：

?

那對于標識符和數字怎么辦呢？明眼人肯定一眼就看出來，這是給檢查符號用的，譬如左括號、右括號、冒號和關鍵字等。在聲明里面我們是不需要太復雜的東西的，因此我們還需要兩外一個函數來輸入標識符。Tinymoe事實上有兩個針對標識符的語法分析函數，第一個是讀入標識符，第二個不僅要讀入標識符還要判斷是否到了行末否則報錯：

?

在這里我需要強調一個重點，在寫語法分析器的時候，函數的各式一定要整齊劃一。Tinymoe的語法分析函數有兩個格式，分別是針對parse一行的一個部分，和parse一個文件的一些行的。ParseToEnd和ParseToFarest就屬于parse一行的一個部分的函數。這種函數的格式如下：

1. 返回值一定是語法樹的一個節點。在這里我們以share_ptr<SymbolName>作為標識符的節點。一個標識符可以含有多個標識符token，譬如說the Chinese people、the real Tinymoe programmer什么的。因此我們可以簡單地推測SymbolName里面有一個vector<CodeToken>。這個定義可以在TinymoeLexicalAnalyzer.h的最后一部分找到。
2. 前兩個參數分別是iterator&和指向末尾的iterator。末尾通常指"從這里開始我們不希望這個parser函數來讀"，當然這通常就意味著行末。我們把"末尾"這個概念抽取出來，在某些情況下可以得到極大的好處。
3. 最后一個token一定是vector<CodeError>&，用來存放過程中遇到的錯誤。

?

除了函數格式以外，我們還需要所有的函數都遵循某些前置條件和后置條件。在語法分析里，如果你試圖分析一個結構但是不幸出現了錯誤，這個時候，你有可能可以返回一個語法樹的節點，你也有可能什么都返回不了。于是這里就有兩種情況：

1. 你可以返回，那就證明雖然輸入的代碼有錯誤，但是你成功的進行了錯誤恢復——實際上就是說，你覺得你自己可以猜測這份代碼的作者實際是要表達什么意思——于是你要移動第一個iterator，讓他指向你第一個還沒讀到的token，以便后續的語法分析過程繼續進行下去。
2. 你不能返回，那就證明你恢復不了，因此第一個iterator不能動。因為這個函數有可能只是為了測試一下當前的輸入是否滿足一個什么結構。既然他不是，而且你恢復不出來——也就是你猜測作者本來也不打算在這里寫某個結構——因此iterator不能動，表示你什么都沒有讀。

?

當你根據這樣的格式寫了很多語法分析函數之后，你會發現你可以很容易用簡單結構的語法分析函數，拼湊出一個復雜的語法分析函數。但是由于Tinymoe的聲明并沒有一個編程語言那么復雜，所以這種嵌套結構出現的次數并不多，于是我們這里先跳過關于嵌套的討論，等到后面具體分析"函數指針類型的參數"的時候自然會涉及到。

?

說了這么多，我覺得也應該上ParseToEnd和ParseToFarest的代碼了。首先是ParseToEnd：

?

我們很快就可以發現，其實語法分析器里面絕大多數篇幅的代碼都是關于錯誤處理的，真正處理正確代碼的部分其實很少。ParseToEnd做的事情不多，他就是從it開始一直讀到end的位置，把所有不是標識符的token都扔掉，然后把所有遇到的標識符token都連起來作為一個完整的標識符。也就是說，ParseToEnd遇到類似"the real 100 Tinymoe programmer"的時候，他會返回"the real Tinymoe programmer"，然后在"100"的地方報一個錯誤。

?

ParseToFarest的邏輯差不多：

?

只是當這個函數遇到"the real 100 Tinymoe programmer"的時候，會返回"the real"，然后把光標移動到"100"，但是沒有報錯。

?

看了這幾個基本的函數之后，我們可以進入正題了。做語法分析器，當然還是從文法開始。跟上一篇文章一樣，我們來嘗試直接構造一下文法。但是語法分析器跟詞法分析器的文法的區別是，詞法分析其的文法可以 "定義函數"和"調用函數"。

?

首先，我們來看symbol的文法：

SymbolName ::= <identifier> { <identifier> }

Symbol ::= "symbol" SymbolName

?

其次，就是type的聲明。type是多行的，不過我們這里只關心開頭的一樣：

Type ::= "type" SymbolName [ ":" SymbolName ]

?

在這里，中括號代表可有可無，大括號代表重復0次或以上。現在讓我們來看函數的聲明。函數的生命略為復雜：

?

Function ::= ("phrase" | "sentence" | "block") { SymbolName | "(" Argument ")" } [ ":" SymbolName ]

Argument ::= ["list" | "expression" | "argument" | "assignable"] SymbolName

Argument ::= SymbolName

Argument ::= Function

?

Declaration ::= Symbol | Type | Function

?

在這里我們看到Function遞歸了自己，這是因為函數的參數可以是另一個函數。為了讓這個參數調用起來更加漂亮一點，你可以把參數寫成函數的形式，譬如說：

pharse (the number) is odd : odd numbers

????return the number % 2 == 1

end

?

print all (phrase (the number) is wanted) in (numbers)

????repeat with the number in all numbers

????????if the number is wanted

????????????print the number

????????end

????end

end

?

print main

????print all odd numbers in array of (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

end

?

我們給"(the number) is odd"這個判斷一個數字是不是奇數的函數，起了一個別名叫"odd numbers"，這個別名不能被調用，但是他等價于一個只讀的變量保存著奇數函數的函數指針。于是我們就可以把它傳遞給"print all (…) in (…)"這個函數的第一個參數了。第一個參數聲明成函數，所以我們可以在print函數內直接調用這個參數指向的odd numbers函數。

?

事實上Tinymoe的SymbolName是可以包含關鍵字的，但是我為了不讓它寫的太長，于是我就簡單的寫成了上面的那條式子。那Argument是否可以包含關鍵字呢？答案當然是可以的，只是當它以list、expression、argument、assignable、phrase、sentence、block開始的時候，我們強行認為他有額外的意義。

?

現在一個Tinymoe的聲明的第一行都由Declaration來定義。當我們識別出一個正確的Declaration之后，我們就可以根據分析的結果來對后面的行進行分析。譬如說symbol后面沒有東西，于是就這么完了。type后面都是成員函數，所以我們一直找到"end"為止。函數的函數體就更復雜了，所以我們會直接跳到下一個看起來像Declaration的東西——也就是以symbol、type、phrase、sentence、block、cps、category開始的行。這些步驟都很簡單，所以問題的重點就是，如何根據Declaration的文法來處理輸入的字符串。

?

為了讓文法可以真正的運行，我們需要把它做成狀態機。根據之前的描述，這個狀態及仍然需要有"定義函數"和"執行函數"的能力。我們可以先假裝他們是正則表達式，然后把整個狀態機畫出來。這個時候，"函數"本身我們把它看成是一個跟標識符無關的輸入，然后就可以得到下面的狀態機：

?

?

這樣我們的狀態機就暫時完成了。但是現在還不能直接把它轉換成代碼，因為當我們遇到一個輸入，而我們可以選擇調用函數，而且可以用的函數還不止一個的時候，那應該怎么辦呢？答案就是要檢查我們的文法是不是有歧義。

?

文法的歧義是一個很有意思的問題。在我們真的實踐一個編譯器的時候，我們會遇到三種歧義：

1. 文法本身就是有歧義的，譬如說C++著名的A* B;的問題。當A是一個變量的時候，這是一個乘法表達式。當A是一個類型的時候，這是一個變量聲明語句。如果我們在語法分析的時候不知道A到底指向的是什么東西，那我們根本無從得知這一句話到底要取什么意思，于是要么返回錯誤，要么兩個結果一起返回。這就是問法本身固有的歧義。
2. 文法本身沒有歧義，但是在分析的過程中卻無法在走每一步的時候都能夠算出唯一的"下一個狀態"。譬如說C#著名的A<B>C;問題。當A是一個變量的時候，這個語句是不成立的，因為C#的一個語句的根節點不能是一個操作符（這里是">"）。當A是一個類型的時候，這是一個變量聲明語句。從結果來看，這并沒有歧義，但是當我們讀完A<B>的時候仍然不知道這個語句的結構到底是取哪一種。實際上B作為類型參數，他也可以有B<C>這樣的結構，因此這個B可以是任意長的。也就是說我們只有在">"結束之后再多讀幾個字符才能得到正確的判斷。譬如說C是"(1)"，那我們知道A應該是一個模板函數。如果C是一個名字，A多半應該是一個類型。因此我們在做語法分析的時候，只能兩種情況一起考慮，并行處理。最后如果哪一個情況分析不下去了，就簡單的扔掉，剩下的就是我們所需要的。
3. 文法本身沒有歧義，而且分析的過程中只要你每一步都往后多看最多N個token，酒可以算出唯一的"下一個狀態"到底是什么。這個想必大家都很熟悉，因為這個N就是LookAhead。所謂的LL(1)、SLR(1)、LR(1)、LALR(1)什么的，這個1其實就是N=1的情況。N當然不一定是1，他也可以是一個很大的數字，譬如說8。一個文法的LookAhead是多少，這是文法本身固有的屬性。一個LR(2)的狀態機你非要在語法分析的時候只LookAhead一個token，那也會遇到第二種歧義的情況。如果C語言沒有typedef的話，那他就是一個帶有LookAhead的沒有歧義的語言了。

?

看一眼我們剛才寫出來的文法，明顯就是LookAhead=0的情況，而且連左遞歸都沒有，寫起來肯定很容易。那接下來我們要做的就是給"函數"算first set。一個函數的first set，顧名思義就是，他的第一個token都可以是什么。SymbolName、Symbol、Type、Function都不用看了，因為他們的文法第一個輸入都是token，那就是他們的first set。最后就剩下Argument。Argument的第一個token除了list、expression、argument和assignable以外，還有Function。因此Argument的first set就是這些token加上Function的first set。如果文法有左遞歸的話，也可以用類似的方法做，只要我們在函數A->B->C->…->A的時候，知道A正在計算于是返回空集就可以了。當然，只有左遞歸才會遇到這種情況。

?

然后我們檢查一下每一個狀態，可以發現，任何一個狀態出去的所有邊，他接受的token或者函數的first set都是沒有交集的。譬如Argument的0狀態，第一條邊接受的token、第二條邊接受的SymbolName的first set，和第三條邊接受的Function的first set，是沒有交集的，所以我們就可以斷定，這個文法一定沒有歧義。按照上次狀態機到代碼的寫法，我們可以機械的寫出代碼了。寫代碼的時候，我們把每一個文法的函數，都寫成一個C++的函數。每到一個狀態的時候，我們看一下當前的token是什么，然后再決定走哪條邊。如果選中的邊是token邊，那我們就跳過一個token。如果選中的邊是函數邊，那我們不跳過token，轉而調用那個函數，讓函數自己去跳token。《如何手寫語法分析器》用的也是一樣的方法，如果對這個過程不清楚的，可以再看一遍這個文章。

?

于是我們到了定義語法樹的時候了。幸運的是，我們可以直接從文法上看到語法樹的形狀，然后稍微做一點微調就可以了。我們把每一個函數都看成一個類，然后使用下面的規則：

1. 對于A、A B、A B C等的情況，我們轉換成class里面有若干個成員變量。
2. 對于A | B的情況，我們把它做成繼承，A的語法樹和B的語法樹繼承自一個基類，然后這個基類的指針就放在class里面做成員變量。
3. 對于{ A }，或者A { A }的情況，那個成員變量就是一個vector。
4. 對于[ A ]的情況，我們就當A看，區別只是，這個成員變量可以填nullptr。

?

對于每一個函數，要不要用shared_ptr來裝則見仁見智。于是我們可以直接通過上面的文法得到我們所需要的語法樹：

?

首先是SymbolName：

?

其次是Symbol：

?

然后是Type：

?

接下來是Argument：

?

最后是Function：

?

大家可以看到，在Argument那里，同時出去的三條邊就組成了三個子類，都繼承自FunctionFragment。圖中紅色的部分就是Tinymoe源代碼里在上述的文法里出現的那部分。至于為什么還有多出來的部分，其實是因為這里的文法是為了敘述方便簡化過的。至于Tinymoe關于函數聲明的所有語法可以分別看下面的四個github的wiki page：

https://github.com/vczh/tinymoe/wiki/Phrases,-Sentences-and-Blocks

https://github.com/vczh/tinymoe/wiki/Manipulating-Functions

https://github.com/vczh/tinymoe/wiki/Category

https://github.com/vczh/tinymoe/wiki/State-and-Continuation

?

在本章的末尾，我將向大家展示Tinymoe關于函數聲明的那一個Parse函數。文章已經把所有關鍵的知識點都講了，具體怎么做大家可以上https://github.com/vczh/tinymoe 閱讀源代碼來學習。

?

首先是我們的函數頭：

?

回想一下我們之前講到的關于語法分析函數的格式：

1. 返回值一定是語法樹的一個節點。在這里我們以share_ptr<SymbolName>作為標識符的節點。一個標識符可以含有多個標識符token，譬如說the Chinese people、the real Tinymoe programmer什么的。因此我們可以簡單地推測SymbolName里面有一個vector<CodeToken>。這個定義可以在TinymoeLexicalAnalyzer.h的最后一部分找到。
2. 前兩個參數分別是iterator&和指向末尾的iterator。末尾通常指"從這里開始我們不希望這個parser函數來讀"，當然這通常就意味著行末。我們把"末尾"這個概念抽取出來，在某些情況下可以得到極大的好處。
3. 最后一個token一定是vector<CodeError>&，用來存放過程中遇到的錯誤。

?

我們可以清楚地看到這個函數滿足上文提出來的三個要求。剩下來的參數有兩個，第一個是decl，如果不為空那代表調用函數的人已經幫你吧語法樹給new出來了，你應該直接使用它。領一個參數ownerToken則是為了產生語法錯誤使用的。然后我們看代碼：

?

第一步，我們判斷輸入是否為空，然后根據需要報錯：

?

第二步，根據第一個token來確定函數的形式是phrase、sentence還是block，并記錄在成員變量type里：

?

第三步是一個循環，我們根據當前的token（還記不記得之前說過，要先看一下token是什么，然后再決定走哪條邊？）來決定我們接下來要分析的，是ArgumentFragment的兩個子類（分別是VariableArgumentFragment和FunctionArgumentFragment），還是普通的函數名的一部分，還是說函數已經結束了，遇到了一個冒號，因此開始分析別名：

?

最后就不貼了，是檢查格式是否滿足語義的一些代碼，譬如說block的函數名必須由參數開始啦，或者phrase的參數不能是argument和assignable等。

?

這篇文章就到此結束了，希望大家在看了這片文章之后，配合wiki關于語法的全面描述，已經知道如何對Tinymoe的聲明部分進行語法分析。緊接著就是下一篇文章——Tinymoe與帶歧義語法分析了，會讓大家明白，想對諸如"print sum from 1 to 100"這樣的代碼做語法分析，也不需要多復雜的手段就可以做出來。

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

?

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

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

?

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

?

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

?

首先是token：

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

?

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

?

Tinymoe的詞法分析器除了token的類型以外，肯定還需要定義整個文件結構在詞法分析后的結果：

這個數據結構體現了"Tinymoe的token列表是二維的"的這個觀點。一個文件會被詞法分析器處理成一個shared_ptr<CodeFIle>對象，CodeFile::lines記錄了所有非空的行，CodeLine::tokens記錄了該行的所有token。

?

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

?

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

?

首先我們添加整數和標識符進去：

?

其次是加減和浮點：

?

最后把字符串和注釋補全：

?

這樣狀態機就已經完成了。讀過編譯原理的可能會問，為什么終結狀態都是由虛線而不是帶有輸入的實現指向的？因為虛線在這里有特殊的意義，也就是說它不能移動輸入的字符串的指針，而且他還要負責添加一個token。當狀態跳到End之后，那他就會變成Start，所以實際上Start和End是同一個狀態。這個狀態機也不是輸入什么字符都能跳轉到下一個狀態的。所以當你發現輸入的字符讓你無路可走的時候，你就是遇到了一個詞法錯誤。

?

這樣我們的設計就算完成了，接下來就是如何用C++來實現它了。為了讓代碼更容易閱讀，我們應該給Start和1-9這么多狀態起名字，做法如下：

在這里類似狀態3這樣的狀態被我省略掉了，因為這個狀態唯一的出路就是虛線，所以跳到這個狀態意味著你要立刻執行虛線，也就是說你不需要做"跳到這個狀態"這個動作。因此它不需要有一個名字。

?

然后你只要按照下面的做法翻譯這個狀態機就可以了：

?

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

?

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

?

第一個，當然是傳說中的"Hello, world!"測試了：

?

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

?

第二個測試用例針對的是整數和浮點的輸出和報錯上，重點在于檢查每一個token的列號是不是正確的計算了出來：

?

第三個測試用例的重點主要是-符號和—注釋的分析：

?

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

?

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

最近學習C++11的variadic template argument，終于可以擺脫用fpmacro模板來復制一大堆代碼的做法了，好開心。這個例子的main函數用lambda寫了一個斐波那契數列的遞歸計算函數。跟以往不同的是，在Y函數的幫助下，這個lambda表達是可以成功看到自己，然后遞歸調用。當然這仍然需要用普通的C++遞歸來實現，并不是λ-calculus那個高大上的Y Combinator。

?

#include <functional>

#include <memory>

#include <iostream>

#include <string>

?

using namespace std;

?

template<typename TResult, typename ...TArgs>

class YBuilder

{

private:

????function<TResult(function<TResult(TArgs...)>, TArgs...)> partialLambda;

?

public:

????YBuilder(function<TResult(function<TResult(TArgs...)>, TArgs...)> _partialLambda)

????????:partialLambda(_partialLambda)

????{

????}

?

????TResult operator()(TArgs ...args)const

????{

????????return partialLambda(

????????????[this](TArgs ...args)

????????????{

????????????????return this->operator()(args...);

????????????}, args...);

????}

};

?

template<typename TMethod>

struct PartialLambdaTypeRetriver

{

????typedef void FunctionType;

????typedef void LambdaType;

????typedef void YBuilderType;

};

?

template<typename TClass, typename TResult, typename ...TArgs>

struct PartialLambdaTypeRetriver<TResult(__thiscall TClass::*)(function<TResult(TArgs...)>, TArgs...)>

{

????typedef TResult FunctionType(TArgs...);

????typedef TResult LambdaType(function<TResult(TArgs...)>, TArgs...);

????typedef YBuilder<TResult, TArgs...> YBuilderType;

};

?

template<typename TClass, typename TResult, typename ...TArgs>

struct PartialLambdaTypeRetriver<TResult(__thiscall TClass::*)(function<TResult(TArgs...)>, TArgs...)const>

{

????typedef TResult FunctionType(TArgs...);

????typedef TResult LambdaType(function<TResult(TArgs...)>, TArgs...);

????typedef YBuilder<TResult, TArgs...> YBuilderType;

};

?

template<typename TLambda>

function<typename PartialLambdaTypeRetriver<decltype(&TLambda::operator())>::FunctionType> Y(TLambda partialLambda)

{

????return typename PartialLambdaTypeRetriver<decltype(&TLambda::operator())>::YBuilderType(partialLambda);

}

?

int _tmain(int argc, _TCHAR* argv[])

{

????auto fib = Y([](function<int(int)> self, int index)

????{

????????return index<2

?????????????1

????????????:self(index-1)+self(index-2);

????});

?

????for (int i = 0; i < 10; i++)

????{

????????cout << fib(i) << " ";

????}

????cout << endl;

}

自從《序》胡扯了快一個月之后，終于迎來了正片。之所以系列文章叫《看實例學編譯原理》，是因為整個系列會通過帶大家一步一步實現Tinymoe的過程，來介紹編譯原理的一些知識點。

 

但是第一個系列還沒到開始處理Tinymoe源代碼的時候，首先的跟大家講一講我設計Tinymoe的故事。為什么這種東西要等到現在才講呢，因為之前沒有文檔，將了也是白講啊。Tinymoe在github的wiki分為兩部分，一部分是介紹語法的，另一部分是介紹一個最小的標準庫是如何實現出來的，地址在 https://github.com/vczh/tinymoe/wiki 不帶問號的那些都是寫完了的。

系列文章的目標

在介紹Tinymoe之前，先說一下這個系列文章的目標。Ideally，只要一個人看完了這個系列，他就可以在下面這些地方得到入門：

• 詞法分析
• 歧義與不歧義的語法分析
• 語義分析
• 符號表
• 全文CPS變換
• 編譯生成高效的其他語言的代碼
• 編譯生成自己的指令集
• 帶GC的虛擬機
• 類型推導（intersection type，union type，concept mapping）
• 跨過程分析（inter-procedural analyzing）

 

當然，這并不能讓你成為一個大牛，但是至少自己做做實驗，搞一點高大上的東西騙師妹們是沒有問題了。

Tinymoe設計的目標

雖然想法很多年前就已經有了，但是這次我想把它實現出來，是為了完成《如何設計一門語言》的后續。光講大道理是沒有意義的，至少得有一個例子，讓大家知道這些事情到底是什么樣子的。因此Tinymoe有一點教學的意義，不管是使用它還是實現它。

 

首先，處理Tinymoe需要的知識點多，用于編譯原理教學。既然是為了展示編譯原理的基礎知識，因此語言本身不可能是那種爛大街的C系列的東西。當然除了知識點以外，還會讓大家深刻的理解到，難實現和難用，是完全沒有關系的！Tinymoe用起來可爽了，啊哈哈哈哈哈。

 

其次，Tinymoe容易嵌入其他語言的程序，作為DSL使用，可以調用宿主程序提供的功能。這嚴格的來講不算語言本身的功能，而是實現本身的功能。就算是C++也可以設計為嵌入式，lua也可以被設計為編譯成exe的。一個語言本身的設計并不會對如何使用它有多大的限制。為了讓大家看了這個系列之后，可以寫出至少可用的東西，而不僅僅是寫玩具，因此這也是設計的目標之一。

 

第三，Tinymoe語法優化于描述復雜的邏輯，而不是優化與復雜的數據結構和算法（雖然也可以）。Tinymoe本身是不存在任何細粒度控制內存的能力的，而且雖然可以實現復雜的數據結構和算法，但是本身描述這些東西最多也就跟JavaScript一樣容易——其實就是不容易。但是Tinymoe設計的時候，是為了讓大家把Tinymoe當成是一門可以設計DSL的語言，因此對復雜邏輯的描述能力特別強。唯一的前提就是，你懂得如何給Tinymoe寫庫。很好的使用和很好地實現一個東西是相輔相成的。我在設計Tinymoe之初，很多pattern我也不知道，只是因為設計Tinymoe遵循了科學的方法，因此最后我發現Tinymoe竟然具有如此強大的描述能力。當然對于讀者們本身，也會在閱讀系列文章的有類似的感覺。

 

最后，Tinymoe是一個動態類型語言。這純粹是我的個人愛好了。對一門動態類型語言做靜態分析那該多有趣啊，啊哈哈哈哈哈哈。

Tinymoe的設計哲學

當然我并不會為了寫文章就無線提高Tinymoe的實現難度的。為了把他控制在一個正常水平，因此設計Tinymoe的第一條就是：

 

一、小規模的語言核心+大規模的標準庫

 

其實這跟C++差不多。但是C++由于想做的事情實在是太多了，譬如說視圖包涵所有范式等等，因此就算這么做，仍然讓C++本身包含的東西過于巨大（其實我還是覺得C++不難怎么辦）。

 

語言核心小，實現起來當然容易。但是你并不能為了讓語言核心小就犧牲什么功能。因此精心設計一個核心是必須的，因為所有你想要但是不想加入語言的功能，從此就可以用庫來實現了。

 

譬如說，Tinymoe通過有條件地暴露continuation，要求編譯器在編譯Tinymoe的時候做一次全文CPS變換。這個東西說容易也不是那么容易，但是至少比你做分支循環異常處理什么的全部加起來要簡單多了吧。所以我只提供continuation，剩下的控制流全部用庫來做。這樣有三個好處：

1. 語言簡單，實現難度降低。
2. 為了讓庫可以發揮應有的作用，語言的功能的選擇十分的正交化。不過這仍然在一定的程度上提高了學習的難度。但是并不是所有人都需要寫庫對吧，很多人只需要會用庫就夠了。通過一點點的犧牲，正交化可以充分發揮程序員的想象能力。這對于以DSL為目的的語言來說是不可或缺的。
3. 標準庫本身可以作為編譯器的測試用例。你只需要準備足夠多的測試用例來運行標準庫，那么你只要用C++（假設你用C++來實現Tinymoe）來跑他們，那所有的標準庫都會得到運行。運行結果如果對，那你對編譯器的實現也就有信心了。為什么呢，因為標準庫大量的使用了語言的各種功能，而且是無節操的使用。如果這樣都能過，那普通的程序就更能過了。

 

說了這么多，那到底什么是小規模的語言核心呢？這在Tinymoe上有兩點體現。

 

第一點，就是Tinymoe的語法元素少。一個Tinymoe表達式無非就只有三類：函數調用、字面量和變量、操作符。字面量就是那些數字字符串什么的。當Tinymoe的函數的某一個參數指定為不定個數的時候你還得提供一個tuple。委托（在這里是函數指針和閉包的統稱）和數組雖然也是Tinymoe的原生功能之一，但是對他們的操作都是通過函數調用來實現的，沒有特殊的語法。

 

簡單地講，就是除了下面這些東西以外你不會見到別的種類的表達式了：

1

"text"

sum from 1 to 100

sum of (1, 2, 3, 4, 5)

(1+2)*(3+4)

true

 

一個Tinymoe語句的種類就更少了，要么是一個函數調用，要么是block，要么是連在一起的幾個block：

do something bad

 

repeat with x from 1 to 100

    do something bad with x

end

 

try

    do something bad

catch exception

    do something worse

end

 

有人可能會說，那repeat和try-catch就不是語法元素嗎？這個真不是，他們是標準庫定義好的函數，跟你自己聲明的函數沒有任何特殊的地方。

 

這里其實還有一個有意思的地方："repeat with x from 1 to 100"的x其實是循環體的參數。Tinymoe是如何給你自定義的block開洞的呢？不僅如此，Tinymoe的函數還可以聲明"引用參數"，也就是說調用這個函數的時候你只能把一個變量放進去，函數里面可以讀寫這個變量。這些都是怎么實現的呢？學下去就知道了，啊哈哈哈哈。

 

Tinymoe的聲明也只有兩種，第一種是函數，第二種是符號。函數的聲明可能會略微復雜一點，不過除了函數頭以外，其他的都是類似配置一樣的東西，幾乎都是用來定義"catch函數在使用的時候必須是連在try函數后面"啊，"break只能在repeat里面用"啊，諸如此類的信息。

 

Tinymoe的符號十分簡單，譬如說你要定義一年四季的符號，只需要這么寫：

symbol spring

symbol summer

symbol autumn

symbol winter

 

symbol是一個"與眾不同的值"，也就是說你在兩個module下面定義同名的symbol他們也是不一樣的。所有symbol之間都是不一樣的，可以用=和<>來判斷。symbol就是靠"不一樣"來定義其自身的。

 

至于說，那為什么不用enum呢？因為Tinymoe是動態類型語言，enum的類型本身是根本沒有用武之地的，所以干脆就設計成了symbol。

 

第二點，Tinymoe除了continuation和select-case以外，沒有其他原生的控制流支持。

 

這基本上歸功于先輩發明continuation passing style transformation的功勞，細節在以后的系列里面會講。心急的人可以先看 https://github.com/vczh/tinymoe/blob/master/Development/Library/StandardLibrary.txt 。這個文件暫時包含了Tinymoe的整個標準庫，里面定義了很多if-else/repeat/try-catch-finally等控制流，甚至連coroutine都可以用continuation、select-case和遞歸來做。

 

這也是小規模的語言核心+大規模的標準庫所要表達的意思。如果可以提供一個feature A，通過他來完成其他必要的feature B0, B1, B2…的同時，將來說不定還有人可以出于自己的需求，開發DSL的時候定義feature C，那么只有A需要保留下來，所有的B和C都將使用庫的方法來實現。

 

這么做并不是完全有益無害的，只是壞處很小，在"Tinymoe的實現難點"里面會詳細說明。

 

二、擴展后的東西跟原生的東西外觀一致

 

這是很重要的。如果擴展出來的東西跟原生的東西長得不一樣，用起來就覺得很傻逼。Java的string不能用==來判斷內容就是這樣的一個例子。雖然他們有的是理由證明==的反直覺設計是對的——但是反直覺就是反直覺，就是一個大坑。

 

這種例子還有很多，譬如說go的數組和表的類型啦，go本身如果不要數組和表的話，是寫不出長得跟原生數組和表一樣的數組和表的。其實這也不是一個大問題，問題是go給數組和表的樣子搞特殊化，還有那個反直覺的slice的賦值問題（會合法溢出?。?，類似的東西實在是太多了。一個東西特例太多，坑就無法避免。所以其實在我看來，go還不如給C語言加上erlang的actor功能了事。

 

反而C++在這件事情上就做得很好。如果你對C++不熟悉的話，有時候根本分不清什么是編譯器干的，什么是標準庫干的。譬如說static_cast和dynamic_cast長得像一個模板函數，因此boost就可以用類似的手法加入lexical_cast和針對shared_ptr的static_pointer_cast和dynamic_pointer_cast，整個標準庫和語言本身渾然一體。這樣子做的好處是，當你在培養對語言本身的直覺的時候，你也在培養對標準庫的直覺，培養直覺這件事情你不用做兩次。你對一個東西的直覺越準，學習新東西的速度就越快。所以C++的設計剛好可以讓你在熬過第一個階段的學習之后，后面都覺得無比的輕松。

 

不過具體到Tinymoe，因為Tinymoe本身的語法元素太少了，所以這個做法在Tinymoe身上體現得不明顯。

Tinymoe的實現難點

首先，語法分析需要對Tinymoe程序處理三遍。Tinymoe對于語句設計使得對一個Tinymoe程序做語法分析不是那么直接（雖然比C++什么的還是容易多了）。舉個例子：

module hello world

 

phrase sum from (lower bound) to (upper bound)

…

end

 

sentence print (message)

…

end

 

phrase main

    print sum from 1 to 100

end

 

第一遍分析是詞法分析，這個時候得把每一個token的行號記住。第二遍分析是不帶歧義的語法分析，目標是把所有的函數頭抽取出來，然后組成一個全局符號表。第三遍分析就是對函數體里面的語句做帶歧義的語法分析了。因為Tinymoe允許你定義變量，所以符號表肯定是一邊分析一邊修改的。于是對于"print sum from 1 to 100"這一句，如果你沒有發現"phrase sum from (lower bound) to (upper bound)"和"sentence print (message)"，那根本無從下手。

 

還有另一個例子：

module exception handling

 

…

 

phrase main

    try

        do something bad

    catch

        print "bad thing happened"

    end

end

 

當語法分析做到"try"的時候，因為發現存在try函數的定義，所以Tinymoe知道接下來的"do something bad"屬于調用try這個塊函數所需提供的代碼塊里面的代碼。接下來是"catch"，Tinymoe怎么知道catch是接在try后面，而不是放在try里面的呢？這仍然是由于catch函數的定義告訴我們的。關于這方面的語法知識可以點擊這里查看。

 

正因為如此，我們需要首先知道函數的定義，然后才能分析函數體里面的代碼。雖然這在一定程度上造成了Tinymoe的語法分析復雜度的提升，但是其復雜度本身并不高。比C++簡單就不說了，就算是C、C#和Java，由于其語法元素太多，導致不需要多次分析所降低的復雜度被完全的抵消，結果跟實現Tinymoe的語法分析器的難度不相上下。

 

其次，CPS變換后的代碼需要特殊處理，否則直接執行容易導致call stack積累的沒用的東西過多。因為Tinymoe可以自定義操作符，所以操作符跟C++一樣在編譯的時候被轉換成了函數調用。每一個函數調用都是會被CPS變換的。盡管每一行的函數調用次數不多，但是如果你的程序油循環，循環是通過遞歸來描述（而不是實現，由于CPS變換后Tinymoe做了優化，所以不存在實際上的遞歸）的，如果直接執行CPS變換后的代碼，算一個1加到1000都會導致stack overflow。可見其call stack里面堆積的closure數量之巨大。

 

我在做Tinymoe代碼生成的實驗的時候，為了簡單我在單元測試里面直接產生了對應的C#代碼。一開始沒有處理CPS而直接調用，程序不僅慢，而且容易stack overflow。但是我們知道（其實你們以后才會知道），CPS變換后的代碼里面幾乎所有的call stack項都是浪費的，因此我把整個在生成C#代碼的時候修改成，如果需要調用continuation，就返回調用continuation的語句組成的lambda表達式，在最外層用一個循環去驅動他直到返回null為止。這樣做了之后，就算Tinymoe的代碼有遞歸，call stack里面也不會因為遞歸而積累call stack item了。于是生成的C#代碼執行飛快，而且無論你怎么遞歸也永遠不會造成stack overflow了。這個美妙的特性幾乎所有語言都做不到，啊哈哈哈哈哈。

 

當然這也是有代價的，因為本質上我只是把保存在stack上的context轉移到heap上。不過多虧了.net 4.0的強大的background GC，這樣做絲毫沒有多余的性能上的損耗。當然這也意味著，一個高性能的Tinymoe虛擬機，需要一個牛逼的垃圾收集器作為靠山。context產生的closure在函數體真的被執行完之后就會被很快地收集，所以CPS加上這種做法并不會對GC產生額外的壓力，所有的壓力仍然來源于你自己所創建的數據結構。

 

第三，Tinymoe需要動態類型語言的類型推導。當然你不這么做而把Tinymoe的程序當JavaScript那樣的程序處理也沒有問題。但是我們知道，正是因為V8對JavaScript的代碼進行了類型推導，才產生了那么優異的性能。因此這算是一個優化上的措施。

 

最后，Tinymoe還需要跨過程分析和對程序的控制流的化簡（譬如continuation轉狀態機等）。目前具體怎么做我還在學習當中。不過我們想，既然repeat函數是通過遞歸來描述的，那我們能不能通過對所有代碼進行inter-procedural analyzing，從而發現諸如

repeat 3 times

    do something good

end

就是一個循環，從而生成用真正的循環指令（譬如說goto）呢？這個問題是個很有意思的問題，我覺得我如果可以通過學習靜態分析從而解決它，不進我的能力會得到提升，我對你們的科普也會做得更好。

后記

雖然還不到五千字，但是總覺得寫了好多的樣子?？傊蚁Ｍx者在看完《零》和《一》之后，對接下來需要學習的東西有一個較為清晰的認識。

在《如何設計一門語言》里面，我講了一些語言方面的東西，還有痛快的噴了一些XX粉什么的。不過單純講這個也是很無聊的，所以我開了這個《跟vczh看實例學編譯原理》系列，意在科普一些編譯原理的知識，盡量讓大家可以在創造語言之后，自己寫一個原型。在這里我拿我創造的一門很有趣的語言 https://github.com/vczh/tinymoe/ 作為實例。

 

商業編譯器對功能和質量的要求都是很高的，里面大量的東西其實都跟編譯原理沒關系。一個典型的編譯原理的原型有什么特征呢？

1. 性能低
2. 錯誤信息難看
3. 沒有檢查所有情況就生成代碼
4. 優化做得爛
5. 幾乎沒有編譯選項

 

等等。Tinymoe就滿足了上面的5種情況，因為我的目標也只是想做一個原型，向大家介紹編譯原理的基礎知識。當然，我對語法的設計還是盡量靠近工業質量的，只是實現沒有花太多心思。

 

為什么我要用Tinymoe來作為實例呢？因為Tinymoe是少有的一種用起來簡單，而且庫可以有多復雜寫多復雜的語言，就跟C++一樣。C++11額標準庫在一起用簡直是愉快啊，Tinymoe的代碼也是這么寫的。但是這并不妨礙你可以在寫C++庫的時候發揮你的想象力。Tinymoe也是一樣的。為什么呢，我來舉個例子。

 

Hello, world!

Tinymoe的hello world程序是很簡單的：

 

module hello world

using standard library

 

sentence print (message)

    redirect to "printf"

end

 

phrase main

    print "Hello, world!"

end

 

module指的是模塊的名字，普通的程序也是一個模塊。using指的是你要引用的模塊——standard library就是Tinymoe的STL了——當然這個程序并沒有用到任何standard library的東西。說到這里大家可能意識到了，Tinymoe的名字可以是不定長的token組成的！沒錯，后面大家會慢慢意識到這種做法有多么的強大。

 

后面是print函數和main函數。Tinymoe是嚴格區分語句和表達式的，只有sentence和block開頭的函數才能作為語句，而且同時只有phrase開頭的函數才能作為表達式。所以下面的程序是不合法的：

 

phrase main

    (print "Hello, world!") + 1

end

 

原因就是，print是sentence，不能作為表達式使用，因此他不能被+1。

 

Tinymoe的函數參數都被寫在括號里面，一個參數需要一個括號。到了這里大家可能會覺得很奇怪，不過很快就會有解答了。為什么要這么做，下一個例子就會告訴我們。

 

print函數用的redirect to是Tinymoe聲明FFI（Foreign Function Interface）的方法，也就是說，當你運行了print，他就會去host里面找一個叫做printf的函數來運行。不過大家不要誤會，Tinymoe并沒有被設計成可以直接調用C函數，所以這個名字其實是隨便寫的，只要host提供了一個叫做printf的函數完成printf該做的事情就行了。main函數就不用解釋了，很直白。

1加到100等于5050

這個例子可以在Tinymoe的主頁（https://github.com/vczh/tinymoe/）上面看到：

 

module hello world

using standard library

 

sentence print (message)

redirect to "printf"

end

 

phrase sum from (start) to (end)

set the result to 0

repeat with the current number from start to end

add the current number to the result

end

end

 

phrase main

print "1+ ... +100 = " & sum from 1 to 100

end

 

為什么名字可以是多個token？為什么每一個參數都要一個括號？看加粗的部分就知道了！正是因為Tinymoe想讓每一行代碼都可以被念出來，所以才這么設計的。當然，大家肯定都知道怎么算start + (start+1) + … + (end-1) + end了，所以應該很容易就可以看懂這個函數里面的代碼具體是什么意思。

 

在這里可以稍微多做一下解釋。the result是一個預定義的變量，代表函數的返回值。只要你往the result里面寫東西，只要函數一結束，他就變成函數的返回值了。Tinymoe的括號沒有什么特殊意思，就是改變優先級，所以那一句循環則可以通過添加括號的方法寫成這樣：

 

repeat with (the current number) from (start) to (end)

 

大家可能會想，repeat with是不是關鍵字？當然不是！repeat with是standard library里面定義的一個block函數。大家知道block函數的意思了吧，就是這個函數可以帶一個block。block有一些特性可以讓你寫出類似try-catch那樣的幾個block連在一起的大block，特別適合寫庫。

 

到了這里大家心中可能會有疑問，循環為什么可以做成庫呢？還有更加令人震驚的是，break和continue也不是關鍵字，是sentence！因為repeat with是有代碼的：

 

category

    start REPEAT

    closable

block (sentence deal with (item)) repeat with (argument item) from (lower bound) to (upper bound)

    set the current number to lower bound

    repeat while the current number <= upper bound

        deal with the current number

        add 1 to the current number

    end

end

 

前面的category是用來定義一些block的順序和包圍結構什么的。repeat with是屬于REPEAT的，而break和continue聲明了自己只能直接或者間接方在REPEAT里面，因此如果你在一個沒有循環的地方調用break或者continue，編譯器就會報錯了。這是一個花邊功能，用來防止手誤的。

 

大家可能會注意到一個新東西：(argument item)。argument的意思指的是，后面的item是block里面的代碼的一個參數，對于repeat with函數本身他不是一個參數。這就通過一個很自然的方法給block添加參數了。如果你用ruby的話就得寫成這個悲催的樣子：

 

repeat_with(1, 10) do |item|

    xxxx

end

 

而用C++寫起來就更悲催了：

 

repeat_with(1, 10, [](int item)

{

    xxxx

});

 

block的第一個參數sentence deal with (item)就是一個引用了block中間的代碼的委托。所以你會看到代碼里面會調用它。

 

好了，那repeat while總是關鍵字了吧——不是！后面大家還會知道，就連

 

if xxx

    yyy

else if zzz

    www

else if aaa

    bbb

else

    ccc

end

 

也只是你調用了if、else if和else的一系列函數然后讓他們串起來而已。

 

那Tinymoe到底提供了什么基礎設施呢？其實只有select-case和遞歸。用這兩個東西，加上內置的數組，就圖靈完備了。圖靈完備就是這么容易啊。

 

多重分派（Multiple Dispatch）

講到這里，我不得不說，Tinymoe也可以寫類，也可以繼承，不過他跟傳統的語言不一樣的，類是沒有構造函數、析構函數和其他成員函數的。Tinymoe所有的函數都是全局函數，但是你可以使用多重分派來"挑選"類型。這就需要第三個例子了（也可以在主頁上找到）：

 

module geometry

using standard library

 

phrase square root of (number)

    redirect to "Sqrt"

end

 

sentence print (message)

    redirect to "Print"

end

 

type rectangle

    width

    height

end

 

type triangle

    a

    b

    c

end

 

type circle

    radius

end

 

phrase area of (shape)

    raise "This is not a shape."

end

 

phrase area of (shape : rectangle)

    set the result to field width of shape * field height of shape

end

 

phrase area of (shape : triangle)

    set a to field a of shape

    set b to field b of shape

    set c to field c of shape

    set p to (a + b + c) / 2

    set the result to square root of (p * (p - a) * (p - b) * (p - c))

end

 

phrase area of (shape : circle)

    set r to field radius of shape

    set the result to r * r * 3.14

end

 

phrase (a) and (b) are the same shape

    set the result to false

end

 

phrase (a : rectangle) and (b : rectangle) are the same shape

    set the result to true

end

 

phrase (a : triangle) and (b : triangle) are the same shape

    set the result to true

end

 

phrase (a : circle) and (b : circle) are the same shape

    set the result to true

end

 

phrase main

    set shape one to new triangle of (2, 3, 4)

    set shape two to new rectangle of (1, 2)

    if shape one and shape two are the same shape

        print "This world is mad!"

    else

        print "Triangle and rectangle are not the same shape!"

    end

end

 

這個例子稍微長了一點點，不過大家可以很清楚的看到我是如何定義一個類型、創建他們和訪問成員變量的。area of函數可以計算一個平面幾何圖形的面積，而且會根據你傳給他的不同的幾何圖形而使用不同的公式。當所有的類型判斷都失敗的時候，就會掉進那個沒有任何類型聲明的函數，從而引發一場。嗯，其實try/catch/finally/raise都是函數來的——Tinymoe對控制流的控制就是如此強大，啊哈哈哈哈。就連return都可以自己做，所以Tinymoe也不提供預定義的return。

 

那phrase (a) and (b) are the same shape怎么辦呢？沒問題，Tinymoe可以同時指定多個參數的類型。而且Tinymoe的實現具有跟C++虛函數一樣的性質——無論你有多少個參數標記了類型，我都可以O(n)跳轉到一個你需要的函數。這里的n指的是標記了類型的參數的個數，而不是函數實例的個數，所以跟C++的情況是一樣的——因為this只能有一個，所以就是O(1)。至于Tinymoe到底是怎么實現的，只需要看《如何設計一門語言》第五篇（http://www.shnenglu.com/vczh/archive/2013/05/25/200580.html）就有答案了。

Continuation Passing Style

為什么Tinymoe的控制流都可以自己做呢？因為Tinymoe的函數都是寫成了CPS這種風格的。其實CPS大家都很熟悉，當你用jquery做動畫，用node.js做IO的時候，那些嵌套的一個一個的lambda表達式，就有點CPS的味道。不過在這里我們并沒有看到嵌套的lambda，這是因為Tinymoe提供的語法，讓Tinymoe的編譯器可以把同一個層次的代碼，轉成嵌套的lambda那樣的代碼。這個過程就叫CPS變換。Tinymoe雖然用了很多函數式編程的手段，但是他并不是一門函數是語言，只是一門普通的過程式語言。但是這跟C語言不一樣，因為它連C#的yield return都可以寫成函數！這個例子就更長了，大家可以到Tinymoe的主頁上看。我這里只貼一小段代碼：

 

module enumerable

using standard library

 

symbol yielding return

symbol yielding break

 

type enumerable collection

    body

end

 

type collection enumerator

    current yielding result

    body

    continuation

end

 

略（這里實現了跟enumerable相關的函數，包括yield return）

 

block (sentence deal with (item)) repeat with (argument item) in (items : enumerable collection)

    set enumerator to new enumerator from items

    repeat

        move enumerator to the next

        deal with current value of enumerator

    end

end

 

sentence print (message)

    redirect to "Print"

end

 

phrase main

    create enumerable to numbers

        repeat with i from 1 to 10

            print "Enumerating " & i

            yield return i

        end

    end

 

    repeat with number in numbers

        if number >= 5

            break

        end

        print "Printing " & number

    end

end

 

什么叫模擬C#的yield return呢？就是連惰性計算也一起模擬！在main函數的第一部分，我創建了一個enumerable（iterator），包含1到10十個數字，而且每產生一個數字還會打印出一句話。但是接下來我在循環里面只取前5個，打印前4個，因此執行結果就是

當！

 

CPS風格的函數的威力在于，每一個函數都可以控制他如何執行函數結束之后寫在后面的代碼。也就是說，你可以根據你的需要，干脆選擇保護現場，然后以后再回復。是不是聽起來很像lua的coroutine呢？在Tinymoe，coroutine也可以自己做！

 

雖然函數最后被轉換成了CPS風格的ast，而且測試用的生成C#代碼的確也是原封不動的輸出了出來，所以運行這個程序耗費了大量的函數調用。但這并不意味著Tinymoe的虛擬機也要這么做。大家要記住，一個語言也好，類庫也好，給你的接口的概念，跟實現的概念，有可能完全不同。yield return寫出來的確要花費點心思，所以《序言》我也不講這么多了，后續的文章會詳細介紹這方面的知識，當然了，還會告訴你怎么實現的。

 

尾聲

這里我挑選了四個例子來展示Tinymoe最重要的一些概念。一門語言，要應用用起來簡單，庫寫起來可以發揮想象力，才是有前途的。yield return例子里面的main函數一樣，用的時候多清爽，清爽到讓你完全忘記yield return實現的時候里面的各種麻煩的細節。

 

所以為什么我要挑選Tinymoe作為實例來科普編譯原理呢？有兩個原因。第一個原因是，想要實現Tinymoe，需要大量的知識。所以既然這個系列想讓大家能夠看完實現一個Tinymoe的低質量原型，當然會講很多知識的。第二個原因是，我想通過這個例子向大家將一個道理，就是庫和應用 、編譯器和語法、實現和接口，完全可以做到隔離復雜，只留給最終用戶簡單的部分。你看到的復雜的接口，并不意味著他的實現是臃腫的。你看到的簡單的接口，也不意味著他的實現就很簡潔。

 

Tinymoe目前已經可以輸出C#代碼來執行了。后面我還會給Tinymoe加上靜態分析和類型推導。對于這類語言做靜態分析和類型推導又很多麻煩，我現在還沒有完全搞明白。譬如說這種可以自己控制continuation的函數要怎么編譯成狀態機才能避免掉大量的函數調用，就不是一個容易的問題。所以在系列一邊做的時候，我還會一邊研究這個事情。如果到時候系列把編譯部分寫完的同時，這些問題我也搞明白的話，那我就會讓這個系列擴展到包含靜態分析和類型推導，繼續往下講。

2013年我就干了兩件事情。第一件是gaclib，第二件是tinymoe。

 

Gaclib終于做到安全的支持C++的反射、從XML加載窗口和控件了?，F在在實現的東西則是一個給gaclib用的workflow小腳本，用來寫一些簡單的view的邏輯、定義viewmodel接口，還有跟WPF差不多的data binding。

 

Tinymoe是我大二的時候就設計出來的東西，無奈以前對計算機的理論基礎了解的太少，以至于沒法實現，直到現在才能做出來。總的來說tinymoe是一個模仿英語語法的嚴肅的編程語言——也就是說它是不基于NLP的，語法是嚴格的，寫錯一個單詞也會編譯不過。因此所有的函數都要寫成短語，包括控制流語句也是。所以我就想了一想，能不能讓分支、循環、異常處理和異步處理等等其他語言的內置的功能在我這里都變成庫？這當然是可以的，只要做全文的cps變換，然后要求這些控制流函數也寫成cps的風格就可以了。

 

目前的第一個想法是，等搞好了之后先生成javascript或者C#的代碼，不太想寫自己的VM了，然后就出一個系列文章叫做《看實例跟大牛學編譯原理》，就以這個tinymoe作為例子，來把《如何設計一門語言》延續下去，啊哈哈哈哈哈。

 

寫博客是一件很難的事情。我大三開始經營這個cppblog/cnblogs的博客的時候，一天都可以寫一篇，基本上是在記錄我學到的東西和我造的輪子?，F在都比較懶了，覺得整天說自己在開發什么也沒意思了，于是想寫一些別的，竟然不知如何下手，于是就出了各種沒填完的系列。

 

我覺得我學編程這13年來也是學到了不少東西的，除了純粹的api和語言的知識以外，很多方法論都給我起到了十分重要的作用。一開始是面向對象，然后是數據結構算法，然后是面向方面編程，然后是函數式編程，后來還接觸了各種跟函數式編程有關的概念，譬如說reactive programming啊，actor啊，異步啊，continuation等等。腦子里充滿了各種各樣的方法論和模型之后，現在無論寫什么程序，幾乎都可以拿這些東西往上套，然后做出一個維護也很容易（前提是有這些知識），代碼也很簡潔的程序了。

 

工作的這四年半里，讓我學習到了文檔和自動化測試的重要性，于是利用這幾年我把文檔和測試的能力也鍛煉的差不多了?，F在我覺得，技術的話工作應付起來是超級簡單，但是自己對技術的熱情還是促使我不斷的研究下去。2014年應該研究的技能就是嘴炮了。

     摘要: 在思考怎么寫這一篇文章的時候，我又想到了以前討論正交概念的事情。如果一個系統被設計成正交的，他的功能擴展起來也可以很容易的保持質量這是沒錯的，但是對于每一個單獨給他擴展功能的個體來說，這個系統一點都不好用。所以我覺得現在的語言被設計成這樣也是有那么點道理的。就算是設計Java的那誰，他也不是傻逼，那為什么Java會被設計成這樣？我覺得這跟他剛開始想讓金字塔的底層程序員也可以順利使用Java是有關系...  閱讀全文