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
