#
author: Kevin Lynx email: zmhn320#163.com date: 3.7.2009
詞法分析
詞法分析屬于整個編譯流程中的第一個階段。為什么要把編譯過程分為多個階段，這就
如同軟件分層一樣，個人覺得是出于降低復雜性的考慮。
再次聲明我不會告訴你任何編譯原理的理論知識，因為坦率地說我也不會:D。所以我努
力將我們需要了解的概念盡可能簡單地告訴你。當然，可能會與教科書不吻合。
什么是詞法分析?
詞法分析就是把一段話整理成單詞集合。舉個簡單的例子，例如有代碼:age = age + 1;，
經過詞法分析后，將得到：age、=、age、+、1、;幾個符號。為了方便，我稱每個單詞為一
個token。
詞法分析的作用
詞法分析分析出來的單詞集合，直接作為編譯流程中接下來的語法分析的輸入。那么語
法分析階段面對的將是一個一個的token，而不是單個的字符。
例如，在處理age = age + 1;這種語句時，當我們獲取到token "="時，我們直接期望接
下來的token應該是個表達式。以單詞為單位地處理，比直接處理單個字符簡單很多。
詞法分析的過程
詞法分析的輸入是單個字符流，一般我們fopen一個源代碼文件，保存在一個char緩存
里，這就是詞法分析的輸入。而詞法分析的最終輸出結果就是一個一個的token。
為了處理方便，token并不是單純的單詞。通常我們會將源代碼中的所有單詞分類，例
如變量名其實都屬于一類token。簡單的token可定義為：
struct Token
{
int type;
char value[256];
};
type用于表示token的類型，例如一個變量名token的類型是一個標識符。value可以用
來具體地保存這個變量的名字。
對于type的處理，通常會事先定義一組枚舉值，例如：
enum { ID, NUM, STRING, IF, ELSE, WHILE, RETURN, FUNCTION }等等用于標示
在一個源代碼中可能出現的所有token。
雖然說詞法分析的結果是一個token集合，但事實上我們并不是一次做完詞法分析。通常
詞法分析模塊提供一個get_token函數。每次調用該函數時，都返回源代碼中下一個token。
例如，有源代碼：age = age + 1;
第一次調用get_token將獲得 { ID, "age" }，第二次獲得 { ASSIGN, "=" }，第三次
獲得{ ID, "age" }，等等。
那么，詞法分析該如何實現？也就是struct Token get_token()函數如何實現？其實很
簡單，你告訴我：給你一個字符串，你如何判斷這個字符串全部是數字？
int is_num( const char *str )
{
while( *str != 0 )
{
if( !isdigit( *str++ ) ) return 0;
}
return 1;
}
所以，基本上，詞法分析的過程也就是這個過程。就拿標識符舉例，典型的標識符一般
以字符開頭，然后接著是數字或字符或_，當遇到非法字符時，這個標識符的掃描即結束。
詞法分析一般是個while+switch：
struct Token get_token()
{
while( current_char != 0 )
{
switch( current_char )
{
case CHARACTER:
/* 掃描一個標識符 token */
break;
case '=':
/* 獲得一個 ASSIGN token */
break;
...
}
}
}
現在，試著去總結一門語言里的每一個token的規則，然后自己去寫寫看。
代碼導讀
在本節我將提供kl在googlecode的SVN上的代碼，先不要去管代碼包中的其他東西。關于
詞法的代碼可以在kllex.c kllex.h中找到。lex_token是提供給其他模塊的接口，用于獲取
當前掃描的token。掃描結果可以通過lexState結構體獲取。
再次提下版權問題，代碼文件以及代碼包中我并沒有加入任何版權說明，哪怕是GPL。
但是如同我之前說的一樣，我不介意你傳播、改動此代碼，但是請保留原作者信息。當然，
我并不介意你加上@modified by xxx:)。
下載kl源代碼：http://klcommon.googlecode.com/files/kllan_0.1.0.zip
author: Kevin Lynx email: zmhn320#163.com date: 3.6.2009
語言特性
在正式討論實現細節前明確下這個腳本語言的一些語言特性，基本上可以讓我們預見將
來會遇到哪些難題。總的來說，它（腳本）將同我們平時接觸的如lua一樣的腳本語言：擁
有一般的編程語言特性，如變量、各種控制流程、也許還有函數，另一方面它還應該和它的
宿主語言結合，如作為一個庫被用進C，這還涉及到給這門語言設計一種插件方式，最好能
通過獨立的解釋程序讓腳本載入一些插件運行。
以下在描述我寫的這個腳本語言時，將以kl表示它的名字，以方便描述。
代碼塊：
首先從整體風格上，kl如同C語言一樣被劃分為函數塊，如：
function func1()
{
}
function func2()
{
}
...
kl支持以{}隔離代碼塊，但是這并不意味著kl有多個獨立的局部堆棧，如同C語言一樣。
這些細節暫不討論。本節描述的所有內容你都不必深究，因為我只要求你對kl有個感性上的
認識。
函數塊之外沒有可執行的語句(statement)。那么你可能會想到程序的入口點也許會是
main。事實上從kl提供的庫來看，并沒有這種硬性要求。但是，kl的獨立解釋程序是這樣要
求的。
變量：
kl允許你在任何地方使用一個變量。變量不需要事先定義，任何地方出現一個合
法的標識符時，就意味著kl內部會增加這個變量，并給予初值。變量也沒有靜態類型，也不
會固定為某一類型。就一門最簡單的語言來看，我覺得數據類型無非就是字符串和數字類型
。
所以，kl的變量在某一時刻必然是數字，或者字符串。在腳本里，你無法獲知一個變量
的類型，事實上也沒這個必要。說變量擁有一個類型屬性，倒不如說值(value)有一種類型
屬性。
當字符串值與數字值參與運算時，如1+"a"，其運算結果將自動轉換為字符串，也就是
"1a"。
一個只有標識符的語句(statement)通常意味著你想定義一個變量。這種無聊的手段通
常被用于定義全局變量。
運算符：
kl支持一般的C語言風格的算術、比較、邏輯運算符。例如加減乘除、大于小于、邏輯
與邏輯或。
作用域：
kl腳本里只有兩個作用域：全局的和局部的。
位于所有函數塊外的變量處于全局作用域；位于函數內的變量處于局部作用域，位于函
數塊內的代碼塊變量，還是處于局部作用域。
當局部作用域內出現一個全局里的同名變量時，優先取局部作用域里的變量。這同C語
言一樣。
控制語句if：
if的語法同C語言一樣，如：
if( a > 10 )
{
}
else
{
}
if( a > 10 )中的a>10被我成為條件語句，所有條件語句，包括下面的while，都不能
為字符串。例如if( "a" )將被視為非法語句。（我為什么要這樣考慮？- -!）
控制語句while:
c-like while:
while( a > 10 )
{
}
很遺憾，我暫時沒有加入對for的支持。因為我覺得既然有了while，有了循環控制，在
沒有更多無聊時間的前提下，我沒有必要加入for。
函數：
很遺憾，函數的定義和調用和C語言有點不一樣。這是因為kl沒有變量類型，那就意味
著函數定義如果和C語言一樣，就會出現語法歧義，如：
func( a )
{
}
就會和函數調用func(a)出現混淆。所以，我加入了function關鍵字。定義函數的語法
為：
function func( a, b )
{
}
如你所見，函數支持參數傳遞，當然也支持return a;返回值。kl是簡陋的，因為它沒
有指針之類的概念，所以你無法為函數傳遞一塊數據。當然，kl也不能像lua一樣讓函數可
以返回多個值。
函數調用的語法相對熟悉：
func( 1, 3 );
數組：
從一開始我就沒考慮為kl加入數組。事實證明加入數組是一個不明智的做法。數組的支
持讓代碼在很多地方變得臟亂。無論如何，kl后來支持一維數組了。為了讓代碼保持那么一
點點的干凈，我甚至為定義數組加入dim的關鍵字。這意味著，在kl里，數組和一般的變量
總有點不一樣：變量無需定義，數組卻必須事先定義。
數組的長度不支持動態擴充。如果支持，我得讓kl內部更好地去管理內存。
數組元素的類型沒有硬性的規定，這意味著a[0] = 1; a[1] = "a";是允許的。
語言特性上就描述這些，在本節末尾我決定貼一段kl計算階乘的代碼：
/* fac.kl */
function main()
{
n = input( "%d" );
print( "fac(" + n + ") = " + fac( n ) );
}
function fac( n )
{
if( n == 1 )
{
return 1;
}
else
{
return fac( n - 1 ) * n;
}
}
author: Kevin Lynx email: zmhn320#163.com date: 3.6.2009
（相信我，這一節全是廢話。）
我不是標題黨，但是有必要解釋下這個標題。綜合來說我就是想與你分享我所學到的。
我會將我實現的這個簡單的腳本語言的實現細節展示給你。它將涵蓋：詞法分析、語法分析
、符號表管理、語法樹解釋執行、插件管理等內容。
我并不擅長傳授編譯原理知識。我沒有聽過編譯原理課，所以我也不會編譯原理（也許
即使我聽了也不會:D）。所以對于這方面的能手而言，我口中的‘DFA‘可能會貽笑大方。
顯然，CPPBLOG上有編譯原理上的大牛。如果你想學習更深入的知識，可以去請教他們。
vczh(http://www.shnenglu.com/vczh/) 看起來是我所說的這個人。在致謝名單里我將真誠地
寫上他的名字。他的’手把手xxx腳本‘系列多多少少還是給了我一些有用的信息。
其次是FOX，在詞法分析的DFA和NFA那里我請教了他一些問題。雖然我現在又忘了。如
你們所知，理論和實現之間總會隔著鴻溝。
推薦《編譯原理與實踐》(<Compiler Construction:Principles and Practice>
Kenneth C. Louden)這本書。在你將來閱讀我的腳本語言的實現代碼時，你會發現有很一些地
方同這本書里的TINY語言實現代碼有相似之處。建議你閱讀TINY的代碼。
感謝VIM、GCC、GDB、MingW，我用這些軟件在工作之余寫出了這個東西的幾千行C代碼。
很明顯我是個開源文化的愛好者。但是我不會告訴你unix有多么多么好，因為我也是個初學
者，我還不懂unix。開源在我看來更是一種分享知識的精神。讓這種精神如同GPL一樣病毒
式地傳染下去。
還有版權問題。但也許它不是個問題。我不會添加任何版權信息。我允許你任意傳播、
改動我所散播的東西，但是唯一的基本條件是：保留作者的信息---不要告訴別人，這東西
是你做的。
在所有的文章發布后，我都可能會再次修改。也許通過RSS或者日志日期之類你可以獲
得修改提醒。
從我接觸的UNIX文化中我知道，要學會更好地去使用工具去組合工具來完成日常的工作。項目使用alienbrain作為源代碼管理工具。每次在VC里有些代碼文件里總會寫些并不想簽入到代碼服務器上的代碼，例如我經常#include "vld.h"來檢測內存泄漏。但是真的等到簽入代碼時，又經常忘記刪除這些代碼。
于是我想，如果每次在我簽入代碼前，VC或者alienbrain或者其他工具能根據我的設置檢查我的代碼中是否存在這種不想簽入的代碼，然后提示我。問了一下向來很熟悉工具的FOX（很抱歉，我甚至不會使用WORD，我真不敢相信我的坦率:D），結果他也不知道。今天閑來無事翻了下alienbrain附帶的文檔，發現EventsScript。
alienbrain里的EventScript總的來說是一種讓用戶定制更多功能的機制。它定義諸如簽入簽出獲取版本等動作為event，然后用戶可以使用alienbrain支持的VBScript和JavaScript腳本來處理這些事件。例如，當你簽出一個文件時，ab(alienbrain)會調用你的腳本，讓你來處理這一事件）。當腳本返回時，ab繼續處理剛才的操作（如果你實在想中止這一動作也可以）。
這正是我需要的一種機制。迅速地看完了EventScript這一節的文檔。再想想我的需求，大體思路就是：給check in掛個腳本，讓該腳本調用一個外部程序，處理將要check in的文件，分析這個文件。我可以規定在我的代碼中凡是不想簽入的代碼都可以附加一個tag，例如：#include "vld.h" //DUMMY，分析該代碼文件時，發現代碼中有//DUMMY字符串，就提示我說該代碼文件有不想被簽入的代碼，位于某某行。
看來我似乎需要一個grep工具，萬惡的是windows只有find。不過find基本可以滿足我的需求，但是find的輸出結果看起來并不是那么友好，并不是可以被另一個程序處理的格式。（linux下通過建立標準的輸入輸出格式，從而可以輕松地讓多個程序協作起來更好地完成很多事）無論如何，我需要使用ab提供給我的接口來試驗下我的想法。
然后噩夢開始了。先是發現NxNLauncher（ab提供的一個接口，大致是這樣拼寫的，現在機器上沒ab）的Exec接口是異步執行進程，從而StdOut屬性及ExitCode總是得不到正確的值。后來一不小心在ab的wiki上看到，說Exec有個隱藏參數，用來標識是同步執行進程還是異步執行，顯然，這個隱藏參數undocumented。- -!
再然后是每次執行find后，find程序倒是被執行起來了，結果卻崩潰了。萬惡的是我執行其他程序卻很正常。google了一下居然發現沒人遇到這個問題。最近我的windows總是崩潰各種程序，visual stdio, word, find。但是，我并不打算自己寫個find，即使是簡化版的。于是我決定寫個findwrapper，讓ab來調用我自己寫的程序，然后我這個程序調用find。然后為了搞定兩個程序的通信，又想起了管道pipe。當然，這里的通信很簡單，我只需要讓find的輸出重定向到我的findwrapper，然后我的findwrapper又會被重定向到ab，然后我的ab腳本就可以捕獲這些輸出，然后再分析這些輸出就可以了。- -！
其實，最簡單的解決方法，就是我自己寫個撇腳的程序，自己去分析要簽入的文件是否含有//DYMMY字符串。但是很顯然，我更喜歡證明我最初的想法是否正確。
然后，在我的findwrapper里，再一次讓find崩潰。經過幾次試驗，顯然問題出在共享管道上。find和ping的不同在于，find可以從標準輸入里獲取輸入，而ping只需要一個標準輸出（也許還有stderr）。在CreateProcess里傳入的startup info結構體里，需要提供標準輸入、標準輸出、及錯誤輸出三個handle。顯然，問題出在標準輸入上，我提供了錯誤的值。按照一般的接口設計，我以為我如果不提供輸入句柄，find就會忽略。但是find顯然沒那么聰明，或者說，find更喜歡直接*ptr = 10而不是if( ptr != 0 ) *ptr = 10。無論如何，當我把輸入句柄填為輸出句柄后，findwrapper可以捕獲find的輸出了，當然，find也不崩潰了。
我總覺得折騰windows api有點噩夢的感覺。我記得幾年前剛學windows編程的時候很多函數總要試驗很多次才能得到正確的結果，基本上我要嘗試各個參數的諸多組合。這還不包括上下文的影響，你要RegisterClass出了問題，CreateWindow楞是不會給你一點點有意義的error code，OMG。
開始用FLEX做詞法分析，然后在此基礎上稍微做些符號匹配（實在稱不上語法分析），即完成了XML
文件的簡單解析。
我把XML文件拆分成：<, >, />, </, =, ID, STRING 等token。這樣一整理，用FLEX直接生成詞法
分析程序。每一次getToken就返回這些token。上層的語法匹配就變得比較簡單。例如當得到"/>"token
時，我就可以判斷這是一個節點的結束；當得到ID token時，就可以推測下一個token為"="，再下一個
是個STRING。不過對于部分token，也需要做一兩個token的回溯，例如當遇到"<"時，并不一定表示一個
新節點的開始，它可能是新節點的開始，同樣也可能是上一個節點的結束("</")。
以我薄弱的編譯原理知識來看，解析XML變得非常容易。除此之外，還需要寫一些上層代碼來保存
XML結構，以方面更上層代碼獲取XML文件的配置信息。因為我打算用純C來寫這個東西，所以數據結構方
面只有自己處理。這里我以一種變相的樹結構來保存：每一個節點有兩個域：first child, sibling。
其實這樣做是一個很明顯的通用做法，因為XML種每一個節點都可能擁有不定數量的children節點，如果
讓parent直接去保存，顯然很笨。例如：
<Resource>
<bmp file="1.bmp"/>
<bmp file="2.bmp"/>
</Resource>
可以使用這樣的數據結構來存儲：
struct xmlNode
{
...
struct xmlNode *child;
struct xmlNode *sibling;
};
對于Resource這個node而言，其child域指向第一個bmp節點(file屬性為1.bmp那個節點)；對于第一
個bmp節點而言，其sibling域則指向了第二個bmp節點。
這個簡單的xml解析器是在公司外網機器上寫的，沒有VC，沒有任何IDE。代碼我是用VIM敲的，敲好
后寫makefile，用mingw里的gcc、make來生成程序，用gdb來調試程序。這算是第一次離開VC寫的一個非
練習程序(起碼用makefile來組織工程)。- -| makefile寫的比較爛，gdb用得很不熟，不過好歹調試出來
了。越來越想換個平臺，只可惜工作還是得在windows vc下，很掃興。
后來發覺詞法分析也很簡單，用FLEX的時候正則表達式都寫出來了。前段時間一直在看編譯原理，雖然不
用功。但是就這里而言，基本可以直接根據正則表達式畫出DFA。終于不用接觸那惡心的從NFA轉DFA的
過程，因為我至今不會，更不會寫代碼轉。- - 總而言之，自己手寫了詞法分析。邊寫邊參考編譯原理
與實踐中附帶的tiny-c編譯器的詞法分析部分，最終發現我抄了一遍。MD，一點技術含量都沒有。
附上全部源代碼（對于代碼我還是比較滿意的:D），下載
說下最近自己遇到的兩個值得讓人注意的問題。
其一是關于自己給std::map寫less predicate，std::map第三個參數是一個典型的functor。map內部將使用
這個functor去判定兩個元素是否相等，默認使用的是std::less。但是為什么傳入的是一個判斷第一個參數
小于第二個參數的functor，而不是一個判斷兩個參數是否相等的functor？按照STL文檔的說法，當檢查兩
個參數沒有小于也沒有大于的關系時，就表示兩個參數相等。不管怎樣，我遇到了需要自己寫這個functor
的需求，于是：
struct MyLess
{
bool operator() ( long left, long right )
{
//...
}
};
DEBUG模式下編譯沒問題，RELEASE模式下卻出現C3848的錯誤。這就有點奇怪了，如果確實存在語法錯誤，
那么DEBUG和RELASE應該一樣才對。查了下MSDN，C3848的錯誤是因為const限定符造成的，如：
const MyLess pr;
pr(); // C3848
于是，在operator()后加上const，就OK了。看了下VC std::map相關代碼，以為是DEBUG和RELEASE使用了不
同的代碼造成。但是我始終沒找到不同點。另一方面，就STL內部的風格來看，應該不會把predicator處理
成const &之類的東西，全部是value形式的。奇怪了。
第二個問題，涉及到靜態變量。這個東西給我的印象特別深刻，因為以前去一家外企應聘時被問到，當時
覺得那個LEADER特別厲害?；貋砗笞屛曳此?，是不是過多地關注了C++里的花哨，而漏掉了C里的樸素？導致
我至今對純C存在偏好。
說正題，我現在有如下的文件關系：
// def.h
struct Obj
{
Obj()
{
ObjMgr::AddObj( id, this );
}
int id;
};
struct ObjMgr
{
static void AddObj( int id, Obj *t )
{
ObjTable[id] = t;
}
static std::map<int, Obj*> ObjTable;
};
static Obj _t;
// ObjMgr.cpp
#include "def.h"
static std::map<int, Obj*>::ObjMgr ObjTable;
// main.cpp
#include "def.h"
這里舉的例子可能有點不恰當，我在一臺沒有編譯器的機器上寫的這篇文章。忽略掉這些旁支末節。我的意思，
就是想讓Obj自己自動向ObjMgr里添加自己。我們都知道靜態變量將在程序啟動時被初始化，先于main執行之前。
上面代碼有兩個問題：
一、
代碼沒有按照我預期地執行，如果你按照我的意思做個測試，你的程序甚至在進main之前就crash了。我假定你
用的是VC，因為我沒在其他編譯器上試驗過。問題就在于，Obj的構造依賴于ObjTable這個map對象。在調試過程
中我發現，雖然ObjTable擁有了內存空間，其this指針有效，但是，map對象并沒有得到構造。我的意思是，Obj
的構造先于ObjTable構造（下幾個斷點即可輕易發現），那么在執行map::operator[]時，就出錯了，因為這個時候
map里相關數據還沒準備好。
那是否存在某種機制可以手動靜態變量的初始化順序呢？不知道。我最后怎樣解決這個問題的？
二、
在還沒有想到解決辦法之前（不改變我的設計），我發現了這段代碼的另一個問題：我在頭文件里定義了靜態
變量：static Obj _t; 這有什么問題？想想預編譯這個過程即可知道，頭文件在預編譯階段被文本展開到CPP
文件里，然后，ObjMgr.cpp和main.cpp文件里都將出現static Obj _t;代碼。也就是說，ObjMgr.obj和main.obj
里都有一個文件靜態變量_t。
看來，在頭文件里放這個靜態變量是肯定不對的。于是，我將_t移動到ObjMgr.cpp里：
// ObjMgr.cpp
#include "def.h"
static std::map<int, Obj*>::ObjMgr ObjTable;
static Obj _t;
按照這樣的順序定義后，_t的構造居然晚于ObjTable了。也就是說，放置于前面的變量定義，就意味著它將被
首先構造初始化。這樣兩個問題都解決了。
但是，誰能保證這一點特性？C標準文檔里？還是VC編譯器自己？
Macro Recursion
author: Kevin Lynx
Preface
本文可能是<代碼自動生成-宏帶來的奇技淫巧>的續寫。我盡力闡述如何讓宏遞歸（或者說重復）地有規律地產生一
些符號，而讓我們少寫很多重復代碼，也許這些代碼只有那么一點點的不同。將這項小技巧用于底層庫的編寫，會讓代碼
看起來干凈不少，同時文件尺寸也會驟然下降。
Problem
如果你曾經寫過functor，那么你肯定對某些代碼進行粘貼復制然后修改。更讓人郁悶的是，這些代碼基本是一樣的。
例如，一個典型的functor可能為：
template <typename Prototype>
class functor;
template <typename R, typename P1>
class functor<R(P1)>;
template <typename R, typename P1, typename P2>
class functor<R(P1,P2)>;
//好，接下去你可能厭煩了，可能會復制一個帶有兩個參數的functor，然后修改為處理3個參數的。
這只是一個很簡單的問題。宏不是c++里的東西，本文自然也不是討論各種花哨的模板技術的。如果我之前那篇關于
宏的文章只是讓你去分析問題以及更深層次地認識宏，那么現在我將分享我的這部分思想給你。
關于上面的問題，我們期待得到這樣的解決方案：
template <typename R, DEF_PARAM( 2 )>
class functor<R( DEF_ARG( 2 ) )>;
那么，它將自動生成：
template <typename R, typename P1, typename P2>
class functor<R(P1,P2)>;
也就是說，DEF_PARAM(n)這個宏將根據n值自動生成一串符號，例如DEF_PARAM(2)就生成typename P1, typename P2。
同樣，DEF_ARG(n)也會根據參數生成類似于P1,P2,...,Pn的符號串。
思考
仔細思考下，我們可以看出DEF_PARAM和DEF_ARG這樣的宏具有一種遞歸的特性（其實說成重復可能更合適）：每次展
開的內容基本一樣，不斷調用自身直到遇到終止條件。
那么，我們的目標鎖定于，用宏來實現遞歸。
Pre-Implement
在開始之前，我需要告訴你一些基本的東西：
在閱讀一個宏時，你最好按照預處理的處理方式去逐個展開。當我說到展開時，我的意思是把宏替換為宏體。預處理器
展開宏的過程大致為：如果宏參數也是個宏，那么先將宏參數全部展開，再展開該宏；這個時候會掃描展開后的宏，如果
遇到其他宏，則繼續展開。例如有一下宏：
#define PI 3.14
#define MUL_PI( n ) n * PI
#define TWO 2
當我們寫下MUL_PI( TWO )時，預處理發現MUL_PI的參數TWO 是個宏，那么先將TWO展開得到2，然后將2放進宏體展開
得到 2 * PI；預處理器對 2 * PI 進行掃描，發現還有宏PI，于是對PI做展開，得到 2 * 3.14。這個過程是遞歸的。
但是也有例外，如果MUL_PI對宏參數進行了#或者##，那么該宏參數不會被展開。（參見以前那篇文章吧）
任何時候，你可以通過以下宏去查看某個宏展開后的樣子，可以方便你調試你的宏：
#define TO_STRING( x ) TO_STRING1( x )
#define TO_STRING1( x ) #x
（為什么要寫個TO_STRING1，因為這是為了讓x充分展開，避免上面提到的那個例外）
其他規則我會在文中需要的地方提出來。
實現
就像大部分介紹遞歸函數時候給的例子，這里我也將階乘作為例子?？紤]如下典型的階乘函數：
int fac( int n )
{
if( n == 1 ) return 1;
return n * fac( n - 1 );
}
其核心部分在于 n * fac( n - 1 )，我們假設我們的宏也可以寫成這樣的的形式：
#define FAC( n ) n * FAC( n - 1 )
但是這樣的宏是有問題的：
當宏被展開時，如果遇到了自身，那么將被處理為一般符號，例如展開FAC( 3 )時，會遇到 FAC( 2 )，那么就把FAC
( 2 )中的FAC當成了一搬符號。
這樣的限制注定了我們無法讓宏真正地調用自身來實現遞歸。于是，我們不得不寫下以下丑陋的符號，從而去模擬遞
歸的每一次符號調用：
#define FAC_1( n ) 1
#define FAC_2( n ) n * FAC_##(n-1)( n - 1 )
#define FAC_3( n ) n * FAC_##(n-1)( n - 1 )
這系列宏有點別扭（如果你足夠細心），因為我們明顯知道FAC_2返回的將是2，而FAC_3返回的當時6。我們這里只是
模擬，同樣，這使得我們可以把FAC_1作為遞歸的終止條件。
我們的預想是，當調用FAC_3時，它把n-1的值2合并到FAC_中，從而調用FAC_2，以此類推。
但是這依然有問題，編譯器會提示‘找不到符號FAC_’。導致這個問題的原因在于：宏展開只是單純的字符替換，是我們
想太多了，預處理器并不會去計算( n - 1 )的值是多少，也就是我們無法得到FAC_2這個宏。
所以，FAC_3( 3 ) 會被初次替換為 3 * FAC_(3-1)( 3 - 1 )。這個時候編譯器就把FAC_當成了一個普通符號。我們可以
自己定義個FAC_來證明這一點：
#define FAC_( n ) T
那么，FAC_3( 3 )就被替換為 3 * T(3-1)( 3 - 1 )。
解決這個問題的辦法關鍵在于，讓預處理器自動計算出( n - 1 )。記住，我們解決問題的唯一辦法是：字符替換。
所以，我們可以寫下如下代碼：
#define DEC_1 0
#define DEC_2 1
#define DEC_3 2
#define DEC( n ) DEC_##n
通過，DEC( n )這個宏，我們可以獲取到一個( n -1 )的數。例如，DEC( 3 )被替換為 DEC_3，繼續替換為 2。
于是，我們新的FAC系列宏變為：
#define FAC_1( n ) 1
#define FAC_2( n ) n * FAC_##DEC( n )( n - 1 )
#define FAC_3( n ) n * FAC_##DEC( n )( n - 1 )
不好意思，這樣依然是不正確的！預處理器直接把FAC_和DEC( n )連接成符號了，而不是單個地先處理他們，最后再
合并他們。
OK，先解決這個問題：先處理FAC_和DEC( n )，再合并他們，而不是先合并他們。要解決這個問題，可以通過第三個宏
來實現：
#define CHR( x, y ) x##y
作為連接兩個符號為一個符號的宏，這個宏顯然是不正確的，因為宏展開還有個規則：如果宏體對宏參數使用了#或##，
那么宏參數不會被展開，也就是說：如果CHR( FAC_, DEC( 3 ) 那么得到的只會是 FAC_DEC( 3 )。通常情況下我們是
再寫個宏：
#define CHR( x, y ) CHR1( x, y )
#define CHR1( x, y ) x##y
從而可以保證在正式連接x和y前，x和y都被完全展開。
這個時候，我們的FAC系列宏變為：
#define FAC_1( n ) 1
#define FAC_2( n ) n * CHR( FAC_, DEC( n ) )( n - 1 )
#define FAC_3( n ) n * CHR( FAC_, DEC( n ) )( n - 1 )
結果呢？結果還是有問題。= =
我們假設CHR( FAC_, DEC( n ) )已經真的按我們預想展開為 FAC_2了，那么FAC_3( 3 )會被展開為什么呢？
被展開為 3 * FAC_2( 3 - 1 )。這是錯誤的，傳給 FAC_2 的參數是 3 - 1就意味著錯誤。我們又臆想預處理器會
幫我們計算 3 - 1的結果了。我們必須保證傳給 FAC_2的參數是個數字2。解決這個問題的辦法就是通過DEC(n)宏。
于是，FAC系列宏變為：
#define FAC_1( n ) 1
#define FAC_2( n ) n * CHR( FAC_, DEC( n ) )( DEC( n ) )
#define FAC_3( n ) n * CHR( FAC_, DEC( n ) )( DEC( n ) )
這個時候，FAC_3( 3 )將會被替換為：3*2*1。這就是我們要的結果。
In practice
以上只是向你展示一個過程，用宏去計算階乘，就像用模板去計算階乘（模板元編程）一樣，只是一個用于展示的東西，
沒有什么實際價值。接下來我們開始有實際的工作，完成之前的預想：
template <typename R, typename P1, typename P2, typename P3>
class functor<R (P1, P2, P3)>
直接:
template <typename R, PARAM( 3 )>
class functor<R (ARG( 3 ))>
先考慮PARAM宏，該宏的任務就是生成類似于：typename P1, typename P2, typename P3這樣的符號。我們假象它每一次
遞歸都生成 typename Pn, 的字符串，那么當他遞歸完時，可能就生成typename P1, typename P2, typename P3, 結果
多了個逗號，也許最后一次結果不該有逗號。
ARG宏和PARAM宏本質上相同，只是重復的符號不是typename Pn，而是Pn。
最直接想到的是：
#define PARAM_1( n ) typename P##n
#define PARAM_2( n ) CHR( PARAM_, DEC( n ) )( DEC( n ) )##,typename P##n
#define PARAM_3( n ) CHR( PARAM_, DEC( n ) )( DEC( n ) )##,typename P##n
結果我們得到了個錯誤的展開結果：
typename PDEC( 2 ),typename PDEC( 3 ),typename P3
這個問題出在：PARAM_3( 3 )當替換為 PARAM_2( DEC( n ) )時，因為PARAM_2(n)宏對于宏參數n使用了##，也就是那個
typename P##n，所以這里不會把 DEC( n )展開，而是直接接到P后面。所以就成了typename PDEC( 3 )。
為了消除這個問題，我們改進PARAM為：
#define TYPE( n ) ,typename P##n
#define PARAM_1( n ) CHR( typename P, n )
#define PARAM_2( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define PARAM_3( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
之所以加入TYPE(n)，是因為 ,typename P##n 這個宏本身存在逗號，將其直接用于宏體會出現問題。
于是，我們得到了正確的結果。
其實，PARAM系列宏宏體基本是一樣的，除了終止條件那個宏，為什么我們要寫這么多呢？理由在于宏體不能自己調用
自己，所以才有了PARAM_3, PARAM_2。
我們可以將上面的一系列宏抽象化，使其具有可復用性：
#define PARAM( n ) ,typename P##n
#define PARAM_END typename P
#define ARG( n ) ,P##n
#define ARG_END P
#define PARAM_1( n ) CHR( typename P, n )
#define PARAM_2( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define PARAM_3( n ) CHR( CHR( PARAM_, DEC( n ) )( DEC( n ) ), TYPE( n ) )
#define REPEAT_1( n, f, e ) CHR( e, n )
#define REPEAT_2( n, f, e ) CHR( CHR( REPEAT_, DEC( n ) )( DEC( n ), f, e ), f( n ) )
#define REPEAT_3( n, f, e ) CHR( CHR( REPEAT_, DEC( n ) )( DEC( n ), f, e ), f( n ) )
#define DEF_PARAM( n ) REPEAT_##n( n, PARAM, PARAM_END )
#define DEF_ARG( n ) REPEAT_##n( n, ARG, ARG_END )
我們創建了可重用的REPEAT系列宏，用于創建諸如typename P1, typename P2, typename P3或者P1,P2,P3之類的符號，
通過更上層的DEF_PARAM(n)和DEF_ARG(n)，就可以直接創建出我們上面所需要的符號串，例如：
DEF_PARAM( 3 ) 就得到 typename P1, typename P2, typename P3
DEF_ARG( 3 ) 就得到 P1, P2, P3
More in practice
下載中提供了我使用這個宏遞歸技術寫的lua_binder(如果你看過<實現自己的LUA綁定器-一個模板編程挑戰 >)，你
可以與上一個版本做一下比較，代碼少了很多。
同樣，我希望你也能獲取這種宏遞歸的思想。
相關下載
使用宏遞歸的lua_binder
摘要: 實現LUA綁定器 author : Kevin Lynx Preface 當LUA腳本調用我們注冊的C函數時，我們需要逐個地從LUA棧里取出調用參數，當函數返回時，又需要一個一個地往LUA棧壓入返回值，并且我們注冊的函數只能是int()(lua_State*)類型。這很不方便，對于上層程序員來說更不方便。 因此我們要做的...
閱讀全文