InfoQ

News

Treetop - PEG parser generator for Ruby

Posted by Werner Schuster on Jan 17, 2008 07:00 PM

Community
Ruby
Topics
Programming ,
Domain Specific Languages
Tags
Language Features ,
Code Generation ,
Languages

Ruby already ships with a parser generator called RACC, a version of YACC (which is used to build ruby_parser, the first Ruby parser written in Ruby).

When it comes to parser generators, Parsing Expression Grammars (PEG) have become quite popular recently after a thesis by Bryan Ford introduced an optimization called "Packrat Parsing". Packrat parsing solves the problem of this kind of parser, i.e. exponential parse time. This is caused by the fact that the parser uses backtracking to parse the code, i.e. they try many if not all possible combinations of outcomes until they figure out the right one. The solution of Packrat parsing is to use memoization, i.e. storing intermediate parsing results, instead of calculating these results over and over. This allows for the runtime behavior to be linear, but has the downside of relatively large memory requirements, potentially multiple times the size of the input source. Note that other parser generators, such as ANTLR, use similar approaches.

With this in mind, the Treetop website explains the benefits of PEGs:

Parsing expression grammars (PEGs) are simple to write and easy to maintain. They are a simple but powerful generalization of regular expressions that are easier to work with than the LALR or LR-1 grammars of traditional parser generators. There's no need for a tokenization phase, and lookahead assertions can be used for a limited degree of context-sensitivity.

Treetop generates parse trees automatically but allows the user to customize the generated nodes by adding methods:

grammar Arithmetic
 rule additive
  multitive '+' additive {
   def value
    multitive.value + additive.value
   end
  }
 /
  multitive
 end
# other rules below ... 
end 

This means that the node generated for the additive node will have a method named value. Alternatively, it's possible to specify a node class to be generated for each rule. (Note: the slash is the choice operator, i.e. the additive is either an two operands separated by a plus character or just the result of the multitive rule).

To get started with Treetop, you need to install it first. Either get the Treetop source from the Rubyforge project, or install it as a gem:

gem install treetop 

To start using it, check the Treetop documentation or look at the provided examples. Treetop ships with a simple parser for arithmetic expressions and a very basic language parser and runtime.

Treetop can turn a grammar definition file into Ruby code with the tt utility:

tt foo.treetop  

Another option is to do the parser generation from Ruby code:

Treetop.load "arithmetic"
parser = ArithmeticParser.new
parser.parse('1+1') 


For a live demo of the Treetop by it's creator, see Nathan Sobo's RubyConf 2007 presentation of Treetop

Documentation by Mickael Faivre-Macon Posted Jan 26, 2008 3:57 PM
  1. Back to top

    Documentation

    Jan 26, 2008 3:57 PM by Mickael Faivre-Macon

    The documentation is terse, and lack many example for use in ruby code. Does someone know if the project has a mailing list of a forum ?

Educational Content

Bindings, Platforms, and Innovation

This presentation focuses on the Internet and separating myth from fact, history from the future, and the mundane from the imaginative. Bob Frankston presents a vision of what could and should be.

Orchestrating Long Running Activities with JBoss / JBPM

This article explores the use of JBoss and jBPM to implement design solutions that effectively address the issue of orchestrating long running activities.

Neo4j - The Benefits of Graph Databases

This presentation covers the use of graph databases as an optimal solution for data that is difficult to fit in static tables, rapidly evolving data or data that has a lot of optional attributes.

Realistic about Risk: Software development with Real Options

This session introduces Real Options and shows how it can help in running your project. Real Options is a decision-making process that can be used to manage risk.

Communication Flexibility Using Bindings

This article discusses the use of bindings on services and references (including the instance of non-configured bindings) as the means to implement SCA communications in a Web and SOA environment.

Writing DSLs in Groovy

After a short introduction to DSLs, Scott Davis plays with the keyboard showing how to approach the creation of a DSL by typing working snippets of Groovy code that get executed.

Scaling Agile with C/ALM (Collaborative Application Lifecycle Management)

IBM Rational and InfoQ present, Scaling Agile with C/ALM, an eBook showing organizations how to become “finely tuned software delivery machines” by enabling team integration and scaling.

Concurrent Programming with Microsoft F#

Amanda Laucher presents a real life enterprise application written in F#. She shows actual code snippets, explaining design decisions and suggesting how to use some of the F# constructs.