随笔 - 31  文章 - 128  trackbacks - 0
<2005年12月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(5)

随笔分类(38)

随笔档案(31)

收藏夹(4)

College

High School

最新随笔

搜索

  •  

积分与排名

  • 积分 - 47440
  • 排名 - 395

最新评论

  • 1. re: [yc]详解link
  • 面试的时候面试官就问过我什么是编译和链接,我说编译就是把代码文件生成目标文件,链接就是把目标文件生成可执行文件,他说不对,又问我什么是动态链接,还问我预编译都做什么处理。。。都在这里找到了答案!!!!
  • --王至乾
  • 2. re: [yc]详解link
  • @刘伟
    我是说博主,不是叫你啊
  • --溪流
  • 3. re: [yc]详解link
  • 谁是石老师,我不是哈@溪流
  • --刘伟
  • 4. re: [yc]详解link
  • 石老师?我是溪流~
  • --溪流
  • 5. re: [yc]详解link
  • 期待楼主下文啊,多谢楼主了
  • --刘伟

阅读排行榜

评论排行榜

    最近为了解析SQL语法,怀着试一试的心态去翻了翻boost的spirit库,因为该库的文档的简介里写着LL parser framework  represents parsers directly as EBNF grammars in inlined C++。看着framework这个词自然觉得这个库很牛B,试用了一下果然如此。
    所谓EBNF即扩展巴克斯范式,是一种描述Context-Free Language的文法。在目前常见的非自然语言中,大部分都可以用EBNF表示。例如:
      group  ::='('exp
')'
      factor ::=integer|
group
      term   ::=factor(('*'factor)|('/'factor
))*
      exp    ::=term(('+'term)|('-'term
))*
这是一个整数表达式的EBNF。该段描述用spirit在C++中的实现则是:
   

   rule<> group, factor, term, exp;
   group  
= '(' >> exp >> ')';
   factor 
= int_p | group;
   term   
= factor >> *(('*' >> factor) | ('/' >> factor));
   exp    
= term >> *(('+' >> term) | ('-' >> term));

这里使用=代替::=, 用>>代替空格连接。并且由于C++语法所限,EBNF中后置的*在spirit中改为前置。
等式左边的单词被称为一个rule,等式右边为rule的定义。我们可以看出一个group是一个exp加上一对括号,一个factor是一个整数或者一个group,一个term是一个或多个factor用*/连接,一个exp是一个或多个term用+-连接。处于最顶端的exp可以据此识别出以下表达式
   

   12345
   
-12345
   
+12345
   
1 + 2
   
1 * 2
   
1/2 + 3/4
   
1 + 2 + 3 + 4
   
1 * 2 * 3 * 4
   (
1 + 2* (3 + 4)
   (
-1 + 2* (3 + -4)
   
1 + ((6 * 200- 20/ 6
   (
1 + (2 + (3 + (4 + 5))))

    得到一个rule之后,我们就可以用 parse函数对一个串进行识别了。例如
         

         parse( " (1 + (2 + (3 + (4 + 5)))) " , exp);


该函数返回一个结构parse_info,可以通过访问其中的full成员来判断是否成功识别,也可以访问stop成员来获知失败的位置。这里要特别提一点,关于各个符号之间的空格,spirit的文档的正文说的是给parse再传一个参数space_p,通知parse跳过所有的空格,然而在FAQ中又提到,如果使用以上方法定义rule,第三个参数传space_p会失败。原因是使用rule默认定义的规则被称为character level parsing,即字符级别解析,而parse的第3个参数仅适用于phrase level parsing,即语法级别解析。要使用第3个参数可以有几种方法。
      1。在parse的第二个参数直接传入一个EBNF表达式,不创建rule对象。
         

            parse( " hello world " * anychar_p, space_p);  


      2。以rule<phrase_scanner_t>创建rule。
         

            rule < phrase_scanner_t >  exp; 

注意虽然可以用这两个办法屏蔽空格,但是这样可能完全改变EBNF文法的语义,尤其是在语言本身需要识别空格的时候。对于这种情况,可以不使用第三个参数,并在需要出现空格的地方加上space_p,或者+space_p及*space_p,其中+和*分别表示后面的符号连续出现一次以上和0次以上。例如一个以空格分隔的整数列表可以写成int_p >> *(+space_p >> int_p)
   如上使用parse可以识别一个串,但并不能做更多的操作,例如将语法里的各个成分提取出来。对于这样的需求,可以通过actor实现。下面是使用actor的一个简单例子
   

   bool
   parse_numbers(
char const* str, vector<double>& v)
   
{
      
return parse(str,

   
//  Begin grammar
      (
         real_p[push_back_a(v)] 
>> *(',' >> real_p[push_back_a(v)])
      )
      ,
      
//  End grammar
      space_p).full;
   }

注意到real_p后面的[],中括号里面是一个仿函数(函数指针或者函数对象),该仿函数具有如下调用型别
   

   void operator()(IterT first, IterT last) const;
   
void operator()(NumT val) const;
   
void operator()(CharT ch) const;


一旦spase发现了匹配real_p的子串,就会调用该functor。不同的rule可能会对应不同的调用型别。
第一个型别针对一般规则,first和last为两个指向字符的迭代器(一般为char*),匹配的子串为[first, last)
第二个型别针对数字型规则,如real_p和int_p, 参数val是一个数字类型。
第三个性别针对单字符型规则,如space_p, 参数ch是一个字符类型。
real_p[push_back_a(v)]中的push_back_a是一个spirit已经定义好的functor,它会将匹配好的内容依照匹配到的时间顺序调用v的push_back函数加入到v中。

   到此spirit的常用功能就都介绍完了。要详细深入了解可以参考spirit的文档。

最后在题一个注意要点。spirit的各种EBNF连接都是指针连接,因此才能在expression被赋值前就在group的定义里面使用。所以在使用EBNF的时候一定要小心不要将局部变量的rule提供给全局或者类成员变量使用,例如:
   

   class A
   
{
      rule
<> s;
      A()
      
{
         rule
<> r = int_p | hex_p;

         s 
= r >> *(+space_p >> r); //error, r destructed after return 
      }

   }
;

如果真想使用局部作用域,可以在局部的rule前面加上static.

posted on 2005-12-18 12:02 shifan3 阅读(6587) 评论(5)  编辑 收藏 引用 所属分类: templateBoostC++

FeedBack:
# re: boost::spirit初体验 2005-12-18 20:22 Windreamer Is Not DREAMER
赞,华丽的石老师
没想到spirit竟然这么厉害??
看来我真得系统的把Boost好好看一遍,走马观花的看一圈真是暴殄天物啊

顺便来踩踩地方~~~~~~~
沙发~~~~~~~~~~~~~~~~~~  回复  更多评论
  
# re: boost::spirit初体验 2006-02-15 20:02 firestorm
我现在也在为一个oracle sql的简单解析重组而烦恼!考虑使用lex和yacc,但是时间不太允许,想找个免费的数据库的源码看看,发现都不是很好用的哪种。
郁闷~  回复  更多评论
  
# re: boost::spirit初体验 2006-09-13 19:51 manzheng

不懂,但还是re一下

~~~~~~~~~  回复  更多评论
  
# re: [yc]boost::spirit初体验 2007-12-25 17:18 aaaaaaaaaa
英文阅读太累,看到这个感觉没那么冷了~~~~~  回复  更多评论
  
# re: [yc]boost::spirit初体验 2007-12-25 17:20 aaaaaaaaaa
英文终究还是要看的,但有类似这种中文介绍做预习,感觉好多了,再顶~~~~~~  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理