小试 boost spirit

2022-10-29 07:46:44

解释文本文件是日常编程中太平常的一件事情了，一般来说，土鳖点的做法可以直接手写 parser 用循环暴力地去 map 文本上的关键字从而提取相关信息，想省力一点则可以使用 tokenizer 或正则表达式之类的工具，无论怎样，总的来说，手写 parser 去解释文本基本是件苦力活：写出的代码比较难重用，可读性可维护性也差，要是设计的差点，哪天文本格式一变，以前辛苦写的代码马上推倒重来，未尝是新鲜事。

解救的方法是通过工具来生成 parser，这方面有好多比较出名的工具，比如 Lex, Yacc, ANTLR 等，它们的功能大同小异，都基于文法(用 EBNF 进行描述) 转换成相应的 parser. 但这些工具使用起来通常比较麻烦：首先是生成的代码可读性不大好，再者如果要把这些代码加入到工程中，通常都需要对生成的代码加以修改，因此文法一旦发生变动，parser 需要再次生成，这些修改基本又都得再次重来，因此维护困难。

那么除了上述这些工具还有没有别的解决方案呢？也许你可以尝试一下 boost spirit。

以下内容基于 boost 1.37.0，spirit 的版本是 1806，比较老的一个版本，与最新版本相比，大概原理虽是差不多，但库的目录结构已有很大不同，知悉。

Spirit 是什么

简单来说，Spirit 是一个 parser generator，功能与 Yacc，ANTLR 类似，且也是基于 EBNF 来描述文法，再基于文法生成 parser，但与前面这些工具相比，它最大的不同点在于它使用了 C++ 代码来对文法进行描述，通过非常残暴的模板编程技巧，在编译阶段就生成了相应的 parser。从使用者的角度来看，文法是用代码进行描述的，因此它天生就能直接加入到你当前的工程中与现成代码揉合在一起。

当然，Spirit 的文法在形式上 EBNF 还是有一点点的出入，比如说，用 ">>" 来连接不同表达式，表示重复的符号放在了表达式的前面等，这些都是受 c++ 语法的限制所做出的折衷，文法的语义其实未变。

初体验

一个经典的整数四则运算如用 EBNF 来描述的话，可以写成如下的形式：

    group       ::= '(' expression ')'

    factor      ::= integer | group

    term        ::= factor (('*' factor) | ('/' factor))*

    expression  ::= term (('+' term) | ('-' term))*

其中 group, factor, term, expression 分别称为一个 rule，用于表示怎么去匹配一条相应的文本，上述 EBNF 文法在 Spirit 中可以写成如下形式：

    group       = '(' >> expression >> ')';

    factor      = integer | group;

    term        = factor >> *(('*' >> factor) | ('/' >> factor));

    expression  = term >> *(('+' >> term) | ('-' >> term));

看起来语法好像差不多，只是运算符有些不同，需要指明的是，在 Spirit 中一个 rule 就是一个 parser 对象，一个 parser 对象包含了相应的语法规则使得该 parser 只能 parse 符合这些规则的文本，比如说，我们现在想 parse 出一组用逗号隔开的整数(CSV)，则我们可以定义如下一个 rule：

boost::spirit::rule<> csv_int = int_p >> *(',' >> int_p);

上述代码中，int_p 是 Spirit 内建的一个 rule 或者说 parser，该 parser 专门用于 parse 一个整型(除了 int_p，Spirit 还内建了一系列用于 parse 其它基本数据类型的 parser, 具体列表参考这里)。parser 与 parser 通过 ">>" 运算符连接在一起后就组成了一个新的 parser，那么怎么来使用 csv_int 这个新生成的 parser 呢？ Spirit 内建定义了一个函数，原型大概如下：

boost::spirit::parse_info<> parse(const char* text, parser, separator);

通过调用 parse() 函数传入需要 parse 的文本与相应的 parser 就能对该文本进行相应的解释，返回结果会指明 parse 的过程是否成功了，及如果出错，在哪个位置出错了。

Semantic actions

