Hardware accelerated validating parser Number:7,080,094 from the United States Patent and Trademark Office (PTO) owispatent

Title: Hardware accelerated validating parser

Abstract: A hardware accelerated validation parser is provided to remove a large portion if not all of the processing and overhead burden of validation parsing from a host processor by parallel access to both a state table and a data dictionary based on a token and merging and selective redirection of the respective outputs thereof; a portion of a transition control word (TCW) formed by the merged data being used to advance through the state table and a portion of the TCW being used to control formation of a tree structured data object (TSDO) corresponding to a text document in a language such as XML.TM. which supports interoperability and platform independence. A stack is provided to accommodate nesting of elements and aggregate elements. The formation of the TSDO can be and preferably is performed asynchronously and autonomously in parallel with the validation parsing.

Patent Number: 7,080,094 Issued on 07/18/2006 to Dapp,   et al.

---

Inventors:	Dapp; Michael C. (Endwell, NY); Lett; Eric C. (Endwell, NY); Ng; Sai Lun (Vestal, NY)
Assignee:	Lockheed Martin Corporation (Bethesda, MD)
Appl. No.:	334086
Filed:	December 31, 2002

---

Current U.S. Class:	707/102
Current International Class:	G06F 17/30 (20060101)
Field of Search:	707/1-10,100-104.1,200-206 715/513,531,501.1

---

References Cited [Referenced By]

---

U.S. Patent Documents

	4279034		July 1981		Baxter
	4527270		July 1985		Sweeton
	4556972		December 1985		Chan et al.
	4622546		November 1986		Sfarti et al.
	4879716		November 1989		McNally et al.
	5003531		March 1991		Farinholt et al.
	5027342		June 1991		Boulton et al.
	5193192		March 1993		Seberger
	5214778		May 1993		Glider et al.
	5247664		September 1993		Thompson et al.
	5280577		January 1994		Trevett et al.
	5319776		June 1994		Hile et al.
	5379289		January 1995		DeSouza et al.
	5414833		May 1995		Hershey et al.
	5511213		April 1996		Correa
	5513345		April 1996		Sato et al.
	5600784		February 1997		Bissett et al.
	5606668		February 1997		Shwed
	5621889		April 1997		Lermuzeaux et al.
	5649215		July 1997		Itoh
	5655068		August 1997		Opoczynski
	5666479		September 1997		Kashimoto et al.
	5684957		November 1997		Kondo et al.
	5696486		December 1997		Poliquin et al.
	5737526		April 1998		Periasamy et al.
	5742771		April 1998		Fontaine
	5798706		August 1998		Kraemer et al.
	5805801		September 1998		Holloway et al.
	5815647		September 1998		Buckland et al.
	5832227		November 1998		Anderson et al.
	5848410		December 1998		Walls et al.
	5850515		December 1998		Lo et al.
	5905859		May 1999		Holloway et al.
	5919257		July 1999		Trostle
	5919258		July 1999		Kayashima et al.
	5920698		July 1999		Ben-Michael et al.
	5922049		July 1999		Radia et al.
	5958015		September 1999		Dascalu
	5969632		October 1999		Diamant et al.
	5982890		November 1999		Akatsu
	5991881		November 1999		Conklin et al.
	5995963		November 1999		Nanba et al.
	6000045		December 1999		Lewis
	6006019		December 1999		Takei
	6021510		February 2000		Nachenberg
	6083276		July 2000		Davidson et al.
	6094731		July 2000		Waldin et al.
	6119236		September 2000		Shipley
	6151624		November 2000		Teare et al.
	6167448		December 2000		Hemphill et al.
	6173333		January 2001		Jolitz et al.
	6182029		January 2001		Friedman
	6233704		May 2001		Scott et al.
	6279113		August 2001		Vaidya
	6282546		August 2001		Gleichauf et al.
	6295276		September 2001		Datta et al.
	6301668		October 2001		Gleichauf et al.
	6304973		October 2001		Williams
	6321338		November 2001		Porras et al.
	6363489		March 2002		Comay et al.
	6366934		April 2002		Cheng et al.
	6370648		April 2002		Diep
	6374207		April 2002		Li et al.
	6393386		May 2002		Zager et al.
	6405318		June 2002		Rowland
	6408311		June 2002		Baisley et al.
	6418446		July 2002		Lection et al.
	6421656		July 2002		Cheng et al.
	6446110		September 2002		Lection et al.
	6684335		January 2004		Epstein, III et al.
	6697950		February 2004		Ko
	6792546		September 2004		Shanklin et al.
	6862588		March 2005		Beged-Dov et al.
	2001/0056504		December 2001		Kuznetsov
	2002/0010715		January 2002		Chinn et al.
	2002/0013710		January 2002		Shimakawa
	2002/0035619		March 2002		Dougherty et al.
	2002/0038320		March 2002		Brook
	2002/0059528		May 2002		Dapp
	2002/0066035		May 2002		Dapp
	2002/0069318		June 2002		Chow et al.
	2002/0073091		June 2002		Jain et al.
	2002/0073119		June 2002		Richard
	2002/0082886		June 2002		Manganaris et al.
	2002/0083343		June 2002		Crosbie et al.
	2002/0087882		July 2002		Schneier et al.
	2002/0091999		July 2002		Guinart
	2002/0099710		July 2002		Papierniak
	2002/0099715		July 2002		Jahnke et al.
	2002/0099734		July 2002		Yassin et al.
	2002/0103829		August 2002		Manning et al.
	2002/0108059		August 2002		Canion et al.
	2002/0111963		August 2002		Gebert et al.
	2002/0111965		August 2002		Kuttler
	2002/0112224		August 2002		Cox
	2002/0116550		August 2002		Hansen
	2002/0116585		August 2002		Scherr
	2002/0116644		August 2002		Richard
	2002/0120697		August 2002		Generous et al.
	2002/0122054		September 2002		Hind et al.
	2002/0133484		September 2002		Chau et al.
	2002/0143819		October 2002		Han et al.
	2002/0152244		October 2002		Dean et al.
	2002/0156772		October 2002		Chau et al.
	2002/0165872		November 2002		Meltzer et al.
	2003/0041302		February 2003		McDonald
	2003/0229846		December 2003		Sethi et al.
	2004/0025118		February 2004		Renner
	2004/0073870		April 2004		Fuh et al.
	2004/0083221		April 2004		Dapp et al.
	2004/0083387		April 2004		Dapp et al.
	2004/0083466		April 2004		Dapp et al.
	2004/0172234		September 2004		Dapp et al.
	2004/0194016		September 2004		Liggitt
	2005/0039124		February 2005		Chu et al.
	2005/0177543		August 2005		Chen et al.

