System and method for natural language parsing by initiating processing prior to entry of complete sentences

• US 4,994,966 A
• Filed: 03/31/1988
• Issued: 02/19/1991
• Est. Priority Date: 03/31/1988
• Status: Expired due to Fees

• Current Assignee: Emerson & Stern Associates, Inc.
• Original Assignee: Emerson & Stern Associates, Inc.
• Inventors: Hutchins, Sandra E.
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Hayes, Gail O.
• Application Number:
  US07/176,133
• Time in Patent Office: 1,055 Days
• Field of Search: 364/419, 364/364, 364/200, 364/900
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

A system and method for parsing natural language is provided. The system comprises a plurality of computer program code modules which address a plurality of predetermined lookup tables. Strings of characters, such as words, assigned one or more syntactical tags identifying the grammatical roles the strings can play are stored in a dictionary and retrieved as a system user inputs text to be processed. The tags are manipulated by a phrase parsing program module and translated into phrases according to grammatical rules stored in a lookup table. Sequences of the phrases corresponding to input sentences are maniplated by a sentence checking program module which consults another suitable rule table. The system and method optionally provide help in identifying grammatically incorrect passages in the input text.

Claims

1. A language parsing system for processing a string of words, comprising:

means for entering into the system strings of characters comprising words;

means for assigning syntax tags to entered words;

parsing means for grouping syntax tags of entered words into phrases according to a first set of predetermined grammatical rules relating the syntax tags to one another;

checking means for verifying the conformance of sequences of the phrases to a second set of predetermined grammatical rules relating the phrases to one another; and

control means for coordinating the assigning means, parsing means and checking means;

wherein the system processes each word of the word string upon entry of such word.

2. The parsing system of claim 1, wherein the system further comprises memory means for storing the syntax tags and phrases in lookup tables and the checking means verifies a plurality of parallel sequences of the phrases, each of the plurality of parallel sequences comprising a respective one of the sequences that are possible for the entered words.

3. The parsing system of claim 2, further comprising means for providing grammar help, wherein the checking means indicates the locations in the parallel sequences of subjects, verbs, and deviations from the sets of rules, and the grammar help providing means provides a predetermined help message for a sequence having such a deviation.

4. The parsing system of claim 3, wherein the parsing means addresses a lookup table that includes the first set of rules, the first set comprises first and second subsets, the rules in the second subset denote types of deviations from the rules in the first subset, the checking means indicates the location and type of such deviations in the parallel sequences, and the grammar help providing means provides help messages comprising explanations for correcting the deviations.

5. The parsing system of claim 1, wherein the assigning means assigns syntax tags to each entered word upon such word being entered.

6. The parsing system of claim 1, wherein the assigning means looks up words in a dictionary as each word is entered and deduces syntax tags for words not found in the dictionary based on the endings of such words.

7. The parsing system of claim 1, further comprising combining means for combining phrases produced by the parsing means into combinations thereof and the checking means verifies the conformance of sequences of the combinations to predetermined grammatical rules relating the combinations to one another.

8. The parsing system of claim 1, wherein the control means converts a selected plurality of syntax tags from the assigning means into a smaller plurality of translated tags, each translated tag representing a predetermined plurality of the selected syntax tags, and the translated tags from the control means and syntax tags from the assigning means being grouped by the parsing means.

9. A language parsing system for processing a sentence of at least one word, comprising:

means for entering characters comprising the words of the sentence into the system;

means for identifying syntax tags associated with entered words;

means for grouping the syntax tags into phrases;

means for combining predetermined phrases into combinations thereof;

means for checking the conformance of sequences of the phrase combinations and phrases not combined into the phrase combinations to a set of predetermined checking rules relating the phrases and phrase combinations to one another; and

control means for coordinating operation of the identifying means, the grouping means, the combining means and the checking means;

wherein the identifying means identifies syntax tags and the grouping means groups the tags before the sentence is completely entered.

10. The parsing system of claim 9, wherein the identifying means, grouping means, combining means and checking means access a plurality of lookup tables that contain words associated with syntax tags, groups of syntax tags associated with phrases, groups of phrases associated with phrase combinations, and the set of checking rules.

