Dhaka is a set of tools for generating lexers and LALR(1) parsers for context-free grammars. It is written solely in Ruby with no native extensions and no dependencies. Its primary aim is to be easy to adapt and use for common parsing tasks. For example, if you need to parse and evaluate arithmetic or some other expression language with nested constructs in your Ruby application you might find it useful.
Dhaka allows encoding lexical and grammar rules completely in Ruby. From these rules, it can generate state-machines for lexing and parsing a given language. The state-machines are then ‘compiled’ to Ruby source-code which when executed reconstructs them in memory without having to calculate all the states and actions again.
For those who are comfortable with context-free grammars and want to take advantage of the full scope of Dhaka’s lexer/parser generator, the test suite includes an example interpreter for a small language which features arithmetic, boolean expressions, functions, conditionals, loops and exceptions.
Dhaka is one amongst several Ruby parser libraries. Racc is another – it generates the same type of parser and the Racc runtime is part of the Ruby distribution.
Dhaka is available as a gem, so you can simply:
sudo gem install dhaka
These examples are presented as solutions for challenges posed in the wonderful Ruby Quiz:
This is a brief overview of how to go about specifying a more complex language:
Marcel Molina Jr – for suggestions and patch to make the code cleaner
Bruce Williams – for suggestions and keyword-search.
Rick Olson – for a patch to add default actions to tokenizer states.
Florian Gross – for various cool ideas.
Peter Cooper – for blogging about Dhaka.
Mike Clark – for letting me talk about it at RailsEdge.
Emmanuel Oga – for pushing me to make the library faster.
There are some pretty comprehensive examples in the tests that come with the gem. If you’re new to context-free grammars or parsing, start with the examples for evaluating arithmetic expressions. If you’re no stranger to Yacc, then the tests for the mini-programming language (prefixed with ‘chittagong’) are likely to be of more interest, since they touch upon the deeper functionality. If you’re stuck, post in the forum and I’ll try to help.
You can also reach me on AIM. My screen name is wrnhmhgg.