From: Wincent Colaiuta <win@...>
Date: 2008-09-25T03:24:49+09:00
Subject: Re: ANTLR Target for Ruby

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.

Cheers,
Wincent