11. The parsing system of claim 9, further comprising means for deducing syntax tags, wherein the identifying means finds entered words in a dictionary lookup table including words associated with syntax tags and the deducing means deduces syntax tags based upon the endings of words not found in the dictionary lookup table.

12. The parsing system of claim 9, further comprising means for providing grammar help, wherein the checking means checks a plurality of parallel sequences of the phrase combinations and phrases not combined into the phrase combinations, each of the plurality of parallel sequences comprising a respective one of the sequences that are possible for the entered words, and indicates the locations in the parallel sequences of subjects, verbs, and deviations from the set of checking rules, and the grammar help providing means provides predetermined help messages for correcting the deviations.

13. The parsing system of claim 12, wherein the grouping and combining means address lookup tables including first and second sets, respectively, of rules relating to both correct and incorrect grammatical usages of words, wherein the rules in the second set denote types of deviations from the rules in the first set, the checking means indicates the location in the parallel sequences of predetermined deviation types, and the grammar help providing means provides help messages for correcting the deviation types.

14. The parsing system of claim 13, wherein the grammar help providing means identifies any rules from the second set used by the grouping and combining means.

15. The parsing system of claim 9, wherein the system operates in conjunction with a work processor in a digital computer and the entering means includes a keyboard.

16. The parsing system of claim 15, wherein the entering means retrieves the entered words from a memory.

17. The parsing system of claim 9, wherein the checking means checks a plurality of parallel sequences of the phrase combinations and phrases not combined into phrase combinations, each of the plurality of parallel sequences comprising a respective one of the sequences possible for the entered words.

18. The parsing system of claim 9, wherein the control means converts a selected plurality of syntax tags from the identifying means into a smaller plurality of translated tags, each translated tag representing a predetermined plurality of the selected syntax tags, and the translated tags from the control means and syntax tags from the identifying means being grouped by the grouping means.

20. The parsing system of claim 18, wherein the system operates in conjunction with a word processor.

21. The parsing system of claim 18, where the system includes at least one ROM.

22. The parsing system of claim 18, further comprising means for providing grammar help, wherein the lookup tables include rules relating to both correct and incorrect grammatical usages and the checking means verifies a plurality of parallel sequences of the phrase combinations and phrases not combined into the phrase combinations, each of the plurality of parallel sequences comprising a respective one of the sequences possible for the entered words and indicates the locations in the parallel sequences of subjects, verbs, and deviations from the set of rules, and the grammar help providing means identifies the deviations, indicates the incorrect phrases, and provides predetermined help messages for correcting the incorrect phrases.

23. The parsing system of claim 18, wherein the control means converts a selected plurality of syntax tags from the locating means into a smaller plurality of translated tags, each translated tag representing a predetermined plurality of the selected syntax tags, and the translated tags from the control means and syntax tags from the locating means being grouped by the parsing means. PG,95

19. In a digital computer for processing information, a language parsing system for processing a sentence of at least one word, comprising:

means for entering characters comprising the words of the sentence into the system;

means for locating syntax tags of entered words in a dictionary lookup table as each word is entered;

means for deducing syntax tags for words not found in the dictionary, wherein the syntax tags are deduced from the words not found in the dictionary;

parsing means for locating phrases associated with the entered words in a first lookup table mapping sequences of syntax tags into phrases, wherein the phrases are located as each word is entered;

combining means for combining phrases by locating phrases combinations in a second lookup table mapping sequences of phrases into phrase combinations;

checking means for verifying, as each word is entered, the conformance of sequences of the phrase combinations and phrases not combined into the phrase combinations to a set of predetermined grammatical rules relating phrases and phrases combinations to one another, the checking means being responsive to the combining means; and

control means for coordinating operation of the locating means, the deducing means, the parsing means, the combining means and the checking means.

24. A method for parsing a natural language sentence of at least one word, comprising the steps of:

assigning syntax tags to the words of the sentence;

