System for decreasing the time required to parse a sentence
AssigneeMitsubishi Electric Research Laboratories, Inc.
InventorsYves Schabes, Richard C. Waters
Life of this patent
Estimating the term…
Abstract
A system is provided for dramatically decreasing the time required to parse a sentence by automatically converting a context-free grammar into a lexicalized form called lexicalized context-free grammar (LCFG) which is used in the parsing process. Lexicalized context-free grammar employs adjoining but, to decrease parsing time, only allows non-wrapping adjoining. The lexicalized context-free grammar is parsed using a parser that decreases parsing time by filtering the grammar based on the words in a sentence and maintaining the valid prefix property while parsing.
Claims7
A system for parsing sentences, comprising:
- means for providing a sentence to be parsed;
- means for providing a context-free grammar;
- means for converting said context-free grammar into a lexicalized context-free grammar, said lexicalized context-free grammar employing adjoining, but only allowing non-wrapping adjoining;
- and
- means coupled to said converting means for parsing said sentence in accordance with said lexicalized context-free grammar, said parsing means including means for determining if the sentence is parsable, and if parsable means for producing a corresponding parse tree;
- and,
- means coupled to said parsing means for utilizing said parse tree.
Dependencies are inferred from the claim text.