- From: Martin Duerst <duerst@w3.org>
- Date: Fri, 10 Dec 2004 16:38:27 +0900
- To: uri <uri@w3.org>, uri@w3.org
- Cc: Graham Klyne <GK@ninebynine.org>
At 23:17 04/12/07, Bruce Lilly wrote:
>
>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.
The draft does not claim that it's suitable for direct LALR
implementation; only that the changes from RFC 2396 make it
more 'friendly' to LALR implementations. As cited by you at
the start of this thread:
The ABNF for URI and URI-reference has been redesigned to make them
more friendly to LALR parsers and reduce complexity.
>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 [*]).
Some doubts may remain. The IETF in general doesn't deal
with doubts, only with actual issues. If you have an
actual issue, please bring it up. General doubt isn't
helpful.
>One issue is whether or not there is such a rigorous
>demonstration that the specified grammar in the draft is
>correct and unambiguous.
The grammar isn't unambiguous. There is language in the
draft that explains what's to be done in an ambiguous
case. My understanding is also that at least some GLR
parser generators can handle ambiguity.
>Lacking such a demonstration,
>there is still the question of whether any implementations
>which appear to interoperate actually implement the
>specified grammar.
Such questions don't help. If you can come up with a reasonable
test case that you think doesn't interoperate, or interoperates
but doesn't match the spec, that would help.
>* 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.
Well, yes, but such grammars are often less readable than
grammars designed for human consumption.
Regards, Martin.
Received on Friday, 10 December 2004 08:08:25 UTC