phrase parsing a sequence of the words by grouping the syntax tags assigned to the words of the sequence into phrases; and

sentence checking by verifying the conformance of a plurality of parallel sequences of the phrases to a set of predetermined grammatical rules relating the phrases to one another.

25. The method of claim 24, wherein the method is carried out in a digital computer on strings input from a keyboard.

26. The method of claim 24, wherein the method is carried out in a digital computer on strings input from a memory.

27. The method of claim 24, further comprising the steps of looking up the words in a dictionary and of deducing syntax tags for words not found in the dictionary based upon the endings of such words.

28. The method of claim 27, wherein the method is carried out in a digital computer.

29. The method of claim 24, further comprising the step of combining phrases into phrase combinations, wherein the sentence checking step includes verifying the conformance of a plurality of parallel sequences of the phrase combinations and phrases not combined into the phrase combinations to a set of predetermined grammatical rules relating phrases and phrase combinations to one another, each of the plurality of parallel sequences comprising a respective one of the sequences possible for the words of the sentence.

30. The method of claim 24, further comprising the step of converting selected syntax tags into translated tags, wherein each translated tag represents a predetermined plurality of the selected syntax tags, and the phrase parsing step includes grouping syntax tags and translated tags into phrases.

31. A method of parsing a natural language sentence of at least one word, comprising the steps of:

assigning syntax tags to the words of the sentence;

grouping the syntax tags assigned to sequences of the words into phrases according to a set of predetermined rules;

combining the phrases into a plurality of parallel sequences of phrase combinations and phrases not combined into the phrase combinations, each of the plurality of parallel sequences comprising a respective one of the sequences possible for the words of the sentence; and

comparing the plurality of parallel sequences of phrases and phrase combinations to the set of grammar rules.

32. The method of claim 31, further comprising the step of looking up the words in a dictionary to retrieve the assigned syntax tags.

33. The method of claim 32, further comprising the step of deducing syntax tags for words not found in the dictionary from the endings of such words.

34. The method of claim 31, further comprising the step of sentence checking by verifying the conformance of the plurality of parallel sequences of the phrases and phrase combinations to first and second sets of predetermined grammar rules, wherein the first set includes rules relating to correct grammatical usage and the second set includes rules relating to deviations from the first set and denoting types of the deviations.

35. The method of claim 31, further comprising the step of converting selected syntax tags into translated tags, wherein each translated tag represents a predetermined plurality of the selected syntax tags, and the grouping step includes grouping syntax tags and translated tags into phrases.

36. A language parsing system for processing a sentence of at least one word, comprising:

input means for entering strings of characters,

a sentence buffer for storing input strings of characters;

a word dictionary, wherein syntax tags are stored in association with words comprising character strings;

lookup means for finding entered words in the word dictionary;

a phrase table, wherein non-terminals are stored in association with a predetermined set of phrase sequences of syntax tags;

phrase parsing means for finding the non-terminals from the phrase table associated with the phrase sequences of the syntax tags of the entered words as the words are entered;

a sentence table, wherein is stored a predetermined set of sentence checking rules in association with sentences of non-terminals;

means for sentence checking, the sentence checking means applying the sentence checking rules in the sentence table to the sentences of non-terminals from the phrase parsing means to verify the conformance of the non-terminal sentences to the sentence checking rules; and

control means for coordinating the lookup means, phrase parsing means and sentence checking means, the control means tracking a plurality of parallel grammar paths representing states of the phrase parsing means and sentence checking means produced as the words are entered.

37. The system of claim 36, wherein the word dictionary includes a set of a plurality of syntax tag deduction rules for deducing syntax tags based on the characters in entered words, and the lookup means assigns syntax tags to entered words not found in the word dictionary according to the plurality of syntax tag deduction rules.

38. The system of claim 37, wherein the lookup means assigns syntax tags to entered words not found in the dictionary according to the deduction rules based on the endings of such words.

39. The system of claim 37, wherein the set of syntax tag deduction rules includes first and second subsets of rules, the second subset of rules providing for exceptions to the first subset.

