Parsing, evaluating leaf, and branch nodes, and navigating the nodes based on the evaluation

• US 7,818,666 B2
• Filed: 01/27/2006
• Issued: 10/19/2010
• Est. Priority Date: 01/27/2005
• Status: Active Grant

• Current Assignee: Dassault Systemes Americas Corp. (Dassault Systemes SA)
• Original Assignee: Symyx Solutions, Inc.
• Inventors: Ferino, Fabrice, Dorsett, David R. Jr.
• Primary Examiner(s): Paula; Cesar B
• Application Number:
  US11/342,088
• Publication Number:
  US 20060168515A1
• Time in Patent Office: 1,726 Days
• Field of Search: 715/205, 715/234, 715/237, 717/129, 717142-143
• US Class Current: 715/237
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets
• CPC Class Codes: G06F 40/205 Parsing

Abstract

Methods, systems, and apparatus, including computer program products, for processing input data and for defining processing operations to be performed on such data. Input data is processed according to a data parser description associated with the input data format, and output data is generated based on the processing. The data parser description includes a plurality of leaf nodes and a plurality of branch nodes arranged in a tree structure. The leaf nodes each have an associated function. Each of the branch nodes has one or more associated child nodes selected from leaf nodes and other branch nodes. The nodes of the data parser description are evaluated in an order defined by the tree structure. For branch nodes, one or more of the associated child nodes are evaluated; for leaf nodes, the associated function is executed based on data in a current location in the input data.

Claims

1. A computer-implemented method for processing electronic data having a first format, comprising:

defining a data parser description describing the first format, the data parser description including a plurality of leaf nodes and a plurality of branch nodes arranged in a tree structure, the leaf nodes each having an associated function, each of the branch nodes having one or more associated child nodes selected from leaf nodes and other branch nodes;

receiving input data having the first format;

processing the input data according to the data parser description, the processing including evaluating the nodes of the data parser description in an order defined by the tree structure, the evaluating including;

if the node is a branch node, evaluating one or more of the associated child nodes;

if the node is a branch node, determining whether the node evaluates successfully based on a result of the evaluating one or more of the child nodes;

if the node is a leaf node, executing the associated function based on data in a current location in the input data;

if the node is a leaf node, determining whether the node evaluates successfully based on a result of the executing; and

after evaluating a given node, determining a next node to evaluate based on whether the given node has evaluated successfully; and

generating output data based on the processing.

2. The method of claim 1, wherein:

generating output data includes generating structured output data having a structure defined at least in part by nodes of the data parser description.

3. The method of claim 2, wherein:

the structured output data is generated as an extensible markup language document.

4. The method of claim 3, wherein generating the structured output data includes:

for one or more leaf nodes of the data parser description, reading data from the current location in the input data, and associating the data read from the current location in the input data with an element of the extensible markup language document.

5. The method of claim 3, wherein generating the structured output data includes:

for one or more leaf nodes of the data parser description, reading data from the current location in the input data, and executing a callback function to send the data read from the current location in the input data to a client; and

in the client, associating the sent data with an element of the extensible markup language document.

6. The method of claim 1, wherein:

the branch nodes include one or more first nodes, each first node being a branch node that evaluates successfully only if all of its associated child nodes evaluate successfully.

7. The method of claim 6, wherein:

the first nodes include one or more second nodes, each second node being a first node that is evaluated in response to a call function associated with one or more leaf nodes.

8. The method of claim 7, wherein:

the branch nodes include one or more third nodes, each third node being a branch node that evaluates successfully if any of its associated child nodes evaluates successfully.

9. The method of claim 8, wherein:

the branch nodes include one or more fourth nodes, each fourth node being a branch node that defines a number of iterations over one or more child nodes.

10. The method of claim 9, wherein:

the fourth node has a max parameter, a min parameter, and a counter value, and the fourth node is evaluated by;

evaluating each child node associated with the fourth node;

if each of the child nodes has evaluated successfully, incrementing the counter value, comparing the counter value with the max parameter, and, if the counter value is less than the max parameter, repeating the evaluating of each child node; and

