Method and apparatus for analyzing and debugging natural language parses

• US 7,379,862 B1
• Filed: 11/19/1999
• Issued: 05/27/2008
• Est. Priority Date: 11/19/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wada, Hajime, Chang, Su Chin
• Primary Examiner(s): Edouard; Patrick N.
• Assistant Examiner(s): SPOONER, LAMONT M
• Application Number:
  US09/443,779
• Time in Patent Office: 3,112 Days
• Field of Search: 704/9, 704/10, 704/1, 704/225, 704/257, 715/531, 715/532, 715/533, 715/534, 717/143, 717/144
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing

Abstract

A method and apparatus for analyzing and debugging natural language parses is provided. An input sentence is received and parsed by a parsing engine. A table of constituents is retrieved from the parsing engine and a grid tree is drawn representing the input sentence. Nodes of the tree, or connecting points, appear at intersections of the tree “branches.” Once the grid has been drawn, the first syntactically correct parse of the sentence is mapped to the grid in a tree-like manner (the “parse tree”). Input is then received for selecting one of several graphical buttons, for selecting a node that is in the parse tree, for selecting a node that is not in the parse tree, or for selecting options from one of several “pull-down” menus. If a connecting point that is not contained in the parse tree is selected, a group of menu options may be displayed adjacent to the selected connecting point. The user may select menu options for displaying successful rules applied at the connecting point, or for displaying unattempted and failed rules for the connecting point. If a connecting point that is contained in the parse tree (i.e. a constituent was formed at the connecting point) is selected, a second group of menu options may be displayed adjacent to the selected connecting point. The menu options may include displaying the name of the connecting point and the name of the rule that was applied at the connecting point to form the constituent.

Claims

1. A method for analyzing and debugging natural language parses, comprising the steps of:

displaying a parse tree for a textual input, the parse tree being generated based on rules and comprising at least one connecting point having two children;

receiving control input selecting one of said connecting points as a selected connecting point;

determining whether a rule was applied to form a constituent at said selected connecting point, the constituent representing at least the two children joined together; and

if the determination is positive, displaying a plurality of display items proximate to said selected connecting point, the display items including alternate rules applicable at the selected connecting point to generate constituents, other than the rule used in generating the constituent at the selected connecting point.

2. The method of claim 1, further comprising the step of:

receiving control input selecting one of said plurality of display items for deleting said constituent formed at said selected connecting point; and

in response to receiving said control input for deleting said constituent, deleting said constituent.

3. The method of claim 2, further comprising the steps of:

receiving control input selecting one of said plurality of display items for deleting said parse tree; and

in response to receiving said control input for deleting said parse tree, deleting constituents formed at each connecting point in said parse tree.

4. The method of claim 3, further comprising the steps of:

receiving control input selecting one of said plurality of display items for displaying information regarding said children of said selected connecting point; and

displaying information regarding said children of said selected connecting point.

5. The method of claim 4 wherein said step of displaying a first plurality of display items further comprises displaying information identifying a grammar rule comprising one of the rules applied at said selected connecting point to form said constituent.

6. The method of claim 1, wherein said control input selecting one of said connecting points as a selected connecting point comprises:

receiving input from an input device placing a pointer of a user interface proximate to one of said connecting points; and

receiving input representing an enabled state for the control of the input device.

7. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 1.

8. A computer-controlled apparatus for implementing the method of claim 1.

9. The method of claim 1, wherein said step of determining whether a constituent was formed at said selected connecting point comprises determining whether a rule was successfully applied at said selected connecting point to form a constituent between said children of said selected connecting point.

10. The method of claim 1 wherein if the determination is positive, the method further comprises:

determining that a given rule if applied to the selected connecting point would be unsuccessful in generating the constituent; and

including the given rule in the alternate rules.

11. The method of claim 1 wherein the alternate rules comprise rules not applied to the selected connecting point in generating the constituent.

12. A method for analyzing and debugging natural language parses, comprising the steps of:

displaying a parse tree, generated by applying grammar rules, for an input text comprising at least one connecting point having two children;

receiving control input selecting one of said connecting points as a selected connecting point;

determining whether a rule was applied to successfully form a constituent, formed by joining at least the two children, at said selected connecting point; and

displaying a first plurality of menu items proximate to said selected connecting point, the menu items including an alternate grammar rules display item which, when activated, displays alternate grammar rules, other than the rule used in generating the constituent at the selected connecting point, comprising displays alternate grammar rules, other than the rule used in generating the constituent at the selected connecting point, comprising grammar rules for generating constituents that are alternates to the rule applied in generating the constituent formed at the selected connecting point in the parse tree.

13. The method of claim 12, further comprising the steps of:

receiving control input selecting one of said first plurality of menu items for displaying a group of rules applied to successfully form a constituent at said selected connecting point; and

in response to receiving user input selecting said menu item for displaying rules applied to successfully form a constituent at said selected connecting point, displaying a second plurality of menu items proximate to said first plurality of menu items.

14. The method of claim 13, further comprising the steps of:

receiving control input activating the alternate grammar rules display items for displaying a group of alternate rules applied at said selected connecting point that did not successfully form a constituent at said selected connecting point; and

displaying the group of alternate rules.

15. The method of claim 12 wherein said children comprise constituents of said selected connection point, and further comprising the steps of:

receiving control input activating the alternate grammar rules display item for displaying a group of alternate rules that were not applied at said selected connecting point but that may be applied in view of said constituents of said selected connecting point; and

displaying the group of alternate rules.

16. The method of claim 12 wherein said children comprise constituents of said selected connecting point, and further comprising the steps of:

receiving control input activating the alternate grammar rules display item for displaying a group of alternate rules that were not applied at said selected connecting point without regard to said constituents of said selected connecting point; and

displaying the group of alternate rules.

17. The method of claim 16, further comprising the steps of:

receiving control input selecting a rule from the alternate grammar rules as a selected rule; and

applying said selected rule at said selected connecting point and updating said parse tree.

18. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 17.

19. A computer-controlled apparatus for implementing the method of claim 17.

20. The method of claim 17, further comprising the steps of:

determining whether said application of said selected rule at said selected connecting point was successful; and

in response to determining that said application of said selected rule was unsuccessful, displaying information identifying the reasons for the failure of said application of said selected rule.

21. The method of claim 16, further comprising the steps of:

receiving control input requesting the computation of the success or failure of each of said displayed group of alternate rules;

in response to said receiving control input requesting the computation of the success or failure of each of said displayed group of alternate rules, transmitting each rule in said displayed group of alternate rules to a parsing engine;

retrieving an associated success or failure indicator for each of said rules in said displayed group of alternate rules from said parsing engine; and

displaying said success or failure indicators.

22. A computer-readable medium having computer-executable instructions for performing the steps recited in claim 21.

23. A computer-controlled apparatus for implementing the method of claim 21.