A formal language model for detecting ambiguity in SGML
R. W. Matzen · SHAREOK (University of Oklahoma; Oklahoma State University; Central Oklahoma University) · 1993
Scope and method of study. The Standard Generalized Markup Language (SGML) is an international standard for document definition, ISO 8879. Authors define documents using a set of rules called a document type declaration, more commonly called a document type definition or DTD. This study involved the syntax productions defining DTDs, the components of DTDs that affect the high level syntax of documents defined by DTDs, the definitions of ambiguity in the standard, and related areas of formal language theory. The optional SGML features, DATATAG, RANK, and SHORTTAG were not considered. The definitions of ambiguity in the standard were revised. A formal language model was developed for DTDs that applies in two ways: it can be used to recognize DTDs and to recognize the class of documents defined by a DTD (the document instances). Using this language model, algorithms were developed for detecting ambiguity under the revised definitions, and proofs of correctness were developed for these algorithms. An algorithm was also developed for examining how exceptions affect model groups in a DTD; this algorithm was used to include exceptions in the language model for document instances. Findings and conclusions. The revised definitions of ambiguity formalize the existing definitions, they are consistent with them where feasible, and they distinguish the kinds of ambiguity that can occur in DTDs. Thus, they will resolve questions in the SGML community regarding ambiguity. The language model for document instances is the first static language model shown that includes omitted tag minimization and exceptions. Using this language model, ambiguity caused by omitted tags can be detected while parsing the DTD. The language model will be a useful tool that resolves important open problems in implementing SGML: it can be used to parse DTDs, to detect and prevent ambiguity as prohibited by the standard, and to remove useless and inaccessible elements from a DTD.