Re: C.10 Allow nondeterministic content models?

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 
SGML...


--Joe English

  jenglish@crl.com

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