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，編譯要兩個小時[1]。

執行效能也是 boost::spirit 的一個問題，
每個 parsing rule 被引用的時候，都涉及一次 virtual function 的呼叫。

相較於此，yard 的編譯速度非常快速！
編譯完整的 c 語言語法 + XML 語法 + scheme 語法，全部加起來不用一秒。



跟 yacc 的比較

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



















簡單教學範例

好，在使用 yard 的時候，我們都要 include <yard.hpp>，
如果你要 parse 一般簡單的文字的話，順便 include <yard_text_grammar.hpp>，
然後為了方便，就 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<'-'> > >, // (+\-)?
Plus < Digit >, // [0-9]+
Opt < Seq < Char<'.'>, Star < Digit > > // (.[0-9]*)?
>
{} ;










最後總結一下：

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

[1] http://nedbatchelder.com/blog/200409/spirit_parser_framework.html
記錯了，是兩個小時，本文更正，文章沒有講他用的是什麼機器。
--
To iterate is human, to recurse is divine.
遞迴只應天上有, 凡人該當用迴圈. 　 L. Peter Deutsch

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.120.198
※ 編輯: yoco315 來自: 118.160.120.163 (01/24 00:44)