Parsing system

• US 5,687,384 A
• Filed: 10/12/1994
• Issued: 11/11/1997
• Est. Priority Date: 12/28/1993
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Nagase, Tomoki
• Primary Examiner(s): Hofsass, Jeffery
• Assistant Examiner(s): HILL, ANDREW M
• Application Number:
  US08/322,382
• Time in Patent Office: 1,126 Days
• Field of Search: 395/751, 395/752, 395/754, 395/757, 395/759, 395/760
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/242 Dictionaries
• CPC Class Codes: G06F 40/268 Morphological analysis

Abstract

A subject-of-analysis input section inputs an input sentence or phrase to be analyzed. A dictionary unit holds dictionary data for dictionary consultation for a language of the input sentence. A morphemic analyzer consults the dictionary for the input sentence and recognizes breaks between every input word. A grammatical rule unit holds grammatical rules for parsing in the form of a general context-free grammar. A parsing unit applies the grammatical rules to the input sentence for parsing of the sentence. An analysis table unit stores the analysis intermediate results by the parsing unit in predetermined storage locations and holds an analysis table for storing the storage locations for the intermediate analysis results and/or pointers to the storage locations. The intermediate analysis result information in the analysis table unit includes syntactic category information and at least one of syntactic, semantic and control attributes.

Claims

1. A parsing system comprising:

input means for inputting a sentence or phrase of a natural language which serves as a subject of analysis;

dictionary means for holding dictionary data for dictionary consultation for said subject of analysis of said natural language;

morphemic analyzer means for recognizing breaks between every word by performing dictionary consultation on said subject of analysis;

parsing means for holding grammatical rules for parsing in the form of a context-free grammar and applying said grammatical rules to said subject of analysis for parallel parsing;

intermediate result storage means for storing syntactic category information in the intermediate results of an analysis by said parsing means and intermediate result information including parsing attribute information in predetermined storage locations; and

table holding means for holding an analysis table which stores said storage locations for the intermediate results of the analysis in said intermediate result storage means and/or pointers to said storage locations.

2. A parsing system according to claim 1, wherein said parsing attribute information includes at least one of syntactic, semantic and control attributes.

3. A parsing system according to claim 1, wherein said intermediate result storage means stores said intermediate result information including information as to a distinction between a complete subtree which has fully satisfied rules and an incomplete subtree which has partially satisfied rules.

4. A parsing system according to claim 3, wherein said table holding means includes an active-edge table for an incomplete subtree and an inactive-edge table for a complete subtree, which serve as an analysis table for access to said intermediate result information.

5. A parsing system according to claim 1, wherein said table holding means includes, as said analysis table, a rule reference table using grammatical categories as keys.

6. A parsing system according to claim 1, further including analysis preprocessing means for carrying out preprocessing between dictionary consultation and parsing to thereby increase the accuracy of an analysis.

7. A parsing system according to claim 6, wherein said analysis preprocessing means includes polysemic word processing means for looking up a polysemic words in each of word groups which are the results of dictionary consultation and, when polysemic words are found, adding some or all of them to said analysis table beforehand.

8. A parsing system according to claim 6, wherein said analysis preprocessing means includes idiom processing means for examining the possibility that each of word groups which are the results of dictionary consultation may be an idiom and, if there is found the possibility of an idiom, adds its central word and invariant portion to said analysis table beforehand.

9. A parsing system according to claim 8, wherein said idiom processing means includes means for assigning to the central word of an idiom to be added to said analysis table an attribute indicating a grammatical feature of that idiom.

10. A parsing system according to claim 6, wherein said analysis preprocessing means includes constituent word processing means for, when words which are the results of dictionary consultation include an entry constructed of two or more words, adding each of constituent words in said entry to said analysis table for later analysis.

11. A parsing system according to claim 10, wherein said constituent word processing means adds said constituent words in said entry to said analysis table only when the first of said constituent words has a given attribute.

12. A parsing system according to claim 1, wherein said parsing means includes evaluation means for evaluating a plurality of subtree candidates corresponding to the same partial character string and deciding ranking among them in accordance with predetermined criteria.

13. A parsing system according to claim 12, wherein said intermediate result storage means includes means for assigning, as an attribute, information on the frequencies of appearance of every word counted by part of speech, and said evaluation means includes means for establishing, as the criteria for ranking, priority among subtrees with priority increasing in ascending order of frequencies of appearance of words therein.

14. A parsing system according to claim 12, wherein said intermediate result storage means includes means for assigning, as an attribute, information as to how many times the rules have been applied, and said evaluation means includes means for establishing, as the criteria for ranking, priority among subtrees with priority increasing in descending order of the number of times the rules are applied.

15. A parsing system according to claim 12, wherein said intermediate result storage means includes means for assigning, as an attribute, information on the total of distances between every modifier and modified word, and said evaluation means includes means for establishing, as the criteria for ranking, priority among subtrees with priority increasing in decreasing order of the total of distances.

16. A parsing system according to claim 12, wherein said intermediate result storage means includes means for assigning, as an attribute, information on the total of marks assigned to the applied rules, and said evaluation means includes means for establishing, as the criteria for ranking, priority among subtrees with priority increasing in increasing order of the total of marks assigned to the applied rules.

17. A parsing system according to claim 12., wherein said intermediate result storage means includes means for assigning, as an attribute, information on an evaluation value for a semantic distance between a modifier and a modified word, and said evaluation means includes means for establishing, as the criteria for ranking, priority among subtrees with priority increasing in increasing order of the evaluation value.

18. A parsing system according to claim 12, in which said evaluation means for making unavailable for subsequent analysis some of analysis tree candidates of low ranking of a plurality of analysis tree candidates for the same partial character string among which ranking has been established.

19. A parsing system according to claim 18, wherein said evaluation means includes means for, when the unavailability of the partial analysis tree candidates of low ranking results in a failure in the entire analysis, retrying the failed analysis using said partial tree candidates which have been made unavailable previously to make up for failed analysis trees.