From: Wincent Colaiuta <win@...>
Date: 2008-09-24T17:49:56+09:00
Subject: Re: ANTLR Target for Ruby

I wrote a PEG parser generator a couple of years ago to support my
Walrus object-oriented templating system (inspired by the Cheetah
template engine in Python, and carrying over a lot of its syntax and
directives). Actually, the reason I did this was because I didn't have
any luck getting ANTLR to do what I wanted it to do.

The parser generator uses a Ruby DSL to specify the grammar,
dynamically constructing the parser on the fly. To get an idea of what
the DSL looks like and what it can do, check out the parser for the
Walrus language itself; it is a fairly complex example because it
demonstrates things like "here documents", include files, and parses a
subset of Ruby itself in addition to the Walrus markup:

http://git.wincent.com/Walrus.git?a=blob;f=lib/walrus/parser.rb

Like Treetop, it is fairly slow, but it works. The major performance
penalty actually seems to be the memory bloat associated with
memoization. There is also a resource leak in there where a lot of the
memoized data doesn't appear to be getting garbage-collected when you
run the parser over lots of documents in the same session; never got
to the bottom of that one despite spending quite a few hours on it. My
workaround was to process multiple files in batches, running Walrus
once for each file rather than passing it all the files at once. Not
very elegant but it worked.

Given that it works I haven't really done any more development on it.
But an academic itch that I've wanted to scratch for some time now has
been turning it into a performance powerhouse; either by replacing the
dynamically generated parser with a custom Ragel lexer (packaged as a
C extension for Ruby) or by doing static grammar analysis like ANTLR
does to identify places where prediction could be used to circumvent
unnecessary backtracking and jump straight to the right alternative.

But I think both of those options would require me to lose the Ruby
DSL and switch to a custom, non-Ruby language for specifying grammars.
One of the things I always liked about the system was that you wrote
your grammars in Ruby. Evidently, you can only do static analysis once
you've parsed the grammar, and that would be fiendishly difficult (or
impossible?) to do with a dynamically-constructed one built on the fly
by evaluating the Ruby DSL.

Cheers,
Wincent