From: Clifford Heath <no@...>
Date: 2008-01-29T09:00:02+09:00
Subject: Re: Treetop Email Parser

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.

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?

Clifford Heath.

P.S. It'd be nice to know whether my other Treetop messages were useful to you...?