從最初開始
讓我們回想一下 recursive decent parser 最原始的模樣，假設我今天想要 parse 的文法是 (ab)*xyz[cd] 那我會怎麼寫我的 parser？大概是這樣
// ab
bool ab() {
char* q = p ;
// 成功
if ( *p++ == 'a' && *p++ == 'b' )
return true ;
// 失敗，roll back
else {
p = q ;
return false ;
}
}
// xyz
bool xyz() {
char* q = p ;
if ( *p++ == 'x' && *p++ == 'y' && *p++== 'z' )
return true ;
else {
p = q ;
return false ;
}
}
// (ab)*xyz[cd]
bool abab_xyz_cd() {
char* q = p ;
if ( abab() && xyz() && cd() )
return true ;
else {
p = q ;
return false ;
}
}
可以看得出來，其實這些函數的架構都非常相似，首先是保留 roll back 時需要的目前指標的位置，然後是一個一個比對吃進來的序列，最後如果失敗就進行 roll back，除了裡面用來比對所呼叫的函數不一樣，整個架構都是一樣的。
C++ template function 帶來曙光
既然這些函數架構都一樣，除了裡面呼叫的函數不一樣，那讓我們想到：C++ 的 template 剛剛好可以派上用場！我們可以寫一個 function template。
template < class F0, class F1, class F2 >
bool Seq () {
char* q = p ;
if ( F0() && F1() && F2() ) {
return true ;
}
else {
p = q ;
return false ;
}
}
於是 abab_xyz_cd() 其實可以寫成這樣…
//(ab)*xyz[cd]
bool Seq < abab, xyz, cd > () ;
預設型別引數
不過這邊有兩個問題要解決，一個是小問題，另外一個比較麻煩，小的那個問題是：如果我只想傳入兩個參數怎麼辦？好在 C++ 的 template 支援了預設參數的功能！我們可以設計一個函數永遠傳回 true
bool True () { return true ; }然後把我們的 Seq 改寫成
template < class F0, class F1=True, class F2=True >
bool Seq () {
........
}
事情輕輕鬆鬆就解決了！注意一下第一個參數沒有預設值，因為當你說你要一個 "Seq" 的時候，想當然你不會什麼東西都不給他就叫他去比對吧。當然如果你想要實現一個不吃東西的 rule，那是另外一回事，這邊不多說，可以自己看看 yard 的 source 是怎麼做的 :)
用 class template 封裝跟命名新規則
另外一個問題比較麻煩，讓我們回頭看一下剛剛新寫好的那個規則…
//(ab)*xyz[cd]
bool Seq < abab, xyz, cd > () ;
其實這東西編譯根本不會過，他看起來像是一個特化函數，但是語法也不對。而且他沒有名字，你沒辦法重複使用這個新定義出來的函數，沒有人會希望每次用到這個規則的時候都要重複打上整串東西。
聰明的人馬上就想到：我可以用 function pointer 阿！
bool (*abab_xyz_cd)() = Seq < abab, xyz, cd > ;
媽阿，這鬼東西編譯會過嗎？會。不過事情沒這麼美好，當你想要
//(ab)*xyz[cd]gg
bool (*abab_xyz_cd_gg)() = Seq < abab_xyz_cd, gg > ;
的時候你就 gg 了。編譯器會跟你靠北一個你看不懂的錯誤訊息，不用看懂沒關係，簡單的原因就是因為這時候 abab_xyz_cd 不是一個型別也不是函數，而是一個變數，函數指標不是函數，是變數，而你不能把變數塞到 template 裡面當作參數，於是你現在有辦法定義一個函數，但是你辦法復用他，等於還是沒用。
解決的方法是把這些函數 rule 用 class 包起來。
template < class F0, class F1, class F2 >
class Seq {
bool match() {
char* q = p ;
if (F0.match()&&F1.match()&&F2.match()) {
return true ;
}
else {
p = q ;
return false ;
}
}
}
然後當你要定義新規則的時候，定一個 class，繼承那些泛型的 rule，
class abab_xyz_cd
: Seq < abab, xyz, cd >
{} ;
現在一切都解決了，這些 rule 有名字，也可以被復用！而且改寫成 class 還有另外一個好處：函數指標不能被 inline，但是 funtor 可以！雖然我們取的名字不是 operator()()，但是效果一樣，這對執行效能有很大的提昇。
最後來一點小修飾
我們很接近最後的完成品了，只剩下一點點小問題，就是我們的 p 是個全域變數，我們可以設計一個 ParseState class 把目前處理到的位置跟本文封裝起來，ParseState 的細節就不提了，我們直接看改好的 Seq 是什麼樣子……
template < class F0, class F1, class F2 >
class Seq {
bool match(ParseState& p) {
ParseState::Iter q = p.pos() ;
if (F0.match(p)&&F1.match(p)&&F2.match(p)) {
return true ;
}
else {
p.setPos(q) ;
return false ;
}
}
}
終於大功告成啦！這個是用來 match 序列的 class template，只要明白設計理念以後，其實勝下的像是 Or, Star, Plus 或是 Repeat 都很簡單了，
阿上次不是說要講 AST？嗯……下次吧，我是個沒信用的人 XD 最近先翻 C++0x rvalue reference 的文章，我覺得這比較有趣 XD
