Ruby 已经有了一个叫做 RACC 的解析器生成器,是一个 YACC 的移植版本(被用来编写ruby_parser,第一个用Ruby 写成的Ruby 解析器)。
当谈到解析器生成器的时候,解析表达式语法(PEG)最近因为一篇 Bryan Ford 介绍的一种叫做“Packrat 解析”优化的论文而 变得很流行。Packrat 解析解决了诸如指数级解析时间的问题。这是由于解析器使用回溯来解析代码,例如,它们会尝试诸多结果的组合直到找到正确的那一 个。Packrat 解析的解决方法是使用记忆化,例如将解析的中间结果保存下来,而不是一遍一遍的重新计算。这决定了 Packrat 解析的时间复杂度是线 性的,但是缺点是需要很大的内存,通常是源代码大小的几倍。注意,其他的解析器生成器也是采用类似的方法,比如 ANTLR 。
基于这个前提, Treetop 网站上如此解释 PEG 的优点:
解析表达式语法(PEGs)编写简单、易于维护。它们是简单但功能强大的泛化正则表达式,比起传统的 LALR 或者 LR-1 语法的解析器生成器来说更易于使用。没有必要再进行符号化解析,或者用于有限度上下文敏感的前向断言。
Treetop 会自动生成解析树,而且还允许用户添加方法来定制所生成的节点:
grammar Arithmetic<br></br> rule additive<br></br> multitive '+' additive {<br></br> def value<br></br> multitive.value + additive.value<br></br> end<br></br> }<br></br> /<br></br> multitive<br></br> end<br></br># other rules below ... <br></br>end
这段代码的意思是通过 additive 节点生成的节点有一个叫做 value 的方法。另外,可以为每条规则指定一个要生成的节点类。(注意:这个斜杠是选择操作符,意思是,additive 规则要么是两个操作数和之间的加号,要么是 multitive 规则的结果)。 在开始使用 Treetop 之前,你需要先安装它。可以从Rubyforge 下载Treetop 的源代码,或者通过gem 安装,命令为:
gem install treetop
想要开始使用它的话,可以去查看Treetop 的文档或者看看上文中的示例。Treetop 需要一个简单的算术表达式解析器、一个非常基本的语言解析器以及运行时间。
Treetop 可以通过 tt 工具将语法定义文件转换成 Ruby 代码: <span>tt foo.treetop</span>
另一种选择是通过 Ruby 代码来进行解析器生成:
Treetop.load "arithmetic"<br></br>parser = ArithmeticParser.new<br></br><span color="#000000">parser.parse('1+1') </span>
Treeop 创始人的现场演示,参见 Nathan Sobo 在 RubyConf 2007 上关于 Treetop 的报告。
查看英文原文: Treetop - PEG parser generator for Ruby
评论