W3C home > Mailing lists > Public > w3c-sgml-wg@w3.org > October 1996

Re: C.10 Allow nondeterministic content models?

From: Joe English <jenglish@crl.com>
Date: Sun, 20 Oct 1996 06:50:08 -0700
Message-Id: <199610201350.AA10916@mail.crl.com>
To: W3C SGML Working Group <w3c-sgml-wg@w3.org>

Tim Bray <tbray@textuality.com> wrote:

> At 11:46 AM 18/10/96 -0700, Joe English wrote:
> >
> >In fact, the ambiguity rule can make things *easier* for implementors.)
> Say what?  The algorithms necessary to detect ambiguity are not typically
> within the repertoire of the hypothetical CS bachelor's-degree type that
> we'd like to be able to construct a validating parser.

True: the ambiguity restriction makes it harder to validate DTDs.
However, it can make it considerably easier to validate *instances*,
if the parser is allowed to assume a DTD with no nondeterminstic
content models (i.e., that the DTD has already been validated).

How much easier depends on the algorithm you use, of course,
but for many automata-based algorithms the savings are considerable.

The "run it through perl and feed it to yacc" algorithm on the
other hand does not benefit from the restriction at all (modulo 
potential exponential blowups in pathological cases); but I've 
never found this to be a particularly efficaceous way to process 

--Joe English

Received on Sunday, 20 October 1996 09:49:22 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 20:25:04 UTC