40. The system of claim 36, wherein the phrase table includes a plurality of syntax tag deduction rules for deducing syntax tags based on the characters in entered words, and the phrase parsing means assigns syntax tags to entered words not found in the word dictionary according to the plurality of syntax tag deduction rules.

41. The system of claim 40, wherein the syntax tag deduction rules are rules for deducing syntax tags based on ending characters in entered words.

42. The system of claim 36, further comprising a spelling output buffer and an error flag, wherein the lookup means writes entered words not found in the word dictionary to the spelling output buffer and sets the error flag, and the error flag indicates the number of erroneous characters of the entered words not found in the word dictionary.

43. The system of claim 36, further comprising a phrase combination table, wherein predetermined non-terminals are stored in association with predetermined sequences of non-terminals, and means for phrase combining, the phrase combining means finding non-terminals from the phrase combination table associated with the sequences of non-terminals for the entered words from the phrase parsing means, and wherein the sentence checking means applies the set of sentence checking rules to the sentences of non-terminals from the phrase combining means.

44. The system of claim 36, further comprising a grammar path data area, wherein the control means tracks the plurality of parallel grammar paths by storing the paths in a working path and a path log in the grammar path data area.

45. The system of claim 44, further comprising a grammar help table, means for providing grammar help, and a grammar help buffer, wherein the grammar help table stores explanations for correcting deviations from the set of sentence checking rules in the entered sentence, and the grammar help providing means finds an explanation in the grammar help table based on non-terminal strings for the entered words stored in the grammar path data area and outputs the explanation to the grammar help buffer.

46. The system of claim 45, further comprising a grammar help data area, wherein the grammar help providing means finds the explanation in the grammar table by storing in the grammar help data area a synopsis of the grammar paths in the grammar path data area.

47. The system of claim 45, wherein at least one of the phrase table stores non-terminals in association with a second set of predetermined phrase sequences deviating from the set of predetermined phrase sequences and the sentence table stores a second predetermined set of sentence checking rules in association with sentences of non-terminals deviating from the set of sentence checking rules.

48. The system of claim 47, further comprising a grammar output flag for indicating when the entered words conform to at least one of the second sets.

49. The system of claim 36, further comprising a translated tag table, wherein translated tags are stored in association with selected syntax tags and each translated tag represents a predetermined plurality of the selected syntax tags, and means for translating tags, the translating means finding the translated tags from the translated tag table associated with the syntax tags of the entered words, and wherein the phrase table stores non-terminals in association with a predetermined set of phrase sequences of syntax tags and translated tags.

50. In a computer, a method for parsing a natural language by processing sentences, each having at least one word, comprising the steps of:

entering a sentence;

storing the entered sentence;

finding syntax tags associated with the entered words in a word dictionary;

finding in a phrase table non-terminals associated with the syntax tags associated with the entered words as each word is entered;

applying sentence checking rules associated with sequences of non-terminals to the found non-terminals to verify the conformance of the found non-terminal sequences to the rules; and

tracking a plurality of parallel grammar paths representing the found non-terminals as the words are entered, each of the plurality of parallel grammar paths comprising a respective one of the possible sequences of the found non-terminals.

51. The method of claim 50, further comprising the step of converting predetermined syntax tags associated with the entered words to translated tags, wherein each translated tag represents a predetermined plurality of the predetermined syntax tags and wherein the step of finding non-terminals includes finding non-terminals associated with the translated tags.

52. The method of claim 50, further comprising the step of combining the found non-terminals into combinations, and wherein the step of applying sentence checking rules includes applying sentence checking rules associated with sequences of non-terminals and combinations to the found non-terminals and combinations, and each of the plurality of grammar paths comprises a respective one of the possible sequences of the combinations and the found non-terminals not combined into combinations.

53. The method of claim 52, further comprising the step of deducing syntax tags for entered words not in the word dictionary from the endings of such words.

54. The method of claim 53, further comprising the step of providing explanations for correcting deviations from the sentence checking rules found in the entered sentence after applying the sentence checking rules.