Re: C.10 Allow nondeterministic content models?

At 12:13 PM 10/20/96, James Clark wrote:
>If you don't have &-groups, detecting non-determinism (I think that's a much
>less confusing term than ambiguity) is pretty trivial.  In fact it you use
>one obvious algorithm for checking instances, non-determinism checking can
>be done in, I would guess, less than 10 lines of code.  The obvious
>algorithm I have in mind is a simplification of Algorithm 3.5 in the Dragon
>Book (p140 in my copy), which is the algorithm for constructing a DFA from a
>regexp.  The simplification is that instead of the complicated final step
>where you do the subset construction, you simply read off the DFA directly
>from the followpos() sets.  While you're doing that, all you have to do to
>check non-determinism is to check each followpos set to see if it includes
>two distinct positions labeled with the same symbol (ie generic identifier).
>
>James

   This is OK. But it still fails a few crucial tests for me. I've never
seen a beginning DTD designer fail to create an ambiguous content model in
their first 2 projects. And it takes some time to understand why this is an
error, since everyone know the rules for regexps and thus that it _need
not_ be an error.

   I am actually more symathetic to & groups than ambiguity because one is
a pain (in several parts of the anatomy, including the neck), and the other
is useful. So I'd rather XML admitted ambiguous models and broke SGML
parsers (a minority of the users will have those, if we're successful),
than retained an odd syntactic restriction that breaks users (and drives
them away).

   What is the justification for unambiguity, independent of SGML
compatibility? I don't see a very good one. That is the kind of
justification we will have to offer the world at large, and be evaluated
on. Asking that question of XML features pretty much determines my
positions on a number of these seemingly minor issues.

   -- David

RE delenda est.
I am not a number. I am an undefined character.
_________________________________________
David Durand              dgd@cs.bu.edu  \  david@dynamicDiagrams.com
Boston University Computer Science        \  Sr. Analyst
http://www.cs.bu.edu/students/grads/dgd/   \  Dynamic Diagrams
--------------------------------------------\  http://dynamicDiagrams.com/
MAPA: mapping for the WWW                    \__________________________
http://www.dynamicdiagrams.com/services_map_main.html

Received on Sunday, 20 October 1996 19:03:42 UTC