System and method to compile instructions to manipulate linguistic structures into separate functions

• US 6,529,865 B1
• Filed: 10/18/1999
• Issued: 03/04/2003
• Est. Priority Date: 10/18/1999
• Status: Expired due to Term

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Duan, Lei, Franz, Alexander, Horiguchi, Keiko
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/419,533
• Time in Patent Office: 1,233 Days
• Field of Search: 704/1, 704/9, 704/10, 707/530, 707/531, 707/532, 717/1, 717/4, 717/8
• 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/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 8/41 Compilation

Abstract

A grammar programming language (“GPL”) compiler compiles each rule in a natural language grammar into a separate function that can be invoked by a translation system to apply the rule to a representation of a natural language expression. The GPL compiler can output the functions for the rules as source code for a standard computer programming language to be further compiled into object code that can be directly executed by a computer processor. The GPL compiler can also generate special functions for each rule to enable multi-layered operations on the representations and to handle the processing of representations of ambiguous expressions.

Claims

1. A method of compiling natural language grammar rules into separate functions comprising:

determining a set of operations that manipulate a representation of a natural language expression for each rule, wherein the representation is a disjunctive feature structure;

generating an expansion function to build an expanded feature structure for a combination represented by the disjunctive feature structure;

generating a combination function to create a new disjunctive feature structure from a resulting feature structure created by applying the rule to the expanded feature structure;

mapping each operation in the set to a corresponding library function; and

creating an interface function containing the mapped library functions from the expansion function and the combination function, wherein the interface function is executed when the corresponding rule is invoked.

2. The method of claim 1, wherein the interface function contains computer programming language source code, the method further comprising:

inputting the interface function to a corresponding computer programming language compiler; and

executing object code output from the compiler when the rule is invoked.

3. The method of claim 1, further comprising:

addressing each interface function using an identifier for the corresponding rule.

4. The method of claim 3, further comprising:

creating a common interface function for all interface functions having a like number of input arguments, wherein a particular rule is invoked by specifying the identifier for the rule to the common interface function.

5. The method of claim 1, wherein the natural language grammar rules are defined by a compiler grammar and wherein determining the set of operations comprises:

analyzing the rule according to the compiler grammar.

6. The method of claim 1, wherein each natural language grammar rule comprises a context-free rule and an associated rule body and the set of operations is specified by the associated rule body.

7. A method of compiling natural language grammar rules into separate functions comprising:

determining a set of operations that manipulate a representation of a natural language expression for each rule;

mapping each operation in the set to a corresponding library function;

recognizing a nested operation, wherein a nested operation comprises an inner operation nested within an outer operation;

mapping a separate library function to each of the outer and inner operations;

generating a pointer to the library function mapped to the inner operation;

specifying the pointer as an argument for the library function mapped to the outer operation; and

creating an interface function containing the mapped library functions, wherein the interface function is executed when the corresponding rule is invoked.

8. The method of claim 7, wherein mapping a separate library function, generating a pointer, and specifying the pointer are repeated for each inner operation that is recognized as a nested operation.

9. The method of claim 7, further comprising:

addressing each interface function using an identifier for the corresponding rule.

10. The Method of claim 9, further comprising:

creating a common interface function for all interface functions having a like number of input arguments, wherein a particular rule is invoked by specifying the identifier for the rule to the common interface function.

11. A computer-readable medium having stored thereon executable instructions to cause a computer to perform a method of compiling natural language grammar rules into separate functions, the method comprising:

determining a set of operations that manipulate a representation of a natural language expression for each rule, wherein the representation is a disjunctive feature structure;

generating an expansion function to build an expanded feature structure for a combination represented by the disjunctive feature structure;

generating a combination function to create a new disjunctive feature structure from a resulting feature structure created by applying the rule to the expanded feature structure;

mapping each operation in the set to a corresponding library function; and

creating an interface function containing the mapped library functions from the expansion function and the combination function, wherein the interface function is executed when the corresponding rule is invoked.

12. The computer-readable medium of claim 11, wherein the interface function contains computer programming language source code, and further comprising:

inputting the interface function to a corresponding computer programming language compiler; and

executing object code output from the compiler when the rule is invoked.

13. The computer-readable medium of claim 11, further comprising:

addressing each interface function using an identifier for the corresponding rule.

14. The computer-readable medium of claim 13, further comprising:

creating a common interface function for all interface functions having a like number of input arguments, wherein a particular rule is invoked by specifying the identifier for the rule to the common interface function.

