Tom Anderson
Usenet Archive
- Joined
- Aug 22, 2003
- Messages
- 2,716
- Reaction score
- 0
Afternoon all,
Call me mad, but i'm interested in writing an XML validator. Not as part of a parser, but operating on DOM-like objects in a program. Basically, i want to write a function createElement that looks a bit like:
Node a, b, c; // create these somehow
Element list = createElement("xhtml
", new Node {a, b, c});
Where createElement is able to determine whether {a, b, c} is a valid sequence of child elements for an xhtml
element, and so throw an exception of something if it isn't.
The idea would be to parse a DTD in order to create objects representing the content model, then use those to validate the nodes.
The XML spec says:
More formally: a finite state automaton may be constructed from the content model using the standard algorithms, e.g. algorithm 3.5 in section 3.9 of Aho, Sethi, and Ullman [Aho/Ullman]. In many such algorithms, a follow set is constructed for each position in the regular expression (i.e., each leaf node in the syntax tree for the regular expression); if any position has a follow set in which more than one following position is labeled with the same element type name, then the content model is in error and maybe reported as an error.
Firstly, roughly how hard is this? Expressed in, say,
milli-Dijkstra's-algorithms - 5000? 20 000? 100 000?
Secondly, i'm not keen to rush out and buy Aho et al's no doubt wonderful book on compilers just so i can do this. Can anyone direct me to anything i can read online where i can learn about this? That could be in English or source code - presumably, there are numerous open-source projects which have implemented XML validators, right?
It occurs to me that i could avoid having to write the validator myself by using a grotesque hack - if i can map node types to strings, i can express a node sequence as a string, and a content model as a regular expression, and then just let a standard regexp library do the heavy lifting. In python, operating on standard DOM objects:
def validateAsParagraph(nodelist):
nodeString = "".join(map(lambda node: "<" + node.nodeName + ">", nodelist)) pPattern = re.compile("(?:<(?:#PCDATA|br|span|bdo|map|tt|i|b|big|small|em|strong|dfn|code|q|samp|kbd|var|cite|abbr|acronym|sub|sup|input|select|textarea|label|button|ins|del|script)>)*") m = pPattern.match(nodeString) return (m != None) and (m.end == len(nodeString))
I can't decide if this is brilliant or revolting, or both.
tom
Call me mad, but i'm interested in writing an XML validator. Not as part of a parser, but operating on DOM-like objects in a program. Basically, i want to write a function createElement that looks a bit like:
Node a, b, c; // create these somehow
Element list = createElement("xhtml
Where createElement is able to determine whether {a, b, c} is a valid sequence of child elements for an xhtml
The idea would be to parse a DTD in order to create objects representing the content model, then use those to validate the nodes.
The XML spec says:
More formally: a finite state automaton may be constructed from the content model using the standard algorithms, e.g. algorithm 3.5 in section 3.9 of Aho, Sethi, and Ullman [Aho/Ullman]. In many such algorithms, a follow set is constructed for each position in the regular expression (i.e., each leaf node in the syntax tree for the regular expression); if any position has a follow set in which more than one following position is labeled with the same element type name, then the content model is in error and maybe reported as an error.
Firstly, roughly how hard is this? Expressed in, say,
milli-Dijkstra's-algorithms - 5000? 20 000? 100 000?
Secondly, i'm not keen to rush out and buy Aho et al's no doubt wonderful book on compilers just so i can do this. Can anyone direct me to anything i can read online where i can learn about this? That could be in English or source code - presumably, there are numerous open-source projects which have implemented XML validators, right?
It occurs to me that i could avoid having to write the validator myself by using a grotesque hack - if i can map node types to strings, i can express a node sequence as a string, and a content model as a regular expression, and then just let a standard regexp library do the heavy lifting. In python, operating on standard DOM objects:
def validateAsParagraph(nodelist):
nodeString = "".join(map(lambda node: "<" + node.nodeName + ">", nodelist)) pPattern = re.compile("(?:<(?:#PCDATA|br|span|bdo|map|tt|i|b|big|small|em|strong|dfn|code|q|samp|kbd|var|cite|abbr|acronym|sub|sup|input|select|textarea|label|button|ins|del|script)>)*") m = pPattern.match(nodeString) return (m != None) and (m.end == len(nodeString))
I can't decide if this is brilliant or revolting, or both.
tom