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 就下次再說，先這樣囉掰。