IMMUTABLE PARSING

• US 20140289715A1
• Filed: 06/02/2014
• Published: 09/25/2014
• Est. Priority Date: 08/07/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meijer, Henricus Johannes Maria, Dyer, John Wesley, Meschter, Thomas, Najmabadi, Cyrus
• Application Number:
  US14/294,107
• Publication Number:
  US 20140289715A1
• Time in Patent Office: Days
• US Class Current: 717/143
• CPC Class Codes: G06F 8/427 Parsing

Abstract

Immutable structures are employed to effect immutable parsing. In particular, a parsing configuration, comprising a stack and lookahead buffer, is utilized by a parser to perform lexical and syntactical analysis of an input stream and optionally output an immutable parse tree or the like, wherein at least one of the stack and buffer is immutable. Performance with respect to the immutable structures can be optimized utilizing sharing and lazy computation. In turn, immutability benefits are afforded with respect to parsing including safe sharing amongst services and/or across multiple threads as well as history preservation, among other things.

Claims

1. A parsing method, comprising:

employing at least one processor configured to execute computer-executable instructions stored in memory to perform the following act;

parsing an input stream with at least one of an immutable stack or immutable lookahead buffer.

2. The method of claim 1 further comprises producing an immutable parse tree as a function of the parsing.

3. The method of claim 2 further comprises producing multiple versions of the parse tree that share common portions.

4. The method of claim 1 further comprises deferring producing at least a portion of a parse tree from input elements of the lookahead buffer until the at least a portion of the parse tree is needed for a computation.

5. The method of claim 1 further comprises detecting a conflict during parsing and passing a current parser configuration including the stack and the lookahead buffer to a method that identifies a conflict resolution strategy based on the configuration.

6. The method of claim 1 further comprises detecting a parsing error and passing a current parser configuration including the stack and lookahead buffer to a method that affords an error recovery strategy as a function of the configuration.

7. The method of claim 1 further comprises dividing execution of parsing across multiple threads of execution with multiple copies of a configuration including the stack and lookahead buffer.

8. The method of claim 1 further comprises producing a version of the stack or lookahead buffer that shares common unchanged elements.

9. The method of claim 1 further comprises:

detecting a change in the input stream; and

producing a new immutable token stream that shares tokens in common with a previous stream of tokens.

10. A parser system, comprising:

a processor coupled to a memory, the processor configured to execute the following computer-executable components stored in the memory;

a first component configured to perform lexical analysis of an input sequence to produce a sequence of tokens; and

a second component configured to perform syntactic analysis on a sequence of tokens produced from an input sequence to determine a grammatical structure, at least one of the first and second components employ a parser configuration including a stack and buffer, at least one of the stack or the buffer is immutable.

11. The system of claim 10, the second component produces an immutable parse tree.

12. The system of claim 10, the second component generates multiple versions of a parse tree that share common portions.

13. The system of claim 10 further comprising a third component configured to provide one or more services to respond to one or more inquiries regarding a parse tree.

14. The system of claim 13, at least one of the one or more services defers constructing a parse tree, or portion thereof, until needed to respond to at least one of the one or more inquiries.

15. The system of claim 10 further comprises a third component configured to pass the parser configuration to a fourth component configured to perform conflict resolution based on the parser configuration.

16. The system of claim 10 further comprising a third component configured to provide the parser configuration to a fourth component configured to perform error recovery based on the parser configuration.

17. The system of claim 10, the first component and the second component execute in parallel with immutable parser configurations including an immutable stack and buffer.

18. A computer-readable storage medium having stored thereon instructions that when executed perform a method, the method comprising:

parsing an input stream with at least one of an immutable stack or immutable lookahead buffer.

19. The computer-readable storage medium of claim 18, the method further comprises producing an immutable parse tree as a function of the parsing.

20. The computer-readable storage medium of claim 19, the method further comprises producing multiple versions of the parse tree that share common portions.