BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

Treetop——基于Ruby的PEG解析器生成器

| 作者 Werner Schuster 关注 6 他的粉丝 ,译者 李明(nasi) 关注 0 他的粉丝 发布于 2008年1月23日. 估计阅读时间: 3 分钟 | Google、Facebook、Pinterest、阿里、腾讯 等顶尖技术团队的上百个可供参考的架构实例!
Ruby已经有了一个叫做RACC的解析器生成器,是一个YACC的移植版本(被用来编写ruby_parser,第一个用Ruby写成的Ruby解析器)。

当谈到解析器生成器的时候,解析表达式语法(PEG)最近因为一篇Bryan Ford介绍的一种叫做“Packrat解析”优化的论文而 变得很流行。Packrat解析解决了诸如指数级解析时间的问题。这是由于解析器使用回溯来解析代码,例如,它们会尝试诸多结果的组合直到找到正确的那一 个。Packrat解析的解决方法是使用记忆化,例如将解析的中间结果保存下来,而不是一遍一遍的重新计算。这决定了Packrat解析的时间复杂度是线 性的,但是缺点是需要很大的内存,通常是源代码大小的几倍。注意,其他的解析器生成器也是采用类似的方法,比如ANTLR

基于这个前提Treetop网站上如此解释PEG的优点:
解析表达式语法(PEGs)编写简单、易于维护。它们是简单但功能强大的泛化正则表达式,比起传统的LALR或者LR-1语法的解析器生成器来说更易于使用。没有必要再进行符号化解析,或者用于有限度上下文敏感的前向断言。
Treetop会自动生成解析树,而且还允许用户添加方法来定制所生成的节点:
grammar Arithmetic
 rule additive
 multitive '+' additive {
 def value
 multitive.value + additive.value
 end
  }
 /
 multitive
end
# other rules below ...
end
这段代码的意思是通过additive节点生成的节点有一个叫做value的方法。另外,可以为每条规则指定一个要生成的节点类。(注意:这个斜杠是选择操作符,意思是,additive规则要么是两个操作数和之间的加号,要么是multitive规则的结果)。

在开始使用Treetop之前,你需要先安装它。可以从Rubyforge下载Treetop的源代码,或者通过gem安装,命令为:
gem install treetop 
想要开始使用它的话,可以去查看Treetop的文档或者看看上文中的示例。Treetop需要一个简单的算术表达式解析器、一个非常基本的语言解析器以及运行时间。

Treetop可以通过tt工具将语法定义文件转换成Ruby代码:
tt foo.treetop  
另一种选择是通过Ruby代码来进行解析器生成
Treetop.load "arithmetic"
parser = ArithmeticParser.new
parser.parse('1+1')
Treeop创始人的现场演示,参见Nathan Sobo在RubyConf 2007上关于Treetop的报告

查看英文原文:Treetop - PEG parser generator for Ruby

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT