SGML & XML Content ModelsPekka Kilpeläinen: SGML & XML Content Models. Report C-1998-12, Department of Computer Science, University of Helsinki, May 1998. 16 pages. <http://www.cs.helsinki.fi/TR/C-1998/12> Full paper: gzip'ed Postscript file AbstractThe 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. Index Terms
Categories and Subject Descriptors:
General Terms: Algorithms Additional Key Words and Phrases: SGML, XML, content model, regular expression, determinism, unambiguity, deterministic automaton, analysis |
Online Publications of Department of Computer Science, Anna Pienimäki