前面定义的 csv_int 这个 parser 虽然定义了文法，但它基本没做什么事情，只能用来检查一下某段文本是不是一组逗号隔开的整型，功能显然太弱了，因为通常来说，我们是需要从文本中提取出数据来的，因此 parse 的过程需要支持某些动作，我们需要 parser 在 parse 到某些内容时，能够执行用户指定的行为动作，在 Spirit 中，这个些动作就叫作 semantic action.

Semantic action 是属于一个 parser 的，它的意义在于指明当该 parser 执行成功了之后，要执行哪些操作，而这些操作是由用户指定的。我们可以通过如下方式将一个 semantic action 与一个 parser 联系起来：

parser[func];

至于 func 的原型，当然是有要求的，而且这个要看具体的 parser， 比如说 int_p 这样的 parser，它就只能接受 void func(const int val); 这样的函数，很简洁的语法！现在我们来在将前面用于解释一组整型的代码中加入一个新功能，在 parse 完每一个整型后，我们将得到的数据保存下来。

#include <vector>

#include <boost/spirit.hpp>

#include <boost/spirit/include/qi.hpp>

#include <boost/spirit/include/phoenix_core.hpp>

#include <boost/spirit/include/phoenix_object.hpp>

std::vector<int> g_output;

int on_parse_int(const int val)

{

   g_output.push_back(val);

}

int main()

{

   boost::spirit::rule<> int_csv_rule = int_p[on_parse_int] >> *(',' >> int_p[on_parse_int]);

   boost::spirit::parse("2,3,4", int_csv_rule);

   return 0;

}

semantic action 的实现依赖于 boost 里另一个名声显赫的函数式模板库：phoenix, 上面的例子只是一个简单示范，未及冰山一角，spirit 其实还支持用 lambda 来写回调函数，以及用闭包来在不同的 rule 之间传递用户定义的上下文信息等，功能很强大，有兴趣的读者可以参考下这里相对完整点的一个例子，它实现了一个简单的四则运算及基本的函数调用。

生成的 Parser 的类型

Parser 是整个 Spirit 库的核心功能所在，那么 Spirit 生成的 parser 是怎么进行工作呢？ 结论是，spirit 所生成的 parser 就是所谓的 LL recursive decent parser，因此 parse 的时候是从左往右扫描输入，而对 parser 中的文法，采取先左后右的顺序进行匹配的，因此左递归之类的问题需要使用者自己消除，对如下一个例子：

rule<> rule1 = (int_p >> ',' >> int_p) | real_p;

rule1 在 parse 文本时，会优先匹配 (int_p >> ',' >> int_p)，如若失败，则再去匹配 real_p。

优缺点

因为使用该库的时间还不是很长，初步上手的感觉，优点上个人觉得有如下几点：

  1. 使用非常方便，尤其当要 parse 一些不太复杂的文本时，写代码的效率很高。
  2. 生成的 parser 执行效率也很好。

结论就是：很好很强大，但与此同时，缺点也明显：

  1. 错误提示不够友好。当一段文本格式上有错误时，spirit 直接从出错的地方返回但却不提供相应的错误信息，上层的代码只知道在哪里出了错，却不知道是因什么出了错，因此很难生成一个有意义的错误提示。
  2. 该库的实现大量使用了模板及符号重载，代码写起来很酷炫，但是一旦出错，错误提示基本没有包含太多有意义的信息，因此调试起来很痛苦，尤其是在使用不够熟练的情况下，因此个人建议在使用 Spirit 时，最好把任务进行适当分解，每完成一个小的任务就先测试确认它功能正常稳定再进行下一步，不要一下子写一大堆代码，先不说功能如不正常难以调试，甚至编译错误时，找到出错的地方都困难。
  3. 该库在实现上严重依赖模板元编程，使用了诸多如 expression template 这样的 coding idiom，parser 的生成实际上是在编译阶段完成，因此当你写的 rule 很复杂时，编译时间会很长，真的很长。

【参考】

http://boost-spirit.com/distrib/spirit_1_8_3/libs/spirit/doc/quick_start.html

http://en.highscore.de/cpp/boost/

上一篇：JavaScript 局部刷新


下一篇：KendoUI系列：DropDownList