GENERATING PARSER COMBINATION BY COMBINING LANGUAGE PROCESSING PARSERS

• US 20120065960A1
• Filed: 09/13/2011
• Published: 03/15/2012
• Est. Priority Date: 09/14/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nakamura, Taiga, Takeuchi, Hironori, Iwama, Futoshi
• Granted Patent: US 8,838,440 B2
• Time in Patent Office: Days
• 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, the method comprising a step of:

generating a parser combination by combining parsers each associated with at least one grammar description, wherein the step is carried out using (i) at least one grammar description means and (ii) a computer device.

2. The method according to claim 1, wherein the at least one grammar description means is selected from the group consisting of:

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

3. The method according to claim 2, 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 to an input character string.

4. The method according to claim 3, 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.

5. The method according to claim 4, 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.

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

7. The method according to claim 4, 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 formal language processing parser.

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

9. The method according to claim 4, 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).

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

11. The method according to claim 10, 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.

12. The method according to claim 2 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.

13. The method according to claim 2 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.

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

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

14. A computer system for generating a parser combination by combining at least two language processing parsers, the computer system comprising:

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.

15. The computer system according to claim 14, wherein the at least one grammar description means is selected from the group consisting of:

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

16. The computer system according to claim 15, 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 to an input character string.

17. The computer system according to claim 15, 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.

18. The computer system according to claim 17, 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.

19. The computer system according to claim 17, 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 formal language processing parser.

20. The computer system according to claim 15, 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).

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

22. The computer system according to claim 21, 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.