Re: C.10 Allow nondeterministic content models?

At 01:23 PM 10/17/96 CDT, Michael Sperberg-McQueen wrote:
>
>C.10 Should XML allow nondeterministic content models (11.2.4.3)?

Yes.

(I assume that "determinism" -- or the complementary "ambiguity" -- here
pertains to the sense clarified in Anne Bruggemann-Klein's work: that the
Glushkov NFA is also a DFA.)

Strictly speaking, this is an issue of validation, not parsing, i.e. the
software involved need only be a recognizer, not necessarily a parser. (A
similar comment applies to "syntax directed translation" via attribute or
transduction grammars, where the need to preserve the semantic content -- or
intent -- can introduce tradeoffs in algorithms between scope and efficiency.) 

AFAIK, most recognition algorithms actually exploit nondeterminism in the
sense that they work as NFAs rather than DFAs (sometimes even constructing
states and transitions on the fly), because the problem is to validate an
instance as an admissible member of a class without necessarily preserving a
parse tree (like a non-constructive existence proof.) 

Annex H notwithstanding, the only advantage of "deterministic" content
models is forwards compatibility with unreviewed 8879. 


Arjun
--
"Features whose purpose is to cause errors should be removed" -- Erik Naggum

Received on Friday, 18 October 1996 18:19:13 UTC