System for decreasing the time required to parse a sentence

• US 5,475,588 A
• Filed: 06/18/1993
• Issued: 12/12/1995
• Est. Priority Date: 06/18/1993
• Status: Expired due to Term

• Current Assignee: Binary Services LLC (Intellectual Ventures LLC)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Schabes, Yves, Waters, Richard C.
• Primary Examiner(s): Weinhardt, Robert A.
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US08/079,633
• Time in Patent Office: 907 Days
• Field of Search: 364/419.08, 364/419.01, 395/12, 395/700, 395/800, 395/600, 395/650, 395/200, 395/375
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

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.

Claims

1. 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.

2. The system of claim 1, and further including means for indicating when a sentence is ungrammatical and therefore not parsable.

3. The system of claim 1, and further including means for displaying said parse trees.

4. The system of claim 1, wherein said converting means includes

means for developing a graph representing the interaction of the rules of said context-free grammar, said graph including acyclic and cyclic paths, with at least one of said cyclic paths being a minimal cyclic path;

means for creating an initial tree from each acyclic path in said graph; and

,

means for creating a non-wrapping auxiliary tree from each minimal cyclic path in said graph, said initial and auxiliary trees forming said lexicalized context-free grammar.

5. The system of claim 1, wherein said parsing means includes means for analyzing said sentence by selecting for consideration during the parsing process only adjacent groups of words, thereby to achieve k*n³ parsing time, where k is a constant and n is the number of words in said sentence.

6. The system of claim 5, wherein said parsing means further includes means for dynamic filtering of said lexicalized context-free grammar to select for parsing only those rules that contain a word in said sentence.

7. The system of claim 5, wherein said parsing means further includes means for maintaining the valid prefix property during parsing.