From: Wincent Colaiuta Date: 2008-09-28T01:34:26+09:00 Subject: Re: ANTLR Target for Ruby On 27 sep, 06:55, Eric Mahurin wrote: > On Fri, Sep 26, 2008 at 12:24 PM, Wincent Colaiuta wrote: > > On 26 sep, 04:30, Eric Mahurin 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/ 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). Cheers, Wincent