IMMUTABLE PARSING

• US 20100037212A1
• Filed: 08/07/2008
• Published: 02/11/2010
• Est. Priority Date: 08/07/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Najmabadi, Cyrus, Meschter, Thomas, Meijer, Henricus Johannes Maria, Dyer, John Wesley
• Granted Patent: US 8,762,969 B2
• Time in Patent Office: Days
• US Class Current: 717/142
• 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 first component that performs lexical analysis of an input sequence to produce a sequence of tokens; and

a second component that performs syntactic analysis on the tokens to determine a grammatical structure, at least one of the first and second components employ immutable parsing configurations, each configuration including an immutable stack and an immutable input buffer.

2. The system of claim 1, the second component produces an immutable parse tree.

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

4. The system of claim 3, further comprising a component that provisions one or more services to facilitate response to inquires regarding parse tree.

5. The system of claim 4, at least one of the one or more services performs lazy computation of the parse tree.

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 that passes 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 leverage the immutability of the parser configuration to execute in parallel.

10. A parsing method, comprising:

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 lazily computing input elements from the lookahead buffer.

12. The method of claim 10, further comprising identifying a conflict during parsing and passing a current parser configuration to 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 medium having stored thereon a parser configuration, comprising:

an immutable look ahead buffer that includes a sequence of characters for processing; and

an immutable stack that provides a historical account of processed characters.

19. The computer-readable medium of claim 18, the buffer records multiple previous states for potential backtracking.

20. The computer-readable medium of claim 18, the stack is a rooted, directed, acyclic graph with a single sink node that allows a parser record multiple pasts.