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

看板C_and_CPP作者yoco315 (眠月)時間15年前 (2009/01/22 23:05)推噓13(13推 0噓 6→)

留言19則, 15人參與討論串1/3 (看更多)

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

推

revivalworld

01/22 23:09, , 1^F

01/22 23:09, 1^F

推

StubbornLin

01/22 23:30, , 2^F

01/22 23:30, 2^F

→

StubbornLin

01/22 23:30, , 3^F

01/22 23:30, 3^F