Generating parser combination by combining language processing parsers

• US 8,838,440 B2
• Filed: 09/13/2011
• Issued: 09/16/2014
• Est. Priority Date: 09/14/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iwama, Futoshi, Nakamura, Taiga, Takeuchi, Hironori
• Primary Examiner(s): He, Jialong
• Application Number:
  US13/231,015
• Publication Number:
  US 20120065960A1
• Time in Patent Office: 1,099 Days
• Field of Search: 704/9, 704/1
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

A computer implemented method, a computer system, and a program for generating a parser combination. The method includes: generating a parser combination by combining parsers each associated with at least one grammar description, where the step is carried out using (i) at least one grammar description means and (ii) a computer device. The computer system includes: a processor, a memory connected to the processor, and a parser generator for generating a parser combination in the memory by combining parsers each associated with at least one grammar description, and at least one grammar description type means.

Claims

1. A computer-implemented method for generating a parser combination by combining at least two language processing parsers comprising at least one formal language processing parser and one natural language processing parser, the method comprising steps of:

obtaining a declarative description including a plurality of grammar descriptions generated based on characteristics of target text;

dynamically generating a parser combination to selectively parse parts of target text with different parsers by combining parsers each associated with at least one of the plurality of grammar descriptions, wherein the generating is carried out using (i) at least one grammar description means and (ii) a computer device, wherein the at least one grammar description means is one of;

(i) a grammar description type 1 P1 until P2 (P1 U P2) means to parse input character strings by use of a first parser associated with a first grammar description (P1) until finding at least one input character string first acceptable by a second parser associated with a second grammar description (P2) which is parsed by use of the second parser, and (ii) a grammar description type 2 P1 for P2 (P1 F P2) means to parse input character strings in such a manner that a prefix string of input character strings which are acceptable by the second parser associated with the second grammar description (P2), is cut out and stored, the acceptable input character strings are parsed by use of the second parser, and the cut out and stored prefix string is parsed by use of the first parser associated with the first grammar description (P1).

2. The method according to claim 1, wherein the grammar description type 1 (P1 U P2) means is such that the at least one input character string first acceptable by the second parser is preceded by a first input of an input character string.

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

receiving a declarative description including a plurality of grammar descriptions; and

identifying a combination of grammar descriptions of those described in the received declarative description by parsing the declarative description, wherein the grammar descriptions include at least one of the grammar description types 1 (P1 U P2) and 2 (P1 F P2), wherein,

in the step of generating a parser combination, a parser combination is generated by combining parsers associated, respectively, with the grammar descriptions identified in the identifying step.

4. The method according to claim 3, wherein, in the grammar description type 1 (P1 U P2) or the grammar description type 2 (P1 F P2), one of the first grammar description (P1) and the second grammar description (P2) describes a character string processing function which does not have any accept language while accepting and parsing all input character strings, wherein the function describing grammar description is referred to as grammar description N.

5. The method according to claim 4, wherein, in the grammar description N, the character string processing function is a natural language processing function.

6. The method according to claim 3, wherein, in the grammar description type 1 (P1 U P2) or the grammar description type 2 (P1 F P2), one of the first grammar description (P1) and the second grammar description (P2) describes a character string processing function which does not have any accept language while accepting and parsing all input character strings, wherein the function describing grammar description is referred to as grammar description N, and wherein grammar description N describes a natural language processing parser.

7. The method according to claim 6, wherein, in the grammar description N, the character string processing function is a natural language processing function.

8. The method according to claim 3, wherein, in the grammar description type 2 (P1 F P2), at least one input character string is the longest one of the character strings, wherein the at least one input character string is acceptable by the second grammar description (P2).

9. The method according to claim 3, wherein the identifying step includes identifying a top-level combination of grammar descriptions in the declarative description.

10. The method according to claim 9, further comprising the step of:

parsing, after the top-level combination of grammar descriptions is identified, at least one of the grammar descriptions of the identified combination, thereby further identifying a combination of grammar descriptions included in the at least one of the grammar descriptions.

11. The method according to claim 1 further comprising the steps of:

receiving data from which information is to be extracted;

