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

• US 20060236225A1
• Filed: 07/01/2004
• Published: 10/19/2006
• Est. Priority Date: 01/13/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Willis, Steven R., Achilles, Heather D., McManus, Patrick R., Nelson, Jan-Christian, Kuznetsov, Eugene, Ballou, Kenneth R., Morgan, Charles R.
• Granted Patent: US 7,954,051 B2
• Time in Patent Office: Days
• US Class Current: 715/205
• 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 markup language 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 markup language constructs identified by the sequences of characters; 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 representative of the original stream of markup language data.

2. The method of claim 1 wherein:

the markup language data is formatted according to an extensible markup language (XML) specification;

the plurality of construct state machines include respective construct state machines to process different types of XML constructs; and

the intermediate representation of the markup language constructs identified by the sequence of characters of the character stream of markup language data are encoded items containing type, length, value representations of the XML constructs identified by application of the sequences of characters of the character stream to the set of state machines.

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

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.

4. The method of claim 3 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.

5. The method of claim 4 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.

6. The method of claim 5 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.

7. The method of claim 4 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.

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

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

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

an end element;

a partial end element.

9. The method of claim 8 wherein operating the end element state machine to produce at least one end element encoded item comprises:

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

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

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.

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

detecting a sequence of characters representative of an character data element and invoking a character data element state machine; and

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

a character data element; and

a partial character data element.

11. The method of claim 10 wherein operating the character data element state machine to produce at least one character data element encoded item comprises:

detecting a non-normalization setting associated with the character stream of markup language data to which the plurality of state machines are applied; and

copying the character data element to the character data element encoded item using non-normalization processing.

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

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

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

a comment data element;

a partial comment data element.

13. The method of claim 3 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.

14. The method of claim 13 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;

15. The method of claim 13 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.

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

detecting a sequence of characters representative of a content declaration within the character stream of markup language data and invoking a content state machine; and

operating the content state machine to produce at least one content element encoded item containing type, length, value representations for the content declaration encountered within the character stream of markup language data.

17. The method of claim 16 wherein operating the content state machine to produce at least one content element encoded item comprises:

identifying and eliminating unnecessary white space within the character stream of markup language data; and

producing an unnecessary white space encoded item within encoded item output.

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

detecting a sequence of characters representative of a document type definition within the character stream of markup language data and invoking a document type definition state machine; and

operating the document type definition state machine to produce at least one document type definition element encoded item containing type, length, value representations for the document type definition encountered within the character stream of markup language data.

19. The method of claim 3 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.

20. The method of claim 3 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.

21. The method of claim 3 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.

22. The method of claim 21 wherein 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 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.

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

identifying and eliminating unnecessary white space within the character stream of markup language data.

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

performing normalization processing on the sequence of characters to perform at least one of;

removing end-of-line and line feed characters within the character stream of markup language data; and

converting the markup data to from a first data format to a second data format.

25. The method of claim 3 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 processing 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.

26. A character processor device comprising:

an input interface for receiving a character stream of markup language 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 markup language constructs identified by the sequences of characters; 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 markup language data, the intermediate representation containing encoded items representative of the original stream of markup language data.

27. The character processor device of claim 26 wherein:

the markup language data is formatted according to an extensible markup language (XML) specification;

the plurality of construct state machines include respective construct state machines to process different types of XML constructs; and

the intermediate representation of the markup language constructs identified by the sequence of characters of the character stream of markup language data are encoded items containing type, length, value representations of the XML constructs identified by application of the sequences of characters of the character stream to the set of state machines.

28. The character processor device of claim 27 wherein when the logic processing performs the operation of applying sequences of characters of the character stream to a set of state machines, the logic processing performs 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.

29. The character processor device of claim 28 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.

30. The character processor device of claim 29 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.

31. The character processor device of claim 30 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.

32. The character processor device of claim 29 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.

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

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

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

an end element;

a partial end element.

34. The character processor device of claim 33 wherein operating the end element state machine to produce at least one end element encoded item comprises:

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

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

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.

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

detecting a sequence of characters representative of an character data element and invoking a character data element state machine; and

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

a character data element;

a partial character data element.

36. The character processor device of claim 35 wherein operating the character data element state machine to produce at least one character data element encoded item comprises:

detecting a non-normalization setting associated with the character stream of markup language data to which the plurality of state machines are applied; and

copying the character data element to the character data element encoded item using non-normalization processing.

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

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

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

a comment data element;

a partial comment data element.

38. The character processor device of claim 28 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.

39. The character processor device of claim 38 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;

40. The character processor device of claim 38 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.

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

detecting a sequence of characters representative of a content declaration within the character stream of markup language data and invoking a content state machine; and

operating the content state machine to produce at least one content element encoded item containing type, length, value representations for the content declaration encountered within the character stream of markup language data.

42. The character processor device of claim 41 wherein operating the content state machine to produce at least one content element encoded item comprises:

identifying and eliminating unnecessary white space within the character stream of markup language data; and

producing an unnecessary white space encoded item within encoded item output.

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

detecting a sequence of characters representative of a document type definition within the character stream of markup language data and invoking a document type definition state machine; and

operating the document type definition state machine to produce at least one document type definition element encoded item containing type, length, value representations for the document type definition encountered within the character stream of markup language data.

44. The character processor device of claim 28 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.

45. The character processor device of claim 28 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.

46. The character processor device of claim 28 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.

47. The character processor device of claim 46 wherein 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 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.

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

identifying and eliminating unnecessary white space within the character stream of markup language data.

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

performing normalization processing on the sequence of characters to perform at least one of;

removing end-of-line and line feed characters within the character stream of markup language data; and

converting the markup data to from a first data format to a second data format.

50. 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 markup language 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 markup language constructs identified by the sequences of characters; 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 representative of the original stream of markup language data.

51. The computer program product of claim 50 wherein:

the markup language data is formatted according to an extensible markup language (XML) specification;

the plurality of construct state machines include respective construct state machines to process different types of XML constructs; and

the intermediate representation of the markup language constructs identified by the sequence of characters of the character stream of markup language data are encoded items containing type, length, value representations of the XML constructs identified by application of the sequences of characters of the character stream to the set of state machines.

52. The computer program product of claim 51 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.

53. A character processor device comprising:

an input interface for receiving a plurality of character streams of extensible markup language (XML) data, each formatted according to an extensible markup language (XML) specification;

logic processing coupled to the input interface and configured to receive and apply sequences of characters of the character streams to a set of state machines encoded within the logic processing, the set of state machines including a plurality of construct state machines that provide means for processing respective markup language constructs identified by the sequences of characters, the plurality of construct state machines include respective construct state machines to process different types of XML constructs; and

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

54. The character processor device of claim 53 wherein:

during application of sequences of characters of a first character stream associated with a first markup processing session to the set of state machines, the logic processing including a means for identifying a session switch event indicating that sequences of characters of a second character stream associated with a second respective markup processing session are to be processed by the set of state machines, and in response, within a current state machine that is processing the sequence of characters for the first character stream, means for 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

the logic processing further including;

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

means for 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

means for 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.

55. The character processor device of claim 54 comprising:

means for selecting a set of state machines from a plurality of sets of state machines, each set optimized for processing a specific type of markup language data;

means for programming the character processor device with the selected set of state machines to optimally perform the processing operations of 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 based on the specific type of markup language data for which the selected set of state machines is selected.