Methods and apparatus for converting markup language data to an intermediate representation

• US 7,954,051 B2
• Filed: 07/01/2004
• Issued: 05/31/2011
• Est. Priority Date: 01/13/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nelson, Jan-Christian, Kuznetsov, Eugene, Ballou, Kenneth R., Morgan, Charles R., Willis, Steven R., Achilles, Heather D., McManus, Patrick R.
• Primary Examiner(s): Hong; Stephen S
• Assistant Examiner(s): Ludwig; Matthew J
• Application Number:
  US10/883,484
• Publication Number:
  US 20060236225A1
• Time in Patent Office: 2,525 Days
• Field of Search: 715/234, 715/236, 715/237, 715/239
• 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/221 Parsing markup language streams streaming G06F40/149

Abstract

Systems, methods and apparatus provide a character process for processing markup language data, such as XML data, by receiving a character stream of markup language data and applying sequences of characters of the character stream to a set of state machines. The set of state machines includes a plurality of construct state machines responsible for processing respective markup language constructs identified by the sequences of characters. The character processor produces, from application of the sequences of characters to the set of state machines, an intermediate representation of the markup language constructs identified by the sequence of characters of the character stream of markup language data. The intermediate representation contains encoded items containing type, length, value representations representative of constructs within the character stream of markup language data.

Claims

1. A method for processing extensible markup language (XML) data, the method comprising:

receiving a character stream of markup language data;

applying sequences of characters of the character stream to a set of state machines, the set of state machines including a plurality of construct state machines responsible for processing respective XML constructs identified by the sequences of characters;

operating a character provider in a character processor to provide characters from the character stream to the set of state machines;

operating a primary state machine to control to control invocation of the respective construct state machines to process different types of XML constructs encountered during reception of the character stream of XML data; and

producing, from application of the sequences of characters to the set of state machines, an intermediate representation of the markup language constructs identified by the sequence of characters of the character stream of markup language data, the intermediate representation having encoded items including type, length, value representations of the XML constructs and representative of the original stream of XML data.

2. The method of claim 1 wherein operating a primary state machine to control invocation of the respective construct state machines comprises:

detecting a sequence of characters representative of a start element and invoking a start element state machine; and

operating the start element state machine to produce at least one start element encoded item containing type, length, value representations for at least one of;

a complete start element;

a partial start element; and

an empty element.

3. The method of claim 2 wherein operating the start element state machine comprises:

identifying a sequence of character representative of an attribute element within a start element and in response, invoking an attribute element state machine; and

operating the attribute element state machine to perform at least one of;

i) parsing the attribute element into an attribute name prefix and an attribute value suffix and producing an attribute name prefix encoded item for the attribute name prefix of the attribute element and producing an attribute value suffix encoded item for the attribute value suffix of the attribute element; and

ii) identifying that the attribute element is indicative of an namespace declaration and in response, invoking operation of a name space element state machine.

4. The method of claim 1 wherein operating a primary state machine to control invocation of the respective construct state machines comprises:

detecting a sequence of characters representative of a processing instruction element and invoking a processing instruction element state machine; and

operating the processing instruction element state machine to produce at least one processing instruction data element encoded item containing type, length, value representations for at least one of;

a processing instruction data element;

a partial processing instruction data element.

5. The method of claim 4 wherein the processing instruction is a non-declaration processing instruction and wherein operating the processing instruction element state machine to produce at least one processing instruction data element encoded item comprises:

producing a non-declaration processing instruction target data element; and

producing a non-declaration processing instruction value data element.

6. The method of claim 4 wherein the processing instruction is an XML declaration processing instruction and wherein operating the processing instruction element state machine to produce at least one processing instruction data element encoded item comprises:

identifying at least one of encoding and standalone constructs within the XML declaration processing instruction and copying the version, encoding and standalone constructs within the XML declaration processing instruction into encoded item output.

7. The method of claim 1 wherein applying sequences of characters of the character stream to a set of state machines comprises:

obtaining at least two characters from the character stream of markup language data; and

applying the at least two characters to the primary state machine and during invocation of the respective construct state machines during one state machine cycle, such that each state machine can process state transitions at least two characters at one time.

8. The method of claim 1 wherein the state machines of the plurality of state machines can invoke each other, such that control can be transferred from once respective construct state machine to another, without control returning to the primary state machine.

9. The method of claim 1 wherein the character stream of markup language data is associated with a respective markup processing session, and wherein there are a plurality of respective markup processing sessions, each having an associated character stream of markup language data, and wherein the method comprises:

