Facilitating the spread of knowledge and innovation in professional software development

Contribute

### Topics

InfoQ Homepage News Treetop - PEG parser generator for Ruby

# Treetop - PEG parser generator for Ruby

This item in japanese

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
def 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

Style

## Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

• ##### Documentation

by Mickael Faivre-Macon,

• ##### Documentation

Your message is awaiting moderation. Thank you for participating in the discussion.

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 ?

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Is your profile up-to-date? Please take a moment to review and update.

Note: If updating/changing your email, a validation request will be sent

Company name:
Company role:
Company size:
Country/Zone:
State/Province/Region:
You will be sent an email to validate the new email address. This pop-up will close itself in a few moments.