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