Foreign Patent Documents

	2307529		Sep., 2001		CA
	WO 02/11399		Feb., 2002		WO
	WO 02/095543		Nov., 2002		WO

Other References

B Trippe; "XML Hits the Big Time: Major Database Player get into XML"; Find articles.com; Sep. 2002; pp. 1-9. cited by other . Business Wire, Bellevue, Wash; "DataChannel Releases the Most Advanced XML Parser--XJParser--and IntriducesxDeve its XML Developers Program"; Find articles.com; Apr. 16, 1999; pp. 1-9. cited by other . InfoWorld; "Extensible Markup Language (XM:). (Technology Information)"; Find articles.com; Jun. 1998; pp. 1-6. cited by other . T. Yager; "New Standards Orbit(XML) (Technology Information)"; Findarticles.com; Jul. 2000; pp. 1-9. cited by other . Microsoft Corp.; "XML: Enabling Next-Generation Web Application"; Dytech Solutions; Apr. 1998; pp. 1-15. cited by other . A.B. Kulkarni; S.F. Bush and S.C. Evans "Detecting Distributed Denial-of-Service Attacks Using Kolmogorov Complexity Metrics" dated Dec. 2001. cited by other . S.C. Evans and S.F. Bush "Symbol Compression Ratio for String Compression and Estimation of Kolmogorov Complexity" dated Nov. 2001. cited by other . Andrivet et al., "A Simple XML Parser", Jul. 1999, C/C++ Users Journal, R&D Publications, Lawrence, KS., US, pp. 22,24,26-28,30,32, XP008015172, ISSN: 1075-2838. cited by other . Cooper, C, "Using Expat", Sep. 1, 1999, XP002177815. cited by other . M. Neumann; "Encryption Black Box(SiNic)"; ESNET Steering Committee Meeting, Sep. 11-13, 2001. cited by other . E. Zadok; "Stackable File Systems as a Security Tool"; Technical Report CUCS-036-99 Columbia University Computer Science Department; Dec. 1999; pp. 1-19. cited by other . Kent, RFC 2401, "Security Architecture for the Internet Protocol," 1998. cited by other . Fraser et al., "Hardening COTs Software with Generic Software Wrappers"; DARPA Information Survivabilty Conference and Exposition, 2000, pp. 323-337. cited by other . Pal et al., "Open Implementation Toolkit for Building Survivable Applications", DARPA Information Survivability Conference and Exposition, 2000, pp. 197-210. cited by other . Aho, A.V. et al., "Principles of Complier Design", Principals Of Compiler Design, Reading, Addison-Wesley Publishing Co., US., 1979, pp. 73-125, XP002140006, p. 88, line 4 --p. 115, line 7; figures 3.5-3.22. cited by other . Bauer, F.L., "Complier Construction --An Advanced Course", 1976, Springer-Verlag, Germany, XP002312623, pp. 45-55; pp. 85-108. cited by other . Lunteren et al., "XML Accelerator Engine", 2004. cited by other . Sakharov, "Finite State Machine Specification and Generation in Java", 2000, http://sakharov.net/fsm.html. cited by other.

