Method and apparatus for robust efficient parsing

• US 20060116868A1
• Filed: 01/11/2006
• Published: 06/01/2006
• Est. Priority Date: 08/21/2001
• Status: Active Grant

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

Abstract

The present invention provides a method for improving the efficiency of parsing text. Aspects of the invention include representing parse tokens as integers where a portion of the integer indicates the location in which a definition for the token can be found. In a further aspect, an integer representing a token points to an array of tokens that can be activated by the token. In another aspect, a list of pointers to partial parses is created before attempting to parse a next word in the text string. The list of pointers includes pointers to partial parses that are expecting particular semantic tokens.

Claims

1. A method of parsing text in a computing device to form a logical representation of the text, the logical representation having tokens representing non-terminals and words of the text, the method comprising:

selecting a token;

identifying an integer that represents the selected token; and

utilizing the integer to identify at least one non-terminal token of the logical representation that begins with the selected token.

2. The method of claim 1 wherein identifying an integer comprises identifying an integer that points to an identifier array, each cell in the identifier array providing a token identifier for a token that begins with the selected token.

3. The method of claim 2 wherein the token identifiers are integers.

4. The method of claim 3 wherein each token identifier integer comprises a table identifying portion and an offset portion, the table identifying portion identifying a table that contains an array of definitions for tokens including the token represented by the token identifier integer and the offset portion identifying the location of the definition for the token represented by the token identifier integer.

5. The method of claim 4 wherein each cell in the identifier array further provides an indication of a rule in which the token represented by the token identifier integer begins with the selected token.

6. A method of parsing text to form a tokenized representation of the text, the method comprising:

selecting a word from the text;

forming a partial parse of a token based on the selected word;

identifying an item that is needed to extend the partial parse; and

placing a pointer to the partial parse in a table associated with a next word in the text, the pointer being mapped from the item that is needed to extend the parse.

7. The method of claim 6 wherein placing a pointer comprises placing a pointer to an array in the table, wherein the array contains at least two partial parses that can be extended by a same item.

8. The method of claim 6 wherein identifying an item comprises identifying a word.

9. The method of claim 6 wherein identifying an item comprises identifying a non-terminal.

10. A method of parsing text to identify a parse structure containing tokens that represent non-terminals and words, the method comprising:

converting a selected token into a token ID;

using a first portion of the token ID to identify a table containing definitions for tokens of a same type as the selected token;

using a second portion of the token ID to locate the definition for the selected token in the identified table; and

using the definition for the selected token as part of the method of identifying the parse structure.