From: Phrogz <phrogz@...>
Date: 2008-01-29T13:50:00+09:00
Subject: Re: Treetop Email Parser

On Jan 28, 8:41 pm, Phrogz <phr...@mac.com> wrote:
> On Jan 28, 4:57 pm, Clifford Heath <n...@spam.please.net> wrote:
> > This is a feature of PEG parsers in general: once a node has
> > succeeded, it will never be retried even though there may be a
> > different way it can succeed. Any backtracking that comes to the
> > same point will remember that it succeeded here once before, and
> > will assume that the *same* success is correct.
...
> ... This limitation
> (which I assume is not in fact limited to PEG in general, but
> specifically to the packrat memoization technique that makes this
> solution perform reasonably) ...

My apologies for second guessing you. Having read the PEG paper[1], I
see now what you're saying. This PEG rule:
  [aeiou]+ 'e'
behaves quite differently from this regular expression:
  /[aeiou]+e/

I had thought - based on the use of the terms 'greedy' and
'backtracking' - that the above PEG rule would be able to match a
string like "aaae", just like the regexp. I see now that PEG in
general (packrat or not) are really, REALLY greedy. The above PEG rule
doesn't match that string because [aeiou]+ consumes the whole string,
and when it fails to find an 'e', it does NOT backtrack on the number
of repetitions of the character class.

Wow.

So...how would you write a PEG rule to match "a string of any number
of vowels, that ends with an 'e'"?

[1] http://pdos.csail.mit.edu/~baford/packrat/popl04/peg-popl04.pdf