Primary Examiner: Mizrahi; Diane
Attorney, Agent or Firm: Miles & Stockbridge PC Carmichael; James T.

---

Parent Case Text

---

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims benefit of priority of U.S. Provisional Patent Application Ser. No. 60/421,774, filed Oct. 29, 2002, the entire contents of which are hereby fully incorporated by reference. Further, this application is related to U.S. patent applications Ser. No. 10/331,879 and 10/331,315, corresponding to U.S. Provisional Patent applications 60/421,773 and 60/421,775, respectively) which are assigned to the assignee of this invention and also fully incorporated by reference herein.

---

Claims

---

The invention claimed is:

1. A validation parser for a tokenized text document in a computer language supporting platform independence and interoperability, said validation parser comprising, means for retrieving data from both a data dictionary and a state table in accordance with a token, means for merging said data from said state table and said data dictionary to form a transition control word, means for merging part of said transition control word with another token to retrieve further data from said state table, and means for forming a tree structured data object corresponding to said tokenized text document under control of part of said transition control word.

2. The validation parser as recited in claim 1, further including means for controlling operation of a stack with said transition control word to derive the next transition state in supporting nested data structures defined in a supported language.

3. The validation parser as recited in claim 2, further including means for forming a data construct from the tokenized text document.

4. The validation parser as recited in claim 3, wherein said means for forming a data construct includes an element and attribute buffer.

5. The validation parser as recited in claim 1, further including means for forming a data construct from the tokenized text document.

6. The validation parser as recited in claim 5, wherein said means for forming a data construct includes an element and attribute buffer.

7. A computer implemented method of accelerating validation parsing of a tokenized file, said method comprising steps of retrieving data from both a data dictionary and a state table in accordance with a token, merging said data from said state table and said data dictionary to form a transition control word, and merging part of said transition control word with another token to retrieve further data from said state table.

8. The method as recited in claim 7, including a further step of operating a stack with said transition control word to derive the next transition state.

9. The method as recited in claim 7, including a further step of verifying that an input stream conforms to one of a set of valid input sequences.

10. The method as recited in claim 9, including a further step of producing a notification when an input stream deviates from a set of valid, allowable input sequences.

11. The method as recited in claim 7, including a further step of producing a notification when an input stream deviates from a set of valid, allowable input sequences.

---

Description

---

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention generally relates to validating parser processing for parsing and validating documents, such as XML.TM. documents, for use in individual data processors interconnected by a network and, more particularly, to hardware validating processors for acceleration of the validation of such documents.

2. Description of the Prior Art

The field of digital communications between computers and the linking of computers into networks has developed rapidly in recent years, similar, in many ways to the proliferation of personal computers of a few years earlier. This increase in interconnectivity and the possibility of remote processing has greatly increased the effective capability and functionality of individual computers in such networked systems. Nevertheless, the variety of uses of individual computers and systems, preferences of their users and the state of the art when computers are placed into service has resulted in a substantial degree of variety of capabilities and configurations of individual machines and their operating systems, collectively referred to as "platforms" which are generally incompatible with each other to some degree particularly at the level of operating system and programming language.