if one or more of the child nodes has not evaluated successfully, comparing the counter value with the min parameter;

wherein, the fourth node has not evaluated successfully if one or more of the child nodes has not evaluated successfully and the counter value is less than the min parameter, and the fourth node has evaluated successfully if the counter value is equal to the max parameter or if one or more of the child nodes has not evaluated successfully and the counter value is greater than or equal to the min parameter.

11. The method of claim 10, wherein:

the data parser description defines a tree containing a plurality of leaf nodes and a plurality of branch nodes selected from the group consisting of fourth nodes, first nodes, and third nodes, each first node being a branch node that evaluates successfully only if all of its associated child nodes evaluate successfully, each third node being a branch node that evaluates successfully if any of its associated child nodes evaluates successfully.

12. The method of claim 1, wherein:

processing the input data includes, before evaluating a given node in the data parser description, storing a current position in the input data, and if the given node evaluates unsuccessfully, returning to stored position in the input data source before evaluating a subsequent node in the data parser description.

13. The method of claim 1, wherein:

one or more of the nodes of the data parser description is configurable with a condition, the evaluation of a node configured with a condition being dependent on the performance of a test specified by the condition.

14. The method of claim 1, wherein:

the input data is a data file or a data stream.

15. The method of claim 1, further comprising:

monitoring output from one or more instruments, wherein receiving input data includes detecting a data file or data stream containing experimental data produced by one of the one or more instruments, and using the detected data as the input data.

16. The method of claim 1, wherein:

processing the input data includes using the data parser description to read data from only a portion of the input data.

17. The method of claim 1, wherein:

defining the data parser description includes defining a plurality of data parser descriptions; and

processing the input data includes processing the input data according to the plurality of data parser descriptions, a first portion of the input data being processed according to a first one of the plurality of data parser descriptions and a second portion of the input data being processed according to a second one of the plurality of data parser descriptions.

18. The method of claim 1, wherein defining the data parser description includes:

providing a set of selectable nodes, in a graphical user interface; and

receiving user input selecting and configuring a plurality of the selectable nodes to define the tree structure of the data parser description.

19. A computer program product, tangibly embodied in a computer-readable storage medium, for processing electronic data having a first format, the product including instructions operable to cause data processing apparatus to perform operations comprising:

defining a data parser description describing the first format, the data parser description including a plurality of leaf nodes and a plurality of branch nodes arranged in a tree structure, the leaf nodes each having an associated function, each of the branch nodes having one or more associated child nodes selected from leaf nodes and other branch nodes;

receiving input data having the first format;

processing the input data according to the data parser description, the processing including evaluating the nodes of the data parser description in an order defined by the tree structure, the evaluating including;

if the node is a branch node, evaluating one or more of the associated child nodes;

if the node is a branch node, determining whether the node evaluates successfully based on a result of the evaluating one or more of the child nodes;

if the node is a leaf node, executing the associated function based on data in a current location in the input data;

if the node is a leaf node, determining whether the node evaluates successfully based on a result of the executing; and

after evaluating a given node, determining a next node to evaluate based on whether the given node has evaluated successfully; and

generating output data based on the processing.

20. The computer program product of claim 19, wherein:

generating output data includes generating structured output data having a structure defined at least in part by nodes of the data parser description.

21. The computer program product of claim 20, wherein:

the structured output data is generated as an extensible markup language document.

22. The computer program product of claim 21, wherein generating the structured output data includes:

for one or more leaf nodes of the data parser description, reading data from the current location in the input data, and associating the data read from the current location in the input data with an element of the extensible markup language document.

23. The computer program product of claim 21, wherein generating the structured output data includes:

for one or more leaf nodes of the data parser description, reading data from the current location in the input data, and executing a callback function to send the data read from the current location in the input data to a client; and

in the client, associating the sent data with an element of the extensible markup language document.

24. The computer program product of any claim 19, wherein:

