Method and apparatus for determining unbounded dependencies during syntactic parsing

• US 7,113,905 B2
• Filed: 12/20/2001
• Issued: 09/26/2006
• Est. Priority Date: 12/20/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Parkinson, David J., Calcagno, Michael
• Primary Examiner(s): Hudspeth, David
• Assistant Examiner(s): Wozniak, James S.
• Application Number:
  US10/028,228
• Publication Number:
  US 20030120479A1
• Time in Patent Office: 1,741 Days
• Field of Search: 704/1, 704/4, 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

A method is provided for identifying non-local relationships between licensing elements in a text segment and a word or phrase external to the text segment during a syntactic parse. Under the method, certain syntactic rules for combining words or phrases with text segments indicate that there is a possibility that the word or phrase being combined with the text segment will fill a gap in a relationship within the text segment. Based on this possibility, the text segment is searched to determine if there are any unfilled gaps in the text segment. Under some embodiments, if an unfilled gap is found, the location of the gap and the role the word or phrase plays in the gap are stored in a data structure associated with the syntactic node formed by combining the word or phrase with the text segment.

Claims

1. A method of identifying non-local linguistic relationships between elements of a text, the method comprising:

identifying a segment of the text during syntactic parsing of the text;

identifying a token outside of the segment during syntactic parsing of the text;

based on properties of the token and properties of the segment, determining that the token may have a non-local linguistic relationship to a licensing element in the segment during syntactic parsing of the text, wherein determining that the token may have a non-local linguistic relationship to a licensing element comprises identifying a syntactic rule for combining the segment and the token;

searching the segment for a licensing element in the segment that is capable of being in a non-local linguistic relationship with the token during syntactic parsing of the text, wherein searching is limited to the segment;

generating a record for a syntactic attribute list associated with the syntactic parse, the record indicating that the token may have a non-local linguistic relationship to a licensing element in the segment, wherein the attribute list is a hierarchical list that has a hierarchy based in part on a hierarchy of clauses in the text;

finding at least one licensing element in the segment that is capable of being in a non-local linguistic relationship with the token and adding the location of the licensing element to the attribute list; and

constructing a logical form based in part on the attribute list.

2. The method of claim 1 wherein searching the segment comprises searching each level of clauses within the segment.

3. The method of claim 1 wherein the step of searching the segment for a licensing element in the segment is performed before executing the syntactic rule.

4. The method of claim 3 wherein the syntactic rule is not executed if a licensing element that is capable of being in a non-local linguistic relationship with the token cannot be found in the segment.

5. The method of claim 1 wherein the step of searching the segment for a licensing element in the segment is performed as part of executing the syntactic rule.

6. The method of claim 1 further comprising adding a role that the token assumes in the non-local linguistic relationship to the attribute list.

7. The method of claim 1 wherein finding at least one licensing element in the segment comprises finding at least two licensing elements and wherein adding the location of the licensing element to the attribute list comprises adding the locations of both licensing elements to the attribute list.

8. The method of claim 7 further comprising for each licensing element found, adding a role that the token is capable of assuming in a non-local linguistic relationship to the attribute list.

9. The method of claim 8 wherein adding a role that the token is capable of assuming comprises adding a first role for a first found licensing element and adding a different role for a second found licensing element.

10. The method of claim 1 wherein constructing a logical form comprises accessing the hierarchical attribute list in a top-down manner.