Redefining the XML language

About this document

This document redefines the production rules of the XML Recommendation 1.0 (http://www.w3.org/TR/1998/REC-xml-19980210/). We provide a listing of the Recommendation's original production rules, well-formedness constraints and validating constraints at http://www11.in.tum.de/~brueggem/XML/Recommendation/xmlRules.xml (XML format) and at http://www11.in.tum.de/~brueggem/XML/Recommendation/xmlRules.htm (HTML format).

The XML Recommendation writes grammar symbols with an initial capital letter if they are "defined by a regular expression", otherwise with an initial lower-case letter. We capitalize all grammar symbols and also all semantically meaningful subwords of grammar symbols; for example, document is renamed Document and Nmtoken is renamed NmToken. We achieve this by referring to grammar symbol XXX by an entity reference &XXX; that expands to <nt def="NT-XXX">XXX</nt>, so the capitalization is easily reversed by redefining these entities.

We demonstrate that an XML processor (also called an XML parser) can be built using well-proven compiler-construction techniques, in particular dividing the task into lexical analysis aka tokenization, syntax analysis, semantic analysis and code generation.

As a first step, we assign categories to the XML production rules. The XML grammar defines a language of strings over the alphabet of Unicode characters. We categorize XML's production rules so that their role with respect to lexical and syntactic analysis becomes apparent. We use the following categories:

Character level: Rules that operate at the character level define sets (or classes) of Unicode characters.

Token level: Rules that operate at the token level define regular languages over the alphabet of Unicode characters, which we call token classes. Token-level rules may refer to character-level rules.

Syntax level: Rules that operate at the syntax level define context-free languages over the alphabet of token classes.

The XML Recommendation uses three grammar symbols as start symbols, namely Document to define the class of well-formed or valid XML documents, ExtParsedEnt to define the class of well-formed external parsed entities (fragments of document instances) and ExtPE to define the class of well-formed external parameter entities (fragments of DTDs). The "orphaned" productions [6], [8], [33], [34], [35], [36], [37], [38] of the XML Recommendation cannot be reached from any of the three start symbols. The XML Recommendation uses these rules to pose additional constraints on XML documents, that belong to the semantic-analysis phase of XML processing. We keep them out of the grammar, which deals with the syntax-analysis phase of XML processors.

We rewrite some rules of the XML grammar, so that character strings in grammar-level rules are turned into tokens. This leads to additional token-level rules.

The character-level rules

The token-level rules

The syntax-level rules

Discussion

It is now easy (though tedious) to verify that the character-level rules denote character sets, that the token-level rules denote regular languages and that the syntax-level rules denote context-free languages of token classes. Again it is easy (though tedious) to verify that we have applied the following rules to the original XML productions:

1. In grammar-level rules, we have replaced some regular subparts of the right-hand sides with token classes. These token classes have token-level rules without an XML number, indicated by [-] in the second column of the rule definitions.

2. We have rewritten the token-level rules for Eq as Eq ::= '='. The original XML production is Eq ::= S? '=' S?. Consequently, we have replaced each Eq token in a right-hand side of a production with S? Eq S. We made this change so that white space that is represented by grammar symbol S can be used as token separator in the lexical-analysis phase and be removed from the syntax-level rules.

Obviously, these transformations preserve languages.

Analyzing the productions