the branch nodes include one or more first nodes, each first node being a branch node that evaluates successfully only if all of its associated child nodes evaluate successfully.

25. The computer program product of claim 24, wherein:

the first nodes include one or more second nodes, each second node being a first node that is evaluated in response to a call function associated with one or more leaf nodes.

26. The computer program product of claim 25, wherein:

the branch nodes include one or more third nodes, each third node being a branch node that evaluates successfully if any of its associated child nodes evaluates successfully.

27. The computer program product of claim 26, wherein:

the branch nodes include one or more fourth nodes, each fourth node being a branch node that defines a number of iterations over one or more child nodes.

28. The computer program product of claim 27, wherein:

the fourth node has a max parameter, a min parameter, and a counter value, and the fourth node is evaluated by;

evaluating each child node associated with the fourth node;

if each of the child nodes has evaluated successfully, incrementing the counter value, comparing the counter value with the max parameter, and, if the counter value is less than the max parameter, repeating the evaluating of each child node; and

if one or more of the child nodes has not evaluated successfully, comparing the counter value with the min parameter;

wherein, the fourth node has not evaluated successfully if one or more of the child nodes has not evaluated successfully and the counter value is less than the min parameter, and the fourth node has evaluated successfully if the counter value is equal to the max parameter or if one or more of the child nodes has not evaluated successfully and the counter value is greater than or equal to the min parameter.

29. The computer program product of claim 28, wherein:

the data parser description defines a tree containing a plurality of leaf nodes and a plurality of branch nodes selected from the group consisting of fourth nodes, first nodes, and third nodes, each first node being a branch node that evaluates successfully only if all of its associated child nodes evaluate successfully, each third node being a branch node that evaluates successfully if any of its associated child nodes evaluates successfully.

30. The computer program product of claim 19, wherein:

processing the input data includes, before evaluating a given node in the data parser description, storing a current position in the input data, and if the given node evaluates unsuccessfully, returning to stored position in the input data source before evaluating a subsequent node in the data parser description.

31. The computer program product of claim 19, wherein:

one or more of the nodes of the data parser description is configurable with a condition, the evaluation of a node configured with a condition being dependent on the performance of a test specified by the condition.

32. The computer program product of claim 19, wherein:

the input data is a data file or a data stream.

33. The computer program product of claim 19, including instructions operable to cause the data processing apparatus to perform operations further comprising:

monitoring output from one or more instruments, wherein ‘

receiving input data includes detecting a data file or data stream containing experimental data produced by one of the one or more instruments, and using the detected data as the input data.

34. The computer program product of claim 19, wherein:

processing the input data includes using the data parser description to read data from only a portion of the input data.

35. The computer program product of claim 19, wherein:

defining the data parser description includes defining a plurality of data parser descriptions; and

processing the input data includes processing the input data according to the plurality of data parser descriptions, a first portion of the input data being processed according to a first one of the plurality of data parser descriptions and a second portion of the input data being processed according to a second one of the plurality of data parser descriptions.

36. The computer program product of claim 19, wherein defining the data parser description includes:

providing a set of selectable nodes in a graphical user interface; and

receiving user input selecting and configuring a plurality of the selectable nodes to define the tree structure of the data parser description.

37. A data processing system for managing experimental data, comprising:

a data parser description describing a first data format, the data parser description including a plurality of leaf nodes and a plurality of branch nodes arranged in a tree structure, the leaf nodes each having an associated function, each of the branch nodes having one or more associated child nodes selected from leaf nodes and other branch nodes; and

a parsing engine for processing input data using a computer, the parsing engine having the first format according to the data parser description, the parsing engine being operable to process the input data by evaluating the nodes of the data parser description in an order defined by the tree structure and to generate output data based on the processing, the evaluating including;

if the node is a branch node, evaluating one or more of the associated child nodes;

if the node is a branch node, determining whether the node evaluates successfully based on a result of the evaluating one or more of the child nodes;

if the node is a leaf node, executing the associated function based on data in a current location in the input data;

if the node is a leaf node, determining whether the node evaluates successfully based on a result of the executing; and

