From: Clifford Heath Date: 2010-08-20T10:20:21+09:00 Subject: Re: Parsing, BNF, TreeTop, GhostWheel, ... 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. Clifford Heath.