during application of sequences of characters of a first character stream associated with a first markup processing session to the set of state machines, identifying a session switch event indicating that sequences of characters of a second character stream associated with a second respective markup processing session is to be processed by the set of state machines;

saving the state of the first markup processing session for the first character stream in a first session state;

determining if a second session state exists that is associated with the second markup processing session, and if so, loading the second session state for use by the set of state machines; and

performing, for sequences of characters of a character stream of the second markup processing session, the operations of receiving the character stream of markup language data, applying the sequences of characters of the character stream of the second markup processing session to a set of state machines, and producing an intermediate representation of the markup language constructs identified by the sequence of characters of the second character stream of markup language data.

10. The method of claim 1 comprising:

embedding the method for processing markup language data as a series of logic instructions within a programmable microcontroller in hardware, the programmable microcontroller including an input interface for receiving the character stream of markup language data and an output interface for producing the intermediate representation; and

operating the programmable microcontroller in hardware to process the character stream of markup language data such that all processing of the character stream of markup language data is done in hardware and such that software processing of the character stream of markup language data is not required by a general purpose central processing unit.

11. The method of claim 1 wherein operating a primary state machine to control invocation of the respective construct state machines comprises:

invoking a content state machine and operating the content state machine to produce an unnecessary white space encoded item within encoded item output.

12. The method of claim 1 wherein the character stream of markup language data is applied to multiple character processors at the same time, such that the character stream is split between the multiple character processors to achieve higher overall throughput.

13. A character processor device comprising:

an input interface for receiving a character stream of extensible markup language (XML) data;

logic processing coupled to the input interface and configured to receive and apply sequences of characters of the character stream to a set of state machines encoded within the logic processing, the set of state machines including a plurality of construct state machines responsible for processing respective XML constructs identified by the sequences of characters;

the logic processing operating a primary state machine to control to control invocation of the respective construct state machines to process different types of XML constructs encountered during reception of the character stream of XML data;

the logic processing operating a character provider in a character processor to provide characters from the character stream to the set of state machines; and

the logic processing producing, from an output interface coupled to the logic processing, from application of the sequences of characters to the set of state machines, an intermediate representation of the markup language constructs identified by the sequence of characters of the character stream of XML language including data type, length, value representations of the XML constructs, the intermediate representation containing encoded items representative of the original stream of markup language data.

14. The character processor device of claim 13 wherein when the logic processing performs the operation of operating a primary state machine to control invocation of the respective construct state machines the logic processing performs the operations of:

detecting a sequence of characters representative of a start element and invoking a start element state machine; and

operating the start element state machine to produce at least one start element encoded item containing type, length, value representations for at least one of;

a complete start element;

a partial start element;

an empty element.

15. The character processor device of claim 14 wherein operating the start element state machine comprises:

identifying a sequence of character representative of an attribute element within a start element and in response, invoking an attribute element state machine; and

operating the attribute element state machine to perform at least one of;

i) parsing the attribute element into an attribute name prefix and an attribute value suffix and producing an attribute name prefix encoded item for the attribute name prefix of the attribute element and producing an attribute value suffix encoded item for the attribute value suffix of the attribute element; and

ii) identifying that the attribute element is indicative of an namespace declaration and in response, invoking operation of a name space element state machine.

16. The character processor device of claim 15 wherein invoking operation of a name space element state machine comprises:

parsing a namespace prefix element from the namespace declaration and producing a namespace prefix encoded item; and

parsing a uniform resource identifier from the namespace declaration and producing a uniform resource identifier encoded item identifying the value of the uniform resource identifier within the namespace declaration.

17. The character processor device of claim 14 wherein operating the start element state machine to produce at least one start element encoded item comprises:

identifying a prefix and suffix portions of the start element; and

producing respective encoded items for the prefix and suffix portions of the start element; and

storing representations of at least one of the prefix and suffix portions of the start element for comparison to at least one corresponding end element prefix and suffix portions that are later detected within at least one end element in the character stream of markup language data.

18. The character processor device of claim 13 wherein operating a primary state machine to control invocation of the respective construct state machines comprises:

detecting a sequence of characters representative of a processing instruction element and invoking a processing instruction element state machine; and

operating the processing instruction element state machine to produce at least one processing instruction data element encoded item containing type, length, value representations for at least one of;

a processing instruction data element;

a partial processing instruction data element.

19. The character processor device of claim 18 wherein the processing instruction is a non-declaration processing instruction and wherein operating the processing instruction element state machine to produce at least one processing instruction data element encoded item comprises:

producing a non-declaration processing instruction target data element; and

producing a non-declaration processing instruction value data element.

20. The character processor device of claim 18 wherein the processing instruction is an XML declaration processing instruction and wherein operating the processing instruction element state machine to produce at least one processing instruction data element encoded item comprises:

