Left-corner chart parsing
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
14 Citations
15 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15)
-
Specification