W3C home > Mailing lists > Public > xmlschema-dev@w3.org > October 2012

Re: Order indicators in the .xsd file

From: Liam R E Quin <liam@w3.org>
Date: Thu, 18 Oct 2012 13:03:42 -0400
To: Michael Kay <mike@saxonica.com>
Cc: xmlschema-dev@w3.org
Message-ID: <1350579822.13689.119.camel@localhost.localdomain>
On Thu, 2012-10-18 at 09:48 +0100, Michael Kay wrote:

> In practice, enumerating the different permutations to permit all 
> possible orderings of 24 elements, some of which can be repeated, is 
> impossible on the kind of computers that are available for purchase 
> today, whatever the computer science theory might say.

We faced this problem when I worked at SoftQuad - SGML had an "&"
operator, and someone who wrote
<!Element test - - (a & b & c & d & e & f & g & h & i)>
found Author/Editor (and/or Rulesbuilder) needed 9! states in its finite
state machine.

Peter Sharpe gave a mathematician friend of his a week's stay on
vacation at his home in exchange for a solution to the problem that
operated in linear time, and this was incorporated into Author/Editor
with considerable success.

But it was not as simple as it might sound, because & interacted with
all of the other operators and SGML rules, so e.g. you could write
things like
<!Element hopeless - - ((a | (b & (c|e))) & (d,a)+) -c>
or even include #PCDATA in there...

Liam

-- 
Liam Quin - XML Activity Lead, W3C, http://www.w3.org/People/Quin/
Pictures from old books: http://fromoldbooks.org/
Ankh: irc.sorcery.net irc.gnome.org freenode/#xml
The barefoot typographer - http://www.holoweb.net/~liam/
Received on Thursday, 18 October 2012 17:05:01 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 23:16:02 UTC