Left-corner chart parsing

Patent 7103535 Issued on September 5, 2006. Estimated Expiration Date:

August 26, 2024. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

System and method for parsing natural language by unifying lexical features of words
Patent #: 5083268
Issued on: 01/21/1992
Inventor: Hemphill, et al.

Parsing system
Patent #: 5687384
Issued on: 11/11/1997
Inventor: Nagase

Method of conjoining clauses during unification using opaque clauses
Patent #: 5903860
Issued on: 05/11/1999
Inventor: Maxwell, III, et al.

Method, device and system for generalized bidirectional island-driven chart parsing Patent #: 6128596
Issued on: 10/03/2000
Inventor: Mackie

Inventor

Moore, Robert C.

Assignee

Microsoft Corporation

Application

No. 10926512 filed on 08/26/2004

US Classes:

704/9, Natural language704/4, Based on phrase, clause, or idiom706/11, HAVING PARTICULAR USER INTERFACE704/257Natural language

Examiners

Primary: Azad, Abul K.

Attorney, Agent or Firm

International Class

G06F 17/21

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.

Other References

Communications of the ACM. Programming Languages “On the Relative Efficiencies of Context-Free Grammar Recognizers” by T.V. Griffiths and S.R. Petrick Air Force Cambridge Research Laboratories, Bedford Mass. vol. 8/No. 5/May 1965, pp. 289-300.
Third Conference of the European Chapter of the Association for Computational Linguistic. “A comparison of rule-invocation strategies in context-free chart parsing”, by Mats Wiren. Apr. 1987, pp. 226-233.
Information Processing Letters: Devoted to the Rapid Publication of Short Contributions to Information. A Recursive Ascent Earley Parser, by Rene Leemarkers, Feb. 1992, pp 87-91.
ACM Transactions on Programming Languages and System. “An Improved Context-Free Recognizer” by Susan L. Grahm, Michael A. Harrison, and Walter L. Ruzzo, University of California at Berkley, vol. 2, No. 3, Jul. 1980, pp. 415-462.
“Linguistic Parsing and Programming Transformations”, Chapter 2, Generalized Left-Corner Parsing, by Mark Jan Nederhof, Oct. 1966.