Method and apparatus for determining unbounded dependencies during syntactic parsing

• US 20030120479A1
• Filed: 12/20/2001
• Published: 06/26/2003
• Est. Priority Date: 12/20/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Parkinson, David J., Calcagno, Michael
• Granted Patent: US 7,113,905 B2
• Time in Patent Office: Days
• US Class Current: 704/4
• 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 linguistic relationships between elements of a text, the method comprising:

identifying a segment of the text;

identifying a token outside of the segment;

based on properties of the token and properties of the segment, determining that the token may have a linguistic relationship to a licensing element in the segment; and

searching the segment for a licensing element in the segment that is capable of being in a linguistic relationship with the token.

2. The method of claim 1 wherein the steps of identifying the segment, identifying the token, determining that the token may have a linguistic relationship to a licensing element in the segment, and searching the segment for a licensing element in the segment are performed during syntactic parsing of the text.

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

4. The method of claim 2 wherein determining that the token may have a linguistic relationship to a licensing element comprises identifying a syntactic rule for combining the segment and the token.

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

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

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

8. The method of claim 4 further comprising generating a record for a syntactic attribute list associated with the syntactic parse, the record indicating that the token may have a linguistic relationship to a licensing element in the segment.

9. The method of claim 8 further comprising finding at least one licensing element in the segment that is capable of being in a linguistic relationship with the token and adding the location of the licensing element to the attribute list.

10. The method of claim 9 further comprising adding a role that the token assumes in the linguistic relationship to the attribute list.

11. The method of claim 9 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.

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

13. The method of claim 12 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.

14. The method of claim 9 further comprising constructing a logical form based in part on the attribute list.

15. The method of claim 14 wherein the attribute list is a hierarchical list that has a hierarchy based in part on a hierarchy of clauses in the text.

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

17. A computer-readable medium having computer-executable instructions for performing steps comprising:

constructing a syntactic parse structure of a segment found in a sentence of text;

identifying a token outside of the segment; and

searching the segment for a gap in a relationship that the token can fill, wherein the gap is not represented in the parse structure.

18. The computer-readable medium of claim 17 further comprising identifying a parse rule for combining the token with the segment.

19. The computer-readable medium of claim 18 wherein the step of searching the segment is performed before deciding to execute the parse rule.

20. The computer-readable medium of claim 18 wherein the step of searching the segment is performed as part of executing the parse rule.

21. The computer-readable medium of claim 17 wherein searching the segment comprises searching each level of subordinate clauses within the segment.

22. The computer-readable medium of claim 17 further comprising creating an attribute list for a syntactic parse node formed by combining the token and the segment.

23. The computer-readable medium of claim 22 wherein creating an attribute list comprises including information in the attribute list that indicates that the token may fill a gap in the segment.

24. The computer-readable medium of claim 23 wherein creating an attribute list further comprises including information in the attribute list that indicates where a gap that the token can fill is located in the parse structure.

25. The computer-readable medium of claim 24 wherein creating an attribute list further comprises including information in the attribute list that indicates the role that the token assumes in a gap.

26. The computer-readable medium of claim 17 further comprising finding two separate gaps in the segment that the token can fill.

27. The computer-readable medium of claim 26 further comprising determining a role that the token assumes in each gap.

28. The computer-readable medium of claim 27 wherein the token assumes one role in one of the gaps and a different role in the other gap.

29. The computer-readable medium of claim 27 wherein the roles are based on logical form attributes.

30. The computer-readable medium of claim 29 further comprising determining a logical form for the syntactic parse structure.

31. The computer-readable medium of claim 30 wherein determining the logical form comprises assigning the token to one of the gaps but not the other.

32. The computer-readable medium of claim 30 wherein determining the logical form comprises assigning the token to both gaps.

33. A computer-readable medium having a data structure, the data structure comprising:

a token identity field that indicates the identity of a token that could satisfy a relationship within a text segment;

a gap location field that indicates the location of a gap in a relationship in a text segment; and

a role field that indicates the role the token would assume if placed in the gap.

34. The computer-readable medium of claim 33 wherein the data structure is associated with a syntax node formed by combining the token with the text segment.

35. A method of identifying non-local relationships during syntactic parsing, the method comprising:

identifying a segment of text that can act as a filler in a non-local relationship found in a second segment of text;

locating a first gap in a relationship in the second segment of text;

locating a second gap in a relationship in the second segment of text; and

indicating that the filler can be placed in both the first gap and the second gap.

36. The method of claim 35 further comprising indicating that the filler assumes one role in the first gap and a different role in the second gap.