Immutable parsing

• US 8,762,969 B2
• Filed: 08/07/2008
• Issued: 06/24/2014
• Est. Priority Date: 08/07/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Meijer, Henricus Johannes Maria, Dyer, John Wesley, Meschter, Thomas, Najmabadi, Cyrus
• Primary Examiner(s): TECKLU, ISAAC TUKU
• Application Number:
  US12/187,753
• Publication Number:
  US 20100037212A1
• Time in Patent Office: 2,147 Days
• Field of Search: None
• US Class Current: 717/143
• CPC Class Codes: G06F 8/427 Parsing

Abstract

Immutable structures are employed to effect immutable parsing. In particular, an immutable 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. 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. An immutable 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 the tokens to determine a grammatical structure, at least one of the first and second components employ an immutable parser configuration including an immutable stack and an immutable input buffer.

2. The system of claim 1, the second component is configured to produce an immutable parse tree.

3. The system of claim 2, the second component is configured to generate multiple versions of the parse tree that share common pre-existing portions.

4. The system of claim 3 further comprising a third component configured to provision one or more services to respond to one or more inquires regarding the parse tree.

5. The system of claim 4, at least one of the one or more services defers computation of the parse tree or portions thereof until needed.

6. The system of claim 1, the immutable input buffer saves a history of enumeration for potential backtracking.

7. The system of claim 1, the immutable stack is a rooted directed, acyclic graph that saves multiple pasts.

8. The system of claim 1 further comprising an interface component configured to pass the immutable parser configuration to another component for conflict resolution or error recover without risk of parser state corruption.

9. The system of claim 1, one or both of the first and second components exploit the immutability of the parser configuration to execute in parallel.

10. A parsing method, comprising:

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

parsing an input stream with one or more immutable parser configurations including an immutable stack and immutable lookahead buffer; and

producing an immutable parse tree as a function of the parsing.

11. The method of claim 10 further comprising deferring computation of input elements from the lookahead buffer until needed.

12. The method of claim 10 further comprising identifying a conflict during parsing and passing a current parser configuration to a method that identifies a conflict resolution strategy based on the configuration.

13. The method of claim 10 further comprising detecting a parsing error and passing a current parser configuration to a method that affords an error recovery strategy as a function of the configuration.

14. The method of claim 10 further comprising forking execution of parsing operations across multiple threads of execution processing utilizing copies of the immutable configuration.

15. The method of claim 10 further comprising producing different versions of the stack and lookahead buffer that share common unchanged elements.

16. The method of claim 10 further comprising producing multiple versions of the parse tree that share common, unchanged nodes.

17. The method of claim 16 further comprising:

detecting a change in the input stream;

reparsing the input stream to produce a new immutable token stream that shares tokens common to a previous stream; and

producing a new immutable parse tree that shares nodes with a previous tree.

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

generating a second immutable token stream that shares tokens with a first immutable token stream by reference to at least a portion of the first immutable token stream after detecting a change in an input; and

constructing a second immutable parse tree that shares nodes with a first immutable parse tree by reference to at least a portion of the first immutable parse tree as a function of the first and second immutable token streams generating the second immutable token stream with an immutable parser configuration including an immutable stack and immutable lookahead buffer.

19. The computer-readable storage medium of claim 18, the method further comprises determining tokens affected by the change in the input.