Re: [教學] yard - 一個高效能的 parser generator

看板C_and_CPP (C/C++)作者yoco315 (眠月)時間16年前 (2009/02/13 22:08)推噓3(3推 0噓 2→)

留言5則, 4人參與討論串2/3 (看更多)

因為有人問道，所以今天講一下 yard 背後的精神跟設計手法… 讓我們回想一下 recursive decent parser 最原始的模樣，假設我今天想要 parse 的文法是 (ab)*xyz[cd] 那我會怎麼寫我的 parser？大概是這樣 // ab bool ab() { char* q = p ; if ( *p++ == 'a' && *p++ == 'b' ) return true ; // 成功 p = q ; return false ; // 失敗，roll back } // xyz bool xyz() { char* q = p ; if ( *p++ == 'x' && *p++ == 'y' && *p++== 'z' ) return true ; p = q ; return false ; } // (ab)*xyz[cd] bool abab_xyz_cd() { char* q = p ; if ( abab() && xyz() && cd() ) return true ; p = q ; return false ; } 可以看得出來，其實這些函數的架構都非常相似，首先是保留 roll back 時需要的目前指標的位置，然後是一個一個比對吃進來的序列，最後如果失敗就進行 roll back，除了裡面用來比對所呼叫的函數不一樣，整個架構都是一樣的。既然這些函數架構都一樣，除了裡面呼叫的函數不一樣，那讓我們想到：C++ 的 template 剛剛好可以派上用場！我們可以寫一個 function template。 template < class F0, class F1, class F2 > bool Seq () { char* q = p ; if ( F0() && F1() && F2() ) return true ; 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 是怎麼做的 :) 另外一個問題比較麻煩，讓我們回頭看一下剛剛新寫好的那個規則… //(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 ; 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 ; p.setPos(q) ; return false ; } } 終於大功告成啦… 這個是用來 match 序列的 class template，只要明白設計理念以後，其實勝下的像是 Or, Star, Plus 或是 Repeat 都很簡單了，阿上次不是說要講 AST？嗯……下次吧，我是個沒信用的人 XD 最近先翻 C++0x rvalue reference 的文章，我覺得這比較有趣 XD -- To iterate is human, to recurse is divine. 遞迴只應天上有, 凡人該當用迴圈. 　 L. Peter Deutsch -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.160.110.239 ※ 編輯: yoco315 來自: 118.160.110.239 (02/13 22:09)