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