after evaluating a given node, determining a next node to evaluate based on whether the given node has evaluated successfully.

38. The system of claim 37, wherein:

the parsing engine is operable to generate structured output data having a structure defined at least in part by nodes of the data parser description.

39. The system of claim 38, wherein:

the structured output data is generated as an extensible markup language document.

40. The system of claim 39, wherein:

the parsing engine is operable to generate the structured output data by, for one or more leaf nodes of the data parser description, reading data from the current location in the input data, and associating the data read from the current location in the input data with an element of the extensible markup language document.

41. The system of claim 39, further comprising a client process in communication with the parsing engine, wherein generating the structured output data includes:

for one or more leaf nodes of the data parser description, reading data from the current location in the input data, and executing a callback function to send the data read from the current location in the input data to the client process; and

in the client process, associating the sent data with an element of the extensible markup language document.

42. The system of claim 37, wherein:

the branch nodes include one or more first nodes, each first node being a branch node that evaluates successfully only if all of its associated child nodes evaluate successfully.

43. The system of claim 42, wherein:

the first nodes include one or more second nodes, each second node being a first node that is evaluated in response to a call function associated with one or more leaf nodes.

44. The system of claim 43, wherein:

the branch nodes include one or more third nodes, each third node being a branch node that evaluates successfully if any of its associated child nodes evaluates successfully.

45. The system of claim 44, wherein:

the branch nodes include one or more fourth nodes, each fourth node being a branch node that defines a number of iterations over one or more child nodes.

46. The system of claim 45, wherein:

the fourth node has a max parameter, a min parameter, and a counter value, and the parsing engine is operable to evaluate the fourth node by;

evaluating each child node associated with the fourth node;

if each of the child nodes has evaluated successfully, incrementing the counter value, comparing the counter value with the max parameter, and, if the counter value is less than the max parameter, repeating the evaluating of each child node; and

if one or more of the child nodes has not evaluated successfully, comparing the counter value with the min parameter;

wherein, the fourth node has not evaluated successfully if one or more of the child nodes has not evaluated successfully and the counter value is less than the min parameter, and the fourth node has evaluated successfully if the counter value is equal to the max parameter or if one or more of the child nodes has not evaluated successfully and the counter value is greater than or equal to the min parameter.

47. The system of claim 46, wherein:

the data parser description defines a tree containing a plurality of leaf nodes and a plurality of branch nodes selected from the group consisting of fourth nodes, first nodes, and third nodes, each first node being a branch node that evaluates successfully only if all of its associated child nodes evaluate successfully, each third node being a branch node that evaluates successfully if any of its associated child nodes evaluates successfully.

48. The system of claim 37, wherein:

the parsing engine operable to, before evaluating a given node in the data parser description, store a current position in the input data, and if the given node evaluates unsuccessfully, return to stored position in the input data source before evaluating a subsequent node in the data parser description.

49. The system of claim 37, wherein:

one or more of the nodes of the data parser description is configurable with a condition, the evaluation of a node configured with a condition being dependent on the performance of a test specified by the condition.

50. The system of claim 37, wherein:

the input data is a data file or a data stream.

51. The system of claim 37, wherein:

the parsing engine is operable to monitor output from one or more instruments to detect a data file or data stream containing experimental data produced by one of the one or more instruments, and use the detected data as the input data.

52. The system of claim 37, wherein:

the parsing engine is operable to use the data parser description to read data from only a portion of the input data.

53. The system of claim 37, wherein:

the system includes a plurality of data parser descriptions; and

the parsing engine is operable to process the input data according to the plurality of data parser descriptions, a first portion of the input data being processed according to a first one of the plurality of data parser descriptions and a second portion of the input data being processed according to a second one of the plurality of data parser descriptions.

54. The system of claim 37, further comprising:

means for defining the data parser description, the means for defining the data parser description including means providing a set of selectable nodes in a graphical user interface, and means for receiving user input selecting and configuring a plurality of the selectable nodes to define the tree structure of the data parser description.