Introduction
Most applications need to save some configuration data, and often need to transmit or receive data to or from other applications. This is especially true for software that interacts with the Internet. If you need a format for interchanging such data, one solution is to design your own binary format. Using binary formats allows you to store complex structures, lists, arrays, etc., but also has some drawbacks. Your binary format will be proprietary and not easy to use or understand. If you need to modify it, you may face compatibility problems; for instance, the offset of a particular piece of data may have changed. As an alternative, you could use a text-based format. Some examples are comma-separated files, Microsoft .INI files, etc. These kinds of files are easy to use and understand (just use a text editor — no fancy binary editor) but they are not very powerful. You can store integers or text, but more complex structures like arrays or lists are a problem.
XML provides a more general solution. It's a text-based, hierarchical format that has the advantage of both the binary and text-based worlds. It's easy to use but is also powerful. Even if it was primarily designed for the Web, it can be used for any application that needs to store data or communicate with other applications. This article presents a simple XML parser that implements a subset of the XML specification. The goal is not to have the best or the most complete XML parser, but simply to have one — as small and as easy-to-use as possible.
What is XML ?
XML means "Extensible Markup Language" and is a subset of SGML (more on SGML later). To be more concrete, the following snippet shows the overall form of an XML document.
<?xml version="1.0"?>
<!— List of towns —>
<townlist>
<town id="geneva">
<name>Geneva</name>
<state>GE</state>
<lang>French</lang>
</town>
<town id="zurich">
<name>Zurich</name>
<state>ZH</state>
</town>
</townlist>
Following are the various parts of this snippet in terms of the XML features it illustrates.
Elements
An XML document contains elements. Examples from the snippet are townlist, town, state, and country. A start tag and an end tag delimit each element. A start tag begins with a < character followed by a name (the type of the element, which is also called the "generic identifier") and ends with a >. An end tag is similar except that it begins with </ instead of <. The name in a start tag must match the name in the end tag.
Content
Anything between the tags is the content of the element. The content itself can consist of data and/or other elements. If an element has no content, it's possible to replace the start/end tag pair with an empty tag. An empty tag is similar to a start tag but ends with />: <abc></abc> and <abc/> are equivalent.
Attributes
A tag can also contain one or more attributes. An attribute has a name and a value separated by an equal sign. An attribute value must always be enclosed by a pair of ' or " delimiters. This is different from HTML, which allows some kinds of attribute values to have no enclosing delimiters.
Hierarchy of Elements
Since an element can contain other elements, they form a hierarchy. In the above example, the element townlist has two children of type town. The first town element has three children and the second town element has two. Each XML document must have one and only one root element. A root element is an element without a parent, and it contains all other elements. In my example, townlist is the root element.
XML Declaration
Though not absolutely required, it's preferable to begin XML documents with a XML declaration such as <?xml version ="1.0"?>. This declaration indicates the version of XML being used, helps identify the document and its encoding (see the sidebar entitled "Unicode and Alternate Character Encodings"), and includes additional useful information.
Markups
Prologs and tags are called markups. There are other kinds of markup: comments, entity references, character references, CDATA sections, processing instructions, and document type declarations. I cover only comments, entity references, and character references in detail here.
Comments are similar to HTML comments. They begin with <!-- and end with -->. For compatibility with SGML, the string -- (double hyphen) is not allowed within comments.
Sometimes you may need to use the character < in the content of an element. But since this character delimits markups in XML, it is not allowed for other purposes. To use it as part of an element's content, you can use an escape, either a character reference (like < or <) or an entity reference (like <). References are delimited by & and ;. Character references give either a decimal (<) or hexadecimal (<) representation of the character. Entity references use a name instead of a numerical value. There are five predefined entities: lt (for <), gt (for >), amp (for &), apos (for ') and quot (for ") You can define your own, but that subject is out of the scope of this article.
The remaining markups I cover only briefly here. CDATA sections are used to escape blocks of text containing characters that would otherwise be recognized as markups. CDATA sections begin with <![CDATA[ and end with ]]>. Processing instructions are similar to pragmas in C/C++. They allow XML documents to contain parser instructions. They begin with <?, are followed by a name (called a "target"), and end with ?>. The target xml is reserved (and is used in particular in XML prologs).
DTDs (Document type declarations) represent the most difficult part of XML. DTDs can be seen as a language by itself inside of XML. A DTD declaration begins with <! and ends with >; for example, <!ELEMENT town (name, state, lang?)>. Unlike in SGML, DTDs are optional in XML.
Well Formed versus Valid XML
A DTD defines the rules of an XML document. Using a DTD, a parser can determine if the document is valid. In fact, there are two complementary types of correct XML documents: well formed and valid. A XML document is well-formed if it follows the previously described syntax. Thus, if you make a mistake and type two < instead of one at the beginning of a markup, your document is not well formed. This is also true if it has no root element. Validity is a different concept. A valid XML document must follow a given logical structure. In the previous example, the DTD specifies that a town element begins with a name element, followed by a state element, and optionally ends with a lang element.
Even if XML DTDs are simpler than SGML DTDs, they remain difficult to understand and to handle especially because they use a different syntax than the remainder of XML. Some efforts are currently being made to replace DTDs by a new syntax called XML schema (or DDML, or XML-Data, etc.), using XML itself to describe the semantic of documents. But this work is still in progress.
The Big Picture: HTML, SGML, XLS, ...
W3C (World Wide Web Consortium) is the international standards group for the World Wide Web, funded by its industrial members but operated principally by MIT (the Massachusetts Institute of Technology), INRIA (the Institut National de Recherche en Informatique et Automatique), and CERN (the Center for European Particle Research). Its website (www.w3c.org) contains all the material (standards, drafts, etc.) concerning the Web and XML in particular.
SGML (Standard Generalized Markup Language) is the international standard (ISO 8879) for defining descriptions of structure and content in electronic documents. Almost all other tag languages such as XML and HTML are derived from SGML. Furthermore, XML is in fact a subset of SGML and every XML document is also an SGML document. (Some people are contesting this assertion.)
HTML (Hypertext Markup Language) is a tag language for representing documents with hypertext links. Even though XML and HTML documents may look similar, they have a major difference: XML documents contain data while the goal of HTML is to present data to the user with a given color, font, etc. However, XML and HTML are related, in particular through XLS.
XLS (Extensible Stylesheet Language) is a bridge between XML (data) and HTML (presentation). It is an XML grammar used to transform XML documents into HTML (or other XML) documents. For example, you may want to display the townlist of the previous example in a browser as a table. With XLS you decide which element will appear as the title of columns, the color and the font, which element will be put in the first column, etc. Using the same XLS template, you can display several XML documents with a similar presentation. XLS can also be used to manipulate, sort, and filter XML data. It is still a working draft.
XLink describes links between objects using XML, from simple unidirectional hyperlinks of today's HTML to more sophisticated multi-ended and typed links. It is currently a working draft.
XPointer, as its name implies, describes a kind of pointer to elements in an XML document. It is also a working draft.
DDML (Document Definition Markup Language) is a schema language for XML documents. It has been influenced by another proposal called XML-Data. It encodes the logical (as opposed to physical) content of DTDs in an XML document. Be careful, it is for the moment only a submission to W3C. It will probably change a lot before becoming a proposition, or may even disappear.
XSchema is the former name for DDML.
DOM (Document Object Model) is a platform- and language-neutral interface that allows programs and scripts to dynamically access and update the content, structure, and style of XML or HTML documents. DOM level 1 is a W3C recommendation.
XML Namespaces provide a simple method for qualifying element and attribute names used in XML documents to avoid name collisions (when the same name is used for different puposes). Namespaces are now a W3C recommendation.
SAX (Simple API for XML) is a standard interface for event-based XML parsing, developed collaboratively by the members of the XML-DEV mailing list. An event-based API reports parsing events (such as at the start and end of elements) directly to the application through callbacks.
It's impossible to give here an exhaustive list of all works around XML, as it is moving fast. To find out the current status of these works, visit the W3C website at www.w3c.org/TR.
XML Parsers
There are two classes of XML parsers: validating and non-validating. All true XML parsers must report violations of the XML specification constraints for being well-formed. Validating parsers must also report violations of the constraints expressed by the declarations in the DTD. Validating parsers must process and use the entire DTD. Non-validating parsers are required only to check that the DTD is well-formed. They are not required to understand and use the DTD for document checking. There are some exceptions, however, in particular, for attributes.
Several parsers are currently available on the Web. A non-exhaustive list follows.
Expat is a non-validating XML 1.0 parser written in C by James Clark. This is the parser being used to add XML support to Netscape 5 (Mozilla). Expat is subject to the Mozilla Public License Version 1.0. See www.jclark.com/xml/expat.html for more information.
SP is a validating XML and SGML parser, written in C++ by James Clark. It is complete and powerful, but is also complex. At the time of this writing, there are no usage restrictions, even for commercial use. See www.jclark.com/sp/.
XP is another non-validating XML parser written by James Clark, but this time in Java 1.1. You can download it from ftp://ftp.jclark.com/pub/xml/xp.zip. This is a beta-test version.
AElfred is a non-validating XML parser from Microstar written in Java. It uses only JDK 1.0.2 features and it is very portable. AElfred is free for both commercial and non-commercial use. You can download it from www.microstar.com/aelfred.html
Microsoft Internet Explorer 4 includes a non-validating XML parser (also called XML Parser in C++). A validating parser (MSXML) written in Java has replaced it and is integrated in Internet Explorer 5. (In fact, it is integrated in the latest Microsoft Java VM, which is available at www.microsoft.com/java/.)
There are numerous parsers available, many written in Java. A list partial list is available at www.w3.org/XML, under XML Software, and at www.xml.com.
A Simple XML Parser
To illustrate the concepts presented in this article, I wrote a simple non-validating XML parser. It recognizes only a subset of the XML specification. It is easy to understand and use in your own applications.
The Grammar Supported
Once again, here's the example from the beginning of the article:
<?xml version="1.0"?>
<!— List of towns —>
<townlist>
<town id="geneva">
<name>Geneva</name>
<state>GE</state>
<lang>French</lang>
</town>
<town id="zurich">
<name>Zurich</name>
<state>ZH</state>
</town>
</townlist>
In this example, there are elements (start and end tags), attributes, and comments. It's a typical example of what my simple parser is able to recognize. The snippet contains no DTDs, no processing instructions, and no CDATA sections. References are mandatory because without them, you have no way to include special characters or even < and &. My parser implements character references and predefined entity references. Figure 1 shows a formal representation of the grammar implemented by my parser. (The grammar is presented in EBNF, or Extended Backus-Naur Form).
The API
The API is divided into two categories: a set a functions to extract a given value from the XML document, and a set of functions to enumerate the elements. Given the sample XML snippet, you extract the name of the first town with the code in Figure 2. The syntax is a little odd at first. I simply define an operator() in XmlElement that returns another XmlElement. Note that there is no point between the parentheses. I choose this syntax because it is very compact. Figure 3 is an example of element enumeration. I have implemented enumeration using STL containers.
But what happens if an element is not there? In such a situation, there are several options: throw an exception, return false or NULL, etc. I've chosen a variation on the latter. Instead of returning NULL, I return a null element (Element::null), which is a real object. This way root("town", 0)("name").GetValue() is safe even if there is no town element.
The Code
This parser uses C++ STL. I use the STL implementation from Silicon Graphics (v3.12 at the time of this writing) because it is quite good and is available on several platforms. The code was compiled with Microsoft Visual C++ 6.2 SP2 and with GNU g++ (from Cygnus), but is probably portable on any platform with a compiler that isn't too old. (The compiler must support at least exceptions, templates, and namespaces.)
The code is divided into four files. XmlReader.h contains all the declarations. There is a class for each type of Element (Tags, Comments, etc.) and two classes for attributes and values (content of elements). The major class is of course Parser. To avoid name clashes, all these classes are declared in a namespace (SimpleXMLParser). XmlReader.inl contains inline functions. The other two files, XmlReader.cpp and XmlElements.cpp contain the code itself. XmlElements.cpp is the implementation of the classes Element, Attribute, etc. XmlReader.cpp is the parser itself. It follows the grammar as much as possible (see Figure 1) and avoids clever tricks in favor of readability.
Conclusion
As you can see, XML is not the successor of HTML. On the contrary, XML is complementary to HTML and avoids mixing data with presentation. XML is beginning to take on more and more importance and some new protocols are now based on it. Even if it is now a W3C recommendation (and as such is very stable) it continues to evolve.
If you need a small parser in your application to store data or communicate with other applications, the parser presented here can be a good starting point. Except for DTDs, missing markups can easily be added. If this parser interests you, check my website at www.sebweb.org/Software/Xml.htm for an enhanced version. You can also choose one of the many other parsers I listed in this article.
References
John Bosak. "XML, Java, and the Future of the Web,'' March 1997.
http://sunsite.unc.edu/pub/sun-info/standards/xml/why/xmlapps.htm.
Document Object Model (DOM) Level 1 Specification, www.w3.org/TR/REC-DOM-Level-1.
Extensible Markup Language (XML) 1.0, www.w3.org/TR/REC-xml.
ISO/IEC 10646-1993. "Universal Multiple-Octet Coded Character Set (UCS) — Part 1: Architecture and Basic Multilingual Plane.''
David Meggison, et al. The XML Revolution, May 1998. http://helix.nature.com/webmatters/xml.html.
David Megginson. Structuring XML Documents (Prentice Hall PTR, 1998).
Namspaces in XML, www.w3.org/TR/REC-xml-names.
The Unicode Consortium. The Unicode Standard, Version 2.0 (Addison-Wesley, 1996).
The XML FAQ, www.ucc.ie/xml.
Sebastien Andrivet is a software developer specializing in Windows programming. He currently works at FotoWire Development S.A. He can be reached at [email protected]; you can visit his website at www.sebweb.org.
