W3C home > Mailing lists > Public > uri@w3.org > December 2004

Re: draft-fielding-uri-rfc2396bis-07 ABNF

From: Bruce Lilly <blilly@erols.com>
Date: Tue, 7 Dec 2004 09:17:40 -0500
To: uri@w3.org
Cc: Graham Klyne <GK@ninebynine.org>
Message-Id: <200412070917.40808.blilly@erols.com>

On Tue December 7 2004 06:14, Graham Klyne wrote:
> 
> Bruce,
> 
> I think you need to be careful about conflating a grammar as a 
> specification of correct sentences (and correspo0nding parse trees) with a 
> grammar as guiding a particular parser implementation.  The importance of 
> grammars satisfying certain properties for LL(1) or LALR parser generation 
> is that they permit creation of the parse tree without backtracking.
> 
> In this case, I think it's sufficient that the grammar satisfies the former 
> purpose;  implementation is a matter for the, er, implementer.

The draft makes a particular claim about implementation via
LALR parsers; in light of that claim, I think it not unreasonable
to question whether or not there is in fact any LALR-based
implementation (particularly as a Standards Track specification
requires at least *two* interoperable implementations at Draft
Standard level or above).  If the grammar is unsuitable for
LALR implementation, then the draft should not claim that it
is suitable for LALR implementation.

LALR and GLR parsers can be built from an ABNF-like
specification, and a working implementation would go a
long way towards comprising a rigorous demonstration that
the grammar is complete and correct (of course, the
specification would have to be compared to the actual ABNF,
which is not difficult for the specific tools I have in mind).
Lacking any such demonstrably correct implementation
which can be clearly and unambiguously tied back to that
ABNF, there must still be some doubt about the grammar
specified by the ABNF (it may be that some implementation
that "works" as expected in fact implements a slightly
different grammar [*]).

One issue is whether or not there is such a rigorous
demonstration that the specified grammar in the draft is
correct and unambiguous.  Lacking such a demonstration,
there is still the question of whether any implementations
which appear to interoperate actually implement the
specified grammar.

* another way of looking at this is that a working LALR
or GLR parser can be used to produce ABNF describing
the grammar implemented by the parser.
Received on Tuesday, 7 December 2004 14:17:46 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:25:08 UTC