Dynamic parser

• US 7,962,904 B2
• Filed: 05/10/2007
• Issued: 06/14/2011
• Est. Priority Date: 05/10/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zabokritski, Evgueni
• Primary Examiner(s): WANG, RONGFA PHILIP
• Application Number:
  US11/746,717
• Publication Number:
  US 20080281580A1
• Time in Patent Office: 1,496 Days
• Field of Search: None
• US Class Current: 717/143
• 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, the method performed upon one or more computer processors, the method comprising:

selecting a set of grammar rules, the set of grammar rules comprising declarations of one or more conditional tokens;

evaluating a set of tokens according to the set of grammar rules;

identifying a token of the set of tokens as a conditional token for transformation;

managing transformation of the identified token;

transforming the identified token at parse time by invoking an independent transform function that transforms the token to a subtoken associated with the identified token such that transformation of the token is a function of context for the token; and

parsing the transformed token.

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

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

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

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

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

8. A computer program product comprising one or more computer-readable devices having encoded therein computer executable instructions which, when executed upon one or more computer processors, perform the method of claim 1.

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