[This local archive copy is from the official and canonical URL, http://www.cs.helsinki.fi/TR/C-1998/12/; please refer to the canonical source document if possible.]

UNIVERSITY OF HELSINKI
DEPARTMENT OF COMPUTER SCIENCE
P.O.BOX 26 (TEOLLISUUSKATU 23), FIN-00014 UNIVERSITY OF HELSINKI, FINLAND


SGML & XML Content Models

Pekka Kilpeläinen

University of Helsinki, Department of Computer Science
Report C-1998-12, May 1998
16 pages
http://www.cs.helsinki.fi/TR/C-1998-12/

Abstract

The SGML and XML standards use a variation of regular expressions called content models for modeling the markup structures of document elements. SGML content models may include so called and groups, which are excluded from XML. An and group, which is a sequence of subexpressions separated by an &-operator, denotes the sequential catenation of its subexpressions in any possible order. If one wants to shift from SGML to XML in document production, one has to translate SGML content models to corresponding XML content models.

The allowed content models in both SGML and XML are restricted by a requirement of determinism, which means that a parser recognizing document element contents has to be able to decide without lookahead, which content model token to match with the current input token, while processing the document from left to right. It is known that not all SGML content models can be expressed as an equivalent XML content model. It is also known that transforming an SGML content model into an equivalent XML content model may cause an exponential growth in the length of the content model. We discuss methods of eliminating and groups and analyze the circumstances where they can be applied. We derive a tight bound of e n! on the number of symbols in the result of eliminating an and group of n symbols, where e = 2.71828... is the base of natural logarithms. We present the analysis in a pedagogical manner, emphasizing mathematical methods which are typical to the analysis of algorithms. We also show that minimal deterministic automata for recognizing an and group of n distinct element names contain 2n states and n 2n-1 transitions, excluding the failure state and transitions leading to it.

CR Categories and Subject Descriptors:

F.4.3 [Mathematical logic and formal languages]: Formal languages.
I.7.2 [Text processing]: Document Preparation.
General Terms: Algorithms

Keywords: SGML, XML, content model, regular expression, determinism, unambiguity, deterministic automaton, analysis

Full report as a GNU-zipped Postscript file (67 kB)