# ANTLR Target for Ruby

**URL:** <https://rubytalk.org/t/antlr-target-for-ruby/49119>\
**Category:** ruby-talk\
**Created:** [16 September 2008 16:17 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119 "2008-09-16T16:17:40Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![abc](https://avatars.discourse-cdn.com/v4/letter/a/2bfe46/32.png) [@abc](https://rubytalk.org/u/abc)\
**Post date:** [16 September 2008 16:17 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/1 "2008-09-16T16:17:40Z")

</div>

Hi everyone,

I've asked the following question in the ANTLR mailing list, with no  
luck. Since it's quite Ruby-centric, perhaps someone here knows the  
answer, given the popularity of ANTLR.

I'm in the process of migrating a YACC grammar to ANTLR.

However, since the rest of the project is written in Ruby, I'd like to  
generate the ANTLR code in Ruby, if possible. Currently I'm generating  
Java and using JRuby to circumvent this limitation. I'd prefer to use  
MRI-Ruby, though

I've read the wiki page related to the Ruby Target (http://  
[www.antlr.org/wiki/display/ANTLR3/Antlr3RubyTarget](http://www.antlr.org/wiki/display/ANTLR3/Antlr3RubyTarget)), and the blog of  
its developer ([http://split-s.blogspot.com/2005/12/antlr-for-](http://split-s.blogspot.com/2005/12/antlr-for-)  
ruby.html). The development seems to have halted in version 3.0b4.  
This version could suit my needs as I'm only using basic Lexer and  
Parser generation. No tree parsers.

Does anyone know where to get this version? It's not listed in the  
Download directory ([http://www.antlr.org/download/](http://www.antlr.org/download/)) and I couldn't  
find it in the development repository. Has anyone used it  
successfully?

Thanks in advance.

---

<div class="post-metadata">

**Author:** ![Clifford\_Heath5](https://avatars.discourse-cdn.com/v4/letter/c/7ab992/32.png) [@Clifford\_Heath5](https://rubytalk.org/u/Clifford_Heath5)\
**Post date:** [21 September 2008 12:56 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/2 "2008-09-21T12:56:58Z")

</div>

arcadio wrote:

> I've asked the following question in the ANTLR mailing list, with no  
> luck. Since it's quite Ruby-centric, perhaps someone here knows the  
> answer, given the popularity of ANTLR.
> 
> I'm in the process of migrating a YACC grammar to ANTLR.
> 
> However, since the rest of the project is written in Ruby, I'd like to  
> generate the ANTLR code in Ruby, if possible.

Have you tried just adding the required options section below your grammar  
statement? It just worked for me, though the generated code is a little  
quirky. The Ruby generator has been a standard part of ANTLR for years.

options {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;language = Ruby;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output = AST;  
}

I found that ANTLR was very poor at reporting situations for which it  
couldn't generate correct code (or rather, the designer has a strange  
idea of "correct"), and in particular the lexing behaviour is very  
non-intuitive. I was attempting a very difficult grammar that needs  
LL(\*) behaviour, and as I know now, needs to handle lexing using parse  
rules (no lexer at all). After some unhelpful arguments, I gave up and  
implemented my grammar using Treetop. Terribly slow, but powerful and  
simple to use, once you get the hang of PEG parsing.

Clifford Heath.

---

<div class="post-metadata">

**Author:** ![Eric\_Mahurin](https://avatars.discourse-cdn.com/v4/letter/e/b4bc9f/32.png) [@Eric\_Mahurin](https://rubytalk.org/u/Eric_Mahurin)\
**Post date:** [21 September 2008 14:38 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/3 "2008-09-21T14:38:09Z")

</div>

Hey Clifford,

I still don't know enough about packrat parsing yet. Do you think it  
possible for this type of parser to reach the same performance as LL (or  
LALR) parsers or is there just extra overhead that you need at parse time  
(as opposed to accounted for at parser generation time)? In my  
benchmarking, the 3 packrat parsers I looked at (Treetop, Ghostwheel, and  
Peggy) are 10-100 X slower than pure ruby LL and LALR parsers.

I also was a previous ANTLR user (you might find my C preprocessor in ANTLR  
2.7.6 releases) before writing my own parser. I decided to stick with LL  
parsing for my Grammar project. It does handle lexer-free parsers (but you  
can have a lexer) and handles LL(\*) parsing, but with a performance penalty  
- backtracking. From my understanding, packrat parsers shine in  
backtracking by memoizing to maintain linear performance. I'm wondering if  
I could use this technique and still maintain my non-backtracking  
performance. I thinking I could also make an "engine" for Grammar that did  
packrat or even LALR parsing instead of LL parsing. Independently I should  
be able to translate a PEG syntax, Regexp syntax, or BNF (YACC/ANTLR) to a  
Grammar.

Also, any of you have JSON parser for ANTLR with a Ruby target? JSON is  
what I've been benchmarking with (because of the ruby quiz) and I'd like to  
compare against ANTLR.

Eric

> **···**
>
> On Sun, Sep 21, 2008 at 7:56 AM, Clifford Heath \<no@spam.please.net\> wrote:
> 
> > arcadio wrote:
> > 
> > > I've asked the following question in the ANTLR mailing list, with no  
> > > luck. Since it's quite Ruby-centric, perhaps someone here knows the  
> > > answer, given the popularity of ANTLR.
> > > 
> > > I'm in the process of migrating a YACC grammar to ANTLR.
> > > 
> > > However, since the rest of the project is written in Ruby, I'd like to  
> > > generate the ANTLR code in Ruby, if possible.
> > 
> > Have you tried just adding the required options section below your grammar  
> > statement? It just worked for me, though the generated code is a little  
> > quirky. The Ruby generator has been a standard part of ANTLR for years.
> > 
> > options {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;language = Ruby;  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output = AST;  
> > }
> > 
> > I found that ANTLR was very poor at reporting situations for which it  
> > couldn't generate correct code (or rather, the designer has a strange  
> > idea of "correct"), and in particular the lexing behaviour is very  
> > non-intuitive. I was attempting a very difficult grammar that needs  
> > LL(\*) behaviour, and as I know now, needs to handle lexing using parse  
> > rules (no lexer at all). After some unhelpful arguments, I gave up and  
> > implemented my grammar using Treetop. Terribly slow, but powerful and  
> > simple to use, once you get the hang of PEG parsing.
> > 
> > Clifford Heath.

---

<div class="post-metadata">

**Author:** ![Clifford\_Heath5](https://avatars.discourse-cdn.com/v4/letter/c/7ab992/32.png) [@Clifford\_Heath5](https://rubytalk.org/u/Clifford_Heath5)\
**Post date:** [23 September 2008 09:20 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/4 "2008-09-23T09:20:08Z")

</div>

Eric Mahurin wrote:

> I still don't know enough about packrat parsing yet. Do you think it  
> possible for this type of parser to reach the same performance as LL (or  
> LALR) parsers or is there just extra overhead that you need at parse time

Unless you can analyse the heck out of the source grammar, as ANTLR does,  
I think there's always going to be an overhead. Terence Parr's achievement  
is to figure out where backtracking might be needed and do it efficiently  
only when needed.

Treetop could be improved with some local optimisations, like using Regexp,  
and perhaps looking at the rest of the rule to reduce memoization for example,  
which might pick up 10x improvement or mor, but I expect there'll always be a  
a large overhead over using a hand-crafted parser. There's a suggestion in the  
wind to implement "skip" rules, that produce no syntax nodes, for things like  
whitespace skipping.

Currently, saying "space\*" will generate one node for \*each\* space - Regexp  
would fix that. So even for a PEG parser, Treetop is unnecessarily slow.

> It does handle lexer-free parsers (but you  
> can have a lexer) and handles LL(\*) parsing, but with a performance penalty  
> - backtracking. From my understanding, packrat parsers shine in  
> backtracking by memoizing to maintain linear performance. I'm wondering if  
> I could use this technique and still maintain my non-backtracking  
> performance.

The major part of the cost is the construction of so many objects.  
If you provide memoize-when-hinted, I think that'd be best.  
If you also provided a sweet metagrammar (I find your earlier Grammar  
examples make my eyes bleed), I'd be onto it like a shot. I need the  
prospect of non-Ruby code generation however...

Perhaps an option to "memoize everything" could gather statistics based  
on actual parser behaviour with real input, and produce the backtracking  
hints automatically? That'd be really sweet, because you wouldn't need to  
be a language wizard to work out where to put them.

> I thinking I could also make an "engine" for Grammar that did  
> packrat or even LALR parsing instead of LL parsing.

Nathan was thinking about implementing Treetop using a VM, Truth is,  
if the VM had the right hints, it'd be awesome.

> Also, any of you have JSON parser for ANTLR with a Ruby target? JSON is  
> what I've been benchmarking with (because of the ruby quiz) and I'd like to  
> compare against ANTLR.

Not I, but I'd be surprised if Google doesn't find one. It'd be pretty  
simple to throw one together anyhow.

Have you used ANTRWorks BTW? It's excellent!

Clifford Heath.

---

<div class="post-metadata">

**Author:** ![Eric\_Mahurin](https://avatars.discourse-cdn.com/v4/letter/e/b4bc9f/32.png) [@Eric\_Mahurin](https://rubytalk.org/u/Eric_Mahurin)\
**Post date:** [23 September 2008 13:58 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/5 "2008-09-23T13:58:15Z")

</div>

> Eric Mahurin wrote:
> 
> > I still don't know enough about packrat parsing yet. Do you think it  
> > possible for this type of parser to reach the same performance as LL (or  
> > LALR) parsers or is there just extra overhead that you need at parse time
> 
> Unless you can analyse the heck out of the source grammar, as ANTLR does,  
> I think there's always going to be an overhead. Terence Parr's achievement  
> is to figure out where backtracking might be needed and do it efficiently  
> only when needed.
> 
> Treetop could be improved with some local optimisations, like using Regexp,  
> and perhaps looking at the rest of the rule to reduce memoization for  
> example,  
> which might pick up 10x improvement or mor, but I expect there'll always be  
> a  
> a large overhead over using a hand-crafted parser. There's a suggestion in  
> the  
> wind to implement "skip" rules, that produce no syntax nodes, for things  
> like  
> whitespace skipping.
> 
> Currently, saying "space\*" will generate one node for \*each\* space - Regexp  
> would fix that. So even for a PEG parser, Treetop is unnecessarily slow.
> 
> It does handle lexer-free parsers (but you
> 
> > can have a lexer) and handles LL(\*) parsing, but with a performance  
> > penalty  
> > - backtracking. From my understanding, packrat parsers shine in  
> > backtracking by memoizing to maintain linear performance. I'm wondering  
> > if  
> > I could use this technique and still maintain my non-backtracking  
> > performance.
> 
> The major part of the cost is the construction of so many objects.  
> If you provide memoize-when-hinted, I think that'd be best.  
> If you also provided a sweet metagrammar (I find your earlier Grammar  
> examples make my eyes bleed), I'd be onto it like a shot. I need the  
> prospect of non-Ruby code generation however...

I'm curious, could you give an example of what makes your eyes bleed? I  
would like to improve the usability where possible. The Grammar layer  
itself will always be just ruby objects with a ruby DSL. But, I would like  
to provide translators from various formats (BNF, PEG, regex, etc) to  
Grammar objects. I'm sure I could even give you a faster replacement for  
Regexp (using ruby2cext). These translators would simply be Grammars that  
build Grammars (or maybe the code, so you could see/edit it).

Also, with Grammar 0.8, I've completely separated the parser generation.  
Grammar is just a light-weight layer used to hold the description of the  
language you are parsing. The real work is in the "engine" that does parser  
generation. There aren't many bounds as to what an "engine" could do with a  
Grammar. An engine could:

&nbsp;&nbsp;&nbsp;- generate a parser in another target language (engine might allow an  
&nbsp;&nbsp;&nbsp;"action" to be simply a code string)  
&nbsp;&nbsp;&nbsp;- directly parse while traversing a Grammar  
&nbsp;&nbsp;&nbsp;- generate another type of parser - LALR, packrat ???  
&nbsp;&nbsp;&nbsp;- build a Graphviz diagram of a Grammar tree  
&nbsp;&nbsp;&nbsp;- "inspect" a Grammar (Grammar#inspect isn't useful because every Grammar  
&nbsp;&nbsp;&nbsp;level mainly just has a lambda)  
&nbsp;&nbsp;&nbsp;- translate to another format - regex, BNF, PEG

Right now I've implemented only a few engines (some built on each other) -  
Ruby (generates very flat LL ruby parsers), RubyCall (puts method calls in  
certain places), Ruby0 (parses directly instead of generating a parser),  
Ruby2CExt (uses ruby2cext to generate a rubyC parser).

Perhaps an option to "memoize everything" could gather statistics based

> on actual parser behaviour with real input, and produce the backtracking  
> hints automatically? That'd be really sweet, because you wouldn't need to  
> be a language wizard to work out where to put them.

Personally, I don't like the idea of automatic backtracking. Regexp does  
this. The big problem I see with auto-backtracking is that when the parse  
fails, you just get a simple "it failed" response. Or you could possibly  
generate a tree of possible failing locations (and expectations) in the  
input. Nothing as simple as "expected this, got that, at line 123". Ever  
try to debug a large Regexp? If it doesn't parse your input, it just  
returns false and you have nothing to go on. I see the auto-backtracking  
feature of Regexp as the reason it can't do much more than that. If/when I  
make a Regexp translator, it would generate a Grammar that can backtrack on  
every alternative (except with the (?\>...) no backtrack construct) to be  
compatible. I guess an "engine" could also backtrack by default.

In my very first incarnation of Grammar (called Syntax on RAA), I did do  
auto-backtracking, but found the above problem. I'd rather it be the  
exception than the rule.

Does Treetop auto-backtrack? How do you deal with error reporting?

If backtracking isn't always on, do you memoize only when you might possibly  
backtrack? In Grammar, I'm wondering if it is possible to take to a  
memoizing performance hit only when backtracking is allowed.

&nbsp;&nbsp;I thinking I could also make an "engine" for Grammar that did

> packrat or even LALR parsing instead of LL parsing.

Nathan was thinking about implementing Treetop using a VM, Truth is,

> if the VM had the right hints, it'd be awesome.

I'd also could make a Grammar engine for generating VM bytecode if that were  
possible.

Also, any of you have JSON parser for ANTLR with a Ruby target? JSON is

> > what I've been benchmarking with (because of the ruby quiz) and I'd like  
> > to  
> > compare against ANTLR.
> 
> Not I, but I'd be surprised if Google doesn't find one. It'd be pretty  
> simple to throw one together anyhow.

I already found it on the antlr site, but not with a ruby target. I didn't  
want to go relearn antlr (v3 now) and how to get it to generate ruby.

Have you used ANTRWorks BTW? It's excellent!

Once. I'd like to make something like this for Grammar (at least an engine  
that graphically displays a Grammar).

Eric

> **···**
>
> On Tue, Sep 23, 2008 at 4:20 AM, Clifford Heath \<no@spam.please.net\> wrote:

---

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [23 September 2008 14:08 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/6 "2008-09-23T14:08:07Z")

</div>

Hopefully it's fixed now, but last time I tried using ANTLR for Ruby output it was very broken. That was a while ago though (shortly after version three released, I think).

James Edward Gray II

> **···**
>
> On Sep 23, 2008, at 8:58 AM, Eric Mahurin wrote:
> 
> > I already found it on the antlr site, but not with a ruby target. I didn't want to go relearn antlr (v3 now) and how to get it to generate ruby.

---

<div class="post-metadata">

**Author:** ![Clifford\_Heath5](https://avatars.discourse-cdn.com/v4/letter/c/7ab992/32.png) [@Clifford\_Heath5](https://rubytalk.org/u/Clifford_Heath5)\
**Post date:** [24 September 2008 02:04 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/7 "2008-09-24T02:04:56Z")

</div>

Eric Mahurin wrote:

> > The major part of the cost is the construction of so many objects.  
> > If you provide memoize-when-hinted, I think that'd be best.  
> > If you also provided a sweet metagrammar (I find your earlier Grammar  
> > examples make my eyes bleed), I'd be onto it like a shot. I need the  
> > prospect of non-Ruby code generation however...
> 
> I'm curious, could you give an example of what makes your eyes bleed?

I must admit I haven't looked closely at Grammar for a while, however...

DSLs are fine for folk who don't know how to make proper grammars :-).  
They tend to have a somewhat high signal-to-noise ratio, by which I mean  
there are too many extraneous characters/symbols, or symbols that aren't  
intuitively communicative.

Every non-essential symbol in a sentence is a significant barrier  
to a newcomer, though experienced users learn to skip them and don't  
understand what the fuss is about. The problem is that the difficulty  
of grasping which symbols are significant and which aren't goes with  
the \*square\* of the S/N ratio.

XML is a perfect example of how to do this wrongly 🙂 sendmail.cf  
and Perl are even better examples ;-).

> I would like  
> to provide translators from various formats (BNF, PEG, regex, etc) to  
> Grammar objects.

That's what I'm talking about, good stuff.

> Also, with Grammar 0.8, I've completely separated the parser generation.  
> Grammar is just a light-weight layer used to hold the description of the  
> language you are parsing.

So you're already halfway to a VM, where the generated parser doesn't have  
to be human-readable at all 🙂

> Personally, I don't like the idea of automatic backtracking. Regexp does  
> this. The big problem I see with auto-backtracking is that when the parse  
> fails, you just get a simple "it failed" response.

Not the case with Treetop. It assumes that the furthest point reached is  
the failure point (not often true but an assumption that works, given...)  
and lists the text leading up to that, and enumerates the terminal tokens  
that would have allowed it to get further. This works \*really\* well.  
Try it - call the "failure\_reason" method on a failed parse to see it  
in action.

> Nothing as simple as "expected this, got that, at line 123".

It's exactly as simple as that. The diagnosis might be wrong, but to  
the human, it's a comprehensible mistake.

> Does Treetop auto-backtrack?

That's what memoizing is for - it's the core of how PEG works.

> If backtracking isn't always on, do you memoize only when you might possibly  
> backtrack? In Grammar, I'm wondering if it is possible to take to a  
> memoizing performance hit only when backtracking is allowed.

I don't think you can guess when backtracking will be needed.  
As I said, it requires heavy analysis - Terrence didn't get his  
PhD for nothing!

But if you always allow backtracking ala PEG, but only memoize in  
places where experience (aka statistics collected) have shown it's  
needed, you could have the best of both worlds.

> I already found it on the antlr site, but not with a ruby target. I didn't  
> want to go relearn antlr (v3 now) and how to get it to generate ruby.

You just ask for Ruby in your options block at the top of the grammar.  
The Ruby target is quite strange and limited though IIRC. The lexer  
in all ANTLR grammars is definitely non-intuitive, it doesn't choose  
the longest possible match like every other lexer in the world. Terr  
isn't concerned about his users, just about big-noting himself. I  
wouldn't say "their weak support ran me off" so much as just "they ran  
me off". When he pisses someone off, that just proves his superiority  
more... and I have the emails to prove it. You mighta thought DHH had  
an attitude problem, heh, he's tame!

> Have you used ANTRWorks BTW? It's excellent!  
> Once. I'd like to make something like this for Grammar (at least an engine  
> that graphically displays a Grammar).

ANTLRWorks shows railroad diagrams, which I used to produce syntax  
documentation for CQL. But the ability to interactively test individual  
rules is great. A lot of work though - I'd have thought your skills  
were better spent elsewhere.

Clifford Heath.

---

<div class="post-metadata">

**Author:** ![Ryan\_Davis1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/ryan_davis1/32/1848_2.png) [@Ryan\_Davis1](https://rubytalk.org/u/Ryan_Davis1)\
**Post date:** [23 September 2008 18:30 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/8 "2008-09-23T18:30:51Z")

</div>

I doubt it is fixed... I tried to submit patches to get the ruby code to work and Terr was a PITA to no end so I walked away. He later came to me asking if I wanted to maintain the ruby side, but... too little, too late.

I just checked perforce and the last change to ruby runtime was:

Change 3846 on 2007/06/26 by martin@martin.MartinXP.antlr3 '- fixed various bugs related...'

My last emails from Terr were 2007-08, so ... no, probably not fixed in the slightest.

> **···**
>
> On Sep 23, 2008, at 07:08 , James Gray wrote:
> 
> > On Sep 23, 2008, at 8:58 AM, Eric Mahurin wrote:
> > 
> > > I already found it on the antlr site, but not with a ruby target. I didn't want to go relearn antlr (v3 now) and how to get it to generate ruby.
> > 
> > Hopefully it's fixed now, but last time I tried using ANTLR for Ruby output it was very broken. That was a while ago though (shortly after version three released, I think).

---

<div class="post-metadata">

**Author:** ![Wincent\_Colaiuta](https://avatars.discourse-cdn.com/v4/letter/w/e79b87/32.png) [@Wincent\_Colaiuta](https://rubytalk.org/u/Wincent_Colaiuta)\
**Post date:** [24 September 2008 08:49 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/9 "2008-09-24T08:49:56Z")

</div>

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](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

---

<div class="post-metadata">

**Author:** ![Eric\_Mahurin](https://avatars.discourse-cdn.com/v4/letter/e/b4bc9f/32.png) [@Eric\_Mahurin](https://rubytalk.org/u/Eric_Mahurin)\
**Post date:** [24 September 2008 12:23 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/10 "2008-09-24T12:23:23Z")

</div>

> DSLs are fine for folk who don't know how to make proper grammars :-).

OK. I guess that's that source of the "bleeding eyes"... I'm sounds like I  
won't be able to convince you why a DSL is better than a specific format,  
and you vice-versa. A quick summary is: although you lose the exact syntax  
that you may want, you gain in power and flexibility. Using Grammar  
(directly), you could template Grammars (method/lambda could return a  
Grammar based on Grammar args and other params), use plain ruby for extra  
control when specifying a Grammar tree, or simply embed Grammar objects in a  
ruby program (like Regexp objects can be - although they parse the grammar  
from a string).

I would like

> > to provide translators from various formats (BNF, PEG, regex, etc) to  
> > Grammar objects.
> 
> That's what I'm talking about, good stuff.
> 
> Also, with Grammar 0.8, I've completely separated the parser generation.
> 
> > Grammar is just a light-weight layer used to hold the description of the  
> > language you are parsing.
> 
> So you're already halfway to a VM, where the generated parser doesn't have  
> to be human-readable at all 🙂

Better - it is a compiler. Compiles from a Grammar to a target language.  
Grammar has always done this. Previously, Ruby code generation was done in  
the Grammar class itself. I've separated it to add quite a bit of  
flexibility.

> Personally, I don't like the idea of automatic backtracking. Regexp does
> 
> > this. The big problem I see with auto-backtracking is that when the parse  
> > fails, you just get a simple "it failed" response.
> 
> Not the case with Treetop. It assumes that the furthest point reached is  
> the failure point (not often true but an assumption that works, given...)  
> and lists the text leading up to that, and enumerates the terminal tokens  
> that would have allowed it to get further. This works \*really\* well.  
> Try it - call the "failure\_reason" method on a failed parse to see it  
> in action.

OK. I guess it just remembers the furthest point it reached when  
backtracking and when all possibilities are exhausted, it reports this  
furthest point. Sounds reasonable. I guess I could try something like this  
when I backtrack. Right now, I ignore errors/mismatches that cause a  
backtrack.

> Does Treetop auto-backtrack?
> 
> > 
> 
> That's what memoizing is for - it's the core of how PEG works.

Don't you mean packrat instead of PEG? I thought PEG was just a format for  
describing something to parse, like BNF. And packrat refers to the type of  
parser - like LL or LALR. From my understanding packrat is a cousin of LL,  
but adds memoizing to achieve linear backtracking performance.

> If backtracking isn't always on, do you memoize only when you might
> 
> > possibly  
> > backtrack? In Grammar, I'm wondering if it is possible to take to a  
> > memoizing performance hit only when backtracking is allowed.
> 
> I don't think you can guess when backtracking will be needed.  
> As I said, it requires heavy analysis - Terrence didn't get his  
> PhD for nothing!

In Grammar, I don't try to guess. Backtracking is normally not done. To  
allow for backtracking, I provide a Grammar#backtrack method that returns a  
new Grammar that can backtrack to the beginning of where the Grammar started  
parsing the input when it fails in the middle. I would only apply  
memoization for one of these - if this is doable.

> I already found it on the antlr site, but not with a ruby target. I
> 
> > didn't  
> > want to go relearn antlr (v3 now) and how to get it to generate ruby.
> 
> You just ask for Ruby in your options block at the top of the grammar.  
> The Ruby target is quite strange and limited though IIRC. The lexer  
> in all ANTLR grammars is definitely non-intuitive, it doesn't choose  
> the longest possible match like every other lexer in the world. Terr  
> isn't concerned about his users, just about big-noting himself. I  
> wouldn't say "their weak support ran me off" so much as just "they ran  
> me off". When he pisses someone off, that just proves his superiority  
> more... and I have the emails to prove it. You mighta thought DHH had  
> an attitude problem, heh, he's tame!

I didn't encounter that a few years ago. I mostly just learned a lot about  
LL parsing and wanted to make something better. It does sound like others  
have been run off though...

> &nbsp;&nbsp;Have you used ANTRWorks BTW? It's excellent!
> 
> > Once. I'd like to make something like this for Grammar (at least an  
> > engine  
> > that graphically displays a Grammar).
> 
> ANTLRWorks shows railroad diagrams, which I used to produce syntax  
> documentation for CQL. But the ability to interactively test individual  
> rules is great. A lot of work though - I'd have thought your skills  
> were better spent elsewhere.

I was only thinking making a Grammar engine that generated dot files for  
Graphviz to get a visualization of a Grammar.

Eric

> **···**
>
> On Tue, Sep 23, 2008 at 9:04 PM, Clifford Heath \<no@spam.please.net\> wrote:

---

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [23 September 2008 19:19 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/11 "2008-09-23T19:19:39Z")

</div>

Yeah, I too felt like Ruby was a second class citizen. I was trying to make the switch to ANTLR as my parsing tool, but their week support ran me off.

James Edward Gray II

> **···**
>
> On Sep 23, 2008, at 1:30 PM, Ryan Davis wrote:
> 
> > On Sep 23, 2008, at 07:08 , James Gray wrote:
> > 
> > > On Sep 23, 2008, at 8:58 AM, Eric Mahurin wrote:
> > > 
> > > > I already found it on the antlr site, but not with a ruby target. I didn't want to go relearn antlr (v3 now) and how to get it to generate ruby.
> > > 
> > > Hopefully it's fixed now, but last time I tried using ANTLR for Ruby output it was very broken. That was a while ago though (shortly after version three released, I think).
> > 
> > I doubt it is fixed... I tried to submit patches to get the ruby code to work and Terr was a PITA to no end so I walked away. He later came to me asking if I wanted to maintain the ruby side, but... too little, too late.
> > 
> > I just checked perforce and the last change to ruby runtime was:
> > 
> > Change 3846 on 2007/06/26 by martin@martin.MartinXP.antlr3 '- fixed various bugs related...'
> > 
> > My last emails from Terr were 2007-08, so ... no, probably not fixed in the slightest.

---

<div class="post-metadata">

**Author:** ![Eric\_Mahurin](https://avatars.discourse-cdn.com/v4/letter/e/b4bc9f/32.png) [@Eric\_Mahurin](https://rubytalk.org/u/Eric_Mahurin)\
**Post date:** [24 September 2008 12:23 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/12 "2008-09-24T12:23:31Z")

</div>

It seems like everybody writing parser (generators) is coming from ANTLR. I  
count Clifford Heath, James Gray, Ryan Davis, Wincent, and me.

Wincent, do you happen to have something in Walrus that parses JSON and  
generates ruby (tree of hashs and arrays)? I've benchmarked a bunch of  
parser generators out there using JSON and would always like to add more.

> **···**
>
> On Wed, Sep 24, 2008 at 3:49 AM, Wincent Colaiuta \<win@wincent.com\> wrote:
> 
> > 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.

---

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [24 September 2008 13:32 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/13 "2008-09-24T13:32:50Z")

</div>

When I wrote GhostWheel, I was convinced the DSL was better too. Then I tried using it and changed my mind. 🙂

The DSL adds a lot of Ruby noise that makes it harder to think about and understand the language being parsed. It keeps you from focusing on the right things.

For example, compare this JSON parser using GhostWheel's DSL:

[http://ghostwheel.rubyforge.org/svn/trunk/test/example/tc\_json\_ruby.rb](http://ghostwheel.rubyforge.org/svn/trunk/test/example/tc_json_ruby.rb)

and this using a grammar:

[http://ghostwheel.rubyforge.org/svn/trunk/test/example/tc\_json\_ghost\_wheel.rb](http://ghostwheel.rubyforge.org/svn/trunk/test/example/tc_json_ghost_wheel.rb)

I'm not arguing my grammar is perfect either. I think it could get even more readable. But have a look at how clear rules like value\_space, value\_content, value, and value\_with\_array\_sep play out.

I also think most of the advantages you list can be gained with non-DSL grammars. I mean, we can always dynamically build up a String in Ruby too and that's the dumbest thing I could possibly think of.

Anyway, the two don't have to be exclusive. As you see, GhostWheel supports both.

James Edward Gray II

> **···**
>
> On Sep 24, 2008, at 7:23 AM, Eric Mahurin wrote:
> 
> > I'm sounds like I  
> > won't be able to convince you why a DSL is better than a specific format,  
> > and you vice-versa. A quick summary is: although you lose the exact syntax  
> > that you may want, you gain in power and flexibility. Using Grammar  
> > (directly), you could template Grammars (method/lambda could return a  
> > Grammar based on Grammar args and other params), use plain ruby for extra  
> > control when specifying a Grammar tree, or simply embed Grammar objects in a  
> > ruby program (like Regexp objects can be - although they parse the grammar  
> > from a string).

---

<div class="post-metadata">

**Author:** ![Wincent\_Colaiuta](https://avatars.discourse-cdn.com/v4/letter/w/e79b87/32.png) [@Wincent\_Colaiuta](https://rubytalk.org/u/Wincent_Colaiuta)\
**Post date:** [24 September 2008 18:24 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/14 "2008-09-24T18:24:49Z")

</div>

I think your right about the first part, but not about the second  
part; Packrat has nothing to do with LL or LALR parsing.

A PEG is a Parsing Expression Grammar. Its distinguishing features  
are:

- has the usual repetition (zero or more, one or more) operators,  
sequence operators, alternative operators, as well as "and predicates"  
and "not predicates"

- grammars are non-ambiguous because alternatives are specified as a  
set of ordered choices

- lends itself to recognition by recursive descent, and maps quite  
well onto the way human beings perform recognition in their own minds

A Packrat parser is a memoizing recursive-descent parser that  
recognizes input based on a PEG. Its distinguishing feature is the  
memoization.

At least, that's my understanding of it.

Cheers,  
Wincent

> **···**
>
> On 24 sep, 14:23, Eric Mahurin \<eric.mahu...@gmail.com\> wrote:
> 
> > On Tue, Sep 23, 2008 at 9:04 PM, Clifford Heath \<n...@spam.please.net\> wrote:  
> > \> Does Treetop auto-backtrack?
> > 
> > \> That's what memoizing is for - it's the core of how PEG works.
> > 
> > Don't you mean packrat instead of PEG? I thought PEG was just a format for  
> > describing something to parse, like BNF. And packrat refers to the type of  
> > parser - like LL or LALR. From my understanding packrat is a cousin of LL,  
> > but adds memoizing to achieve linear backtracking performance.

---

<div class="post-metadata">

**Author:** ![Clifford\_Heath5](https://avatars.discourse-cdn.com/v4/letter/c/7ab992/32.png) [@Clifford\_Heath5](https://rubytalk.org/u/Clifford_Heath5)\
**Post date:** [26 September 2008 00:44 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/15 "2008-09-26T00:44:41Z")

</div>

Eric Mahurin wrote:

> > DSLs are fine for folk who don't know how to make proper grammars :-).
> 
> A quick summary is: although you lose the exact syntax  
> that you may want, you gain in power and flexibility.

As James has said, I don't believe the latter is necessarily true.  
It's beholden on we who want folk to create proper grammars to use  
best practise ourselves, anyhow.

> Don't you mean packrat instead of PEG?

You're right, but I identify the two, as I've never seen one used  
without the other.

> I was only thinking making a Grammar engine that generated dot files for  
> Graphviz to get a visualization of a Grammar.

Ok. That wouldn't use useful to me, because when I have to document a  
grammar, the diagrams aren't as appropriate for that audience cf a railroad  
diagram. See my "Introduction to CQL" here, which has railroads extracted  
from ANTLRWorks: \<dataconstellation.com/ActiveFacts/CQLIntroduction.pdf\>.

Clifford Heath.

> **···**
>
> > On Tue, Sep 23, 2008 at 9:04 PM, Clifford Heath \<no@spam.please.net\> wrote:

---

<div class="post-metadata">

**Author:** ![Clifford\_Heath5](https://avatars.discourse-cdn.com/v4/letter/c/7ab992/32.png) [@Clifford\_Heath5](https://rubytalk.org/u/Clifford_Heath5)\
**Post date:** [26 September 2008 00:59 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/16 "2008-09-26T00:59:43Z")

</div>

Wincent Colaiuta wrote:

> Like Treetop, it is fairly slow, but it works.

Nice!

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

What do you think of my third option: Provide memoization only where a  
test workload shows the need for it? Backtrack in every situation just  
in case, but memoize where testing shows it's useful - totally pragmatic  
approach...

> One of the things I always liked about the system was that you wrote  
> your grammars in Ruby.

I think that's an error, based on the presumption that "is Ruby, is good".  
Not all that's Ruby is golden, err... red ;-). By which I mean that  
one size doesn't fit all, or we wouldn't need parsers in the first place.

Clifford Heath.

---

<div class="post-metadata">

**Author:** ![Eric\_Mahurin](https://avatars.discourse-cdn.com/v4/letter/e/b4bc9f/32.png) [@Eric\_Mahurin](https://rubytalk.org/u/Eric_Mahurin)\
**Post date:** [26 September 2008 02:30 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/17 "2008-09-26T02:30:27Z")

</div>

Hi Wincent,

Just because you are using a Ruby DSL, you shouldn't be limited. There is  
nothing that says your DSL couldn't build exactly the same data structures  
that you'd build if you read/parsed in a non-Ruby DSL. In my Grammar  
project, I create a Grammar tree with a Ruby DSL (simply methods that create  
and combine Grammars). I can parse directly using this tree or I can  
generate highly optimized code. Here are a few optimizations: flattening  
(method calls only needed for recursion), tail call optimization (right  
recursion), left recursion (normally unheard of with LL), some refactoring,  
and boolean minimizations. The main thing that should matter in terms of  
analysis should be your data structures, not how you get there. A ruby DSL  
will only enhance flexibility.

Eric

> **···**
>
> On Wed, Sep 24, 2008 at 3:49 AM, Wincent Colaiuta \<win@wincent.com\> wrote:
> 
> > 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.

---

<div class="post-metadata">

**Author:** ![Ryan\_Davis1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/ryan_davis1/32/1848_2.png) [@Ryan\_Davis1](https://rubytalk.org/u/Ryan_Davis1)\
**Post date:** [23 September 2008 21:56 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/18 "2008-09-23T21:56:53Z")

</div>

I doubt they even gave it that long... \*rimshot\*

> **···**
>
> On Sep 23, 2008, at 12:19 , James Gray wrote:
> 
> > Yeah, I too felt like Ruby was a second class citizen. I was trying to make the switch to ANTLR as my parsing tool, but their week support ran me off.

---

<div class="post-metadata">

**Author:** ![Dave\_Mail\_Archive](https://avatars.discourse-cdn.com/v4/letter/d/f04885/32.png) [@Dave\_Mail\_Archive](https://rubytalk.org/u/Dave_Mail_Archive)\
**Post date:** [24 September 2008 12:54 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/19 "2008-09-24T12:54:02Z")

</div>

Have you tried the JSON parser one built in to 1.9? It's a native extension, but I don't know how its performance compares with other JSON parsers.

Dave

> **···**
>
> On Sep 24, 2008, at 7:23 AM, Eric Mahurin wrote:
> 
> > Wincent, do you happen to have something in Walrus that parses JSON and  
> > generates ruby (tree of hashs and arrays)? I've benchmarked a bunch of  
> > parser generators out there using JSON and would always like to add more.

---

<div class="post-metadata">

**Author:** ![Eric\_Mahurin](https://avatars.discourse-cdn.com/v4/letter/e/b4bc9f/32.png) [@Eric\_Mahurin](https://rubytalk.org/u/Eric_Mahurin)\
**Post date:** [24 September 2008 13:46 UTC](https://rubytalk.org/t/antlr-target-for-ruby/49119/20 "2008-09-24T13:46:44Z")

</div>

I think my DSL is still fairly clean because you can simply use variable  
assignments for "rules" and use the "+" and "|" operators for sequences and  
alternations. Those help a lot. Ideally I would use a space instead of "+"  
to match BNF, but it doesn't seem that bad.

But, I think I'll also have converters (PEG, BNF, regex) to give the non-DSL  
approach.

> **···**
>
> On Wed, Sep 24, 2008 at 8:32 AM, James Gray \<james@grayproductions.net\>wrote:
> 
> > On Sep 24, 2008, at 7:23 AM, Eric Mahurin wrote:
> > 
> > I'm sounds like I
> > 
> > > won't be able to convince you why a DSL is better than a specific format,  
> > > and you vice-versa. A quick summary is: although you lose the exact  
> > > syntax  
> > > that you may want, you gain in power and flexibility. Using Grammar  
> > > (directly), you could template Grammars (method/lambda could return a  
> > > Grammar based on Grammar args and other params), use plain ruby for extra  
> > > control when specifying a Grammar tree, or simply embed Grammar objects in  
> > > a  
> > > ruby program (like Regexp objects can be - although they parse the grammar  
> > > from a string).
> > 
> > When I wrote GhostWheel, I was convinced the DSL was better too. Then I  
> > tried using it and changed my mind. 🙂
> > 
> > The DSL adds a lot of Ruby noise that makes it harder to think about and  
> > understand the language being parsed. It keeps you from focusing on the  
> > right things.
> > 
> > For example, compare this JSON parser using GhostWheel's DSL:
> > 
> > [http://ghostwheel.rubyforge.org/svn/trunk/test/example/tc\_json\_ruby.rb](http://ghostwheel.rubyforge.org/svn/trunk/test/example/tc_json_ruby.rb)
> > 
> > and this using a grammar:
> > 
> > [http://ghostwheel.rubyforge.org/svn/trunk/test/example/tc\_json\_ghost\_wheel.rb](http://ghostwheel.rubyforge.org/svn/trunk/test/example/tc_json_ghost_wheel.rb)
> > 
> > I'm not arguing my grammar is perfect either. I think it could get even  
> > more readable. But have a look at how clear rules like value\_space,  
> > value\_content, value, and value\_with\_array\_sep play out.
> > 
> > I also think most of the advantages you list can be gained with non-DSL  
> > grammars. I mean, we can always dynamically build up a String in Ruby too  
> > and that's the dumbest thing I could possibly think of.
> > 
> > Anyway, the two don't have to be exclusive. As you see, GhostWheel  
> > supports both.

[Next page](https://rubytalk.org/t/antlr-target-for-ruby/49119.md?page=2)
