如何设计一门语言（十）——正则表达式与领域特定语言（DSL）
幾個月前就一直有博友關心DSL的問題，于是我想一想，我在gac.codeplex.com里面也創建了一些DSL，于是今天就來說一說這個事情。
創建DSL恐怕是很多人第一次設計一門語言的經歷，很少有人一開始上來就設計通用語言的。我自己第一次做這種事情是在高中寫這個傻逼ARPG的時候了。當時做了一個超簡單的腳本語言，長的就跟匯編差不多，雖然每一個指令都寫成了調用函數的形態。雖然這個游戲需要腳本在劇情里面控制一些人物的走動什么的，但是所幸并不復雜，于是還是完成了任務。一眨眼10年過去了，現在在寫GacUI，為了開發的方便，我自己做了一些DSL，或者實現了別人的DSL，漸漸地也明白了一些設計DSL的手法。不過在講這些東西之前，我們先來看一個令我們又愛（對所有人）又恨（反正我不會）的DSL——正則表達式！
一、正則表達式
正則表達式可讀性之差我們人人都知道，而且正則表達式之難寫好都值得O’reilly出一本兩厘米厚的書了。根據我的經驗，只要先學好編譯原理，然后按照.net的規格自己擼一個自己的正則表達式，基本上這本書就不用看了。因為正則表達式之所以要用奇怪的方法去寫，只是因為你手上的引擎是那么實現的，所以你需要順著他去寫而已，沒什么特別的原因。而且我自己的正則表達式擁有DFA和NFA兩套解析器，我的正則表達式引擎會通過檢查你的正則表達式來檢查是否可以用DFA，從而可以優先使用DFA來運行，省去了很多其實不是那么重要的麻煩（譬如說a**會傻逼什么的）。這個東西我自己用的特別開心，代碼也放在gac.codeplex.com上面。
正則表達式作為一門DSL是當之無愧的——因為它用了一種緊湊的語法來讓我們可以定義一個字符串的集合，并且取出里面的特征。大體上語法我還是很喜歡的，我唯一不喜歡的是正則表達式的括號的功能。括號作為一種指定優先級的方法，幾乎是無法避免使用的。但是很多流行的正則表達式的括號竟然還帶有捕獲的功能，實在是令我大跌眼鏡——因為大部分時候我是不需要捕獲的，這個時候只會浪費時間和空間去做一些多余的事情而已。所以在我自己的正則表達式引擎里面，括號是不捕獲的。如果要捕獲，就得用特殊的語法，譬如說(<name>pattern)把pattern捕獲到一個叫做name的組里面去。
那我們可以從正則表達式的語法里面學到什么DSL的設計原則呢？我認為，DSL的原則其實很簡單，只有以下三個：
很多DSL其實都滿足這個定義。SQL就屬于API簡單而且可讀性好的那一部分（想想ADO.NET），而正則表達式就屬于API簡單而且語法緊湊的那一部分。為什么正則表達式可以設計的那么緊湊呢？現在讓我們來一一揭開它神秘的面紗。
正則表達式的基本元素是很少的，只有連接、分支和循環，還有一些簡單的語法糖。連接不需要字符，分支需要一個字符“|”，循環也只需要一個字符“+”或者“*”，還有代表任意字符的“.”，還有代表多次循環的{5,}，還有代表字符集合的[a-zA-Z0-9_]。對于單個字符的集合來講，我們甚至不需要[]，直接寫就好了。除此之外因為我們用了一些特殊字符所以還得有轉義（escaping）的過程。那讓我們數數我們定義了多少字符：“|+*[]-\{},.()”。用的也不多，對吧。
盡管看起來很亂，但是正則表達式本身也有一個嚴謹的語法結構。關于我的正則表達式的語法樹定義可以看這里：https://gac.codeplex.com/SourceControl/latest#Common/Source/Regex/RegexExpression.h。在這里我們可以整理出一個語法：
DIGIT ::= [0-9] LITERAL ::= [^|+*\[\]\-\\{}\^,.()] ANY_CHAR ::= LITERAL | "^" | "|" | "+" | "*" | "[" | "]" | "-" | "\" | "{" | "}" | "," | "." | "(" | ")" CHAR::= LITERAL::= "\" ANY_CHAR CHARSET_COMPONENT::= CHAR::= CHAR "-" CHARCHARSET::= CHAR::= "[" ["^"] { CHARSET_COMPONENT } "]"REGEX_0::= CHARSET::= REGEX_0 "+"::= REGEX_0 "*"::= REGEX_0 "{" { DIGIT } ["," [ { DIGIT } ]] "}"::= "(" REGEX_2 ")"REGEX_1::= REGEX_0::= REGEX_1 REGEX_0REGEX_2::= REGEX_1::= REGEX_2 "|" REGEX_1REGULAR_EXPRESSION::= REGEX_2這只是隨手寫出來的語法，盡管可能不是那么嚴謹，但是代表了正則表達式的所有結構。為什么我們要熟練掌握EBNF的閱讀和編寫？因為當我們用EBNF來看待我們的語言的時候，我們就不會被愈發的表面所困擾，我們會投過語法的外衣，看到語言本身的結構。脫別人衣服總是很爽的。
于是我們也要透過EBNF來看到正則表達式本身的結構。其實這是一件很簡單的事情，只要把EBNF里面那些“fuck”這樣的字符字面量去掉，然后規則就會分為兩種：
1：規則僅由終結符構成——這是基本概念，譬如說上面的CHAR什么的。
2：規則的構成包含非終結符——這就是一個結構了。
我們甚至可以利用這種方法迅速從EBNF確定出我們需要的語法樹長什么樣子。具體的方法我就不說了，大家自己聯系一下就會悟到這個簡單粗暴的方法了。但是，我們在設計DSL的時候，是要反過來做的。首先確定語言的結構，翻譯成語法樹，再翻譯成不帶“fuck”的“骨架EBNF”，再設計具體的細節寫成完整的EBNF。
看到這里大家會覺得，其實正則表達式的結構跟四則運算式子是沒有區別的。正則表達式的*是后綴操作符，|是中綴操作符，連接也是中最操作符——而且操作符是隱藏的！我猜perl系正則表達式的作者當初在做這個東西的時候，肯定糾結過“隱藏的中綴操作符”應該給誰的問題。不過其實我們可以通過收集一些素材，用不同的方案寫出正則表達式，最后經過統計發現——隱藏的中綴操作符給連接操作是最靠譜的。
為什么呢？我們來舉個例子，如果我們把連接和分支的語法互換的話，那么原本“fuck|you”就要寫成“(f|u|c|k)(y|o|u)”了。寫多幾個你會發現，的確連接是比分支更常用的，所以短的那個要給連接，所以連接就被分配了一個隱藏的中綴操作符了。
上面說了這么多廢話，只是為了說明白一個道理——要先從結構入手然后才設計語法，并且要把最短的語法分配給最常用的功能。因為很多人設計DSL都反著來，然后做成了屎。
二、Fpmacro
第二個要講的是Fpmacro。簡單來說，Fpmacro和C++的宏是類似的，但是C++的宏是從外向內展開的，這意味著dynamic scoping和call by name。Fpmacro是從內向外展開的，這意味著lexical scoping和call by value。這些概念我在第七篇文章已經講了，大家也知道C++的宏是一件多么不靠譜的事情。但是為什么我要設計Fpmacro呢？因為有一天我終于需要類似于Boost::Preprocessor那樣子的東西了，因為我要生成類似這樣的代碼。但是C++的宏實在是太他媽惡心了，惡心到連我都不能駕馭它。最終我就做出了Fpmacro，于是我可以用這樣的宏來生成上面提到的文件了。
我來舉個例子，如果我要生成下面的代碼：
int a1 = 1; int a2 = 2; int a3 = 3; int a4 = 4; cout<<a1<<a2<<a3<<a4<<endl;就要寫下面的Fpmacro代碼：
$$define $COUNT 4 /*定義數量：4*/ $$define $USE_VAR($index) a$index /*定義變量名字，這樣$USE_VAR(10)就會生成“a10”*/$$define $DEFINE_VAR($index) $$begin /*定義變量聲明，這樣$DEFINE_VAR(10)就會生成“int a10 = 10;”*/ int $USE_VAR($index) = $index; $( ) /*用來換行——會多出一個多余的空格不過沒關系*/ $$end$loop($COUNT,1,$DEFINE_VAR) /*首先，循環生成變量聲明*/ cout<<$loopsep($COUNT,1,$USE_VAR,<<)<<endl; /*其次，循環使用這些變量*/順便，Fpmacro的語法在這里，FpmacroParser.h/cpp是由這個語法生成的，剩下的幾個文件就是C++的源代碼了。不過因為今天講的是如何設計DSL，那我就來講一下，我當初為什么要把Fpmacro設計成這個樣子。
在設計之前，首先我們需要知道Fpmacro的目標——設計一個沒有坑的宏，而且這個宏還要支持分支和循環。那如何避免坑呢？最簡單的方法就是把宏看成函數，真正的函數。當我們把一個宏的名字當成參數傳遞給另一個宏的時候，這個名字就成為了函數指針。這一點C++的宏是不可能完全的做到的，這里的坑實在是太多了。而且Boost::Preprocessor用來實現循環的那個技巧實在是我操太他媽難受了。
于是，我們就可以把需求整理成這樣：
為什么要強調轉義呢？因為如果用Fpmacro隨便寫點什么代碼都要到處轉義的話，那還怎么寫得下去呀！
這個時候我們開始從結構入手。Fpmacro的結構是簡單的，只有下面幾種：
根據上面提到的DSL三大原則，我們要給最常用的功能配置最短的語法。那最短的功能是什么呢？跟正則表達式一樣，是連接。所以要給他一個隱藏的中綴運算符。其次就要考慮到轉義了。如果Fpmacro大量運用的字符與C++用到的字符一樣，那么我們在C++里面用這個字符的時候，就得轉義了。這個是絕對不能接受的。我們來看看鍵盤，C++沒用到的也就只有@和$了。這里我因為個人喜好，選擇了$，它的功能大概跟C++的宏里面的#差不多。
那我們如何知道我們的代碼片段是訪問一個C++的名字，還是訪問一個Fpmacro的名字呢？為了避免轉義，而且也順便可以突出Fpmacro的結構本身，我讓所有的Fpmacro名字都要用$開頭，無論是函數名還是參數都一樣。于是定義函數就用$$define開始，而且多行的函數還要用$$begin和$$end來提示（見上面的例子）。函數調用就可以這么做：$名字(一些參數)。因為不管是參數名還是函數名都是$開頭的，所以函數調用肯定也是$開頭的。那寫出來的代碼真的需要轉義怎么辦呢？直接用$(字符)就行了。這個時候我們可以來檢查一下這樣做是不是會定義出歧義的語法，答案當然是不會。
我們定義了$作為Fpmacro的名字前綴之后，是不是一個普通的C++代碼（因此沒有$），直接貼上去就相當于一個Fpmacro代碼呢？結論當然是成立的。仔細選擇這些語法可以讓我們在只想寫C++的時候可以專心寫C++而不會被各種轉義干擾到（想想在C++里面寫正則表達式的那一堆斜杠臥槽）。
到了這里，就到了最關鍵的一步了。那我們把一個Fpmacro的名字傳遞給參數的時候，究竟是什么意思呢？一個Fpmacro的名字，要么就是一個字符串，要么就是一個Fpmacro函數，不會有別的東西了（其實還可能是數組，但是最后證明沒用）。這個純潔性要一直保持下去。就跟我們在C語言里面傳遞一個函數指針一樣，不管傳遞到了哪里，我們都可以隨時調用它。
那Fpmacro的函數到底有沒有包括上下文呢？因為Fpmacro和pascal一樣有“內部函數”，所以當然是要有上下文的。但是Fpmacro的名字都是只讀的，所以只用shared_ptr來記錄就可以了，不需要出動GC這樣的東西。關于為什么帶變量的閉包就必須用GC，這個大家可以去想一想。這是Fpmacro的函數像函數式語言而不是C語言的一個地方，這也是為什么我把名字寫成了Fpmacro的原因了。
不過Fpmacro是不帶lambda表達式的，因為這樣只會把語法搞得更糟糕。再加上Fpmacro允許定義內部函數和Fpmacro名字是只讀的這兩條規則，所有的lambda表達式都可以簡單的寫成一個內部函數然后賦予它一個名字。因此這一點沒有傷害。那什么時候需要傳遞一個Fpmacro函數呢進另一個函數呢？當然就只有循環了。Fpmacro的內置函數有分支循環還有簡單的數值計算和比較功能。
我們來做一個小實驗，生成下面的代碼：
void Print(int a1) {cout<<"1st"<<a1<<endl; }void Print(int a1, int a2) {cout<<"1st"<<a1<<", "<<"2nd"<<a2<<endl; }....void Print(int a1, int a2, ... int a10) {cout<<...<<"10th"<<a10<<endl; }....我們需要兩重循環，第一重是生成Print，第二重是里面的cout。cout里面還要根據數字來產生st啊、nd啊、rd啊、這些前綴。于是我們可以開始寫了。Fpmacro的寫法是這樣的，因為沒有lambda表達式，所以循環體都是一些獨立的函數。于是我們來定義一些函數來生成變量名、參數定義和cout的片段：
$$define $VAR_NAME($index) a$index /*$VAR_NAME(3) -> a3*/ $$define $VAR_DEF($index) int $VAR_NAME($index) /*$VAR_DEF(3) -> int a3*/ $$define $ORDER($index) $$begin /*$ORDER(3) -> 3rd*/$$define $LAST_DIGIT $mod($index,10)$index$if($eq($LAST_DIGIT,1),st,$if($eq($LAST_DIGIT,2),nd,$if($eq($LAST_DIGIT,3),rd,th))) $$end $$define $OUTPUT($index) $(")$ORDER($index)$(")<<$VAR_NAME($index) /*$OUTPUT(3) -> "3rd"<<a3*/接下來就是實現Print函數的宏：
$$define $PRINT_FUNCTION($count) $$begin void Print($loopsep($count,1,$VAR_DEF,$(,))) {cout<<$loopsep($count,1,$OUTPUT,<<)<<endl; } $( ) $$end最后就是生成整片代碼了：
$define $COUNT 10 /*就算是20，那上面的代碼的11也會生成11st，特別方便*/ $loop($COUNT,1,$PRINT_FUNCTION)注意：注釋其實是不能加的，因為如果你加了注釋，這些注釋最后也會被生成成C++，所以上面那個$COUNT就會變成10+空格+注釋，他就不能放進$loop函數里面了。Fpmacro并沒有添加“Fpmacro注釋”的代碼，因為我覺得沒必要
為什么我們不需要C++的宏的#和##操作呢？因為在這里，A(x)##B(x)被我們處理成了$A(x)$B(x)，而L#A(x)被我們處理成了L$(“)$A(x)$(“)。雖然就這么看起來好像Fpmacro長了一點點，但是實際上用起來是特別方便的。$這個前綴恰好幫我們解決了A(x)##B(x)的##的問題，寫的時候只需要直接寫下去就可以了，譬如說$ORDER里面的$index$if…。
那么這樣做到底行不行呢？看在Fpmacro可以用這個宏來生成這么復雜的代碼的份上，我認為“簡單緊湊”和“C++代碼幾乎不需要轉義”和“沒有坑”這三個目標算是達到了。DSL之所以為DSL就是因為我們是用它來完成特殊的目的的，不是general purpose的，因此不需要太復雜。因此設計DSL要有一個習慣，就是時刻審視一下，我們是不是設計了多余的東西。現在我回過頭來看，Fpmacro支持數組就是多余的，而且實踐證明，根本沒用上。
大家可能會說，代碼遍地都是$看起來也很亂啊？沒關系，最近我剛剛搞定了一個基于語法文件驅動的自動著色和智能提示的算法，只需要簡單地寫一個Fpmacro的編輯器就可以了，啊哈哈哈哈。
三、尾聲
本來我是想舉很多個例子的，還有語法文件啊，GUI配置啊，甚至是SQL什么的。不過其實設計一個DSL首先要求你對領域本身有著足夠的理解，在長期的開發中已經在這個領域里面感受到了極大的痛苦，這樣你才能真的設計出一個專門根除痛點的DSL來。
像正則表達式，我們都知道手寫字符串處理程序經常要人肉做錯誤處理和回溯等工作，正則表達式幫我們自動完成了這個功能。
C++的宏生成復雜代碼的時候，動不動就會因為dynamic scoping和call by name掉坑里而且還沒有靠譜的工具來告訴我們究竟要怎么做，Fpmacro就解決了這個問題。
開發DSL需要語法分析器，而且帶Visitor模式的語法樹可擴展性好但是定義起來特別的麻煩，所以我定義了一個語法文件的格式，寫了一個ParserGen.exe（代碼在這里）來替我生成代碼。Fpmacro的語法分析器就是這么生成出來的。
GUI的構造代碼寫起來太他媽煩了，所以還得有一個配置的文件。
查詢數據特別麻煩，而且就算是只有十幾個T的小型數據庫也很難自己設計一個靠譜的容器，所以我們需要SQLServer。這個DSL做起來不簡單，但是用起來簡單。這也是一個成功的DSL。
類似的，Visual Studio為了生成代碼還提供了T4這種模板文件。這個東西其實超好用的——除了用來生成C++代碼，所以我還得自己擼一個Fpmacro……
用MVC的方法來寫HTML，需要從數據結構里面拼HTML。用過php的人都知道這種東西很容易就寫成了屎，所以Visual Studio里面又在ASP.NET MVC里面提供了razor模板。而且他的IDE支持特別號，razor模板里面可以混著HTML+CSS+Javascript+C#的代碼，智能提示從不出錯！
還有各種數不清的配置文件。我們都知道，一個強大的配置文件最后都會進化成為lisp，哦不，DSL的。
這些都是DSL，用來解決我們的痛點的東西，而且他本身又不足以復雜到用來完成程序所有的功能（除了連http service都能寫的SQLServer我們就不說了=_=）。設計DSL的時候，首先要找到痛點，其次要理清楚DSL的結構，然后再給他設計一個要么緊湊要么可讀性特別高的語法，然后再給一個簡單的API，用起來別提多爽了。
from: http://www.cnblogs.com/geniusvczh/p/3323637.html
總結
以上是生活随笔為你收集整理的如何设计一门语言（十）——正则表达式与领域特定语言（DSL）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 如何设计一门语言（九）——类型
- 下一篇： 如何设计一门语言（十一）——删减语言的功