Method and system for computing semantic logical forms from syntax trees

• US 5,966,686 A
• Filed: 06/28/1996
• Issued: 10/12/1999
• Est. Priority Date: 06/28/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Heidorn, George, Jensen, Karen
• Primary Examiner(s): Thomas, Joseph
• Application Number:
  US08/674,610
• Time in Patent Office: 1,201 Days
• Field of Search: 704/9, 704/8, 704/1, 704/10, 395/12, 707/100, 707/101, 707/102, 707/104
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

Methods and computer systems for semantically analyzing natural language sentences. The natural language processing subsystems for morphological and syntactic analysis transform an input sentence into a syntax parse tree. Semantic analysis applies three sets of semantic rules to create a skeletal logical form graph from a syntax parse tree. Semantic analysis then applies two additional sets of semantic rules to provide semantically meaningful labels for the links of the logical form graph, to create additional logical form graph nodes for missing elements, and to unify redundant elements. The final logical form graph represents the complete semantic analysis of an input sentence.

Claims

1. A method in a computer system for generating a logical form graph for a phrase of words specified in a natural language, the natural language having a grammar specifying syntax of the natural language, the computer system having a memory the method comprising:

generating in the memory all initial syntax parse tree of the phrase based on the grammar of the natural language, the initial syntax parse tree containing nodes representing syntactic construct of the words of the phrase;

adjusting the initial syntax parse tree to complete syntactic analysis for syntactic constructs that arc implicit in the phrase;

generating in the memory a skeletal logical form graph for the adjusted syntax parse tree, the skeletal logical form graph being represented in a data structure that is independent of a data structure of the syntax parse tree; and

adjusting the skeletal logical form graph to identify semantic constructs to complete the logical form graph.

2. The method of claim 1 wherein the step of adjusting the initial syntax parse tree includes adding syntactic roles to the syntax parse tree for any syntactic constructs that are implicit in the phrase.

3. The method of claim 1 wherein the step of adjusting the skeletal logical form graph includes adding semantic labels to the generated skeletal logical form graph.

4. A computer-readable medium containing instructions for causing a computer system to generate a logical form graph for a sentence specified in a natural language, the natural language having a grammar specifying syntax of the natural language, the computer system having an initial syntax parse tree of the sentence that represents a parse of the sentence based on the grammar of the natural language, the initial syntax parse tree containing nodes representing syntactic construct of words of the sentence, the initial syntax parse tree being stored in memory of the computer system by:

adjusting the initial syntax parse tree to complete syntactic analysis for syntactic constructs that are implicit in the sentence;

generating in memory of The computer system a skeletal logical form graph for the adjusted syntax parse tree, the skeletal logical form graph being represented in a data structure that is independent of a data structure of the syntax parse tree; and

adjusting the skelctal logical form graph to identify semantic constructs to complete the logical form graph for the sentence.

5. The computer-readable medium of claim 4 wherein the adjusting of the initial syntax parse tree includes adding syntactic roles to the syntax parse tree for any syntactic constructs that are implicit in the sentence.

6. The computer-readable medium of claim 4 wherein adjusting of the skeletal logical form graph includes adding semantic labels to the generated skeletal logical form graph.

7. A method in a computer system for processing input text representing a phrase or sentence of a natural language in order to represent in the computer system at least one meaning of the input text that a human speaker of the natural language would understand the input text to represent, the method comprising the steps of:

generating in memory of the computer system a first data structure for a syntax parse tree from the input text to represent a syntactic analysis of the input text; and

generating in memory of the computer system a second data structure for a logical form graph to represent a semantic analysis of the input text, the second data structure being generated from the syntax parse tree but being a separate data structure from the first data structure.

8. A computer system for processing input text representing a phrase or sentence of a natural language in order to represent in the computer system at least one meaning of the input text that a human speaker of the natural language would understand the input text to represent, the system comprising:

a component that generates in memory of the computer system a syntax parse tree from the input text to represent a syntactic analysis of the input text; and

a component that generates in memory of the computer system a logical form graph to represent a semantic analysis of the input text, the logical form graph being stored in a data structure that is separate from a data structure in which the generated syntax parse tree is stored, the logical form graph being generated based in part on the generated syntax parse tree.

9. The system of claim 8 wherein the component that generates a separate logical form graph comprises the following sub-components:

a first sub-component that generates an initial skeletal logical form graph; and

a second sub-component that identifies semantic roles for the nodes of the skeletal logical form graph and labels the directed links of the skeletal logical form graph to produce a final, complete logical form graph.