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

看板C_and_CPP (C/C++)作者adxis (Acquire higher)時間14年前 (2010/10/24 20:12)推噓3(3推 0噓 3→)

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

: 阿上次不是說要講 AST？ : 嗯……下次吧，我是個沒信用的人 XD 從這個版上得到許多，趁著最近重溫 yard 幫 y 大延續一下 AST 的教學，不過文筆跟深度相對不足，請多多包涵。 ==================================正文分隔線================================= 語法樹 (Syntax Tree) 相信有編譯器概念的人都懂，這裡簡單舉例一下：如果用 yard 定義一個右遞迴(right recurision) 數字陣列，會長成這樣 struct DecNumberArray // DecNumber 請參考 yard_c_grammar.hpp : Seq<DecNumber, Opt<Seq<Char<','>, DecNumberArray> > > {}; 我們可以預期 "1234, 12, 56" 會長出下面這樣一個語法樹 DecNumberArray / \ DecNumber DecNumberArray | / \ 1234 DecNumber DecNumberArray | | 12 DecNumber | 56 接下來就介紹 yard 提供了甚麼工具幫我們建立這樣一個語法樹 1. TreeBuldingParser (yard/include/yard_parser.h)，簡稱 TBP 注意：yard的原始碼有些錯誤，最後面我會寫一些修正的方式 TBP 這個樣板類別接受兩個樣版參數，通常我們用 TBP<char, char const*> 可以應付 single byte character 的語系，附帶一提，第二個樣版參數有預設值後面的文章就直接省略不寫了。 TBP<char> 內含一個 AST<char> mtree，就是我們要討論的語法樹，TBP 提供了以下四個方法去存取 mtree 1.1 Node* GetAstRoot() { return mTree.GetRoot(); } 1.2 template<typename Rule_T> void CreateNode() { mTree.CreateNode<Rule_T>(*this); } 1.3 void CompleteNode() { mTree.CompleteNode(*this); } 1.4 void AbandonNode() { mTree.AbandonNode(*this); } 2~3 一看就是要在 parsering 過程中拿來建立語法樹用的，但是你在 TBP 的 Parse() 實作中只會看到 template<typename StartRule_T> bool Parse() { try { return StartRule_T::Match(*this); } catch(...) { return false; } } 因為 yard 把呼叫這三個方法的責任交給了 StartRule_T 這個樣版參數，而 yard 也提供了會呼叫 Create, Abandon 等方法的預設實作 Store，請往下看。 2. Store (yard/include/yard_base_grammar.hpp) Store 的 Match 方法如下 template<typename ParserState_T> static bool Match(ParserState_T& p) { p.template CreateNode<Rule_T>(); // 建立 TreeNode bool b = false; try { b = Rule_T::template Match(p); // Match rule } catch(...){ p.AbandonNode(); // Match 失敗，刪掉TreeNode throw; } if (b) { p.CompleteNode(); // Match 成功，把Node 標為 return true; // Completed } else { p.AbandonNode(); return false; } } 所以要建立文章最前面的那個語法樹例子，我們得修改一下 struct DecNumberArray struct DecNumberArray : Seq< Store<DecNumber>, Opt< Seq<Char<','>, Store<DecNumberArray> > > > {}; 接下來就可以這樣使用 TBP char const *s("1234,12,56"); TBP<char> parser(s, s+strlen(s)); TBP<char>::Node* root(0); // EndOfInput 請參考 yard_text_grammar bool ok = parser.Parse<Seq<Store<DecNumberArray>, EndOfInput> > >(); if(ok){ root = parser.GetAsRoot(); your_traverse_function(root); } 3. 抽象語法樹 (Abstract Syntax Tree) (yard/include/yard_tree.h) 之所以為抽象是因為每一個 Rule_T 都是不同的型別，可是 TBP 卻會把這些型別都塞進同一個容器(樹)，這裡就得倚賴 C++ 的動態多型來達成，Ast 這個 class 裡面定義了 AbstractNode 跟 template<typename Rule_T> TypedNode ，透過 TypedNode 繼承 AbstractNode 並且讓 TypedNode 內含(has)不同型別的 Rule_T，Ast 即可以儲存 AbstractNode 的指標來達到儲存不同 Rule_T的目的。這同時表示每次需要具體型別時都至少有一次 dynamic_cast 的支出。如果希望避免的話，需要使用者自己去實作出具虛擬函式的 Node 類別。另外，AbstractNode 裡面只存了符合 Rule_T 的字串起終點，看應用其實可以直接做 text to object 的轉換，比如說 "1234" 直接轉成 integer 1234 。下面示範一個簡單的後序循訪函式 void traverse(TreeBuildingParser<char>::Node *entry) { typedef TreeBuildingParser<char>::Node* Arg; // 對每個子節點作 traverse // 我不喜歡寫 function pointer ... // ForEach 請參考 Ast 的實作 entry->ForEach< std::pointer_to_unary_function<Arg, void> >( std::ptr_fun(traverse) ); // 檢查 Token 是否指向一個有效位址 if(entry->GetFirstToken()){ if(entry->TypeMatches<DecNumberArray>()) printf("DecNumberArray Matched, "); else if(entry->TypeMatches<DecNumber>()) printf("DecNumber Matched, "); std::string tmp( entry->GetFirstToken(), // Token begin entry->GetLastToken() // Token end ); printf("token: %s\n", tmp.c_str()); } } 4. yard 原始碼修正 4.1 TreeBuildingParser 的建構式初始列呼叫了 mtree(first) 改成 mtree() 即可，Ast 並沒有實作 mtree(Token_Iter) 4.2 Ast 裡面增加 typedef AbstractNode Node; 這一行，TreeBuildingParser 需要用到這個 typename 結語：其實如何有效率循訪 AST 這部分我還沒仔細想過，有意見的話懇請指教。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.47.70.194