Again wit da AND and Repetitions

[roddey at us.ibm.com]

I never really had any one say whether they thought that validation that
included both AND connectors and M to N repetition for any of the connectors is
feasible (meaning fast and compact and maintainable and verifiable in my
opinion, but tell me if you disagree.)

Does anyone believe that these can be done in less than brute force tree search
times? Is any combination of trees with some nodes which are traditional DFAs
make any sense? Are there any even theoretical discussions of such things out
there anywhere for folks to study? Give that these are both stated goals of
Schema, if they are not feasible that's an issue that should be discussed early.
If they are feasible, then we can get on with it and not waste time arguing.

I personally am not a big theoretical data structures person, or even a little
one for that matter. I'm an object infrastructure person who just happens to be
doing XML right now. So, from my perspective, I'm pretty concerned that the
Schema spec, as stands, might require a doctoral thesis to implement a validator
for that performs reasonably well. Am I just being paranoid and there is really
a "XML Structural Validation With ANDs and NtoMs for Dummies" out there
somewhere? If there is such a thing, could it be made to perform even within say
20% of the DFA based state machine of existing XML parsers?

What are the feelings of some folks who implemented SGML validators? If you had
to start with that and add NtoM repetition on top of that, where would that have
taken you? Or did SGML already provide both of these things? If so, what was the
general architecture used in some common ones? Why is the sky blue?

Sorry for all the questions, but this is just an area where I don't have very
much understanding and hope that there is some lingering SGML based wisdom in
these areas that could be shared, or that perhaps some of you are big
theoretical data structures folks who would like to expound on this subject for
our enlightenment.

TIA for any light shed.



xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev at ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/ and on CD-ROM/ISBN 981-02-3594-1
To (un)subscribe, mailto:majordomo at ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo at ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa at ic.ac.uk)