- 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