Method and apparatus for schema-driven XML parsing optimization

• US 20050097455A1
• Filed: 10/21/2004
• Published: 05/05/2005
• Est. Priority Date: 10/30/2003
• Status: Active Grant

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Ismael, Ali, Zhou, Dong, Song, Yu, Islam, Nayeem
• Granted Patent: US 8,166,053 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/205 Parsing

Abstract

Schema-driven XML parsing techniques allow an XML parser to optimize its parsing process by composing parse and to dynamically generate parsing code components based on XML schema definition for the targeted XML document. These techniques reduce the XML parsing time and reduce the memory requirement during parsing process. Further, a reconfigurable parser is provided which is guided during parsing of the XML document by XML element lexicographical information and state transition information extracted from a schema associated with the XML document. Pre-allocated element object pools may be provided based on the schema analysis to reduce the requirements for dynamic memory allocation and de-allocation operations.

Claims

1. A method for parsing an XML document, comprising:

Performing an analysis of the XML document from an XML schema associated with the XML document to extract one or more relationships between XML elements included in the XML document; and

parsing the XML elements of the XML document guided by relationships extracted in the analysis.

2. A method as in claim 1, wherein the relationships extracted from the analysis comprises a lexicographical distance between XML elements.

3. A method as in claim 1, wherein the relationships extracted from the analysis comprises state-transition information.

4. A method as in claim 1, further comprising providing element object pools that are created upon system initialization.

5. A method as in claim 4, further comprising, upon parsing an XML element:

retrieving a corresponding element object from the element object pools; and

filling the element object with values extracted from the parsed XML element.

6. A method as in claim 5, further comprising providing the element object as a node in a parse tree.

7. A method as in claim 5, wherein the element object is returned to the element object pools.

8. A method as in claim 4, wherein each element object in the element object pools correspond to an expected data structure of an XML element defined in the XML schema.

9. A reconfigurable parser for an XML document, comprising:

an analyzer for extracting from an XML schema associated with the XML document relationships between XML elements included in the XML document; and

a parser of the XML elements of the XML document guided by the relationships extracted by the analyzer.

10. A reconfigurable parser as in claim 9, wherein the relationships extracted by the analyzer comprises a lexicographical distance between XML elements.

11. A reconfigurable parser as in claim 9, wherein the relationships extracted by the analyzer comprises state-transition information.

12. A reconfigurable parser as in claim 9, further comprising element object pools that are created upon system initialization.

13. A reconfigurable parser as in claim 12, further comprising:

a selector for retrieving a corresponding element object from the element object pools, upon successfully parsing an XML element; and

a writer for filling in the element object with values extracted from the parsed XML element.

14. A reconfigurable parser as in claim 13, further comprising a parse tree constructor which receives the element object as a node in a parse tree.

15. A reconfigurable parser as in claim 13, wherein the element object is returned to the element object pools.

16. A reconfigurable parser as in claim 12, wherein each element object in the element object pools correspond to an expected data structure of an XML element defined in the XML schema.

17. A method for efficiently parsing an XML document, comprising:

analyzing a schema associated with the XML document to extract data structures of XML elements of the XML document;

generating parse code for each data structure of the XML elements; and

parsing the XML elements using the generated parse code as the XML document is read.

18. A method as in claim 17, wherein the generated parse code is compiled.

19. A method as in claim 17, further comprising reading the XML elements from the XML document one element at a time.

20. A method as in claim 19, wherein the XML elements are read into the parser according to a push model.

21. A method as in claim 19, wherein the XML elements are read into the parser according to a pull model.

22. A method as in claim 17, further comprising validating the XML elements against the XML schema.

23. A method as in claim 17, further comprising providing the parsed XML elements in a parse tree.

24. A method as in claim 17, further comprising providing the parsed XML elements one at a time in a continuous stream.

25. A parser for an XML document, comprising:

a schema analyzer for extracting data structures of XML elements from a schema associated with the XML document;

a parse code generator that generates a parse code for each data structure of the XML elements; and

a parser integrator that invokes a corresponding parse code in respond to each XML element encountered as the XML document is read.

26. A parser as in claim 25, wherein the generated parse code is compiled.

27. A parser as in claim 25, further comprising an XML reader that reads the XML elements from the XML document one element at a time.

28. A parser as in claim 27, wherein the XML elements are read into the parser according to a push model.

29. A parser as in claim 27, wherein the XML elements are read into the parser according to a pull model.

30. A parser as in claim 25, wherein the parse code validates the XML elements against the XML schema.

31. A parser as in claim 25, further comprising an output module that provides the parsed XML elements in a parse tree.

32. A parser as in claim 25, further comprising an output module that provides the parsed XML elements one at a time in a continuous stream.