Method and apparatus for determining unbounded dependencies during syntactic parsing

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.

1 . A method of identifying non-local 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 non-local 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 non-local linguistic relationship with the token wherein searching is limited to the segment;    wherein the steps of identifying the segment, identifying the token, determining that the token may have a non-local linguistic relationship to a licensing element in the segment, and searching the segment for a licensing element in the segment are performed during formation of a syntactic parse structure for the text.    
   
   
       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 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.  
   
   
       4 . The method of  claim 3  wherein the step of searching the segment for a licensing element in the segment is performed before executing the syntactic rule.  
   
   
       5 . The method of  claim 4  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.  
   
   
       6 . The method of  claim 3  wherein the step of searching the segment for a licensing element in the segment is performed as part of executing the syntactic rule.  
   
   
       7 . The method of  claim 3  further comprising 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.  
   
   
       8 . The method of  claim 7  further comprising 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.  
   
   
       9 . The method of  claim 8  further comprising adding a role that the token assumes in the non-local linguistic relationship to the attribute list.  
   
   
       10 . The method of  claim 8  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.  
   
   
       11 . The method of  claim 10  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.  
   
   
       12 . The method of  claim 11  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.  
   
   
       13 . The method of  claim 8  further comprising constructing a logical form based in part on the attribute list.  
   
   
       14 . 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 search is limited to the segment and wherein the gap is not represented in the parse structure.    
   
   
       15 . The computer-readable medium of  claim 14  further comprising identifying a parse rule for combining the token with the segment.  
   
   
       16 . The computer-readable medium of  claim 15  wherein the step of searching the segment is performed before deciding to execute the parse rule.  
   
   
       17 . The computer-readable medium of  claim 15  wherein the step of searching the segment is performed as part of executing the parse rule.  
   
   
       18 . The computer-readable medium of  claim 14  wherein searching the segment comprises searching each level of subordinate clauses within the segment.  
   
   
       19 . The computer-readable medium of  claim 14  further comprising creating an attribute list for a syntactic parse node formed by combining the token and the segment.  
   
   
       20 . The computer-readable medium of  claim 19  wherein creating an attribute list comprises including information in the attribute list that indicates that the token may fill a gap in the segment.  
   
   
       21 . The computer-readable medium of  claim 20  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.  
   
   
       22 . The computer-readable medium of  claim 21  wherein creating an attribute list further comprises including information in the attribute list that indicates the role that the token assumes in a gap.  
   
   
       23 . The computer-readable medium of  claim 14  further comprising finding two separate gaps in the segment that the token can fill.  
   
   
       24 . The computer-readable medium of  claim 23  further comprising determining a role that the token assumes in each gap.  
   
   
       25 . The computer-readable medium of  claim 24  wherein the token assumes one role in one of the gaps and a different role in the other gap.  
   
   
       26 . The computer-readable medium of  claim 24  wherein the roles are based on logical form attributes.  
   
   
       27 . The computer-readable medium of  claim 26  further comprising determining a logical form-for the syntactic parse structure.  
   
   
       28 . The computer-readable medium of  claim 27  wherein determining the logical form comprises assigning the token to one of the gaps but not the other.  
   
   
       29 . The computer-readable medium of  claim 27  wherein determining the logical form comprises assigning the token to both gaps.  
   
   
       30 . 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.    
   
   
       31 . The computer-readable medium of  claim 30  wherein the data structure is associated with a syntax node formed by combining the token with the text segment.  
   
   
       32 . A method of identifying non-local relationships during syntactic parsing, the method comprising: 
 before forming a syntactic parse structure that spans an entire sentence, identifying a segment of the sentence that can act as a filler in a non-local relationship found in a second segment of the sentence;    locating a first gap in a relationship in the second segment of the sentence;    locating a second gap in a relationship in the second segment of the sentence; and    indicating that the filler can be placed in both the first gap and the second gap.    
   
   
       33 . The method of  claim 32  further comprising indicating that the filler assumes one role in the first gap and a different role in the second gap.