One way to think of it is that it is a bit like a generalized programming language. Programming languages are typically described formally by grammars. Tools such as YACC allow programmers to describe grammers and then generate code to validate programs against the grammar. An XML validator is a bit like that except that the YACC part of the process happens "on the fly".
The best place to look if you are interested in XML validators is the branch of computer science that deals with parsing. The classic text is the "dragon book" by Aho and Ullman ( http://www.jargon.net/jargonfile/d/DragonBook.html).