Method and system for generating a parser and parsing complex data

• US 8,855,999 B1
• Filed: 02/05/2014
• Issued: 10/07/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Elliot, Mark
• Primary Examiner(s): Godbold, Douglas
• Application Number:
  US14/173,743
• Publication Number:
  US 20140278371A1
• Time in Patent Office: 244 Days
• Field of Search: 704/1, 704/9, 704/10
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 8/427 Parsing

Abstract

Computer-implemented systems and methods are disclosed for constructing a parser that parses complex data. In some embodiments, a method is provided for receiving a parser definition as an input to a parser generator and generating a parser at least in part from the parser definition. In some embodiments, the generated parser comprises two or more handlers forming a processing pipeline. In some embodiments, the parser receives as input a first string into the processing pipeline. In some embodiments, the parser generates a second string by a first handler and inputs the second string regeneratively into the parsing pipeline, if the first string matches an expression specified for the first handler in the parser definition.

Claims

1. A system configured to generate a parser, the system comprising:

a memory device configured to store a set of instructions; and

one or more processors configured to execute the set of instructions to perform the following operations;

receive a parser definition as an input to a parser generator, the parser definition including one or more handler definitions including a handler action definition; and

generate the parser using the parser definition, wherein the parser comprises a parsing pipeline comprising two or more handlers based on the one or more handler definitions,

wherein at least one handler definition of the one or more handler definitions includes a handler listener definition that comprises a definition for an expression used for evaluating an input string to the parsing pipeline, and

wherein the one or more handler action definitions collectively comprise one or more definitions for one or more actions to be performed based on the evaluation, the one or more actions include generating a first string based on the input string and inputting the first string, regeneratively, to the parsing pipeline.

2. The system of claim 1, wherein:

the expression used for evaluating the input string comprises one or more string comparisons.

3. The system of claim 2, wherein two or more string comparisons are associated through a Boolean expression.

4. The system of claim 1, wherein the one or more processors are configured to execute further instructions to perform the following operation:

store the generated parser in a parser cache.

5. The system of claim 4, wherein the one or more processors are configured to execute further instructions to perform the following operations:

receive a request to execute the generated parser;

retrieve the generated parser from the parser cache; and

execute the generated parser retrieved from the parser cache, wherein the executed parser acts on data to generate an output.

6. A method for generating a parser, the method being performed by one or more processors and comprising:

receiving a parser definition as an input to a parser generator, the parser definition including one or more handler definitions including a handler action definition; and

generating, using one or more processors, a parser using the parser definition, wherein the parser comprises a parsing pipeline comprising two or more handlers based on the one or more handler definitions,

wherein at least one handler definition of the one or more handler definitions includes a handler listener definition that comprises a definition for an expression used for evaluating an input string to the parsing pipeline, and

wherein the one or more handler action definitions collectively comprise one or more definitions for one or more actions to be performed based on the evaluation, the one or more actions include generating a first string based on the input string and inputting the first string, regeneratively, to the parsing pipeline.

7. The method of claim 6, wherein

wherein the expression used for evaluating the input string comprises one or more string comparisons.

8. The method of claim 7, wherein two or more string comparisons are associated through a Boolean expression.

9. The method of claim 6, further comprising storing, with one or more processors, the generated parser in a parser cache.

10. The method of claim 9, further comprising:

receiving a request to execute the generated parser;

retrieving the generated parser from the parser cache; and

executing the generated parser retrieved from the parser cache, wherein the executed parser acts on data to generate an output.

11. The method of claim 9, wherein the storing further comprises selecting an entry into which the constructed parser will be stored within the parser cache.

12. The method of claim 11, wherein the selected entry is determined at least in part by identifying the cache entry that was least recently used.

13. A non-transitory computer readable medium that stores a set of instructions that are executable by at least one processor of an electronic device to cause the electronic device to perform a method for generating a parser, the method comprising:

receiving a parser definition as an input to a parser generator, the parser definition including one or more handler definitions including a handler action definition; and

generating a parser using the parser definition, wherein the parser comprises a parsing pipeline comprising two or more handlers based on the one or more handler definitions,

wherein at least one handler definition of the one or more handler definitions includes a handler listener definition that comprises a definition for an expression used for evaluating an input string to the parsing pipeline, and

wherein the one or more handler action definitions collectively comprise one or more definitions for one or more actions to be performed based on the evaluation, the one or more actions include generating a first string based on the input string and inputting the first string, regeneratively, to the parsing pipeline.

14. The non-transitory computer readable medium of claim 13, wherein

the expression used for evaluating the input string comprises one or more string comparisons.

15. The non-transitory computer readable medium of claim 14, wherein two or more string comparisons are associated through a Boolean expression.

16. The non-transitory computer readable medium of claim 13, further comprising instructions executable by the at least one processor of the electronic device to cause the electronic device to perform:

storing the generated parser in a parser cache.

17. The non-transitory computer readable medium of claim 16, further comprising instructions executable by the at least one processor of the electronic device to cause the electronic device to perform:

receiving a request to execute the generated parser;

retrieving the generated parser from the parser cache; and

executing the generated parser retrieved from the parser cache, wherein the executed parser acts on data to generate an output.