15. The computer-readable medium of claim 11, wherein the natural language grammar rules are defined by a compiler grammar and wherein determining the set of operations comprises:

analyzing the rule according to the compiler grammar.

16. The computer-readable medium of claim 11, wherein each natural language grammar rule comprises a context-free rule and an associated rule body and the set of operations is specified by the associated rule body.

17. A computer-readable medium having stored thereon executable instructions to cause a computer to perform a method of compiling natural language grammar rules into separate functions, the method comprising:

determining a set of operations that manipulate a representation of a natural language expression for each rule;

mapping each operation in the set to a corresponding library function;

recognizing a nested operation, wherein a nested operation comprises an inner operation nested within an outer operation;

mapping a separate library function to each of the outer and inner operations;

generating a pointer to the library function mapped to the inner operation;

specifying the pointer as an argument for the library function mapped to the outer operation; and

creating an interface function containing the mapped library functions, wherein the interface function is executed when the corresponding rule is invoked.

18. The computer-readable medium of claim 17, wherein mapping a separate library function, generating a pointer, and specifying the pointer are repeated for each inner operation that is recognized as a nested operation.

19. The computer-readable medium of claim 17, further comprising:

addressing each interface function using an identifier for the corresponding rule.

20. The computer-readable medium of claim 19, further comprising:

creating a common interface function for all interface functions having a like number of input argument, wherein a particular rule is invoked by specifying the identifier for the rule to the common interface function.

21. A system for compiling natural language grammar rules into separate functions comprising:

a processing unit;

a memory coupled to the processing unit through a system bus;

a computer-readable medium coupled to the processing unit through the system bus; and

a grammar programming language compiler executed from the computer-readable medium by the processing unit to cause the processing unit to create an interface function for each rule by

determining a set of operations that manipulate a representation of a natural language expression for each rule, wherein the representation is a disjunctive feature structure,

generating an expansion function to build an expanded feature structure for a combination represented by the disjunctive feature structure,

generating a combination function to create a new disjunctive feature structure from a resulting feature structure created by applying the rule to the expanded feature structure, and

mapping each operation in the set to a corresponding library function, wherein the interface function is executed when the corresponding rule is invoked.

22. The system of claim 21, wherein the interface function contains computer programming language source code and further comprising a computer programming language compiler executed from the computer-readable medium by the processing unit to cause the computer programming language compiler to generate object code from the interface function, wherein the object code is executed when the rule is invoked.

23. The method of claim 21, the grammar programming language compiler further causing the processing unit to assign an identifier to each rule, the identifier operable to address the corresponding interface function.

24. The system of claim 23, the grammar programming language compiler further causing the processing unit to create a common interface function for all interface functions having a like number of input arguments, wherein a particular rule is invoked by specifying the identifier for the rule to the common interface function.

25. The system of claim 21, wherein the natural language grammar rules are defined by a compiler grammar and the grammar programming language compiler further cause the processing unit to determine the set of operations for a rule by analyzing the rule according to the compiler grammar.

26. The system of claim 21, wherein each natural language grammar rule comprises a context-free rule and an associated rule body and the grammar programming language compiler causes the processing unit to determine the set of operations for a rule as specified by the associated rule body.

27. A system for compiling natural language grammar rules into separate functions comprising:

a processing unit;

a memory coupled to the processing unit through a system bus;

a computer-readable medium coupled to the processing unit through the system bus; and

a grammar programming language compiler executed from the compute-readable medium by the processing unit to cause the processing unit to create an interface function for each rule by

determining a set of operations that manipulate a representation of a natural language expression for each rule,

mapping each operation in the set to a corresponding library function,

recognizing a nested operation, a nested operation comprising an inner operation nested within an outer operation, and

processing the nested operation by mapping a separate library function to each of the outer and inner operations, generating a pointer to the library function mapped to the inner operation, and specifying the pointer as an argument for the library function mapped to the outer operation, wherein the interface function is executed when the corresponding rule is invoked.

28. The system of claim 27, the grammar programming language compiler further causes the processing unit to repeat the processing for a nested operation for each inner operation it recognizes as a nested operation.

29. The method of claim 27, the grammar programming language compiler further causing the processing unit to assign an identifier to each rule, the identifier operable to address the corresponding interface function.

30. The system of claim 29, the grammar programming language compiler further causing the processing unit to create a common interface function for all interface functions having a like number of input arguments, wherein a particular rule is invoked by specifying the identifier for the rule to the common interface function.