Left-corner chart parsing

• US 7,236,925 B2
• Filed: 10/04/2005
• Issued: 06/26/2007
• Est. Priority Date: 02/22/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Moore, Robert C.
• Primary Examiner(s): Azad; Abul K.
• Application Number:
  US11/242,767
• Publication Number:
  US 20060036429A1
• Time in Patent Office: 630 Days
• Field of Search: None
• US Class Current: 704/10
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Different embodiments of the present invention provide improvements to left-corner chart parsing. The improvements include a specific order of filtering checks, transforming the grammar using bottom-up prefix merging, indexing productions first based on input symbols, grammar flattening, and annotating chart edges for the extraction of parses.

Claims

1. A method of indexing productions for use in a left-corner chart parser which parses input text containing input symbols, the method comprising:

indexing the productions first based on input symbols which are consistent with the productions; and

generating a data structure comprising one or more discrimination trees corresponding to productions with one or more second daughters that have a left corner comprising one of the input symbols.

2. The method of claim 1 wherein indexing comprises:

precomputing which of the productions are consistent with which of the input symbols.

3. The method of claim 2 wherein precomputing comprises:

precomputing, for each possible input symbol, which productions have a second daughter with that input symbol as a left corner.

4. The method of claim 1 and further comprising:

indexing the productions next based on a left-most daughter of the productions.

5. The method of claim 4 and further comprising:

indexing the productions next based on a mother of the productions.

6. The method of claim 5 and further comprising:

enumerating the productions based on remainder of the productions, other than the left-most daughter and the mother.

7. A method of parsing input text using a left-corner chart parsing process, comprising:

receiving an input symbol in the input text;

accessing an input symbol index comprising one or more discrimination trees corresponding to productions with one or more second daughters that have a left corner comprising one of the input symbols;

obtaining productions from the input symbol index wherein the input symbol is a left corner of the second daughter; and

after obtaining the productions having the input symbol as a left corner of the second daughter, accessing other indices to the productions.

8. The method of claim 7 wherein accessing other indices comprises:

accessing a left-most daughter index to obtain productions based on their left-most daughter.

9. The method of claim 8 wherein accessing other indices comprises:

accessing a mother index to obtain productions based on their mother.

10. The method of claim 9 and further comprising:

accessing a list containing a completion of productions that are obtained by accessing the left-most daughter index and the mother index.

11. A computer-readable data structure indexing productions used in a left-corner chart parser which parses input text, the data structure comprising:

one or more index portions implemented as a set of nested hash tables, the index portions comprising a first index portion indexing the productions first based on input symbols which are consistent with the productions; and

a function which, when executed by the computer, traces the indexed productions to parse the input text.

12. The data structure of claim 11 wherein the first index portion indexes productions by input symbol based on which productions have the input symbol as a left corner of the second daughter.

13. The data structure of claim 12 wherein the index portions further comprise a second index portion indexing the productions based on a left-most daughter of the productions.

14. The data structure of claim 13 wherein the index portions further comprise a third index portion indexing the productions based on a mother of the productions.

15. The data structure of claim 14 wherein the index portions further comprise a fourth index portion enumerating the productions based on a remainder of the productions, other than the left-most daughter and the mother of the productions.