This incompatibility of platform characteristics and the simultaneous requirement for the capability of communication and remote processing and a sufficient degree of compatibility to support it has resulted in the development of object oriented programming (which accommodates the concept of assembling an application as well as data as a group of more or less generalized modules through a referencing system of entities, attributes and relationships) and a number of programming languages to embody it. Extensible Markup Language.TM. (XML.TM.) is such a language which has come into widespread use and can be transmitted as a document over a network of arbitrary construction and architecture.

In such a language, certain character strings correspond to certain commands or identifications, including special characters and other important data (collectively referred to as control words) which allow data or operations to, in effect, identify themselves so that they may be, thereafter treated as "objects" such that associated data and commands can be translated into the appropriate formats and commands of different applications in different languages in order to engender a degree of compatibility of respective connected platforms sufficient to support the desired processing at a given machine. The detection of these character strings is performed by an operation known as parsing, similar to the more conventional usage of resolving the syntax of an expression, such as a sentence, into its component parts and describing them grammatically.

When parsing an XML.TM. document, a large portion and possibly a majority of the central processor unit (CPU) execution time is spent traversing the document searching for control words, special characters and other important data as defined for the particular XML.TM. specification being processed. This is typically done by software which queries each character and determines if it belongs to the predefined set of strings of interest, for example, a set of character strings comprising the following "<command>", "<data type=dataword>", "</command>", etc. If any of the target strings are detected, a token is saved with a pointer to the location in the document for the start of the token and the length of the token. These tokens are accumulated until the entire document has been parsed.

This process must then be followed by processing in order to evaluate the tokens against rules and definitions contained in a "document model" such as the specification of a document type definition (DTD) or an XML.TM. schema in order to assure that the collection of tokens and the character strings they represent in the document are well-constructed to form an unambiguous and internally consistent document, in its entirety. This processing is known as validation and generally proceeds in much the same fashion as processing for finding character strings of interest discussed above but operating on sixteen-bit (or longer) tokens corresponding to sequences of bytes rather than single eight-bit (or longer) bytes representing characters and checking for consistency between tokens and the content or arguments of other tokens to accommodate the self-definition characteristics and properties of languages such as XML, SGML.TM. (of which XML.TM. is a simplified form) and HTML.TM. (which is essentially a special case of XML.TM.) which support platform independence and interconnectivity.

Both the parsing for finding tokens and the parsing for validation are generally implemented using a conceptually table-based finite state machine (FSM) or state table to search for these strings of interest or consistency between elements found and represented by tokens. The state table resides in memory and is designed to search for the specific patterns of characters or tokens in the document. For parsing to find character strings of interest, the current state is used as the base address into the state table and the ASCII representation of the input character or the token is an index into the table. Character strings of interest may be of any of several types such as an element, an attribute/attribute list or data and elements may be simple elements or aggregates and may be nested. The parsing for validation principally looks at the types of character strings presented and the nesting itself to determine which elements or tokens are associated with another specific token(s) and the hierarchical relationship between them.

The goal of this processing is not only to determine that the document is a valid document that conforms to the language (e.g. XML.TM.) standard and have the correct structure as defined by a DTD or XML.TM. schema in its entirety but to develop a hierarchical data structure such as a tree structured document object in which the structure will fully represent the informational content of the data. Therefore, while parsing to find character strings of interest is very time consuming and processor intensive, parsing for validation is much more so. That is, since the XML.TM. data, for example, are textual and not only the data but the data structure, which may be freely specified to express the informational content, must be extracted from such text, it can be readily appreciated that the required processing is particularly time consuming and processor intensive.

At the same time, the potential complexity of the processing needed to properly handle aggregate elements and flexible nesting that may be in multiple hierarchical levels complicates the use of special purpose or hardware processors to reduce the processing load on the CPU of the local computer. That is, while it is generally recognized that special purpose or hardware processors can often provide increased processing speed in comparison with general purpose processors due to the reduced overhead for control of the general purpose processor, itself, it is not assured that a special purpose processor will be feasible or provide any significant advantage in performance as the processing function becomes more complex or with increased requirements for flexibility. In general, increased complexity and/or requirements for flexibility of function can only be accommodated by much increased hardware requirements which may not be economically justified for many applications or for the performance gain that may be possible. It is for this reason that validation parsing has been performed on programmed general purpose computers despite the processing time required.

