DYNAMIC PARSER

• US 20080281580A1
• Filed: 05/10/2007
• Published: 11/13/2008
• Est. Priority Date: 05/10/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zabokritski, Evgueni
• Granted Patent: US 7,962,904 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

The subject disclosure pertains to systems and methods for dynamic parsing. A dynamic parser can perform syntactic analysis or parsing of input data consisting of a set of tokens based upon a provided grammar including conditional tokens. While the parser grammar can be fixed, the dynamic parser can utilize an independent transform function at parse time to translate or replace particular tokens, effectively performing dynamic parsing. The transform function can be utilized in conjunction with conditional tokens to selectively activate and deactivate particular grammar rules. Additionally, systems and methods for automatically generating a dynamic parser from a grammar description are described herein.

Claims

1. A method for performing dynamic syntactic analysis, comprising:

identifying a token of a set of tokens for transformation;

managing transformation of the identified token; and

parsing the transformed token.

2. The method for claim 1, transformation occurs at parse time.

3. The method of claim 1, further comprising invoking an independent transform function that transforms the token to a subtoken associated with the identified token.

4. The method of claim 1, transformation of the token is a function of context for the token.

5. The method of claim 1, further comprising analyzing the transformed token as a function of a formal grammar.

6. The method of claim 5, the formal grammar includes a declaration that describes the transformation of the identified token.

7. The method of claim 5, further comprising generating an error that indicates nonconformance of the set of tokens with the formal grammar.

8. The method of claim 7, the analysis of the transformed token utilizes lookahead to evaluate compliance with a formal grammar.

9. The method of claim 1, further comprising generating an output data structure based at least in part upon the transformed token.

10. The method of claim 1, further comprising utilizing lexical analysis to obtain the set of tokens from input data.

11. A system that facilitates generation of a dynamic parser, comprising:

a grammar component that analyzes a grammar; and

a parser component that generates a dynamic parser as a function of the grammar analysis.

12. The system of claim 11, further comprising a conflict component that evaluates the consistency of the grammar for conflicts.

13. The system of claim 12, further comprising an error handling component that generates an error message that identifies the conflicts.

14. The system of claim 11, the dynamic parser utilizes an independent translation component that translates tokens at parse time.

15. The system of claim 11, further comprising:

a table generation component that generates a data table as a function of the grammar; and

a driver generation component that generates a driver that utilizes the data table to perform parsing of tokens.

16. The system of claim 11, the grammar includes a declaration that defines a parent token and at least one child token, such that during parsing the parent token is replaced by the at least one child token as a function of context of the parent token.

17. The system of claim 16, further comprising a conflict component that analyzes the grammar, the conflict component detects a shift/shift conflict.

18. The system of claim 16, the grammar includes a statement that defines context for the parent token and the at least one child token.

19. An apparatus that facilitates dynamic parsing, comprising:

means for identifying a token of a set of tokens for transformation; and

means for managing transformation of the identified token.

20. The apparatus of claim 19, further comprising means for invoking an independent transform function that transforms the token to a subtoken of the identified token.