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