Natural language parser

• US 6,275,791 B1
• Filed: 02/26/1999
• Issued: 08/14/2001
• Est. Priority Date: 02/26/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weise, David N.
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/261,596
• Time in Patent Office: 900 Days
• Field of Search: 704/1, 704/9, 704/10, 704/2, 704/7, 704/251, 704/252, 704/254, 704/255, 704/257, 707/530, 707/531, 707/532, 707/534
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing

Abstract

An improved natural language parser uses a template set to identify predefined parse conditions and to implement responsive actions, thus reducing processing time while increasing parse tree accuracy. The template set is used to identify predefined conditions of the current parse state, an input span, and the history of the parse process. Once a template has been matched, the improved parser implements associated responsive actions to reduce the parse time typically associated with parsing an input span under the identified conditions. This on-the-fly implementation of responsive actions permits the parser to focus the parse process on the portions of the input span most likely to generate the complete and accurate parse in the shortest amount of time.

Claims

1. A method of parsing a natural language input span, the method comprising the steps of:

breaking the input span into individual words;

looking up each individual word in a lexicon to determine at least one part of speech associated with the word;

storing each individual word and an associated part of speech as a node in a candidate list;

assigning a goodness measure to each node in the candidate list;

setting an anchor point to a right-most portion of the input span;

creating a grow node that contains the anchor point;

promoting the grow node to a node chart;

determining whether the grow node and a first node satisfy a syntax rule;

if the grow node and the first node do not satisfy the syntax rule, comparing a parse condition to a first template; and

if the parse condition and the first template match, performing a first responsive action associated with the first template.

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

comparing the input span to a pre-parse template; and

if the pre-parse template and the input span match, performing a second responsive action associated with the pre-parse template.

3. The method of claim 2, wherein the second responsive action comprises the creation of a constituent node.

4. The method of claim 3, wherein the second responsive action further comprises the promotion of the constituent node to the node chart.

5. The method of claim 1, wherein the parse condition comprises the current state of the node chart.

6. The method of claim 1, wherein the parse condition comprises the current state of the candidate list.

7. The method of claim 1, wherein the parse condition comprises the current state of the input span.

8. The method of claim 1, wherein the parse condition comprises a record of a last adjustment template invoked.

9. The method of claim 1, wherein the grow node contains a first portion of the input span and a second node contains a second portion of the input span and is located immediately to the left of the grow node and the grow node and the second node are joined to form a new grow node.

10. The method of claim 1, wherein the first responsive action comprises promoting a third node to the node chart.

11. The method of claim 1, wherein the first responsive action comprises setting the anchor point to a second portion of the input span that is not the right-most portion of the input span.

12. The method of claim 11, wherein the second portion of the input span is located immediately to the left of a node previously containing the anchor point.

13. The method of claim 11, wherein the first responsive action further comprises setting the grow node to none.

14. The method of claim 1, wherein the first responsive action comprises determining the status of a pending-join state.

15. A computer readable medium on which is stored computer-executable instructions for performing the steps of:

breaking an input span into a plurality of words;

associating each word with a part of speech;

storing each word and each associated part of speech as a leaf node;

creating a grow node that contains a right-most portion of the input span;

growing the grow node leftward;

if the grow node cannot be grown leftward, comparing a parse condition to a first template; and

if the parse condition and the first template match, performing a first responsive action.

16. The computer readable medium of claim 15, further comprising the steps of:

comparing the input span to a pre-parse template; and

if the pre-parse template and the input span match, performing a second responsive action associated with the pre-parse template.

17. The computer readable medium of claim 16, wherein the second responsive action comprises the creation of a constituent node.

18. The computer readable medium of claim 17, wherein the second responsive action further comprises the promotion of the constituent node to the node chart.

19. The computer readable medium of claim 15, wherein the parse condition comprises the current state of a node chart.

20. The computer readable medium of claim 15, wherein the parse condition comprises the current state of a candidate list.

21. The computer readable medium of claim 15, wherein the parse condition comprises the current state of an input span.

22. The computer readable medium of claim 15, wherein the parse condition comprises a record of a last adjustment template invoked.

23. The computer readable medium of claim 15, wherein the first responsive action comprises promoting a third node to a node chart.

24. The computer readable medium of claim 15, wherein the first responsive action comprises setting the grow node to contain a portion of the input span that is not a right-most portion of the input span.

25. The computer readable medium of claim 24, wherein the first responsive action further comprises setting a grow node to none.

26. The computer readable medium of claim 15, wherein the first responsive action comprises determining the status of a pending-join state.

27. A method of increasing efficiency of a natural language parser for parsing an input span, the method comprising the steps of:

creating a grow node that contains a right-most portion of the input span;

growing the grow node leftward;

if the grow node cannot be grown leftward, comparing a parse condition to a template; and

if the parse condition and the template match, performing a first responsive action.

28. The method of claim 27, wherein the parse condition comprises the current state of a node chart.

29. The method of claim 27, wherein the parse condition comprises the current state of a candidate list.

30. The method of claim 27, wherein the parse condition comprises the current state of the input span.

31. The method of claim 27, wherein the parse condition comprises a record of a last adjustment template invoked.

32. The method of claim 27, wherein the responsive action comprises promoting a third node to the node chart.

33. The method of claim 27, wherein the responsive action comprises setting the grow node to contain a first portion of the input span that is not a right-most portion of the input span.

34. The method of claim 33, wherein the first portion of the input span is located immediately to the left of a node previously contained in the grow node.

35. The method of claim 33, wherein the responsive action further comprises setting a grow node to none.

36. The method of claim 27, wherein the first responsive action comprises determining the status of a pending-join state.