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

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