Inclusion and exclusion exceptions

Title: Re: exceptions

Author: jenglish@crl2.crl.com (Joe English)

Date: 18 Aug 1997 11:35:59 -0700


       ------------------------------------------------------

Lars Marius Garshol  <larsga@ifi.uio.no> wrote:
>matzen@a.cs.okstate.edu (MATZEN RICHARD WAL) writes:

[ Re: inclusion and exclusion exceptions ]

>> 2.b. Does it add significant expressive power for authors?
>
>In theory, no, as you can always write an equivalent DTD without exceptions.

Actually, it's _not_ always possible to write an equivalent DTD
without exceptions.

It is always possible to convert a DTD with exclusion exceptions
into a "superset" DTD (which accepts a larger set of documents),
simply by removing the exclusions.  However, it's not possible
to create an _exactly_ equivalent exclusion-free DTD.

One possible approach is to create a new element type (with a
restricted content model) for each original element type that's
affected by an exclusion; for example:

	<!DOCTYPE MYDOC [
	    <!ELEMENT P 	- - (#PCDATA|X|Y|Z)*	>
	    <!ELEMENT STUFF 	- - (P+)		>
	    <!ELEMENT BOTHER	- - (P+) -(X)		>
	    <!ELEMENT MYDOC	- - (STUFF|BOTHER)*	>
	]>

becomes:

	<!DOCTYPE MYDOC2 [
	    <!ELEMENT P 	- - (#PCDATA|X|Y|Z)*	>
	    <!ELEMENT PinBOTHER	- - (#PCDATA|Y|Z)*	>
	    <!ELEMENT STUFF 	- - (P+)		>
	    <!ELEMENT BOTHER	- - (PinBOTHER)+	>
	    <!ELEMENT MYDOC	- - (STUFF|BOTHER)*	>
	]>

but this is *not* equivalent to the first DTD.  You could I
suppose follow it up with an architectural transformation:

	<!ATTLIST PinBOTHER
	    MYDOC	NAME #FIXED "P"
	>

Then the set of documents conforming to MYDOC2 will, after
architectural processing, be equivalent to the set of documents
conforming to MYDOC.


>However, that may be so clumsy that it makes a difference in real life.

Definitely :-)  In the worst case, the new DTD can end up with N*M
element types, where N is the number of element types in the original
DTD and M is the number of different potentially applicable exclusion
exceptions.

When it comes to inclusion exceptions, strictly speaking it's not
even possible to create a superset DTD because of the interaction
between inclusion exceptions and record ends.  However, in the common
case where those special-case semantics are not essential (or even
desired), it is possible to create a superset DTD by adding the
included subelements to the content models of all potentially
affected element types:


	<!DOCTYPE MYDOC3 [
	    <!ELEMENT P 	- - (#PCDATA|Y|Z)*	>
	    <!ELEMENT STUFF 	- - (P+) +(X)		>
	    <!ELEMENT BOTHER	- - (P+) 		>
	    <!ELEMENT MYDOC	- - (STUFF|BOTHER)*	>
	]>

becomes:

	<!DOCTYPE MYDOC4 [
	    <!ELEMENT P 	- - (#PCDATA|Y|Z | X)*	>
	    <!ELEMENT STUFF 	- - (P+) 		>
	    <!ELEMENT BOTHER	- - (P+) 		>
	    <!ELEMENT MYDOC	- - (STUFF|BOTHER)*	>
	]>


Then every document that's legal under MYDOC3 is also legal under
MYDOC4, but the converse is not true since MYDOC4 allows X in P
in BOTHER but MYDOC3 does not.

Beware, though, that this transformation -- adding included elements
to all affected content models -- is not always straightforward.
SEQ and AND groups are tricky, and if an inclusion is also legal
as a proper subelement you have to be particularly careful.

>> 2.c. Are there document types that can be defined by a DTD with exceptions,
>> but not by a DTD without exceptions?
>
>No.

This is absolutely correct, with the caveat that in the DTD without
exceptions some constraints must be expressed informally.



--Joe English

  jenglish@crl.com