From: Eric Mahurin <eric.mahurin@...>
Date: 2008-09-25T04:10:03+09:00
Subject: Re: ANTLR Target for Ruby

------=_Part_62323_8870780.1222283377934
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On Wed, Sep 24, 2008 at 1:24 PM, Wincent Colaiuta <win@wincent.com> wrote:

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

Recursive descent parsing is a form of LL parsing. See here:

http://en.wikipedia.org/wiki/LL_parser

I'd also call packrat parsing a form of LL parsing since recursive descent
is a form of LL parsing and packrat parsing is a form of recursive descent.
Maybe it would be LL(*) with memoization.

Like ANTLR my Grammar project also generates recursive descent parsers,
although mine flattens all methods except where recursion is actually
required.  My Grammars are non-ambiguous (first alternative wins) like
packrat parsers.

------=_Part_62323_8870780.1222283377934--