From: "Jörg W Mittag" <JoergWMittag+Ruby@...>
Date: 2010-09-04T01:10:08+09:00
Subject: Re: Parsing, BNF, TreeTop, GhostWheel, ...

Clifford Heath wrote:
> Philipp Kempgen wrote:
>> Clifford Heath wrote:
>> What I wanted to do is to construct/generate a parser from a bunch
>> of (A)BNF rules (dozends) from an RFC so backtracking is a
>> requirement while lookahead is not. The grammar specification for
>> the parser (/ parser generator) does not need to be exactly like BNF
>> but should not require me to think about where lookahead is needed
>> as this manual conversion can be error-prone.
> Most of the BNFs in RFCs cannot be directly automated by any parser
> generator. In addition, quite a few of them are slightly incorrect
> and/or incomplete, but haven't been fixed because they're always
> implemented by humans, who paper over the issues, and introduce new
> errors instead ;-)
> 
> The upshot is that you're not going to find a direct implementation
> that works without thinking.
> 
>> That seems to rule out PEG parsers.
> On the contrary, I believe that a PEG parser might represent the most
> direct mapping. PEGs do backtrack, just not on a successful rule or
> iteration. You simply have to introduce enough lookahead to prevent
> false success or excessive iteration... which is actually pretty easy
> once you get the hang of it... the point here is that the *rest* of
> the grammar is much more likely to look  like the EBNF you started
> with. Oh, yeah, you have to refactor any left-recursion too, which can
> be difficult.

Actually, while it is true that PEGs as specificied in Bryan Ford's
paper do not support left recursion, PEGs are usually implemented
using packrat parsers which *can* support direct left recursion just
fine as Alessandro Warth showed in his aptly titled paper "Packrat
Parsers Can Support Left Recursion", although with the caveat that you
lose the linear time complexity guarantee that makes packrat parsing
so compelling in the first place.

jwm