identifying at least one of version, encoding and standalone constructs within the XML declaration processing instruction and copying the version, encoding and standalone constructs within the XML declaration processing instruction into encoded item output.

21. The character processor device of claim 13 wherein applying sequences of characters of the character stream to a set of state machines comprises:

obtaining at least two characters from the character stream of markup language data; and

applying the at least two characters to the primary state machine and during invocation of the respective construct state machines during one state machine cycle, such that each state machine can process state transitions at least two characters at one time.

22. The character processor device of claim 13 wherein the state machines of the plurality of state machines can invoke each other, such that control can be transferred from once respective construct state machine to another, without control returning to the primary state machine.

23. The character processor device of claim 13 wherein the character stream of markup language data is associated with a respective markup processing session, and wherein there are a plurality of respective markup processing sessions, each having an associated character stream of markup language data, and wherein the method comprises:

during application of sequences of characters of a first character stream associated with a first markup processing session to the set of state machines, identifying a session switch event indicating that sequences of characters of a second character stream associated with a second respective markup processing session is to be processed by the set of state machines wherein identifying a session switch event comprises within a current state machine that is processing the sequence of characters for the first character stream, producing an partial encoded item associated with a type of construct being processing within the current state machine, such that the intermediate representation of the markup language constructs associated with the first character stream indicates a transition of processing of the first markup processing session to the second markup processing session by the set of state machines;

saving the state of the first markup processing session for the first character stream in a first session state;

determining if a second session state exists that is associated with the second markup processing session, and if so, loading the second session state for use by the set of state machines; and

performing, for sequences of characters of a character stream of the second markup processing session, the operations of receiving the character stream of markup language data, applying the sequences of characters of the character stream of the second markup processing session to a set of state machines, and producing an intermediate representation of the markup language constructs identified by the sequence of characters of the second character stream of markup language data.

24. The character processor device of claim 13 wherein operating a primary state machine to control invocation of the respective construct state machines comprises:

detecting a sequence of characters representative of a data type definition (DTD) element and invoking a DTD element state machine; and

operating the DTD element state machine to produce at least one DTD data element encoded item containing type, length, value representations for at least one of;

a DTD Name

a DTD Public ID

a DTD System ID

a DTD Subset.

25. The character processor device of claim 13 wherein when the logic processing performs the operation of:

detecting the well-formedness of the markup language data by comparing representations of at least one of the prefix and suffix portions of the end element to stored representations of at least one of a prefix and suffix portion of a start element previously detected in the character stream of markup language data for validation of the end element;

storing the start element prefix and suffix in registers; and

providing valid bits associated with the registers such that the character processor is notified that an end element is compared properly.

26. A computer program product having a computer-readable medium including computer program logic encoded thereon that, when executed on processor within a computerized device, provides a character processor that processes extensible markup language (XML) data by performing the operations of:

receiving a character stream of markup language data;

applying sequences of characters of the character stream to a set of state machines, the set of state machines including a plurality of construct state machines responsible for processing respective XML constructs identified by the sequences of characters;

operating a character provider in a character processor to provide characters from the character stream to the set of state machines;

operating a primary state machine to control to control invocation of the respective construct state machines to process different types of XML constructs encountered during reception of the character stream of XML data; and

producing, from application of the sequences of characters to the set of state machines, an intermediate representation of the markup language constructs identified by the sequence of characters of the character stream of markup language data, the intermediate representation containing encoded items including type, length, value including type, length, value representations of the XML constructs and representative of the original stream of XML data.

27. The computer program product of claim 26 wherein when the computer program logic causes the character processor to apply sequences of characters of the character stream to a set of state machines, the computer program logic further includes code to cause the character processor to perform the operation of:

operating a primary state machine to control to control invocation of the respective construct state machines to process different types of XML constructs encountered during reception of the character stream of XML data.

28. A method for processing extensible markup language (XML) data, the method comprising:

receiving a character stream of markup language data;

applying sequences of characters of the character stream to a set of state machines, the set of state machines including a plurality of construct state machines responsible for processing respective XML constructs identified by the sequences of characters;

operating a character provider in a character processor to provide multiple characters from the character stream per state machine cycle to the set of state machines;

operating a primary state machine to control to control invocation of the respective construct state machines to process different types of XML constructs encountered during reception of the character stream of XML data; and

producing from application of the sequences of characters to the set of state machines, an intermediate representation of the markup language constructs identified by the sequence of characters of the character stream of markup language data, the intermediate representation having encoded items including type, length, value representations of the XML constructs and representative of the original stream of XML data.