SUMMARY OF THE INVENTION

The present invention to provide a hardware accelerator for validation processing in which substantial performance gains are derived with limited hardware.

In order to accomplish these and other objects of the invention, method of accelerating validation parsing and a hardware accelerated validation parser for a tokenized text document in a computer language supporting platform independence and interoperability is provided comprising, an arrangement for retrieving data from both a data dictionary and a state table in accordance with a token, and adder for merging the data from the state table and the data dictionary to form a transition control word, and adder for merging part of the transition control word with another token to retrieve further data from the state table, and logic for forming a tree structured data object corresponding to the tokenized text document under control of part of the transition control word.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which:

FIG. 1 is a high level schematic diagram of the hardware validating parser accelerator in accordance with the invention,

FIG. 1A is a diagram of an exemplary tree structured document object illustrative of formation thereof,

FIG. 2 is a diagram of a preferred logical layout of state tables in accordance with the invention,

FIG. 3 is a diagram illustrating a preferred format of a token,

FIG. 4 is a diagram illustrating a preferred logical layout of the element and attribute buffer of FIG. 1 in accordance with the invention,

FIG. 5 is a diagram of a preferred exemplary data dictionary entry format,

FIG. 6 is a diagram illustrating a preferred logical layout of transition control words (TCW) in accordance with the invention,

FIG. 7 is a flow chart illustrating an overview of the operation of the validating parser accelerator illustrated schematically in FIG. 1,

FIG. 8 is a flow chart illustrating operation of the invention to implement TCW update rules, and

FIGS. 9, 10 and 11A 11E are flow charts illustrating TCW operations.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION

Referring now to the drawings, and more particularly to FIG. 1, there is shown in high-level schematic form, an overview of the hardware validating parser accelerator system in accordance with the invention. It is to be understood that the invention operates on a document which has already been parsed for provision or setting of tokens corresponding to character strings of interest in an original document which is generally in textual form, as is typical of XML.TM. documents. (While the invention will be described in connection with the preferred application to parsing of XML.TM. documents, it is to be understood that the principles of the invention as will be evident from the following description are also applicable to parsing of files embodied in any programming language and, particularly, to object-oriented programming language with respect to which it is desirable to identify objects and their structure in accordance with fixed or user-definable rules.) This tokenized document is stored in memory/buffer 110 which is accessed in accordance with registers 112, 114 and 116 containing the document base address, the document limit address and the document next address, respectively.

Tokens are fetched in sequence and stored in token buffer 120. Portions of the token are then used to provide a portion of an address to adder 130 (which provides an address into state table 160), an address into the data dictionary 150 and to a namespace mapping memory (an incident of XML.TM. to avoid problems which could be engendered by different developers using the same element names in regard to different documents which is well-understood by those skilled in the art and need not be discussed further) 140. In regard to the namespace mapping memory 140 which provides a base address into the data dictionary 150 through register 152, a default address is provided from register 142.

Considering the remainder of FIG. 1 at a very high level of abstraction, adder 170, transition control word (TCW) register 180, stack 190, adder 130 and state table 160 form a loop, generally indicated by arrow A which allows the state table to advance from one state to another. Stack 190 is basically for the purpose of interchanging order of tokens as they are considered in order to accommodate evaluation of nested tokens and to determine if the associations or relationships between parent and child elements is correct and well-constructed. Control of the stack is derived from a combination of information from the state table 160 and the data dictionary 150 which is derived in parallel based on the current token. Therefore, stack 190 may be considered as accommodating particular features (e.g. aggregates) of XML.TM. syntax and further discussion deferred until the detailed discussion below.

Thus, the gross function of loop A is to derive information from the state tables including a next state, add further data at adder 170, derive data, stack commands, interrupts and control signals for developing the final tree structured data object (TSDO) from the combined signals in the TCW register 180 and add the next state and/or the base address in registers 192 and 194, respectively to the next token. The extraction of a control signal for providing an addition of a node to the TSDO corresponds to a validation of the current token and a detected error will be represented by the issuance of an interrupt. The TCW is basically a combination of control flags and state transition controls from the state table 160 and data dictionary 150 with certain update and interrupt and stack rules applied.

