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

  • Werner Schuster
  • 李明(nasi)

2008 年 1 月 22 日

话题:Ruby编程语言语言 & 开发架构

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

Ruby编程语言语言 & 开发架构