Method and system for generating a parser and parsing complex data

• US 9,495,353 B2
• Filed: 10/28/2014
• Issued: 11/15/2016
• 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/526,066
• Publication Number:
  US 20150046481A1
• Time in Patent Office: 749 Days
• Field of Search: 704/9, 704/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• 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, wherein each handler definition of the one or more handler definitions comprises a handler action definition and at least one handler definition of the one or more handler definitions comprises a handler listener definition; and

generate the parser using the parser definition, wherein the parser comprises a parsing pipeline comprising two or more handlers, wherein output from a first handler of the two or more handlers is provided to a second handler of the two or more handlers; and

execute the generated parser.

2. The system of claim 1, wherein:

a handler action definition comprises definitions for one or more actions; and

a handler listener definition 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.

15. The method of claim 1, wherein at least one of the two or more handlers is a default handler.

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, wherein each handler definition of the one or more handler definitions comprises a handler action definition and at least one handler definition of the one or more handler definitions comprises a handler listener 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, wherein output from a first handler of the two or more handlers is provided to a second handler of the two or more handlers; and

executing the generated parser.

7. The method of claim 6, wherein:

a handler action definition comprises definitions for one or more actions; and

a handler listener definition 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, wherein each handler definition of the one or more handler definitions comprises a handler action definition and at least one handler definition of the one or more handler definitions comprises a handler listener 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, wherein output from a first handler of the two or more handlers is provided to a second handler of the two or more handlers; and

executing the generated parser.

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

a handler action definition comprises definitions for one or more actions; and

a handler listener definition comprises one or more string comparisons.