finding, from the data, a character string part acceptable by the second parser associated with the second grammar description (P2), by use of the second parser;

parsing a character string part of the data by use of the first parser associated with the first grammar description (P1);

parsing the found character string part by use of the second parser;

creating a syntax tree on the basis of a first analysis result obtained by the parsing done by the first parser and a second analysis result obtained by the parsing performed by the second parser; and

wherein all the steps of the method are carried out using the computer device.

12. The method according to claim 1 further comprising the steps of:

receiving data to be checked;

finding, from the data, at least one character string part by use of the second parser, wherein the one character string part is acceptable by the second parser associated with the second grammar description (P2);

parsing the found character string part by use of the first parser associated with the first grammar description (P1);

creating a syntax tree on the basis of a first analysis result obtained by the parsing done by the first parser; and

wherein all the steps of the method are carried out using the computer device.

21. A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions which, when implemented, cause a computer to carry out the steps of the method according to claim 1.

22. A non-transitory computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions which, when implemented, cause a computer to carry out the steps of the method according to claim 11.

13. A computer system for generating a parser combination by combining at least two language processing parsers comprising at least one formal language processing parser and one natural language processing parser, the computer system comprising:

a processor;

a memory connected to the processor; and

a parser generator for obtaining a declarative description including a plurality of grammar descriptions generated based on characteristics of target text and dynamically generating a parser combination in the memory to selectively parse parts of target text with different parsers by combining parsers each associated with at least one of the plurality of grammar descriptions, and at least one grammar description type means, wherein the at least one grammar description means is selected from the group consisting of;

(i) a grammar description type 1 P1 until P2 (P1 U P2) means to parse input character strings by use of a first parser associated with a first grammar description (P1), until finding at least one input character string first acceptable by a second parser associated with a second grammar description (P2) which is parsed by use of the second parser, and (ii) a grammar description type 2 P1 for P2 (P1 F P2) means to parse input character strings in such a manner that a prefix string of input character strings which are acceptable by the second parser associated with the second grammar description (P2), is cut out and stored, the acceptable input character strings are parsed by use of the second parser, and the cut out and stored prefix string is parsed by use of the first parser associated with the first grammar description (P1).

14. The computer system according to claim 13, wherein the grammar description type 1 (P1 U P2) means is such that the at least one input string first acceptable by the second parser is preceded by a first input of an input character string.

15. The computer system according to claim 13, wherein the computer system further comprises:

an editing unit for describing a declarative description including multiple grammar descriptions; and

an interpretation unit for identifying a combination of grammar descriptions included in the declarative description by parsing the declarative description, wherein the grammar descriptions include at least one of the grammar description types 1 (P1 U P2) and 2 (P1 F P2);

wherein the parser generator generates a parser combination by combining parsers associated, respectively, with the grammar descriptions identified by the interpretation unit.

16. The computer system according to claim 15, wherein, in the grammar description type 1 (P1 U P2) or the grammar description type 2 (P1 F P2), one of the first grammar description (P1) and the second grammar description (P2) is a character string processing function which does not have any accept language while accepting and parsing all input character strings, wherein the function describing grammar description is referred to as grammar description N.

17. The computer system according to claim 15, wherein, in the grammar description type 1 (P1 U P2) or the grammar description type 2 (P1 F P2), one of the first grammar description (P1) and the second grammar description (P2) describes a character string processing function which does not have any accept language while accepting and parsing all input character strings, wherein the function describing grammar description is referred to as grammar description N, and wherein grammar description N describes a natural language processing parser.

18. The computer system according to claim 13, wherein, in the grammar description type 2 (P1 F P2), at least one input character string is the longest one of the character strings, wherein the at least one input character string is acceptable by the second grammar description (P2).

19. The computer system according to claim 15, wherein the interpretation unit identifies a top-level combination of grammar descriptions in the declarative description.

20. The computer system according to claim 19, wherein, after identifying the top-level combination of grammar descriptions, the interpretation unit parses at least one of the grammar descriptions of the identified combination and thereby further identifies a combination of grammar descriptions included in the at least one of the grammar descriptions.