Methods and apparatus for parsing extensible markup language (XML) data streams

• US 20040210599A1
• Filed: 05/07/2004
• Published: 10/21/2004
• Est. Priority Date: 07/26/1999
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zeng, Nanshan, Lovett, Christopher J., Friedman, Greg S.
• Granted Patent: US 6,996,773 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/221 Parsing markup language streams streaming G06F40/149

Abstract

Various features enable an XML data stream to be parsed without the need to build a hierarchical tree structure for the XML document. In the described embodiment, the concept of an element or namespace stack is utilized as a way of organizing parsing activities and maintaining a definable place within the structure of the XML document. Various structures work together with the element or namespace stack to facilitate piecewise parsing of the XML data stream. One structure is a namespace hierarchy that is a collection of namespace objects that each represent a namespace specification that is encountered in the XML data stream. Each object includes a namespace prefix and an associated namespace specification. This structure creates a hierarchical organization that is used for mapping a particular encountered namespace specification into a unique value that represents both the namespace specification and an element tag in which the namespace specification occurs. Another structure is a dictionary collection that contains one or more dictionaries. Each dictionary is specifically associated with a namespace specification that is encountered in the XML data stream. The dictionaries contain entries for one or more tag names and each name'"'"'s associated unique token. The token is returned and placed on the element stack along with another special value that enables the proper state to be maintained during processing of the XML data stream. The stack also includes a text accumulation buffer that can hold any text that is contained within an element (between the element tags). When an XML element is encountered, the element stack is used to organize parsing activities as the parser makes its way through the XL data stream.

Claims

1. A method of parsing an XML data stream comprising:

receiving an XML data stream containing a namespace prefix and an associated element tag name, the element tag name being associated with an element tag;

converting the namespace prefix and the element tag name into a token that uniquely represents a namespace specification that is associated with the namespace prefix and the element tag;

defining a stack that is configured to receive one or more tokens during parsing of the XML data stream; and

placing a token on the stack,

said acts of receiving, converting, defining and placing being configured to permit parsing of the XML data stream to begin without requiring an XML tree structure, comprising an XML document embodied by the XML data stream, to be built.

2. The method of claim 1 further comprising:

receiving a close tag for an element tag; and

responsive to said receiving, removing a token from the stack that is associated with an element tag with which the close tag is associated.

3. A method of parsing an XML data stream comprising:

defining a plurality of unique tokens, each token representing an XML namespace specification and an element tag name;

organizing the tokens in a stack as XML element tags are encountered in the XML data stream; and

removing at least one of the tokens from the stack before another token is added to the stack,

said acts of defining, organizing and removing being configured to permit parsing of the XML data stream to begin without requiring an XML tree structure, comprising an XML document embodied by the XML data stream, to be built.

4. A method of parsing an XML data stream comprising:

receiving an XML data stream;

defining a data structure that comprises a plurality of frames, each frame having a plurality of frame portions;

placing a plurality of representations into respective frame portions of the plurality of frames, each representation representing a namespace specification and an element tag of the XML data stream; and

maintaining the data structure by adding and removing representations to and from, respectively, the data structure as the XML data stream is received,

said acts of receiving, defining, placing and maintaining being configured to permit parsing of the XML data stream to begin without requiring an XML tree structure, comprising an XML document embodied by the XML data stream, to be built.

5. One or more computer-readable media having computer-readable instructions thereon which, when executed, cause the computer to:

receive an XML data stream containing a namespace prefix and an associated element tag name, the element tag name being associated with an element tag;

convert the namespace prefix and the element tag name into a token that uniquely represents a namespace specification that is associated with the namespace prefix and the element tag;

define a stack that is configured to receive one or more tokens during parsing of the XML data stream; and

place and remove one or more tokens on the stack during parsing or the XML data stream,

said acts of receiving, converting, defining and placing being configured to permit parsing of the XML data stream to begin without requiring an XML tree structure, comprising an XML document embodied by the XML data stream, to be built.

6. One or more computer-readable media having computer-readable instructions thereon which, when executed, cause the computer to:

define a plurality of unique tokens, each token representing an XML namespace specification and an element tag name;

organize the tokens in a stack as XML element tags are encountered in the XML data stream; and

remove at least one of the tokens from the stack before another token is added to the stack,

said acts of defining, organizing and removing being configured to permit parsing of the XML data stream to begin without requiring an XML tree structure, comprising an XML document embodied by the XML data stream, to be built.

7. One or more computer-readable media having computer-readable instructions thereon which, when executed, cause the computer to:

receive an XML data stream;

define a data structure that comprises a plurality of frames, each frame having a plurality of frame portions;

place a plurality of representations into respective frame portions of the plurality of frames, each representation representing a namespace specification and an element tag of the XML data stream; and

maintain the data structure by adding and removing representations to and from, respectively, the data structure as the XML data stream is received,

said acts of receiving, defining, placing and maintaining being configured to permit parsing of the XML data stream to begin without requiring an XML tree structure, comprising an XML document embodied by the XML data stream, to be built.