The validation of SGML content models

✍ Scribed by A. Brüggemann-Klein; D. Wood

• Book ID: 104351522
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 990 KB
• Volume: 25
• Category: Article
• ISSN: 0895-7177
• DOI: 10.1016/s0895-7177(97)00025-3

✦ Synopsis

Standard Generalized Markup Language (SGML) is an IS0 standard that prcc vides a syntactic meta-language for the definition of textual markup systems, which are used to indicate the structure of documents so that they can be electronically typeset, searched, and communicated. We address only one problem raised by the standard, namely: in SGML, the right-hand sides of context-free productions are regular expressions, called content models, that are restricted to be what the standard calls "unambiguous," but what is more appropriately called deterministic. We solve the problem of how to define determinism precisely, how to recognize deterministic regular expressions efficiently, and how to recognize deterministic regular languages. Any SGML parser must check that a given document grammar conforms to the standard; that is, it must validate it.. Hence, our results are an important step in the clarification of the standard and in the efficient implementation of an SGML parser for SGML document grammars.