Re: ANTLR Target for Ruby

On Sat, Sep 27, 2008 at 11:34 AM, Wincent Colaiuta <[e-mail]> wrote:

> On 27 sep, 06:55, Eric Mahurin <[e-mail]> wrote:
> > On Fri, Sep 26, 2008 at 12:24 PM, Wincent Colaiuta <[e-mail]>
> wrote:
> > > On 26 sep, 04:30, Eric Mahurin <[e-mail]> wrote:
> > > > 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)
> >
> > > Yes, although Pappy, written in Haskell and one of the first Packrat
> > > parsers (if not the first) does it using Higher Order functions. I do
> > > it using Ruby continuations.
> >
> > If you mean parser combinator when you say "higher order function", I
> would
> > assume that many/most parser DSLs specified in a programming language use
> > parser combinators.  Mine does.  My first approach was to parse directly
> > when the DSL is "executed" and I assume that is what you are doing.  But,
> > instead you can make the DSL build a data structure (which might have
> user
> > specified blocks/lambdas in it).  You can then analyze and then parse.
>
> Not sure if we're using the same terminology here, so I'll clarify
> what I meant.
>
> The left-recursion thing I'm talking about is described in this
> thesis:
>
> http://pdos.csail.mit.edu/~baford/packrat/thesis/<http://pdos.csail.mit.edu/%7Ebaford/packrat/thesis/>
>
> See page 69, which talks about how it "rewrites" simple left recursion
> (but not indirect left recursion) by refactoring it into the
> equivalent right recursive rules, and page 40, where it describes how
> the desired associativity of the original left recursive construct is
> preserved through the use of "higher-order functions as intermediate
> parser results".
>
> As for whether this constitutes a "parser combinator", I think so, if
> we agree that a parser combinator is a "function that can take
> functions as input and can also produce functions as
> output" (paraphrased from the Wikipedia article on parser
> combinators).
>
> According to that definition I don't actually think that many/most
> parser DSLs use parser combinators. Mine, for example, for most
> purposes passes around "parslet" instances rather than functions (or
> lambdas).
>

Sorry, Wincent.  I didn't realize you were talking about left recursion
specifically.  I thought your previous response was about doing analysis and
optimizations in general.  Thank you for pointing out the packrat history
with left recursion.

I also used continuations at one time to accomplish left recursion.  It gave
me a nice education in their use.  But, they are soooo slow.  I found it not
too difficult to form loops when I find left recursion.  My left recursion
can do direct or indirect.  I'm guessing since you are using continuations,
your left recursion is fairly flexible too.

My take on parser combinators is that functions/methods are used to combine
smaller parsers together to make larger ones.  It sounds like yours does
this by building larger "parslet"s from smaller ones.  Mine combines Grammar
objects.

Eric