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

On Jan 28, 4:57 pm, Clifford Heath <n...@spam.please.net> wrote:
> Phrogz wrote:
> > (I would post this to the treetop mailing list...except there doesn't
> > seem to be one.)
>
> It's fine here. A lot of folk here could benefit from using Treetop,
> if only they could work out how to. Discussion here can help them.

Sure. I'd also like a place to send bug reports, however. So far, I've
been sending them to the only contact address I can find for the
entire project - Nathan's email as listed in the gemspec.

> Your problem lies in the direct translation of this rule, which is
> poorly written in the RFC:
>
> >   CFWS            =  *([FWS] comment) (([FWS] comment) / FWS)
>
> to:
>
> >   rule CFWS
> >     (FWS? comment)* ((FWS? comment) / FWS)
> >   end
>
> The issue is that the first parenthesized group is a node that
> will eat too much, succeed, then cause the second group to fail.
> 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.
>
> You need to rewrite it to avoid this incorrect success. This rule
> is equivalent:
>
> rule CFWS
>     ( FWS / comment )+
> end
>
> Just a bit simpler, eh?

You know, I looked at that rule (and some like it) and said "Man, what
were they smoking!?" But yeah, this was a quick translation over lunch
and I explicitly didn't want to try translating anything.

To be fair, that's not quite the same rule, right? Your rule would
allow FWS FWS FWS, while the original requires a comment between them.
(FWS itself only eats one CRLF at a time, so this change allows blank
lines where they were not allowed before. I think.)

I appreciate the help and insight. This insight scares me, I must
admit.

I was happy to accept the no-left-recursion limitation of the grammar,
because it's easy to spot and the downside is infinite recursion. If
it wasn't obvious when writing the grammar, it would be reasonably
obvious at runtime when your parse never finished.

But what you describe here seems far more insidious. 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) says to me: There are some cases where
you can write something that looks correct and technically *is*
correct, but that will silently fail on otherwise valid content.
Please (definitely) correct me if I'm wrong. I definitely don't want
to spread FUD.

Can you provide any guidelines or reading points on how to recognize a
set of rules that may fail like this? Is it limited to use of the zero-
or-more star symbol? Particularly likely to occur when any star or
plus quantifier appears at the start of a rule?

Thanks again for your help. I'm still excited about treetop, but less
so as I find that I actually have to know some theory about the
language I'm writing in (*gasp*) instead of being able to naively
throw together BNF-like rules and have it magically all work out. ;)