US5475588A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for decreasing the time required to parse a sentence
Assignee: Benhov GmbH LLC
•
Filing: 1993-06-18
•
Granted: 1995-12-12
•
Expires: 2013-06-18
Abstract
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.
Inventors
- 👤 Yves Schabes
- 👤 Richard C. Waters
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 06:56
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/253
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
94 words
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.
Claim 2
Independent Claim
94 words
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.
Claim 3
Dependent Claim
20 words
The system of claim 1, and further including means for indicating when a sentence is ungrammatical and therefore not parsable.
Claim 4
Dependent Claim
14 words
The system of claim 1, and further including means for displaying said parse trees.
Claim 5
Dependent Claim
84 words
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.
Claim 6
Dependent Claim
50 words
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 3 parsing time, where k is a constant and n is the number of words in said sentence.
Claim 7
Dependent Claim
34 words
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.
Claim 8
Dependent Claim
20 words
The system of claim 5, wherein said parsing means further includes means for maintaining the valid prefix property during parsing.
References Cited (Backward Citations)
US4688195A
Cited
US4829423A
Cited
US4667290A
Cited
US5083268A
Cited
US4887212A
Cited
US5111398A
Cited
US5095432A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-12-11 | 1999-06-12 | 1999-12-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-12-11 | 2003-06-12 | 2003-12-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-12-11 | 2007-06-12 | 2007-12-12 | $7700.00 | Window Closed / Lapsed |