Gerd Mueller wrote:
Hi,
Is there any documentation/example or something like that for doing the following:
Parse an XML Schema file and find out which elements can be inserted as children for a given parent element and a given list of already existing children for that element.
I know that this is done already in the Xerlin XML editor, but
perhaps somebody can give some more concise examples than the Xerlin code.
The brute-force algorithm:
1. Using a DFA or equivalent, parse the document until you reach the state at which the element is to be inserted. The transitions from this state are the maximal set of elements allowed.
2. Selecting each element in the maximal set in turn, determine if there is a valid sequence beginning with that element at the state reached in (1) that ends with the elements following the insertion point that already exist in the document. The ones that pass this test are the exact set of elements allowed.
Unfortunately, this algorithm has exponential complexity, so most editors report only (1).
(The complexity is the same, but the practical cases are a bit faster for XML Schema and DTDs, since (2) only needs to consider the following siblings of the inserted element rather than the entire document, as RELAX NG would require. There are also a number of simplifying special cases. If the insertion point is at the top level of an iterated choice, e.g., (a|b|...)*, (1) gives the right answer. If the insertion point is at the top level of an unambiguous sequence, e.g., (a, b,...), only the next element needs to be tested. Etc.)
Bob Foster
--------------------------------------------------------------------- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
