2009年2月24日 星期二

yard 的設計理念跟手法

因為有人問到,所以提一下 yard 背後的精神跟設計手法。

從最初開始

讓我們回想一下 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

1 則留言: