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)