From: Clifford Heath <no@...>
Date: 2008-09-23T18:20:08+09:00
Subject: Re: ANTLR Target for Ruby

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.