The TCW register thus functions to merge and redirect control signals and data retrieved from among the contents of the state table 160 and the data dictionary 150 which represents the permissible syntax of tokens such that the effect of progress through the state table is controlled in a manner to detect errors and, while no error has yet been detected, to properly construct the TSDO 300 with data buffered at element and attribute buffer 200 in accordance with base and limit addresses supplied from registers 302, 304 respectively. This architecture supports standard and established types of document definitions being used as a data dictionary by virtue of accommodation by the state table contents which can be arranged at will to do so. The accelerator processing unit 100 is responsible for orchestrating the operations of the invention which will be described below and to construct the TSDO.

A host processor 400 which interfaces with the accelerator processing unit is also provided and used to control initiation of operation of the hardware accelerator in accordance with the invention. It will be appreciated from the following that the role of the host processor 400 in the validation parsing process is reduced, by virtue of the hardware accelerator of the invention, operations requiring only simple memory accesses and to provide interrupt servicing. In essence, substantially all validation processing overhead corresponding to the following of document syntax and element nesting and aggregate elements is removed to the validation parsing accelerator and the processor operations are limited to simple responses to processing calls, as needed, from the hardware accelerator 100. A support processor can also be provided to handle some or all of the processing calls from the hardware accelerator 100.

With the above overview as background, it will be helpful to an understanding of the hardware accelerated validating parser of the invention to discuss an exemplary TSDO 300 which is the goal of the validation parsing process performed by the invention with reference to FIG. 1A which illustrates formation of an exemplary TSDO. The TSDO is preferably constructed in memory as a doubly linked list data structure having seven elements (e.g. sibling element, child element, attribute list, name length, name pointer, value length and value pointer) per member/node as illustrated in the TSDO member layout. The eight rows of elements depicted, each corresponding to the TSDO member layout, thus correspond to eight individual members of the TSDO and are offset horizontally to indicate sibling and parent/child relationships.

To form a doubly linked list, several elements each contain two pointers p, n, to the previous and next member containing the previous and next element of the specified or same type. Thus a "next sibling element pointer" points to the next member equally indented with the current member. Similarly, pointers are provided to and from attribute list elements and the attributes of members. The "previous child element" points to the parent member. As shown in the third through fifth rows and second, sixth and seventh rows, previous and next pointers form chains among sibling members. The remaining elements are lengths and locations of actual data. From this information five controls are preferably provided in correspondence with a current member/node (e.g. the parent node, the current element node, the current attribute node, the element parent and the first attribute), as illustrated. These controls basically track whether the current member is an element or an attribute and the nodes on which they exist, the first attribute of the attribute list of an element, the immediate parent member and the root node. Following these controls allows traversing of the tree to locate any desired information while the nature of each piece of information is fully and unambiguously defined in the structure of the TSDO.

Similarly, it may be helpful in understanding the invention to review the characteristics of the data files operated upon. In the exemplary case of XML.TM., the elements and data will be embodied in a file which is essentially text but following rules which can be freely structured for different classes of documents. The rules embodied in the text document are, in effect, summarized in a file called "document model" which is used to validate the text document and which may be considered as separate from the text file although it need not be. The rules may be freely defined by a developer but some standardized sets of rules exist and which are often utilized as a matter of convenience.

The file defining the rules followed by an XML.TM. document or document in any other interoperable language, at the current time, is referred to as a document model which generally follows one of several forms although others are currently under development. A document model defines the elements which can appear within the document along with attributes that can be associated with a given element and also defines structural information about the document such as child-parent relationships of elements, the sequence in which the child elements can appear and the number of child elements as well as whether an element is empty or can include text as well as default values for attributes. Document type definitions (DTDS) are a well-known example of a description of XML.TM. document models.

The DTD language was developed specifically for defining validation rules for SGML.TM. documents. As alluded to above, XML.TM. is a simplified sub-set of SGML.TM. and DTDs can also be used to define XML.TM. validation rules. It should be recognized, however, that since the information required for validation of a particular document or class of documents must be the same regardless of the form in which it is transmitted or utilized, conversion between types of expressions of the validation information (e.g. DTDs and XML.TM. schema) should, in theory, be substantially trivial and discussion in terms of DTDs should be equally applicable to any other form of the same information. By the same token, details of DTD syntax, which is very complex with heavy reliance on typograp