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

yard parser framework

Yet Another Recursive Descent (YARD) parsing framework for C++

網站 http://code.google.com/p/yardparser/

網站上面沒有什麼教學,只有下載,然後抓下來的東西裡面有 demo 程式,因為本身非常簡單,所以大致上是看了就懂,但是我還是想寫一篇教學,這樣大家可以減少一點摸索的時間。

這篇文章會先介紹 yard 跟其他 parsing gramework 的比較,然後我會從非常簡單的範例開始出發,一直到最後給一個很難的範例,讓你們熟悉如何使用 yard 建立自己的 grammar。在學會了如何使用 yard 建立自己的 grammar 之後,我會示範如何使用 yard 來自動建立 abstract syntax tree (AST),並且把 yard 使用在自己的程式裡面。

跟 boost::spirit 的比較

yard 跟 boost::spirit 一樣的地方是他們的 grammar 都不限於 LR(1),可以寫 EBNF 的 parsing rule,語法好寫好讀。boost::spirit 強勢的地方在於支援 dynamic parsing,也就是 parsing rule 可以在 runtime 動態改變。

boost::spirit 最大的弱點在於編譯效能,boost::spirit 很難用來開發大型的 parser,當你的 parsing rule 到了 30~40 以後,編譯時間就快要一個小時,一個 78 parsing rule 的 grammar,編譯要兩個小時

執行效能也是 boost::spirit 的一個問題,每個 parsing rule 被引用的時候,都涉及一次 virtual function 的呼叫。相較於此,yard 的編譯速度非常快速!編譯完整的 c 語言語法 + XML 語法 + scheme 語法,全部加起來不用一秒。

跟 yacc 的比較

沒什麼好比的 -________-|| yacc 再見再見

簡單教學範例

好,在使用 yard 的時候,我們都要 include ,如果你要 parse 一般簡單的文字的話,順便 include ,然後為了方便,就 using namespace 吧!所以你開發的每個 grammar 原始碼架構大概是這樣的。
// == my_grammar.hpp ==
#include <yard.hpp>
#include <yard_text_grammar.hpp>

namespace my_grammar {
using namespace yard ;
using namespace yard::text_grammar ;
/*...[[[ 這邊就是我們要寫自己的 grammar 的地方 ]]]...
}

那這篇文章之後的範例就不寫這部份了,只著重在 grammar 的地方。

yard 的設計是建立在 C++ 強大的 template 機制上面,每一個 parsing rule 就是一個 struct,藉由組合不同的 struct 來完成複雜的 grammar。

先來一個最簡單的例子
// AB
struct AB
: CharSeq < 'A', 'B' >
{} ;

這樣就完成一個可以用來 parse "AB" 這個字串的 rule 了,CharSeq 是 yard 裡面已經定義好的 struct,會從來源讀入一個一個字元來進行 match 的動作。實做細節其實很不難,但是很有創意!有興趣的去看翻一下原始碼就知道。

再來一個稍微難一點的
// (AB)*
struct ABAB
: Star < AB > // 這邊 AB 當然是接續前面的範例
{}

不用說,Star 也是 yard 裡面已經定義好的一個 struct,可以 match 零到無限多個你放在 < > 裡面當作 template 參數的規則。

馬上應用剛剛學到的兩個…
// ABC(AB)*
struct ABC_ABAB
: Seq <
CharSeq < 'A', 'B', 'C' >,
ABAB
>
{} ;

Seq 也是 yard 已經有的 struct,可以用來 match 一串序列的 rule,他跟 CharSeq 一樣都可以接不同數量的 template 參數,但是也不是沒有上限,他內部設計是 10 還是 16 我忘記了,你可以自己改,但是最後的限制會取決於你的編譯器所支援的上限。

有的時候你會想 match 多種可能的其中一種
// (AB|XYZ)
struct AB_or_XYZ
: Or <
AB,
CharSeq < 'X', 'Y', 'Z' >,
>
{} ;

當你用 Or 的時候,你就可以只 match 其中一種 rule,注意一下,當某個順序在前面的 rule match 成功的時候,match 就結束,這跟一般我們 C/C++ 預設的 operator || 行為一樣,因為 Or 底層就是這樣實做的。
所以注意下面這個例子
Or<CharSeq<'A','B'>, CharSeq<'A'>> //   match   "A"
Or<CharSeq<'A','B'>, CharSeq<'A'>> // match "AB"

Or<CharSeq<'A'>, CharSeq<'A','B'>> // match "A"
Or<CharSeq<'A'>, CharSeq<'A','B'>> // not match "AB"

因為當 rule 看到第一個 'A' 的時候,rule 會把這個 'A' 消耗掉,剩下一個 'B',但是你的 grammar 已經結束了,所以 parsing 失敗。

最後一個整合的範例

上面的例子為了示範,都非常簡單,但是你其實可以用 yard 直接建立非常複雜的 rule,例如:
// (+|-)?[0-9]\+(\.[0-9]\*)?    就是一般的浮點數啦
struct number
: Seq <
// (+\-)?
Opt<Or<Char<'+'>,Char<'-'>>>,
// [0-9]+
Plus<Digit>,
// (.[0-9]*)?
Opt<Seq<Char<'.'>,Star<Digit>>>
>
{} ;

最後總結一下:

yard 讓你可以用高階的語法寫成 parsing rule,這點跟 boost::spirit 一樣,平心而論,template 寫起來比起 boost::spirit 的 operator overloading 是稍微麻煩了一點,但是 boost::spirit 的編譯時間實在讓人不敢恭維。

yard 本質上是一個 recursive descent parser generator,執行速度非常快,他跟你用手寫出來的 recursive descent parser 一樣好,如果你要處理的東西不需要 dynamic parsing,那 yard 會是你的第一選擇。

yard 跟 boost::spirit 一樣,支援自動的 abstract syntax tree (AST) 生成,我很想繼續寫下去,但是剛剛右下角跟我說活屍日記完檔了,所以 AST 跟怎麼在自己的程式當中使用 yard 就下次再說,先這樣囉掰。